数据结构（本）期末综合练习2016年6月

20.5

21. 15

22.该结点的直接前驱 23. 3

24.主关键字

三、综合应用题 1

（1）图4

51 6

14 3 81 9

5 15 61 82 10 14 7

2 5 8 8 33 73 93

图4

(2) 4次

(3) ( 1+2*2+3*4+4*4)/11=33/11=3

2．

（1）图5

60 4

11 38 69 9 2 6

20 48 68 80 7 3 1 5

图5

(2) 3次 (3) 3次

(4) 1(20) 2 (38) 3 (48) 4(60) 5(68) 6(69) 7(80) 3.

(1) acdbfeh

(2) 152364 或 152634 或 156234

第29页

4. (1) 图6 39221712108 9 7 5

3 4

图6

(2)

3 0000 4 0001 5 001 10 01 8 10 9 11 5.

(1) 图7 7 4 9 36 8 5

图7

(2) 4

(3) 3,4,,5,6,7,8,9 6.

(1) acdbehf

第30页

(2) acedhbf aechdfb （3）

44，51，46，62，85，52

44

51 9 46

62

四、程序填空题 1.

(1) low<=high (2) mid

(3) a[mid].key < k (4) high=mid -1 (5) return -1

2.

(1) q=q ?next

(2) malloc(siseof(NODE)) (3) q?next (4) q?next (5) q?next=p

3. (1) sizeof(struct node) (2) p?next=top (3) top=p

4. (1) front= =rear (2) p->next (3) return x

85 52 图4 第31页