34．哈夫曼树中没有度数为1的结点。（N ）
35．对连通图进行深度优先遍历可以访问到该图中的所有顶
点。（Y ）
36．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（Y）
37．由树转化成二叉树，该二叉树的右子树不一定为空。（Y ）
38．线性表中的所有元素都有一个前驱元素和后继元素。（ N）
39.带权无向图的最小生成树是唯一的。（ N ） 四、应用题
1、已知一棵二叉树的先根序列和中根序列分别为
ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树，并给出其后序序列。
2、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
B A D E F H G K L M N O
P I J C
3、已知无向图如下所示：
（1）．给出从V1开始的广度优先遍历序列；（2）．画出它的邻接表；
（3）．画出从V1开始深度优先遍历生成树
4、假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码。 5
、
已
知
一
表
为
（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求：
(1)画出建立的二叉排序树（值的大小以字母顺序为准）。 (2)对该二叉排序树作中序遍历，试写出遍历序列。 (3)求出在等概率情况下查找成功的平均查找长度。
6、已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7};
E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,
(4,6)4,(5,7)20};
按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
________, ________, ________, ________, ________, ________, ________。
7、已知散列函数为H(K)=K mod 11,健值序列为{47，7，29，11，16，92，22，8，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功和不成功的平均查找长度。
8、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。
(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。
(2) 输出最小值后，如何得到次小值。（并画出相应结果图）。
9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。
10、已知图G=（V, E），其中V={v1,v2,v3,v4,v5}, E={
v1 19 16 21 11 v2 6 6
5 v6 33 18 14 v3 v5 v4 11、设有关键码序列{20，35，40，15，30，25，38}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。
12、已知散列函数为H(K)=K mod 13,健值序列为13，41，15，44，06，68，12，25，38，64，19，49，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。
13、对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果。
14、在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。
A 0 1 2 3 4 5 6 7 Data Next
五、算法与程序设计 1、阅读算法完成题目要求：
3 5 7 2 0 4 1 60 50 78 90 34 40
