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

typedef struct { int key;

?? }NODE;

int Binary_Search(NODE a[ ], int n, int k) {

int low, mid, high; low=0; high=n-1;

while( __(1)______)

{ mid=(low+high)/2; if(a[mid].key==k)

return __(2)______ ; else if (__(3)______)

low=mid+1; else __(4)______; }

return -1; }

设数组元素：a[0]=2；a[1]=5 a[2]=3; a[3]=4; a[4]=9；a[5]=6; a[6]=1; a[ 7]=10; 按上述程序查找元素5，能否成功查到，说明理由__(5)_____

3．以下冒泡法程序对存放在a[1]，a[2]，??，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。

void bsort (NODE a[ ], int n) { NODE temp; int i,j,flag;

for(j=1; （1） ;j++); {flag=0;

for(i=1; （2） ;i++) if(a[i].key>a[i+1].key)

{flag=1; temp=a[i];

（3） ; （4） ; }

if(flag= =0)break; } }

设有序列6，4，5，8，2，1，给出由该程序经过两趟冒泡后的结果序列（5）

4.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

第17页

void Inorder (struct BTreeNode *BT) {

if(BT!=NULL){ __(1)______;

Inorder(BT->right); __(2)_____；} }

利用上述程序对右图进行遍历，结果是__(3)______; a b e c d

练习二答案

一、单项选择题

1． B 2．C 3．A 4. B 5．C 6．D 7． B 812．C 13．D 14．A 15．C 16．B 17． 22. B 23. B 24. A 25. D 26. A 27. A 28 .D 29. A 3031．B 32．C 33．D 34．D 35．D

二、填空题 1． 10 2．后出

3． p->next;

4．行下标 行下标 数组元素 5． 数组元素 6．4

7． 后出 8．a2 9． n-1 10．5 11． 有序 12．中序 13． 6 14．4 15． 3 16．3

17. front==rear 18. 2, 4, 3, 5, 6, 8 19. 2

20.1,2,4,8,3,5,9 21. n+1 22.顺序 23. 3

24.（5，6），（1，2），（3，4），（7，8）

第18页

f 图7

．A 9． A 10． C 11． C ．C 19 D 20. C 21. C ． B

D 1825. 4 26.34 27.31 28. 14 29. 4

三、综合题 1． (1)

2 5 7 1 3 6 8 4 9

图8

(2) 按序号 5,2,3,4。按元素23，10，11，14 4次 (3)ASL=(1+2*2+3*4+4*2)/9=25 /9 2．

(1) 59

6 22 89

3 9

8 23 69 90 1 4 7 10

16 41 81 121 2 8 11 5

图9

(2) 3次

(3) 59，89，69，81共4次比较

3. (1)

29

12第19页 177 5 8 9

(2) 3: 000 4: 001 5: 01 8:10 9:11 (3) 2n-1

4. (1) 28，30，35，69，36，46

30

69

28 35 36 46 图11 (2) 30，28，36，46，69，74 (3)

30

73 4

2 8

9 81

图12

四、程序填空题

1.（1） Inorder(BT->left)

（2） printf(“%c”,BT->data) （3） d b f e a c

第20页

101