A E（a,(b,c)） B E(a,E) C E (a,b) D
(1)
E(a,L( ) )
36、递归表、再入表、纯表、线性表之间的关系为（ C ） 3 2 ∧ 1 v1 0 A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入
2v2 2 ∧ 表>纯表 C 递归表>再入表>纯表>线性表 D递归表>再入表>线性3 V3 2 5 ∧ 表>纯表
3 ∧ 4 v4 0 5 6 37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）
5 v5 3 的二叉树。 2 ∧ A 空或只有一个结点 B 高度等于其结点数 6 v6 1 5 ∧ C 任一结点无左孩子 D 任一结点无右孩子
38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为
(2)v4,v6,v1,v3,v5,v2
n2.,则( A )
A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1
3. 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：
39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）
A 24 B 73 C 48 D 53 40、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（ A ）。
A da1+(I-1)*m B da1+I*m C da1-I*m D
da1+(I+1)*m 41、34 具有35个结点的完全二叉树的深度为( A )
A 5 B 6 C 7 D 8
42、对线性表进行折半搜索时，要求线性表必须（ C ） A 以链接方式存储且结点按关键码有序排列 B 以数组
方式
C 以数组方式存储且结点按关键码有序排列 D以链接方
式存储
43、顺序搜索算法适合于存储结构为（ B ）的线性表。
A 散列存储 B 顺序存储或链接存储
C 压缩存储 D 索引存储
44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ）
A O（n2） B O（n log2n） C O（log2n） D O（n） 45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A ) A n B n+1 C n-1 D n+e
46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还
可以利用（C ）。
A 求关键路径的方法 B 求最短路径的Dijkstra方法
C 深度优先遍历算法 D 广度优先遍历算法 47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A )
A 1 B 2 C 9 D 10
48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ）
A O（log2n） B O（n） C 不直接依赖于n D
上述都不对
2. 已知一个AOV网如图所示。
(1)试画出它的邻接链表。（顶点号递减出现在各邻接表中） (2)试写出按照拓扑排序算法得到的拓扑序列。
V2V1 V3 V5V4 V6 【答案】
（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），
写出执行f30(&L)后的L状态； （2）简述算法f30的功能。 void f30 (SeqList *L) { int i,j; for (i=j=0;i
j++； }
L->length=j; }
【答案】（1）L=(21,19,0,34,30) (2) 删除顺序表中小于0的数。 4. 已知关键字序列{34,26,47,12,63,41,22,59},利用堆排序的方法对其排序。
（1）写出在构成初始堆后关键字的排列情况。
（2）写出在堆排序的过程中输出前4个记录时,每次调整后关键字的排
列情况。
【答案】（1）初始堆：{12,26,22,34,63,41,47,59} （2）输出12后：{22，26，41，34，63，59，47} 输出22后：{26，34，41，47，63，59} 输出26后：{34，47，41，59，63}
输出34后：{41，47，63，59}
5. 请用克鲁斯卡尔算法构造下图所示网络的最小生成树。
18 v 1 12 v2 22 10 14 v16 3 19 8 V6 v4 20 v10 5 【答案】
最小生成树如下图所示：
v1 14 18 12 v3 v2 12. 已知二叉树如右图所示。（1）画出该二叉树的二叉链表；（2）分
10 V6 B 别写出该二叉树的先根、中根和后根遍历序列。
A C 8 v5 v4 D E F 6. 给出一组关键字K={14,28,17,9,7,21,13,4,11},写出用下列方法
排序时,第一趟结束时关键字的排列状态。
(1)快速排序(2)希尔排序(d1=4) (3)归并排序
G 【答案】(1)快速排序：{11,4,13,9,7}14{21,17,28}
(2)希尔排序(d1=4) ： {7,21,13,4,11,28,17,9,14}
(3)归并排序：[11，28 ] [9，17 ] [7，21 ] [4，13 ] [11]
【答案】(1)
A B ∧ ∧ D ∧ C ∧ F ∧ 7. 假设一棵二叉树的先根遍历序列为ABCDEFGHI，中根遍历序列为
ADCEBFHIG。
(1)画出该二叉树；（2）写出后根遍历序列。
∧ E ∧ G ∧ 【答案】（1）二叉树：
A B C D E H F G （2）先根遍历序列：ABDCEGF
中根遍历序列: DBAEGCF 后根遍历序列: DBGEFCA
14. 设一段文字中七个常用汉字为{的，地，得，和，个，在，是}，
每个字符的使用频率分别为{26，6，4，7，9，8，18}。请画出对应的哈夫曼编码树（按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。
【答案】哈夫曼树：
I 0 33 78 （2）后根遍历序列： DECIHGFBA
1 45 9. 设网络如图所示，试用普里姆算法按照并入最小生成树中边的次序
填写下表(从顶点A开始)，并画出对应的最小生成树。
2 A 4 F E 5 B 2 C 3 1 4 2 D 0 15 1 18 19 0 1 26 0 7 1 8 是 0 9 1 10 的 1 6 和 在 个 0 4
4 5 哈夫曼编码 得 地 始 点 终 点 权 值 1 3 2 的 11 地 1011 得 1010 和 000 个 100 【答案】
始 点 终 点 权 值 A E 2 18. 已知一组数据元素为（57，24，96，73，18，45，30，40，82），
5 C E 3 E F 1 要求： （1）试从空树开始画出按元素排列顺序输入而生成的一棵二叉排序树； （2）画出删除结点57后的二叉排序树。
1 3 4 2 A R C R C D 2 2 2 B 2 C 3 1 F 2 D 【答案】(1) 二叉排序树:
57 24 96 18 45 73 30 82 40 （2）删除结点57后的二叉排序树:
73 45 24 96 24 96 18 45 82 18 30 73 30 40 82 或： 40 22. 已知有向图的邻接表如图所示,
(1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列; (2) 画出该有向图的逆邻接表。
【答案】（1）ABDCE (2)
0 A 4 ∧ 1 B 0 4 ∧ 2 C 1 3 3 D 0 ∧ 4 E 2 ∧ 23. 依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完
成下列操作：
1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;
2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉
排序树。写出满足上述要求的序列中的第一个元素。
【答案】（1）ASL=(1+2*2+3*3+3*4)/9=26/9 （2）8
24. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依
次为：0110，10，110，111，00，0111和010。 (1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字
符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5
和9，求该哈夫曼树的带权路径长度。
【答案】(1)
26. 假设一棵树的先根序列为ABCEFIJGHKD，后根序列为BEIJFGKHCDA。
请画出该树。【答案】（1）因为树的先根和后根遍历序列分别与其
转换后对应的二叉树的先根和中根遍历序列相同，所以可先得到的对应的二叉树如下图所示：
Ａ Ｂ Ｃ Ｅ Ｄ Ｆ I G H J K （2）根据树与二叉树的转换规则，可得到树如下图所示：
Ａ Ｂ Ｄ Ｃ Ｅ H Ｆ G K I J 28. 已知二叉树的先序序列和中序序列分别为HDACBGFE和
ADCBHFEG。
（1）画出该二叉树；
（2）画出与（1）求得的二叉树对应的森林。
【答案】(1)
34. 假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字
符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：
(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；
(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。
【答案】（1）
101 0 1 47 54 0 1 0 1 21 25 26 28 0 1 0 1 10 11 12 13 0 1 5 7 0 1 2 3 (2) a:0101 b:10 c:01000 d:11 e:011 f:000 g:01001 h:001
35. 根据关键字序列{48,68,72,60,36,25,45,40}
（1）构造一棵二叉排序树；
（2）求出等概率下的平均查找长度ASL。
【答案】
(1) 二叉排序树 48 36 68 25 45 60 72 40 (2) ASL=（1*1+2*2+4*3+1*4）/8=21/8
37. 假设一棵二叉树的先根遍历序列为ABCDEFGHI，中根遍历序列为
ADCEBFGHIJ。
(1)画出该二叉树；（2）写出后根遍历序列。
【答案】（1）二叉树：
A B C F D E G H I （2）后根遍历序列： DECIHGFBA
38. 已知一个AOV网如右图所示。
(1) 试画出它的邻接表。（表结点按顶点编号递减排列） (2) 求出应用拓扑排序算法求得的拓扑排序序列。
v2 v1 v3 v5 v4 【答案】
(1) 邻接表: 1 V1 2 0 V 4 3 2 ∧ 2 2 ∧ 3 V3 1 5 4 ∧ 4 V4 3 ∧ 5 V5 1 4 2 ∧ (2) 拓扑排序序列：v1,v3,v5,v2,v4
39. 已知二叉树如图1所示，试写出该二叉树的先根、中根和后根遍历
序列。
A B C F D E G H 图1 I 【答案】
先根：ABCDEFGHI 中根：ADCEBFHIG 后根：DECIHGFBA
43. 已知二叉树的先序序列和中序序列分别为ABDEHCFI和
DBHEACIF，
(1) 画出该二叉树的二叉链表存储表示; (2) 写出该二叉树的后序序列。
【答案】
（1）
A B ∧ C ∧ D ∧ E ∧ F ∧ ∧ H ∧ ∧ I ∧
（2） DHEBIFCA
相关推荐：
loading