数据结构（本）期末综合练习（2014年12月）

{ Bnode *p; if(bt = = NULL) return (bt); ___(1)_____

while(p->key != __(2)___)

{ if(kkey)

___(3)_____; else ___(4)_____;

if(p==NULL) break; } return p ; }

期末综合练习一答案

一、单项选择题

1．C 2．B 3．C 4．D 5．A 6．B 7．D 8．A 9．C 10．B 11．D 12．C 1314．A 15．B 16．D 17．A 18．B 19.C 20．D 21．D 22．B 23．B 2425．D 26．B 27．A 28．B 29．C 30．A 二、填空题 1. 5

2．树形 3. 3

4．先进后出 5. sq->rear++; 6．3

7.2,4,3,5,6,8 8．4 9. 3

10．sq->fronf++; 11. 数据元素 12．sq->rear++;

13. front= =(rear+1)% MaxSize 14．12,14,13,15,16,18 15.直接插入排序 16．数据元素 17.8

18．front= =rear 19. p->prior； 20．折半插入排序

．A ．D 21. 结点的直接前驱 22．(3,4, a3,4) 23. 存储

24．P所指结点的直接前驱

三、综合应用题 1.

(1)图3 (2)中序遍历 1 , 3 , 5 , 7 , 8 , 9 , 10 , 12 , 13 (3) 5次 (4) 3,7,9,10,8,5,13,12,1

1 12 5 13 3 8 7 10 9

2

(1)图4 (4)4次 (5)15,48,56,30,74,62

图3 62 74 56 30 15 48 图4

3

（1）图5 6 39

10 1 4 7

11 2 5 8

图5

(2) 3次 (3) 4次 (4) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 （序号） 4.

(1)图6 (2)4次41,15,26,38

(3) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41) （4）1( 3）,2(9), 3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)

6 3 9 1 4 7 11 2

四、程序填空题

1. (1) p=p->next;

(2)p->data或prep->data (3) p->next;

2.

(1)low<=high (2)mid (3)a[mid].num

3. (1) n

(2) (s+j)/2; (3) j=m-1; (4) s=m+1; (5) a[k+1]

4．

(1) p=bt; (2) k (3)p=p->left (4)p=p->right

5 8 10 图6 12