第7章图.doc

第7章图
选择题
,在用邻接表表示图时,拓扑排序算法时间复杂度为( )
A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n)
【答案】B
,则该图最多有( )条边。
A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2
【答案】B
( )
A) 无向图中的极小连通子图
B) 无向图中的极大连通子图
C) 有向图中的极小连通子图
D) 有向图中的极大连通子图
【答案】B
( )
A)n*n B)n(n+1) C)n/2 D)n*(n-1)
【答案】D
( )
A) AOE网中从源点到汇点的最长路径
B) AOE网中从源点到汇点的最短路径
C) AOV网中从源点到汇点的最长路径
D) AOV网中从源点到汇点的最短路径
【答案】A
( )
A)入度 B) 出度 C) 入度与出度之和 D) (入度+出度)/2
【答案】C
,若用邻接表存储,表中有( )边结点。
A) e B) 2e C) e-1 D) 2(e-1)
【答案】B
( )
A) 栈 B) 队列 C) 二叉树 D) 树
【答案】B
( )
A) 栈 B) 队列 C) 二叉树 D) 树
【答案】A
( )
A) 上三角矩阵 B)稀疏矩阵 C) 对称矩阵 D) 对角矩阵
【答案】C
( )倍
A) 1/2 B)1 C) 2 D) 4
【答案】B
,求最小生成树的 Prim 算法的时间复杂度为( )
A) O(n) B) O(n+e) C) O(n2) D) O(n3)
【答案】B
,不正确的是( )
A)关键活动不按期完成就会影响整个工程的完成时间
B)任何一个关键活动提前完成,那么整个工程将会提前完成
C)所有的关键活动提前完成,那么整个工程将会提前完成
D)某些关键活动提前完成,那么整个工程将会提前完成
【答案】B
( )
A) 9 B)10 C) 11 D) 12
【答案】A
,零元素的个数为( )
 A) e B)2e C) n2-e D)n2-2e
【答案】D
填空题
。
【答案】2
,具有n个顶点的有向完全图中包含有_____________条边。
【答案】(1)n(n-1)/2 (2) n(n-1)
,要连通所有顶点则至少需要_____________条边。
【答案】n-1