图7
(2)
3 0000 4 0001 5 001 10 01 8 10 9 11
（3）n个，因为非叶结点数比叶结点数少一个,而权值个数=叶结点数 2．（1）对给定权值3，1 ，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层) (2) 求树的带权路径长度。
（3）链接存储上述哈夫曼树，结点中共有多少个指针域为空,说明理由. 2. (1)
23
9
14
8645
44
3 1
图8
（2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58
(3) 共11个结点,22个指针域,除根结点外,每个结点对应一个指针域.,共10个指针域非空,故 有 22-10=12个空指针域, 3．（1）简述拓扑排序的步骤。
（2）说明有向图的拓扑序列不一定是唯一的原因。 （3）如何利用拓扑排序算法判定图是否存在回路。
（4）设有向图G如下，写出首先删除顶点1的3种拓扑序列。
6
1 2 3 4 56 图5 3. (1) 循环执行以下两步
选择一个度为0的顶点并输出 从网中删除此结点及所有出边
（2） 因为选择一个度为0的顶点时不一定是唯一的
（3） 由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱 (4) 152364 152634 156234
4. (1) 如下的一棵树,给出先序遍历序列
(2) 把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树
提示：设图中的树是二叉排序树，找出中序遍历序列与 1，2，…9的对应关系 (3) 请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。
A1 A2 A3 A4A5 A6 A7 A8 A9
图6 4 .
(1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2) (3)
7
7 4 8 2 5 9 1 3 6 3.5 图9
5．设有序表为（21，22，23，24，25，26，27，28，29，30，31,32），元素的下标从 0开始。
（1）说出有哪几个元素需要经过4次元素间的比较才能成功查到。
（2）画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示） （3）设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 （4）求在等概率条件下，成功查找的平均比较次数？ 5.
（1) 5
(2)
26 2329
21242731
2225283032
图10 (3) 3
(4) ASL=(1+2*2+3*4+5*4)/12=37/12
6．设查找表为(5,6,7,8,9,10,11,12,13,14)
（1）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树 是否是二叉排序树(设树中没有相同结点)？
8
(3) 为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？ 6.(1)
9 6 12 5 7 10 13 8 11 14 图10
(2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子 树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值; 左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。 (3) 3次
四、程序填空题
1．以下程序是快速排序的算法
设待序的记录序列存放在a[start],…a[end]中，按记录的关键字进行快速排序， 先进行一次划分，再分别进行递归调用
void quicksort ( NODE a[ ], int start ,int end ) { int i，j; NODE mid ;
if (start>=end ) return; i=start; j=end; mid=a[i]; while (i { while(i { a[i]=a[j]; __(1) i++; ___; } while(i 9 { __(3) a[j]=a[i]; __ __(4)_ j--;__ } } a[i]=mid; quicksort (a,stat, i-1); quicksort __(5) (a, i+1,end);___ } 2．以下函数为直接选择排序算法，对a[1],a[2],?a[n]中的记录进行直接选择排序，完成程序中的空格 typedef struct { int key; ?? }NODE; void selsort(NODE a[],int n) { int i,j,k; NODE temp; for(i=1;i<= ___(1)_ n-1____;i++) { k=i; for(j=i+1;j<= ___(2)_ n ____;j++) if(a[j].key struct node { ElemType data; struct node *next; }; struct node *front，*rear; void InQueue(ElemType x) 10