数据结构题集 | 第1章 绪论

内容纲要

@[toc]

一、基础知识题

1.1(1) 简述下列术语:数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

数据是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位,在计算机程序中通常作为一个整体考虑和处理。
数据对象是性质相同的数据元素的集合,是数据的一个子集。
数据结构是相互之间存在一种或多种关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在值集上的一组操作的总称。
抽象数据类型是一个数学模型及定义在其上的一组操作。

1.2(2) 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

数据结构定义了一组按某些关系结合在一起的数据元素;数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作;抽象数据类型可通过固有数据类型表示和实现,即利用处理器中已存在的数据类型来说明新的结构,用已实现的操作组合新的操作。

1.3(2) 设有数据结构(D, R),其中D = {d1, d2, d3, d4},R = {r},r = {(d1, d2), (d2, d3), (d3, d4)}。
试按图论中图的画法惯例画出其逻辑结构图。

1.4(2) 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义。

ADT Complex
{
        数据对象:D = { r, i | r, i 为实数 }
        数据关系:R = { <r, i> }
        基本操作:
                InitComplex(&C, re, im)
                        操作结果:构造一个复数C,实部和虚部分别为re和im
                DestroyComplex(&C)
                        操作结果:销毁复数C
                Get(C, k, &e)
                        操作结果:用e返回复数C的第k元值
                Put(&C, k, e)
                        操作结果:改变复数C的第k元值为e
                IsAscending(C)
                        操作结果:如果复数C的两个元素按升序排列,则返回1,否则返回0
                IsDescending(C)
                        操作结果:如果复数C的两个元素按降序排列,则返回1,否则返回0
                Max(C, &e)
                        操作结果:用e返回复数C的两个元素中值较大的一个
                Min(C, &e)
                        操作结果:用e返回复数C的两个元素中值较小的一个
}
ADT Complex

ADT RetionalNumber
{
        数据对象:D = { s, m | s, m 为自然数且m不为0 }
        数据关系:R = { <s, m> }
        基本操作:
                InitRationalNumber(&R, s, m)
                        操作结果:构造一个有理数R,其分子和分母分别为s和m
                DestroyRationalNumber(&R)
                        操作结果:销毁有理数R
                Get(R, k, &e)
                        操作结果:用e返回有理数R的第k元值
                Put(&R,k,e)
                        操作结果:改变有理数R的第k元值为 e
                IsAscending(R)
                        操作结果:若有理数R的两个元素按升序排列,则返回1,否则返回0
                IsDescending(R)
                        操作结果:若有理数R的两个元素按降序排列,则返回1,否则返回0
                Max(R, &e)
                        操作结果:用e返回有理数R的两个元素中值较大的一个
                Min(R, &e)
                        操作结果:用e返回有理数R的两个元素中值较小的一个
}
ADT RetionalNumber

1.6(3) 在程序设计中,常用下列三种不同的出错处理方式:
(1) 用exit语句终止执行并报告错误
(2) 以函数的返回值区别正确返回或错误返回
(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回
试讨论这三种方法各自的优缺点。

(1) 常用于异常错误处理,它可以强行中断程序的执行,返回操作系统
(2) 常用于子程序的测试,便于实现程序的局部控制
(3) 可以给出错误类型,便于迅速确定错误

1.7(3) 在程序设计中,可采用下列三种方法实现输出和输入:
(1) 通过scanf和printf语句
(2) 通过函数的参数显式传递
(3) 通过全局变量隐式传递
试讨论这三种方法的优缺点。

(1) 用scanf和printf直接进行输入输出的好处是形象、直观,缺点是需要对其进行格式控制,较为繁琐,如果出现错误,则会引起整个系统的崩溃
(2) 便于实现信息的屏蔽,减少出错的可能
(3) 输入输出最为方便,只需修改变量值即可,但过多全局变量使程序维护更困难

1.8(4) 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度:

(1) i = 1, k = 0;
while (i <= n - 1)
{
        @ k += 10 * i;
        i++;
}

(2) i = 1, k = 0;
do
{
        @ k += 10 * i;
        i++;
} while (i <= n - 1);

(3) i = 1, k = 0;
while (i <= n - 1)
{
        i++;
        @ k += 10 * i;
}

(4) k = 0;
for (i = 1; i <= n; i++)
{
        for (j = 1; j <= n; j++)
                @ k++;
}

(5) for (i = 1; i <=n; i++)
{
        for (j = 1; j <= i; j++)
        {
                for (k = 1; k <= j; k++)
                @ x += delta;
        }
}

(6) i = 1, j = 0;
while (i + j <= n)
{
        @ if (i > j) j++;
        else    i++;
}

(7) x = n, y = 0;       // n是不小于1的常数
while ( x >= (y + 1) * (y + 1))
{
        @ y++;
}

(8) x = 91, y = 100;
while (y > 0)
{
        @ if (x > 100)   x -= 10, y--;
        else    x++;
}

(1)(2)(3) n - 1
(4) n(n + 1) / 2
(5)
(6)
(7)
(8)

1.9(3) 假设n为2的乘幂,并且n > 2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。

int Time (int n)
{
        count = 0, x = 2;
        while (x < n / 2)
        {
                x *= 2, count++;
        }
        return count
}       // Time

O(log~2~n)
count = (log~2~n - 2)

1.10(2) 按增长率由小至大的顺序排列下列各函数:

1.11(3) 已知有实现同一功能的两个算法,其时间复杂度分别为O(2^n^)和O(n^10^),假设现实计算机可连续运算的时间为10^7^秒(100多天),又每秒可执行基本操作(根据这些操作来估算算法时间复杂度)10^5^次。试问在此条件下,这两个算法可解问题的规模(即n值的范围)各位多少?哪个算法更适宜。

(1) n = 40
(2) n = 16
第一种算法更适宜。

1.12(3) 设有以下三个函数:
f(n) = 21n^4^ + n^2^ + 1000, g(n) = 15^n^4 + 500n^3^, h(n) = 5000n^3.5^ + nlogn
判断以下断言正确与否:
(1) f(n)是O(g(n))
(2) h(n)是O(f(n))
(3) g(n)是O(h(n))
(4) h(n)是O(n^3.5^)
(5) h(n)是O(nlogn)

对错错对错

1.13(3) 试设定若干n值,比较两函数n^2^和50nlog~2~n的增长趋势,并确定n在什么范围内,函数n^2^的值大于50nlog~2~n的值。

n^2^增长趋势快,但前期50nlog~2~n值较大。
当n > 438时,n^2^ > 50nlog~2~n

1.14(3) 判断下列各对函数f(n)和g(n),当n→∞时,哪个函数增长更快。

g(n)
g(n)
f(n)
f(n)

1.15(3) 试用数学归纳法证明:

算法设计题

1.16(2) 试写一算法,自大至小依次输出顺序读入的三个整数X,Y和Z的值。

int max3(int x, int y, int z)
{
if (x > y)
if (x > z)  return x;
else    return z;
else
if (y > z)  return y;
else    return z;
}

1.17(3) 已知k阶裴波那契序列的定义为

试编写求k阶裴波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。

```cpp
int Fibonacci(int k, int n)
{
if (k < 1) exit(OVERFLOW);
int p, x;
p = new int[k + 1];
if (!p) exit(OVERFLOW);
int i, j;
for (i = 0; i < k + 1; i++)
{
if (i < k - 1) p[i] = 0;
else p[i] = 1;
}
for (i = k + 1; i < n + 1; i++)
{
x = p[0];
for (j = 0; j < k; j++) p[j] = p[j + 1];
p[k] = 2
p[k - 1] - x;
}
return p[k];
}

```c
unsigned long Fibonacci(unsigned n)
{
if (n > 2)
return Fibonacci(n - 1) + Fibonacci(n - 2);
else
return 1;
}

1.18(3) 假设有A, B, C, D, E五个高等院校进行田径对抗赛,各院校的单项成绩均已存入计算机,并构成一张表,表中每一行的形式为

项目名称性别校名成绩得分

编写算法,处理上述表格,以统计各院校的男、女总分和团体总分,并输出。

typedef enum(A, B, C, D, E) SchoolName;
typedef enum(Female, Male) SexType;
typedef struct {
char event[3];      // 项目
SexType sex;
SchoolName school;
int score;
} Component;
typedef struct {
int MaleSum;        // 男团总分
int FemaleSum;      // 女团总分
int TotalSum;       // 团体总分
} Sum;
Sum SumScore(SchoolName sn, Component a[], int n)
{
Sum temp;
temp.MaleSum = temp.FemaleSum = TotalSum = 0;
int i;
for (i = 0; i < n; i++)
{
if (a[i].school == sn)
{
if (a[i].sex == Male)   temp.MaleSum += a[i].score;
if (a[i].sex == Female) temp.FemaleSum += a[i].score;
}
}
temp.TotalSum = temp.MaleSum + temp.FemaleSum;
return temp;
}

1.19(4) 试编写算法,计算i! 2^i^(i = 0, 1, ... n - 1)的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT,则当n > arrsize或对某个k(0 <= k <= n - 1)使k! 2^k^ > MAXINT时,应按出错处理。注意选择较好的出错处理方法。

```cpp
"#include <iostream>"
"#include <stdlib.h>"
"#define MAXINT 65535"
"#define ArrSize 100"
int fun(int i);
int main()
{
int i, k;
int a[ArrSize];
cout << "Enter k:";
cin >> k;
if (k > ArrSize - 1) exit(0);
for (i = 0; i <= k; i++)
{
if (i == 0) a[i] = 1;
else
{
if (2 i a[i - 1] > MAXINT) exit(0);
else a[i] = 2 i a[i - 1];
}
}
for (i = 0; i <= k; i++)
{
if (a[i] > MAXINT) exit(0);
else cout << a[i] << " ";
}
return 0;
}

1.20(4) 试编写算法求一元多项式的值P~n~(x~0~),并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择较好的输入和输出方法。本题的输入为a~i~(i = 0, 1, ..., n), x~0~和n,输出为P~n~(x~0~)。

"#include "
"#include "
"#define N 10"
double polynomail(int a[], int i, double x, int n);
int main()
{
double x;
int i, n, a[N];
cout << "输入变量的值x:";
cin >> x;
cout << "输入多项式的阶次n:";
cin >> n;
if (n > N - 1)  exit(0);
cout << "输入多项式的系数a[0]--a[n]:";
for (i = 0; i <= n; i++)    cin >> a[i];
cout << "The polynomail value is " << polynomail(a, n, x, n) << endl;
return 0;
}
double polynomail(int a[], int i, double x, int n)
{
if (i > 0)  return a[n - i] + polynomail(a, i - 1, x, n) * x;
else    return a[n];
}

算法时间复杂度为O(n)。

留下评论

您的电子邮箱地址不会被公开。