10001A 000B 10138010621C 10000170121G032301ED 1001E 11F 10001G 01H 0017A10H01116D19B50123CF答案：
4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。
答案：二叉树形态
ABCEDFGH
5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答案：
301218743125116
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。 答案：(1)树形态：
321367919105523
(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79
7、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。
13
ABDGJEHKILCF答案：
8、一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：
（1）设计一棵哈夫曼树；（画出其树结构） （2）计算其带权路径长度WPL； 答案：(1)树形态：
6430341618995413
(2)带权路径长度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129
9、已知某森林的二叉树如下所示，试画出它所表示的森林。
ABCEDHFG答案：
ABC DEGFH
10、有一分电文共使用5个字符;a,b,c,d,e，它们的出现频率依次为4、7、5、2、9，试构造哈夫曼树，并给出每个字符的哈夫曼编码。
14
11、画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。
AIMBCDJNEFGKL
12、如下所示的二叉树，请写出先序、中序、后序遍历的序列。
FDBEGIHACHJ 答案：先序：FDBACEGIHJ
中序：ABCDEFGHIJ 后序：ACBEDHJIGF
第七章 图
一、选择题
1、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。
2
A. n B. n C. n-1 D. (n-1)2 2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 完全图 B. 连通图 C. 有回路 D. 一棵树 3、关键路径是事件结点网络中（ ）。
A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 4、下面（ ）可以判断出一个有向图中是否有环（回路）。
A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ）。
A. 第i行非无穷的元素之和 B. 第i列非无穷的元素个数之和 C. 第i行非无穷且非0的元素个数 D. 第i行与第i列非无穷且非0的元素之和 6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（ ）。
A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 7、无向图的邻接矩阵是一个（ ）。
A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵 9、邻接表是图的一种（ ）。
A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 10、下面有向图所示的拓扑排序的结果序列是（ ）。
A. 125634 B. 516234 C. 123456 D. 521643
15
132 12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A. 入边 B. 出边 C. 入边和出边 D. 不是出边也不是入边 13、设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1?V2,E1?E2则称（ ）。
A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量
14、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（ ）。
A. 将邻接矩阵的第i行删除 B. 将邻接矩阵的第i行元素全部置为0 C. 将邻接矩阵的第i列删除 D. 将邻接矩阵的第i列元素全部置为0 15、任一个有向图的拓扑序列（ ）。
A.不存在 B. 有一个 C. 一定有多个 D. 有一个或多个 16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
A. 1/2 B. 1 C. 2 D. 4 17、下列关于图遍历的说法不正确的是（ ）。
A. 连通图的深度优先搜索是一个递归过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法 D. 图的遍历要求每一顶点仅被访问一次
18、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中：（ ）。
A. 第i行非?的元素之和 B. 第i列非?的元素之和 C. 第i行非?且非0的元素个数 D. 第i列非?且非0的元素个数 19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层次遍历 20、一个具有n个顶点的有向图最多有（ ）条边。
A. n×(n-1)/2 B. n×(n-1) C. n×(n+1)/2 D. n2 21、已知一个有向图的邻接表存储结构如图所示，根据深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ ）。
123452445324564A. v1,v2,v3,v5,v4
C. v1,v3,v4,v5,v2 23、以下说法正确的是（ ）。
A. 连通分量是无向图中的极小连通子图 B. 强连通分量是有向图中的极大强连通子图
C. 在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧
D. 对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
24、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（ ）。
A. n B. e C. 2e D. n*e
B. v1,v2,v3,v4,v5 D. v1,v4,v3,v5,v2
16