【石油大学】数据结构-第三次在线作业
试卷总分:100 得分:100
1.(2.5分)下面结构中最适于表示稀疏无向图的是()
A、邻接矩阵
B、逆邻接表
C、邻接多重表
D、十字链表
正确资料:C
2.(2.5分)下列哪一种图的邻接矩阵是对称矩阵?()
A、有向图
B、无向图
C、AOV网
D、AOE网
正确资料:B
3.(2.5分)当一个有N个顶点的图用邻接矩阵A表示时,顶点Vi的度是()。
A、第j列所有元素之和
B、第i行所有元素之和
C、不确定
D、第j列所有元素之和+第i行所有元素之和
正确资料:B
4.(2.5分)下面哪一方法可以判断出一个有向图是否有环(回路):
A、深度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径
正确资料:B
5.(2.5分)在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()
A、O(n)
B、O(n+e)
C、O(n<sup>2</sup>))
D、O(n<sup>3</sup>))
正确资料:B
6.(2.5分)求解最短路径的Floyd算法的时间复杂度为()。
A、O(n)
B、O(n+c)
C、O(n*n)
D、O(n*n*n)
正确资料
7.(2.5分)已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是()。
A、V1,V3,V4,V6,V2,V5,V7
B、V1,V3,V2,V6,V4,V5,V7
C、V1,V3,V4,V5,V2,V6,V7
D、V1,V2,V5,V3,V4,V6,V7
正确资料:A
8.(2.5分)在用邻接表表示图时,拓扑排序算法时间复杂度为()。
A、O(n)
B、O(n+e)
C、O(n*n)
D、O(n*n*n)
正确资料:B
9.(2.5分)关键路径是事件结点网络中()。
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
正确资料:A
10.(2.5分)下面关于求关键路径的说法不正确的是()。
A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上
正确资料:C
|