数据结构习题 7.docxVIP

? 问题1得 10 分，满分 10 分? 任何一个无向连通图的最小生成树___________。所选答案：C. 有一棵或多棵?? 答案：A. 只有一棵B. 一定有多棵C. 有一棵或多棵?? D. 可能不存在? 问题 2 得 10 分，满分 10 分下面_________算法适合构造一个连通稀疏图G的最小生成树。所选答案：B. Kruskal算法答案：A. Prim 算法?B. Kruskal算法C. Dijkstra算法D. Floyd 算法? 问题 3 得 10 分，满分 10 分1.???????? 图的BFS生成树的树高比DFS生成树的树高___________。所选答案：B. 小或相等答案：A. 大B. 小或相等C. 小D. 大或相等? 问题 4 得 10 分，满分 10 分下面________?方法可以判断出一个有向图是否有环。所选答案：B. 拓扑排序答案：A. 求最小生成树?B. 拓扑排序C. 求关键路径D. 求最短路径? 问题 5 得 10 分，满分 10 分1.???????? 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是___________。所选答案：C. G中有一条从Vj到Vi的路径答案：A. G中有一条从Vi到Vj的路径B. G中有弧Vi,Vj??C. G中有一条从Vj到Vi的路径D. G中没有弧Vi,Vj??? 问题 6 得 10 分，满分 10 分1.???????? 连通图的极小连通子图称为该图的___________。所选答案：B. 生成树答案：A. 关键路径B. 生成树C. 最小回路D. 回路? 问题 7 得 0 分，满分 10 分设有向网 G=(V, {E}), ?V={a, b, c, d, e, f}, ?E={a,b2, a,c15, b,e19, b,d10, c,b4, c,e11, d,f6, e,f5 }，关键路径是 ???????????? 。所选答案：D. a c e f答案：A. a c b e fB. a b d fC. a b e fD. a c e f? 问题 8 得 10 分，满分 10 分在一个带权有向无环图中，用边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图简称为_________ 。所选答案：B. ? ?AOE网答案：A. 生成树B. ? ?AOE网C. ?AOV网D. 顶点表示活动的网? 问题 9 得 10 分，满分 10 分1.???????? 已知有向图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的拓扑序列是___________。所选答案：D. V1,V3,V4,V6,V2,V5,V7??????????? 答案：A. V1,V2,V5,V3,V4,V6,V7B. V1,V3,V2,V6,V4,V5,V7C. V1,V3,V4,V5,V2,V6,V7??????????? D. V1,V3,V4,V6,V2,V5,V7??????????? ? 问题 10 得 10 分，满分 10 分1.???????? 最短路径的生成算法可用___________。所选答案：B. Dijkstra算法答案：A. 哈夫曼算法B. Dijkstra算法C. Kruskal算法?D. prim算法? 问题 11 得 10 分，满分 10 分1.???????? 设有两个无向图G＝（V,E）,G1=(V1,E1),如果G1是G的生成树，则下列说法不正确的是___________。所选答案：C. G1是G的连通分量答案：A. G1是G的极小子图，且V1=VB. G1是G的子图????C. G1是G的连通分量D. G1是G的无环子图?? 问题 12 得 10 分，满分 10 分1.???????? 有拓扑排序的图一定是___________。所选答案：A. 有向无环图答案：A. 有向无环图B. 强连通图?C. 有环图D. 无向图?? 问题 13 得 10 分，满分 10 分1.???????? 设有向图有n个顶点和e条边，采用邻接表存储，进行拓扑排序时，时间复杂度为___________。所选答案：B. O (n+e)答案：A. O (e*n ) B. O (n+e)C. O ( elog2n)???D. O (nlog2e)