发布时间 : 星期六 文章数据结构（本）期末综合练习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