215789 346 图4
23．如图5所示的二叉树，其中序遍历序列为__ 5387946_______。
9 76
5 4
8
3
图5
24 .给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是___不正确_的。(回答正确或不正确) 三、综合题 1．（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。 （2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好
使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。
（3）给出该树的前序遍历序列。 1．（1） a
c b
d e
图8
16
（2）d
2. (1) 说明什么是顶点活动网(AOV网)和拓扑序列 （2）设有向图G如下，写出3种拓扑序列，
（3）在图G中增加一条边，使图G仅有一条拓扑序列
a d b c
图6
2．
(1) 用顶点表示活动，边表示活动间先后关系的有向图称为顶点活动网
在顶点活动网中，若不存在回路,则所有活动可排列成一个线性序列,使每个活动的所 有前驱活动都排在该活动的前面,称此序列为拓扑序列 (2) abdc adbc dabc
(3) 在 b和d间添加有向边 3．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）。
（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 3．（1） 42 16
67 32 82 42
102 16 32 57 82 67 57 52
52 102
初始树 堆
17
图9
（2）102，52，42，82，16，67，32，57
4．如下是一棵二叉排序树，A1,A2,…A9代表1，2，3,…9中各个不同数字， （1）给出对该树中序遍历的结果 （2） A3,A5,A7的值各为多少？
（3）请在该树中再插入一个结点9 .5作为叶结点，并使它仍然是一棵二叉排序树
A1 A2 A3 A4 A5 A6 A7 A8 A9
图7
4．
(1) A7 A4 A8 A2 A5 A9 A1 A3 A6 1 2 3 4 5 6 7 8 9 (2) 8 5 1 （3）
7 4 8 2 5 9 1 3 6 9.5
图10
5．设查找表为(11,12,13,14,15,16,17,18,19,20,21) ,元素的下标从0开始。
（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用数值表示） （2）说明成功查找到元素15，19各需要经过多少次比较？ （3）说明查找不到元素10，15.5各需要经过多少次比较？ （4）給出中序遍历判定树的序列。
18
5（1）
16 1319 11 14 17 20
12 15 18 21
图11 (2) 4次 2次 （3）3次 4次
（4）11，12，13，14，15，16，17，18，19，20，21 6．
(1) 设有查找表{17，26，14，16，15，30，18，19，28}，依次取表中数据构造一棵二叉 排序树.
(2) 对上述二叉树给出后序遍历的结果 (3). 对上述二叉树给出中后序遍历的结果
(4)) 在上述二叉树中查找元素15共要进行多少次元素的比较? 6. (1)见图6
17 (2) 15,16,14,19,18,28,30,26,17 (3) 14,15,16,17,18,19,26,28,30 (4) 4 14 26
16 18 30
28 15 19
四、程序填空题
1 . 以下程序是折半插入排序的算法
设待排序的记录序列存放在a[1],…a[n]中，以a[0]作为辅助工作单元，以下程序是要把a[i] 插入到已经有序的序列a[1],…a[i-1]中。 void binsort (NODE a[ ],int n) { int x,i,j,s,k,m;
for （i=2；i<=__(1)_ n __;i++） { a[0]=a[i];
19
x= a[i].key; s=1; j=i-1;
while (s<=j)
{ m=__(2)_ (s+j)/2;__ if( x
__(4) s=m+1;___ }
for ( k=i-1;k>=j+1;k- -) __(5)_ a[k+1] __=a[k]; a[j+1]=a[0]; }
}
2．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点，不成功p指向为NULL）完成程序中的空格
typedef struct Bnode { int key;
struct Bnode *left; struct Bnode *right; } Bnode;
Bnode *BSearch(Bnode *bt, int k)
/* bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ { Bnode *p;
if(bt== ___(1)__ NULL ___) return (bt); p=bt;
while(p->key!= __(2)__ k ____) { if(k
else ___(4)_ p=p->right ____; if(p==NULL) break; }
return(___(5)_ p ____); }
3．以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针
struct node
{ ElemType data;
struct node *next; };
20