41、已知散列函数为H(k)=k mod 13， 关键字序列为25、37、52、43、84、99、120、15、26、11、80、23，处理冲突的方法为线性探测法，散列表长度为13，
（1）试画出该散列表。（3分）
（2）求出在等概率情况下的查找成功时的平均查找长度。(2分)
答案：（1）哈希表：
0 1 2 3 4 5 6 7 8 9 10 11 12
52 26 15 120 43 11 84 80 99 23 37 25
42、已知待排序记录的关键字序列为{83，69，41，22，15，33，8，20}， 要求：（1）用堆排序法找出最小的值，要求写出排序过程；
43、已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度
为2、度为1及度为0的结点个数。 中序序列：c,b,d,e,a,g,i,h,j,f
后序序列：c,e,d,b,i,j,h,g,f,a 答案：度为2为：3 度为1为：3 度为0为：4
44、给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树
45、已知一个图的邻接表如下，请写出从顶点C0出发按广度遍历时得到的顶点序列。
答案：C0,C1,C2,C3,C4,C5
46、(该题2选1做)
4 B A 27 11 2
F 30 7 10 E D C 1 6 28
对于上图所示的无向图，要求：
(1)按普里姆(prim)算法从顶点A出发求其最小生成树，要求写出求解的顺序步骤。 (2)按克鲁斯卡尔(kruskal)算法求其最小生成树，要求写出求解的顺序步骤。
47、设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋ mod m，给定的关键码序列为19，14，25，01，68，28，84，27，56，12，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。
0 1 2 3 4 5 6 7 8 9 10 11 12 搜索成功时的平均搜索长度为：ASLsucc=
答案：
0 1 2 3 4 5 6 7 8 9 10 11 12 12 14 01 68 28 27 19 84 56 25 解： H（19）=19 mod 13=6 H（14）=14 mod 13=1 H（25）=25 mod 13=12 H（01）=01 mod 13=1
a.elem[1]不空，所以第一次冲突处理后的地址为H（01）=（01+1） mod 13=2 H（68）=68 mod 13=3 H（28）=28 mod 13=2
a.elem[2]不空，所以第一次冲突处理后的地址为H（28）=（28+1） mod 13=3 a.elem[3]不空，所以第二次冲突处理后的地址为H（28）=（28+2） mod 13=4 H（84）=84 mod 13=6
a.elem[6]不空，所以第一次冲突处理后的地址为H（84）=（84+1） mod 13=7 H（27）=27 mod 13=1
a.elem[1]不空，所以第一次冲突处理后的地址为H（27）=（27+1） mod 13=2 a.elem[2]不空，所以第二次冲突处理后的地址为H（27）=（27+2） mod 13=3 a.elem[3]不空，所以第三次冲突处理后的地址为H（27）=（27+3） mod 13=4 a.elem[4]不空，所以第五次冲突处理后的地址为H（27）=（27+4） mod 13=5
H（56）=56 mod 13=4
a.elem[4]不空，所以第一次冲突处理后的地址为H（56）=（56+1） mod 13=5 a.elem[5]不空，所以第二次冲突处理后的地址为H（56）=（56+2） mod 13=6 a.elem[6]不空，所以第二次冲突处理后的地址为H（56）=（56+3） mod 13=7 a.elem[7]不空，所以第二次冲突处理后的地址为H（56）=（56+4） mod 13=8
H（12）=12 mod 13=12
a.elem[12]不空，所以第一次冲突处理后的地址为H（12）=（12+1） mod 13=0 平均搜索长度 ASLsucc=2.3
48、判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。
49、某二叉树的结点数据采用顺序存储表示如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B （1）试画出此二叉树的图形表示。（3分） （2）写出结点D的双亲结点及左、右子女。（3分）
（3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（4分）
答案：(1) E
H A
B
(2) A;C; Ф (3)
C D G I
A E F H I D G
C B
50、已知权值 W={ 5, 6, 2, 9, 7 }，请构造对应的Huffman树。
6 7 9 5 2
51、给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。
答案：
52、已知散列函数为H(k)=k mod 13， 关键字序列为25、37、52、43、84、99、120、15、26、
11、70、82，处理冲突的方法为线性探测法，散列表长度为13，
（1）试画出该散列表。（3分）
（2）求出在等概率情况下的查找成功时的平均查找长度。(2分)
答案：（1）哈希表：
0 1 2 3 4 5 6 7 8 9 10 11 12
52 26 15 120 43 11 84 70 99 82 37 25 （2） 在等概率情况下查找成功的平均查找次数为：2.25
53、已知待排序记录的关键字序列为{83，69，41，22，15，33，8}， 要求：（1）用起泡排序法按从小到大顺序写出每趟排序的结果，直到排序结束；
参考答案：
83 69 41 22 15 15 8 69 41 22 15 22 8 15 41 22 15 33 8 22 22 15 33 8 33 15 33 8 41 33 8 69 8 83
初 第 第 第 第 第 第 始 一 二 三 四 五 六 关 趟 趟 趟 趟 趟 趟 键 排 排 排 排 排 排 字 序 序 序 序 序 序
后 后 后 后 后 后
54、已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。
中序序列：c，b，d，e，a，g，I，h，j，f 前序序列：a，b，c，d，e，f，g，h，I，j 后序序列：
答案：后序：bedcfhjiga
55、