软件技术图习题.doc

习题十一一 单项选择题1 一个有n个顶点的连通无向图 ，其边的个数至少为A. （）要连同具有n个顶点的有向图,至少需要( )条边 A.-1 B. n C. n+1 D. 2n3.一个有个n结点的图, 至少有( )个连通分量 最多有( )个连通分量 一个图中包含个连通分量，如按深度优先搜索遍历访问所有顶点，则必须调用（）次深度优先搜索遍历法5以下说法中不正确的是（ ）A. 无向图中的德及大连通子图称为连通分量。B. 在连通图的广度优先搜索遍历中，一般要采用队列来暂存刚访问过的顶点C .在图的深度优先搜索遍历中，一般要采用栈来暂存刚访问过的顶点D. 有向图的遍历不可采用广度优先搜索遍历6判断一个有向图中是不是存在回路，除了可以用拓扑排序法外还可以利用（ ）A.求关键路径的方法B. 求最短路径的方法 C.广度优先搜索遍历D.深度优先搜索遍历7 用DFS遍历一个无环有向图，若在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（ ）A.逆拓扑有序B. 拓扑有序 C.无序的 D.递增有序8下列哪一种图的邻接矩阵一定是对称矩阵（ ）A. 有向图B.无向图 C. AOV图D.AOE网10 在图采用临街连标存储时，求最小生成树的算法时间复杂度（ ）A. O(n) B.O(n+e) C. O(n*n) D O(n*n*n)11 在有向图G的拓扑序列中如顶点Vi在顶点Vj之前, 则下列情形不可能出现的是（ ）A. 图G中有弧（Vi,Vj） B. 图G中有一条从Vi到Vj的路径C. 图G中没有弧（Vi,Vj） D. 图G中有一条从Vj到Vi的路径12下列关于AOE网的叙述，不正确的事（）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成整个工程就会提前完成C.所有的关键或地动都提前完成整个工程将会提前完成D.某些关键活动提前完成，整个工程建会提前完成二 判断题 1 强连通分量是有向图中的极小连通子图 2强连通图的各顶点均可互相到达 3无向图的邻接矩阵可用一位数组存储 4 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数之和的一半 5 有向图的邻接矩阵可能是对称的 6 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占有的存储空间大小与图中结点个数有关，而与图的边数无关7广度优先搜索生成树描述了从起点到各顶点的最短路经8任何无向图都存在生成树9若连通图上个遍权值均不相同，则该图的最小生成树是唯一的10拓扑排序算法仅适用于有向无环图11一个有向无环图的拓扑排序序列是唯一的12对一个AOV网而言，从源点到终点的所有路径中最长的路径称为关键路径13在AOE网中，关键路径上活动的时间延长多少整个工程的时间就随之延长多少三 填空题1构造n个结点的强联通图，至少需要（ ）条弧3已知一个有向图用邻接矩阵表示，删除第i个顶点的所有相关边的方法是（ ） 4已知有向图用邻接链表示，删除所有从第i个顶点出发的边的方法是（ ）5一个有8个顶点的完全无向图的边数是（）一个图的（）表示法是唯一的，而（）不是唯一的在n个顶点的有向图中，没个顶点的最大度为（）求最小的生成树的prim算法的时间复杂度为（），它对（）图较为适合dijkstra最短路经算法从源点到其余各顶点的最短路经长度按（）次序依次产生10设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为（ ）11在AOE网中，从源点到汇点路径上个活动时间总和最长的路径称为（ ）参考答案一 单项选择题参考答案1A 2.B 3 B;D 4. A 5. D 6. D 7.A 8. B 9. C;C 10. C 11. D 12. B二判断题参考答案 1，错误 强联通分量是有向图中的极大连通子图 2正确 3正确 4正确 5正确 6正确 7错误 广度优先搜索生成树与最短路径无关 8错误 连通无向图存在生成树，非连通无向图不存在生成树 9正确 10正确 11错误 12正确 13正确三。填空题参考答案 1n 2广度优先搜索遍历 3将矩阵第