三、简答计算题（52分）
1．假设一棵二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBDAEGHF，
请画出该二叉树,并给出后序序列（6分）
2． 设字符a，b，c，d，e，f的使用频度分别是0.07，0.09，0.12，0.22，0.23，0.27，
画出赫夫曼树并写出a，b，c，d，e，f的赫夫曼编码（6分）
3． 个7*7的稀疏矩阵的三元组表示为<1，2，15>，<3，2，9>，<5，7，18>，
<5，6，6>，请采用十字链表表示之（6分）
4． 图已知哈希表为空，哈希函数为H(Key)=Key MOD 11,冲突解决方法用二次探测
再散列，填入在依次插入关键字5，37，14，26，9，19，之后的情况（7分） 0 1 2 3 4 5 6 7 8 9 10 5．在下列表格中填入AOE网的活动（边）最早开始时间和最迟开始时间，并写出关键路径（用结点描述）（7分） 15 9 8 C 3 9 9 7 5 F E A B 10 4 8 D 最早开始时间 最迟开始时间 AB AC AD BC BD BE CE CF DE DF EF
6、画出下面三阶B_树中依次插入关键字38，6，16后所得的结果：（6分）
12 36 45 80 14 3 10 7、 图G的邻接矩阵如下，画出G的邻接表（7分） A B C D E
A 0 1 0 0 0 B 0 0 0 1 0 C 1 0 0 1 1 D 0 0 1 0 0 E 0 0 0 0 0
第（1）页
8、 依次插入结点（关键字）10，20，18，15，12构造一棵平衡二叉树，并标出结点的
平衡因子（7分） 四、程序填充（23分）
1、以下为用顺序存储结构表示的循环队列的出队操作的类C语言程序，请填空(7分) #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef int Status; typedef int ＱElmtype; typedef struct{
QElemtype *base; ___①_____ front;
___②______ rear;} SqQueue;
status DeQueue(SqQueue &Q，QElemType e) { if（_____③___________） return ERROR; e=_____④_________ ;
Q.front=___⑤________; return OK;}
2、按广度优先非递归遍历图(8分)
Void BFSTraverse(Graph G，Status(*Visit)*(int v)) { for(v=0；v visited[v]=FALSE; InitQueue(Q); for(v=0；v visited[v]=true; Visit(v); ____⑦_________； while(!QueueEmpty(Q)) { ___⑧________； for(w=FirstAdjVex(G,u)；w>=0；w=NextAdjVex(G,u,w)) if(!visited[w]) {______⑨_________；Visit(w)； EnQueue(Q,W)； } }} 3、对顺序表L作折半插入排序（8分） void BinsertSort(Sqlist &L) { for(i=2；i<=L.length；++i) {______⑩________； low=1;high=i-1; while(___⑾____) { m=(low+high)/2; if(LT(L.r[0].key，L.r[i].key)) high=m-1; 第（2）页 else __⑿____; } for(j=i-1；j>=high+1；--j) L.r[j+1]=L.r[j]; ______⒀____; } } 第（3）页