按章节，做完这本书的题

简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

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

设有数据结构 $(D,R)$，其中

$$D=\{d1,d2,d3,d4\},\quad R=\{r\},\quad r=\{(d1,d2),(d2,d3),(d3,d4)\}。$$

试按图论中图的画法惯例画出其逻辑结构图。

试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

试画出与下列程序段等价的框图。

（1）

product = 1;  i = 1;
while (i <= n) {
    product *= i;
    i++;
}

（2）

i = 0;
do {
    i++;
} while ((i != n) && (a[i] != x));

（3）

switch {
    case x < y: z = y - x; break;
    case x = y: z = abs(x * y); break;  // abs()为取绝对值函数
    default: z = (x - y) / abs(x) * abs(y);
}

在程序设计中，常用下列三种不同的出错处理方式：

（1）用 exit 语句终止执行并报告错误；

（2）以函数的返回值区别正确返回或错误返回；

（3）设置一个整型变量的函数参数以区别正确返回或某种错误返回。

试讨论这三种方法各自的优缺点。

在程序设计中，可采用下列三种方法实现输出和输入：

（1）通过 scanf 和 printf 语句；

（2）通过函数的参数显式传递；

（3）通过全局变量隐式传递。

试讨论这三种方法的优缺点。

设 $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 = i; 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++;
}

假设 $n$ 为 2 的乘幂，并且 $n>2$，试求下列算法的时间复杂度及变量 count 的值（以 $n$ 的函数形式表示）。

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

按增长率由小至大的顺序排列下列各函数：

$$2^{100},\quad (3/2)^n,\quad (2/3)^n,\quad (4/3)^n,\quad n^n,\quad n^{3/2},\quad n^{2/3},\quad \sqrt{n},\quad n!,\quad n,$$

$$\log_2 n,\quad n/\log_2 n,\quad \log_2^2 n,\quad \log_2(\log_2 n),\quad n\log_2 n,\quad n^{\log_2 n}。$$

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

设有以下三个函数：

$$f(n)=21n^4+n^2+1000,\qquad g(n)=15n^4+500n^3,\qquad h(n)=5000n^{3.5}+n\log n$$

请判断以下断言正确与否：

（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(n\log n)$