6-9章 单元测试
一、选择题(每题2分，共10分)
1．在含有n个顶点的有向图G的邻接矩阵A[n][n]中，顶点 i 的入
度为( )。
A. i 行之和 B. A的上三角元素之和 C. i 列之和 D. A的下三角元素之和
2. 设哈希表长m=14, 哈希函数H(key)=key. 表中已有4个数据
元素15，38， 61， 84，他们的哈希地址分别是：addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空，如果采用二次探测再散列处理冲突，则关键字为48的数据元素在哈希表的存放地址是( )。
A. 9 B. 3 C. 5 D. 8
3. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均
相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( ) A.
4. 已知一个散列表如图所示，其散列函数为H(key)=key％11，采用
二次探查法处理冲突，则下一个插入的关键字49的地址为( ) A. 2 B. 3
0
1
2
3
15 38 61 84 4
5
6
7
8
9
10
C. 9
D. 1
39 15
B.49
15C.
51 15 D.
55 15
5. 下列所示各图中是中序线索化二叉树的是( )
二、填空题(每空2分，共20分)
1. 如图所示是一棵正在进行插入运算的平衡二叉树（AVL树），关键
码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡，那么，调整后的AVL树是 。
2. 设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素
的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优顺序存储，元素A[6,6]的存储地址为 。
3. 对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为
n2,则n0= 。
4. 深度为k的二叉树至多有 个结点。深度为k的完全二
叉树上至少有 个结点
5. 已知广义表A=（9,7,(8,10,(99)),12）,如果Head()和Tail()分别代表
求表头和表尾的操作，则
Head(Head(Tail(Tail(Head(Tail(Tail(A)))))))取出的是 。 6. 含有n个顶点的连通图至少有 条边。
7. 下面是在二叉排序树T中查找关键字之值为 key 的结点的算法。
如查找成功，p = 该结点的地址 ，返回TRUE。如查找不成功， p指向查找路径上访问的最后一个结并返回FALSE。指针f指向T的双亲，其初始调用值为 NULL。
Status SearchBST ( BiTree T，KeyType key， BiTree f，BiTree &p ) { if ( !T ) { p = f ; return FALSE; }
else if ( EQ( key, T ->data. key ) ) { p = T; return TRUE; } else if ( LT( key , T ->data. key ) )
return SearchBST ( ); else return
SearchBST ( ); }
三、简答题(每题10分，共70分)
1. 假设一棵二叉树的先序序列为EBADCFHGIKJ 和中序序列为
ABCDEFGHIJK。请画出该树。
2. 已知一有向图的邻接表存储结构如图3所示（V1存在1号单元中，
V5存在5号单元中），请画出该有向图，并根据有向图的深度优先遍历算法，从顶点V1出发，给出所得到的顶点序列。
V1 V2 V3 V4 V5 ^ ^ 3 2 4 ^
4 2 5 ^ 4 ^
3. 给出利用Prim算法构造出下图的一棵最小生成树，并画出构造过
程。
v1
6
11
1 5
5v
5 33
4 8v
3 7v
2
6
4. 假设某电文仅由A, B, C, D, E, F, G, H这8个字符组成。各个字符
在电文中出现的次数分别为6，14，4，7，9，16，28，8。请构造该赫夫曼树，并给出各字符的赫夫曼编码及该树的带权路径长度。
5. 对下面的AOE网，分别给出各个事件Vi(i=1,2,…,9)和各个活动ai
（i=1,2,…,11）的最早发生时间，最迟发生时间，并根据相应结构给出可能的关键活动和关键路径。
a1=66 V1V2a4=1V7a7=9V5a10=2a2=4 a5=1 a3=5 V3a8=7 a11=4 a9=4 V6V9V8V4a6=25 AOE网
6. 线性表的关键字集合｛87，25，310，08，27，132，68，95，187，
123，70，63，47｝，共有13个元素，已知散列函数为：H(k)=k % 13。 采用链地址法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。
7. （1）请画出与左图中二叉树对应的森林，并先序遍历森林。 （2）请画出右图所示的树所对应的二叉树。