图6-16 一棵哈夫曼树
其加权路径长度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80
4. 已知一棵二叉树的中序序列为 cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。
解：由后序序列的最后一个结点 a 可推出该二叉树的树根为 a，由中序序列可推出 a的左子树由 cbed 组成，右子树由 hgijf 组成，又由 cbed 在后序序列中的顺序可推出该子树的根结点为 b，其左子树只有一个结点 c，右子树由 ed 组成，显然这里的 e 是根结点，其右子树为结点 d，这样可得到根结点 a 的左子树的先序序列为：bcde；再依次推出右子树的先序序列为：fghij。因此该二叉树如图 6-17所示。
图 6-17 二叉树
设二叉树的先序线索链表如图 6-18所示。
16
图 6-18 二叉树的先序线索链表
第7章 图
单项选择题
1．在一个图中，所有顶点的度数之和等于所有边数的 倍。 A. 1/2 B. 1 C. 2 D. 4
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 3．具有 4 个顶点的无向完全图有 条边。
A. 6 B. 12 C. 16 D. 20
4．具有 6 个顶点的无向图至少应有 条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8
5．在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边。 A. n B. n+1 C. n-1 D. n/2
6．对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。 A. n B. (n-1)2 C. n-1 D. n2
7．对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是 。
17
A. e/2 B. e C. 2e D. n+e 8．已知一有向图的邻接表存储结构如图 7-2 所示。
（1）根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 。 A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2
（2）根据有向图的广度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 。 A. v1，v2，v3，v4，v5 B. v1，v3，v2，v4，v5 C. v1，v2，v3，v5，v4 D. v1，v4，v3，v5，v2
123452445324
图7-2一个有向图的邻接表存储结构
9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用 。 A. 求关键路径的方法 B. 求最短路径的 Dijkstra 方法 C. 广度优先遍历算法 D. 深度优先遍历算法
1-5.CBAAC 6-9 DCCBD
填空题
1．n 个顶点的连通图至少 条边。
2．在无向图 G 的邻接矩阵 A 中，若 A[i][j]等于 1，则 A[j][i]等于 。 3．已知图G的邻接表如图 7-3 所示，其从顶点 v1 出发的深度优先搜索序列为 ，其从顶点 v1 出发的广度优先搜索序列为 。
18
v1v2v3v4v5v6v2v3v6v5v5v4v4v6v3
图7-3 G的邻接表
4．设x,y是图G中的两顶点，则（x,y）与（y,x）被认为______边，但
5.已知一个图的邻接矩阵表示，删除所有从第 i 个结点出发的边的方法是 。 6．在有向图的邻接矩阵上，由第i行可得到第______个结点的出度，而由第j列可得到第___ ____个结点的入度。①i ②j
7. 在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为______。①连通，②连通图 1. n-1 2. 1
3. 答：① v1，v2，v3，v6，v5，v4 ② v1，v2，v5，v4，v3，v6 4. ① ②
5. 将矩阵第 i 行全部置为 0 5. ① ② 6. ① ②
例题解析
【例7-1】对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题： （1） 图中有多少条边？
（2） 任意两个顶点i和j是否有边相连？
19
（3） 任意一个顶点的度是多少？ 解：
⑴邻接矩阵非零元素个数的总和除以2。
⑵当A[ i,j ]≠0时，表示两顶点i,j之间有边相连。 ⑶计算邻接矩阵上顶点对应行上非零元素的个数。
综合题
1．给出如图 7-4 所示的无向图G的邻接矩阵和邻接表两种存储结构。
图7-4 无向图G
解：图 G 对应的邻接矩阵和邻接表两种存储结构分别如图所示。
2．用广度优先搜索和深度优先搜索对如图 7-5 所示的图 G 进行遍历（从顶点1出发），给出遍历序列。
解：搜索本题图的广度优先搜索的序列为：1，2，3，6，4，5，8，7，深度优先搜索的序列为：1，2，6，4，5，7，8，3。
20