手机扫描二维码答题
00:00:00
第6章-图（常规课）
录音中...
*
您的姓名：
*
1.
下面结构中最适于表示稀疏无向图的是（）?
十字链表
逆邻接表
邻接多重表
邻接表
邻接矩阵
稀疏无向图多用邻接表;含重边需邻接多重表，题面答案给出 C。
*
2.
对于一个有向图，若一个顶点的入度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（）?
k2
k1
k1+k2
k1-k2
邻接表按出边存储，结点表中记录的是出度对应的边结点，数量为 k2。
*
3.
下列哪一种图的邻接矩阵是对称矩阵（）?
有向图
AOV 网
AOE 网
无向图
无向图中边无方向，邻接矩阵关于主对角线对称。
*
4.
一个 n 个顶点的连通无向图，其边的个数至少为（）?
n
n+1
nlogn
n-1
最少边的连通无向图为树，边数为 n-1。
*
5.
在一个无向图中，所有顶点的度数之和等于所有边数（）倍?
4
1/2
2
1
握手定理，度数和为 2e。
*
6.
图中有关路径的定义是（）?
上述定义都不是
由不同顶点所形成的序列
由不同边所形成的序列
由顶点和相邻顶点序偶构成的边所形成的序列
路径是顶点序列相邻顶点间的边序列。
*
7.
设有向无环图G中的有向边集合E={<1，2>，<1，3>，<3，4>}，则下列不属于该有向图G的一种拓扑排序序列的是（）?
1，3，4，2
1，4，2，3
1，2，3，4
1，3，2，4
4 需要在 3 之后，C 中 4 在 3 之前，违背部分序。
*
8.
一个有向图的邻接表和逆邻接表中的结点个数一定相等（）?
对
错
每条边在邻接表作为出边出现一次，在逆邻接表作为入边出现一次，计数相同。
*
9.
设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）?
2，3，4，1
1，2，4，3
1，4，2，3
1，2，3，4
满足有向无环图的部分序关系，1 在 2 与 4 之前，2 在 3 之前，故 1，2，3，4 正确。
*
10.
设无向连通图有n个顶点 e 条边，若满足（），则图中一定有回路?
2e≥n
e=n-1
e<n
e≥n
连通无向图若 e≥n，必含环;若 e=n-1 则为树无环。
*
11.
一个有 n 个结点的图，最多有（）个连通分量?
n
1
0
n-1
所有顶点互不相连时，每个顶点自成一个分量，最多为 n。
*
12.
若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（）?
一般矩阵
对称矩阵
三角矩阵
稀疏矩阵
按拓扑序重排后，邻接矩阵为严格上三角（或下三角）。
*
13.
n个顶点的连通图中，任意两个不同顶点之间的一条简单路径，其长度不可能超过（）?
n
n-1
n/2
1
简单路径不重复顶点，最多包含 n 个顶点，边数不超过 n-1。
*
14.
当各边上的权值（）时，BFS 算法可用来解决单源最短路径问题?
均互不相等
均相等
不一定相等
所有边权相等时，最短路等价于最少边数，BFS 适用。
*
15.
设二叉树有n个结点，则其深度为（）?
⌊log2 n⌋+1
不能确定
n
n-1
同样结点数的二叉树深度与形态有关，如链状与满二叉树深度不同，无法唯一确定。
*
16.
n 个顶点的无向图的邻接表最多有（）个边结点?
n^2
n(n-1)/2
n(n+1)
n(n-1)
无向完全图每条边在两条邻接表中各出现一次，共 2e= n(n-1)。
*
17.
用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是（）?
拓扑有序
逆拓扑有序
无序的
后序输出与拓扑序相反，故为逆拓扑序。
*
18.
用邻接表存储图所用的空间大小（）?
与边数的平方有关
只与图的顶点数有关
只与图的边数有关
与图的顶点数和边数都有关
需要顶点表 O(n) 与边表 O(e) 的空间。
*
19.
在一个无向图中，所有顶点的度数之和等于所有边数的（）倍?
4
1
2
1/2
握手定理:无向图顶点度数和等于 2e。
*
20.
要连通具有 n 个顶点的有向图，至少需要（）条边?
2n
n
n-1
n+1
构成强连通至少 n 条边可成一个有向环;题干常指强连通情形。
*
21.
用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与边数无关（）?
错
对
邻接矩阵固定为 n×n，与边数无关。
*
22.
下列不正确的是（）?
(1) 迪杰斯特拉最短路径算法中弧上权不能为负的原因是在实际应用中无意义;
(2) 利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n^3);（图用邻接矩阵表示）
(3) Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
(2),(3)
(1),(3)
(1)
(1),(2),(3)
(1) 错在原因，不能为负因算法性质;(2) 用 Dijkstra 多源会到 O(n^3) 可成立;(3) 允许负权但不允许负环为对
*
23.
设无向图的顶点个数为 n，则该图最多有（）条边?
n(n+1)/2
n^2
n-1
n(n-1)/2
0
简单无向完全图边数为 C(n,2)=n(n-1)/2。
*
24.
完全有向图是指每对不同顶点之间均存在两条方向相反的有向边，且不包含自环边。n 个结点的完全有向图含有边的数目为（）?
n*n
n(n-1)
n/2
n(n+1)
每对顶点有两条有向边，共 2*C(n,2)=n(n-1)。
二、判断题（共2题，6分）
*
25.
在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（）?
G 中没有弧 <Vi,Vj>
G 中有一条从 Vj 到 Vi 的路径
G 中有一条从 Vi 到 Vj 的路径
G 中有弧 <Vi,Vj>
若存在 Vj→Vi 路径则与拓扑序矛盾（形成环或逆序）。
*
26.
图的 BFS 生成树的树高比 DFS 生成树的树高（）?
小
小或相等
大
大或相等
BFS 分层最短，生成树高度不超过 DFS 生成树高度。
评价对象得分
字体大小
第6章-图（常规课）
复制
