计算机专业基础综合

1、计算机专业基础综合（图）-试卷2（总分：54.00，做题时间：90分钟）一、单项选择题（总题数：18,分数：36.00）单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。下面是一个求最小生成树的算法，其中G是连通无向图，T是所求的生成树。T： =G： While T中存在 回路do begin在T中找一条权值最大的边e； T： =T 一 e； （T中去掉e边）EnD.试问该算法是哪一 种求最小生成树的算法？（）Prim（普里姆）算法Kruskal（克鲁斯卡尔算法）罗巴赫算法其他算法由算法可以看出使用的是Kruskal算法。邻接表是图的一种（）。顺序存储结构链接存

2、储结构 V索引存储结构散列存储结构图的邻接表存储结构是一种链接存储结构。下面试图对图中路径进行定义，说法正确的是（）。由顶点和相邻顶点序列构成的边所形成的序列 V由不同顶点所形成的序列由不同边所形成的序列上述定义都不是由图的定义可知，B与C是错误的。无向图中顶点个数为n，那么边数最多为（）。n 一 1n（n 一 1）/2 Vn（n+1） / 2 TOC o 1-5 h z n 2无向图中有n个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为n（n1） /2。在一个具有n（n0）个顶点的连通无向图中，至少需要的边数是（）。nn+1n 一 1 Vn/2在无向图中，如果从一个顶

3、点v j到另一个顶点v j （i#j）有路径，则称顶点v j和v j是连通的。如果 图中任意两顶点都是连通的，则称该图是连通图。所以具有n个顶点的连通无向图至少有n一1条边。以下叙述中正确的是（）。I .对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能 访问到每个顶点，则该图一定是完全图II.连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 III.图的深度优先搜索中一般要采用栈来暂存访问过的顶点I，IIn，m vi，mi，ii，mI的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图 却非完全图。11、111的叙述显然是正确的。带权有

4、向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。第i行非8的元素之和第i列非8的元素之和第i行非8且非0的元素个数第i列非8且非0的元素个数 V有向图的邻接矩阵中，0和8表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。在一个无向图中，所有顶点的度之和等于边数的（）倍。 TOC o 1-5 h z 1 / 212 V4在无向图中，一条边计入两个顶点的度数。采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）算法。前序遍历 V中序遍历后序遍历按层遍历由图的深度优先遍历算法和二叉树的前序遍历可知选A。任何一个无向连通图（）最小生成树。只有一棵有一棵或多棵 V一定有多棵可能不存在无向

5、连通图应有一棵或多棵最小生成树。判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是（）。求关键路径的方法求最短路径的迪杰斯特拉方法深度优先遍历算法 V广度优先遍历算法当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出I）FSTraverse算法）即为逆 向的拓扑序列。有n个顶点e条边的无向图，采用邻接表存储时，有（）个表头结点，有（）个链表结点。n. 2e Vn. 2e+1n 一 1. 2en 一 1. 2e+1根据邻接表的结构，无向图对应的邻接表有n个表头结点，有2e个链表结点（每条边对应两个链表结点）。对于由n个顶点组成的有向完全图来说，图中共包含（）条边

6、，对于由n个顶点组成的无向完全图来说， 图中共包含（）条边。n，n（n 一 1）n，n（n 一 1）/22n， n（n 一 1）n（n 一 1）， n（n 一 1）/2 V由完全图的定义可知本题答案为D。在一个（）图中寻找拓扑序列的过程称为（）。有向，拓扑排序 V无向，拓扑排序有向，最短路径搜索无向，最短路径搜索寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。 TOC o 1-5 h z 用邻接矩阵A表示图，判定任意两个顶点v和v j之间是否有长度为m的路径相连，则只要检查（） 的第i行第j列的元素是否为零即可。1 JmAAA m VAm-1 此题考查的知识点是图的邻接矩阵存储。在图的邻接

7、矩阵中，两点之间有边，则值为1，否则为0。本题只 要考虑A m =AXAXXA（m个A矩阵相乘后的乘积矩阵）中（i，j）的元素值是否为0就行了。当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。均相等 V均互不相等不一定相等不确定此题考查的知识点是图的BFS算法。BFS是从根结点开始，沿着树的宽度遍历树的结点，如果所有结点均 被访问，则算法中止。当各边上的权值相等时，计算边数即可，所以选A。下面关于图的存储结构的叙述中正确的是（）。用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关 V用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关用邻接表存储图占用空间大小只与图中

8、顶点数有关，与边数无关用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关 邻接矩阵法的基本思想是对于有n个顶点的图，用一维数组vexsn存储顶点信息，用二维数组Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶点i到顶点j之间关系的信息。邻接表法的基本思想:对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点V 的边（对有向图是以顶点V 为头或尾的弧）。二、综合应用题（总题数：8,分数：18.00）1综合应用题41-47小题。证明：具

9、有n个顶点和多于n 一 1条边的无向连通图G 一定不是树。正确答案：（正确答案：此题考查的知识点是图的定义。具有n个顶点n一1条边的无向连通图是自由树， 即没有确定根结点的树，每个结点均可当根。若边数多于n一1条，因一条边要连接两个结点，则必因加 上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回 路的连通图）。）证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为 无环图。正确答案：（正确答案：此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾 顶点的编号大于弧头顶点的编号。由于不允许从某

10、顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线 元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非 零元素（Aij=1 ）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点 编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点出度顺序编 号。）关于图（Graph）的一些问题：（分数：4.00）(1).有n个顶点的有向强连通图最多有多少条边?最少有多少条边?正确答案：(正确答案：n(n1), n)(2).表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?正确答

11、案：(正确答案：10 6，不一定是稀疏矩阵提示：此题考查的知识点是图的相关术语。(1)在有向 图G中，如果对于每一对v j，v j属于V，v j不等于v j，从v j到v j和从v j到v j都存在路径， 则称G是强连通图。最多边是所有的顶点每对之间都有边，边数为n(n 一 1)；最少只有一个方向有边，为 n。 (2)元素个数为矩阵的大小，即10 6，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无 规律，不一定稀疏。)如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？ 正确答案：(正确答案：此题考查的知识点是图顶点度数。可以按各顶点的出度进行排序。n个顶点

12、的有向 图，其顶点最大出度是n 一 1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编 号为n之后，进行调整，即若存在弧i，j，而顶点，的出度大于顶点i的出度，则将j的编号排在顶 点i的编号之前。)假定图G=(V，E)是有向图，V=1，2，N，NN1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A 是一个二维数组。如果i到j有边，则Ai，j=l，否则Ai，j=0。请给出一个算法思想，该算法能判断 G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n 2 )。正确答案：(正确答案：此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行DFS(v)时，若在 退出DFS(v)前碰到某顶点v，其邻接点是巳经访问的顶点v，则说明v的子孙u有到v的回边，即说明有 环；否则，无环。)对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？正确答案：(正确答案：此题考查的知识点是图的遍历。遍历不唯一的因素有：开始遍历的顶点不同；存储正确答案：(正确答案：无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n一1条边。而 最小生成树则是各边权值之和最小的生成树。)