中国石油大学《数据结构》复习题及答案

45. L->next->next==L 46. 边 47. 384 48. 队列

49. 边稠密 、 边稀疏 50. 5 51. 8 、 64 52. 2h-1 、 2h-1 53. n-1 54. n

55. 栈

56. 3

57. O(n2)

58. （42,13,94,55,05,46,17）

三、应用题（本大题共5小题，每小题6分，共30分） 23.

答案：二叉树形态

ABCEDFGH

24.

参考答案：

（1）邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next

17

（2）逆邻接表：

（3）

25.

26.

答案：

1 2 3 4 6 5 答案：原来的电文为：eatst

先序遍历为：12345687 中序遍历为：34867521 27.

答案：

H(45) = 6, H(78) = 0,

H(57) = 5, H(31) = 5,

8 7 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(20) = 7, H(03) = 3, H(15) = 2, H(36) = 10.

18

利用线性探查法造表： 0 1 2 3 78 15 03 4 5 57 6 45 7 20 8 31 9 10 11 23 36 12 12

(1) (1) (1) 搜索成功的平均搜索长度为 (1) (1) (1) (4) (1) (2) (1)

ASLsucc = 1(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14

10

28. 答案：

29.

答案：

哈夫曼编码为：a:1001 注意：答案不唯一

30. 答案：

10 b:01 c:10111 d:1010 e:11 f:10110 301218711456312

19

g:00 h:1000

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

31.

答案：

32.

答案：

（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；（２）平均查找长度ASL?3?2?1?1?25?95

33. 答案：

34.

答案：（1）构造二叉排序树 ： 5 3 7 1 4 6 9 2 8 10 （2）ASL=(1*1+2*2+3*4+4*3)/10=2.9 35.

答案: 邻接矩阵为： A B C D E F

20