《计算机专业基础综合-试卷2》由会员分享，可在线阅读，更多相关《计算机专业基础综合-试卷2（4页珍藏版）》请在金锄头文库上搜索。
1、计算机专业基础综合（图）-试卷 2（总分：54.00，做题时间：90 分钟）一、 单项选择题（总题数：18，分数：36.00）1. 单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。2. 下面是一个求最小生成树的算法，其中G是连通无向图，T是所求的生成树。T： =G： While T中存在 回路do begin在T中找一条权值最大的边e； T： =T 一 e； （T中去掉e边）EnD.试问该算法是哪一 种求最小生成树的算法?（ ）A. Prim（普里姆）算法B. Kruskal（克鲁斯卡尔算法）丿C. 罗巴赫算法D. 其他算法由算法可以看出使用的是 Krus
2、kal 算法。3. 邻接表是图的一种（ ） 。A. 顺序存储结构B. 链接存储结构丿C. 索引存储结构D. 散列存储结构图的邻接表存储结构是一种链接存储结构。4. 下面试图对图中路径进行定义，说法正确的是（ ） 。A. 由顶点和相邻顶点序列构成的边所形成的序列丿B. 由不同顶点所形成的序列C. 由不同边所形成的序列D. 上述定义都不是由图的定义可知， B 与 C 是错误的。5无向图中顶点个数为n,那么边数最多为（）。A. n 一 1B. n（n 一 1）/2 丿C. n（n+1） 2D. n 2无向图中有 n 个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为 n（n1）
3、/ 2。6. 在一个具有 n（n0） 个顶点的连通无向图中，至少需要的边数是（ ） 。A. nB. n+1C. n 一 1 丿D. n/ 2在无向图中，如果从一个顶点v 到另一个顶点v （i#j）有路径，则称顶点v 和v 是连通的。如果ijij图中任意两顶点都是连通的，则称该图是连通图。所以具有 n 个顶点的连通无向图至少有 n 一 1 条边。7以下叙述中正确的是（）。I 对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能 访问到每个顶点，则该图一定是完全图II.连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 III.图的深度优先搜索中一般要采用栈来暂存访问过的顶点A.I，
4、IB.I，IVC.I，ID.I，I，II的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图 却非完全图。11、111的叙述显然是正确的。8带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。A. 第i行非8的元素之和B. 第i列非8的元素之和C. 第i行非8且非0的元素个数D. 第i列非8且非0的元素个数 丿有向图的邻接矩阵中， 0和8表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。9. 在一个无向图中，所有顶点的度之和等于边数的（ ）倍。A. 12B. 1C. 2 丿D. 4在无向图中，一条边计入两个顶点的度数。10. 采用邻接表存储
5、的图的深度优先遍历算法类似于二叉树的（ ）算法。A. 前序遍历丿B. 中序遍历C. 后序遍历D. 按层遍历 由图的深度优先遍历算法和二叉树的前序遍历可知选 A。11. 任何一个无向连通图（ ）最小生成树。A. 只有一棵B. 有一棵或多棵丿C. 一定有多棵D. 可能不存在无向连通图应有一棵或多棵最小生成树。12. 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是（ ）。A. 求关键路径的方法B. 求最短路径的迪杰斯特拉方法C. 深度优先遍历算法 VD. 广度优先遍历算法当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出I）FSTraverse算法）即为逆 向的
6、拓扑序列。13. 有 n 个顶点 e 条边的无向图，采用邻接表存储时，有（ ）个表头结点，有（ ）个链表结点。A. n2e VB. n2e+1C. n 一 12eD. n 一 12e+1根据邻接表的结构，无向图对应的邻接表有n个表头结点，有2e个链表结点（每条边对应两个链表结点）。14. 对于由n个顶点组成的有向完全图来说，图中共包含（）条边，对于由n个顶点组成的无向完全图来说， 图中共包含（ ）条边。A. n， n（n 一 1）B. n， n（n 一 1） 2C. 2n， n（n 一 1）D. n（n 一 1） ， n（n 一 1） 2 V 由完全图的定义可知本题答案为 D。15. 在一个（
7、 ）图中寻找拓扑序列的过程称为（ ）。A. 有向，拓扑排序 VB. 无向，拓扑排序c.有向，最短路径搜索D.无向，最短路径搜索 寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。16. 用邻接矩阵A表示图，判定任意两个顶点v i和v（之间是否有长度为m的路径相连，则只要检查（） 的第i行第j列的元素是否为零即可。1 JA. mAB. AC. A m VD. Am-1 此题考查的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两点之间有边，则值为1，否则为0。本题只 要考虑A m =AXAXXA（m个A矩阵相乘后的乘积矩阵）中（i, j）的元素值是否为0就行了。17. 当各边上的权值（）时，BFS
8、算法可用来解决单源最短路径问题。A. 均相等 VB. 均互不相等C. 不一定相等D. 不确定此题考查的知识点是图的BFS算法。BFS是从根结点开始，沿着树的宽度遍历树的结点，如果所有结点均 被访问，则算法中止。当各边上的权值相等时，计算边数即可，所以选A。18. 下面关于图的存储结构的叙述中正确的是（ ）。A. 用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关 VB. 用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关C. 用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D. 用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关那接表法的基本思想:邻接矩阵法的基本
9、思想是对于有n个顶点的图，用一维数组vexsn存储顶点信息，用二维数组Ann 存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶点i到顶点j之间关系的信息。 对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点V .的边（对有向图是以顶点V .为头或尾的弧）。二、 综合应用题（总题数:8，分数:18.00）19. 综合应用题 41-47 小题。20. 证明:具有 n 个顶点和多于 n 一 1 条边的无向连通图 G 一定不是树。正确答案：（正确答案
10、：此题考查的知识点是图的定义。具有n个顶点n 一 1条边的无向连通图是自由树， 即没有确定根结点的树，每个结点均可当根。若边数多于n一1条，因一条边要连接两个结点，则必因加 上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回 路的连通图）。 ）21证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为 无环图。正确答案： （正确答案：此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾 顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线 元素均为 0。先
11、证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非 零元素（Aij=1）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0,则不允许出现弧头顶点 编号大于弧尾顶点编号的弧，否则，就必然存在环路。 （对该类有向无环图顶点编号，应按顶点出度顺序编 号。 ）关于图（Graph）的一些问题：（分数：4.00）（1）.有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?正确答案：（正确答案：n（n1）, n）（2）. 表示有 1000 个顶点、 1000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?正确答案： （正确答案： 10 6 ,不一定是稀疏矩阵
12、 提示：此题考查的知识点是图的相关术语。 （1）在有向图G中，如果对于每一对v , v 属于V, v 不等于v ，从v 到v 和从v 到v 都存在路径，i j i j i j j i则称G是强连通图。最多边是所有的顶点每对之间都有边，边数为n（n 一 1）；最少只有一个方向有边，为 n。（2）元素个数为矩阵的大小,即10 6 ,稀疏矩阵的定义是非零个数远小于该矩阵元素个数,且分布无规律，不一定稀疏。 ）22. 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1 都集中到对角线以上?正确答案：（正确答案：此题考查的知识点是图顶点度数。可以按各顶点的出度进行排序。n个顶点的有向 图，其
13、顶点最大出度是n 一 1,最小出度为0。这样排序后，出度最大的顶点编号为1,出度最小的顶点编 号为n之后，进行调整，即若存在弧i，j，而顶点，的出度大于顶点i的出度，则将j的编号排在顶 点 i 的编号之前。 ）23. 假定图G=（V，E）是有向图，V=1，2，N，N1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A 是一个二维数组。如果i到j有边，则Ai，j=l，否则Ai，j=0。请给出一个算法思想，该算法能判断 G是否是非循环图（即G中是否存在回路），要求算法的时间复杂性为0（n 2 ）。正确答案：（正确答案：此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行DFS（v）时，若在 退出D
14、FS（v）前碰到某顶点v，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有 环；否则，无环。 ）24. 对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?正确答案： （正确答案：此题考查的知识点是图的遍历。遍历不唯一的因素有：开始遍历的顶点不同；存储正确答案：（正确答案：无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n 一 1条边。而 最小生成树则是各边权值之和最小的生成树。 ）（2）.G如图所示，请找出G的所有最小生成树。正确答案：（正确答案：最小生成树有两棵。下面给出顶点集合和边集合，编以三元组（VV.，W）形式, 其中 W 代表权值。 V（G）=1， 2， 3， 4， 5E1（G）=（4， 5， 2）， （2， 5， 4）， （2， 3， 5）， （1， 2， 7）； E2（G）=（4 5， 2）， （2， 4， 4）， （2， 3， 5）， （1， 2， 7）
