《数据结构》课后部分答案

暨南大学珠海学院

《数据结构》习题及参考答案

据类型。

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

1.3 ③设有数据结构（D，R），其中

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

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

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

理数是其分子，分母均为自然数其分母不零的分数）。

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

（1） product=1 ; i=1;

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

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

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

(1) i = 1; k = 0;

While (i<=n - 1) {

@ k + = 10 * I ;

i ++;

}

(2) i = 1; k = 0;

do (i<=n - 1) {

@ 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 = i;j<=n ;j++) {

for ( k = 1;k<=j ;k++)

(7) x= n; y= o;

while (x>=(y+1) * (y + 1)){

@ y ++;

}

(8) x= 91; y= 100;

while (y>0){

else x ++ ;

}

} // Time

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

2

(4/3)

算法可解问题的规模（即 n 值的范围）各为多少？哪个算法更适宜？请说明理由。

1.12 ③ 设有以下三个函数：

f (n) = 21n

+ 500n

h(n)=5000 n

+nlogn

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

（1）f (n)和 O(g (n))

(2) h(n) 和 O(f (n))

(3) g(n) 和 O(h (n))

(4) h (n) 和 O(n3.5)

(5) h(n) 和 O(nlogn)

1.13 ③ 试设定若干 n 的值，比较两函数 n

和 50nlog

n 的增长趋势，并确定 n 在什

1.15 试用数学归纳法证明：

试编写 k 阶裴波那契序列的第 项值的函数算法，k 和 m 均以值调用的 形式在函数

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

1.19④ 试编写算法，计算 i !. 2

的值并存入数组 a[0…arrsize - 1] 的第 i- 1 个分量中

（I= 1,2,….,n）。假设计算机中允许的整数最大值为 maxint, 则当 n>arrsize 或对某个 k(1≤k

≤n)使 k!. 2

1.20④ 试编写算法求一元多项式的值 的值 P