零元素，其相应的三元组表共有_______个元素。 while( *p!=‘\\0’){ n++; p++;} 结果中，n的值是_______。 三、综合题
1．设查找表为(1,10,11,14,23,27,29,55,68) ,元素的下标依次为1,2,3,??，9。 （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。 （2）说明成功查找到元素14,需要依次经过与哪些元素的比较？共几次比较？ （3）求在等概率条件下，成功查找的平均比较次数？ .
2．设查找表为
序号 1 2 3 4 5 6 7 8 9 10 11 序列 8 16 22 23 41 59 69 81 89 90 121
（1）画出对上述查找表进行折半查找所对应的判定树。 （2）说明成功查找到元素90需要经过多少次比较？
（3）说明不成功查找元素82，依次与哪些元素进行了比较，需要经过多少次比较？
3．
(1) 以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。
(2) 给出相应权重值叶结点的哈夫曼编码。
(3) n个叶结点的哈夫曼树，总共有多少个结点？ 4.
(1) 一组记录的关键字序列为（36，69，46，28，30，35），给出利用堆排序（堆顶 元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述 ）。
(2) 对关键字序列(36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分割 元素，经过一次划分后的结果。
(3) 设有数据集合{30,73,101,4,8,9,2,81}，依次取集合中各数据构造一棵二叉排序树。
四、程序填空题（每空2分，共16分）
1．以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 void Inorder (struct BTreeNode *BT) {
if(BT!=NULL){ （1） ; （2） ; Inorder(BT->right);} }
a b c d e f 利用上述程序对右图进行遍历，结果是 （3） ; 图6
2．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格
第16页
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