c b a ac a b a c c b a b c b 图6.10 树形5种 10. dgbaechif 、abdgcefhi 、gdbeihfca 、 6.3 1. 5种, 图6.11
2. 二叉树如图6.12所示。
E 图6.11 树形5种 BF D C G H I K
3. 中序线索二叉树如图6.13（左）所示；后序该二叉树转换后的的森林如图6.14所示。 aa
bcNULLA线索二叉树如图6.13（右）所示；
bca 图6.12 fc e j J f defdeb h i d 4. 图6.8的树转化为一棵二叉树如下，图6.15： jhNULLjha i图8.18 中序和后序线索树i图 6.14 b 对应的森林 c e d
i g
图 6.15 一棵树的孩子兄弟表
5. 画出构造Huffman树如图6.16所示，计算其带权路径长度为 。
6. 一棵含有N个结点的k叉树,可能达到的最大深度 h=N-k+1 ，
最小深度各为: logkN+1。
62
37 25
19 13 18 12
10 9 7 6
4 5 图6.16 Huffman树
图6.13
习题7 图
7.1 单项选择题
1．在一个图中，所有顶点的度数之和等于所有边数的____倍。
A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树 。
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。
A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。
A. 6 B. 12 C. 16 D. 20
6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。
A. n B. n+1 C. n-1 D. n/2
8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。
22
A. n B. (n-1) C. n-1 D. n
9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。
① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e
10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到
的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。
① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b a
c b e
f d
图 7.1 一个无向图
11．已知一有向图的邻接表存储结构如图7.2所示。
3 2 ^ 1 2 ^ 4 5 ^ 3
4 ^
4 ^ 2 5 图7.2 一个有向图的邻接表存储结构
⑴ 根据有向图的深度优先遍历算法，从顶点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
⑵ 根据有向图的宽度优先遍历算法，从顶点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
12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法 15．关键路径是事件结点网络中 。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长的回路 D.最短的回路 16．下面不正确的说法是 。
（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和；
（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
A.（1） B.（2） C.（3） D.（1）、（2）
17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。
A.逆拓朴有序的 B.拓朴有序的 C.无序的 18．在图7.3所示的拓朴排列的结果序列为 。
A.125634 B.516234 C.123456 D.521634
图7.3有向图 19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。
A.0 B.1 C.n D.n+1
20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
7.2 填空题（将正确的答案填在相应饿空中）
1．n个顶点的连通图至少____条边。 2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。 3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。
4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。 v5 v4 v2 v1
v2 v5 v3
v3 v6
v4 ^
v5 v4 v6 v3
v6 ^ 图7.4 图G的邻接表
5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。
7．如果含n个顶点的图形成一个环，则它有 棵生成树。 8．一个非连通无向图，共有28条边，则该图至少有 个顶点。
9．遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。
10．一个图的 表示法是唯一的，而 表示法是不唯一的。 11．有向图中的结点前驱后继关系的特征是 。
12．若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。 13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。 7.3 综合题
1．已知如图7.5所示的有向图，请给出该图的: （1）每个顶点的入/出度； （2）邻接距阵； （3）邻接表； （4）逆邻接表； （5）强连通分量。
1 6 2 3 5 4 图7。5一个有向图 2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （1） a
16 15 11 b 15 c 15 d
14 12 13 16
21
e
图7.6
f
（2）
6 12 1 4 3 9 12 7 2 15 6 16 20 4 132 5 5 图7.73．试列出图7.8中全部的拓扑排序序列。
1 2 3 10
4 5 图7.8 6
相关推荐：
loading