1、计算机专业基础综合（数据结构）模拟试卷 5及答案解析(总分：102.00，做题时间：90 分钟)一、单项选择题(总题数：35，分数：70.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.下面是一个求最小生成树的算法，其中 G是连通无向图，T 是所求的生成树。 T;=G; While T 中存在回路 do begin在 T中找一条权值最大的边 e； T：=T 一e； (T 中去掉 e边) End 试问该算法是哪一种求最小生成树的算法?( )（分数：2.00）A.Prim(普里姆)算法B.Kruskal(克鲁斯卡尔算法)C.罗巴
2、赫算法D.其他算法3.邻接表是图的一种( )。（分数：2.00）A.顺序存储结构B.链接存储结构C.索引存储结构D.散列存储结构4.下面试图对图中路径进行定义，说法正确的是( )。（分数：2.00）A.由顶点和相邻顶点序列构成的边所形成的序列B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是5.无向图中项点个数为 n，那么边数最多为( )。（分数：2.00）A.n一 1B.n(n-1)2C.n(n+1)2D.n 26.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是( )。（分数：2.00）A.nB.n+1C.n-1D.n27.以下叙述中正确的是( )。 I对有向
3、图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图 连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 图的深度优先搜索中一般要采用栈来暂存访问过的顶点（分数：2.00）A.I，B.，C.I，D.I，8.带权有向图 G用邻接矩阵 A存储，则顶点 i的入度等于 A中( )。（分数：2.00）A.第 i行非的元素之和B.第 i列非的元素之和C.第 i行非且非 0的元素个数D.第 i列非且非 0的元素个数9.在一个无向图中，所有顶点的度之和等于边数的( )倍。（分数：2.00）A.12B.1C.2D.410.采用邻接表存储的图的深度优先遍历算法类似于二叉
4、树的( )算法。（分数：2.00）A.前序遍历B.中序遍历C.后序遍历D.按层遍历11.任何一个无向连通图( )最小生成树。（分数：2.00）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在12.判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。（分数：2.00）A.求关键路径的方法B.求最短路径的迪杰斯特拉方法C.深度优先遍历算法D.广度优先遍历算法13.有 n个顶点 e条边的无向图，采用邻接表存储时，有( )个表头结点，有( )个链表结点。（分数：2.00）A.n，2eB.n，2e+1C.n-1，2eD.n-1，2e+114.对于由 n个顶点组成的有向完全图
5、来说，图中共包含( )条边，对于由 n个顶点组成的无向完全图来说，图中共包含( )条边。（分数：2.00）A.n，n(n 一 1)B.n，n(n1)2C.2n，n(n1)D.n(n一 1)，n(n 一 1)215.在一个( )图中寻找拓扑序列的过程称为( )。（分数：2.00）A.有向，拓扑排序B.无向，拓扑排序C.有向，最短路径搜索D.无向，最短路径搜索16.用邻接矩阵 A表示图，判定任意两个顶点 v i 和 v j 之间是否有长度为 m的路径相连，则只要检查( )的第 i行第 j列的元素是否为零即可。（分数：2.00）A.mAB.AC.A mD.Am-117.当各边上的权值( )时，BFS
6、 算法可用来解决单源最短路径问题。（分数：2.00）A.均相等B.均互不相等C.不一定相等D.不确定18.下面关于图的存储结构的叙述中正确的是( )。（分数：2.00）A.用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关19.在有向图 G的拓扑序列中，若顶点 v i 在顶点 v j 之前，则下列情形不可能出现的是( )。（分数：2.00）A.G中有弧v i ，v j B.G中有一条从 v i 到 v j
7、的路径C.G中没有弧v i ，v j D.G中有一条从 v j 到 v i 的路径20.以下关于图的说法中正确的是( )。 I一个有向图的邻接表和逆邻接表中的结点个数一定相等 用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（分数：2.00）A.I，B.，C.I，D.仅有21.下列关于 AOE网的叙述中，不正确的是( )。（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活
8、动提前完成，那么整个工程将会提前完成22.一个二部图的邻接矩阵 A是一个( )类型的矩阵。（分数：2.00）A.nn矩阵B.分块对称矩阵C.上三角矩阵D.下三角矩阵23.求解最短路径的 Floyd算法的时间复杂度为( )。（分数：2.00）A.O(n)B.O(n+c)C.O(n 2 )D.O(n 3 )24.下列 4组含 C1C7的结点序列中，( )是下图所示的有向图的拓扑序列。 （分数：2.00）A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C625.如果具有 n个顶
9、点的图是一个环，则它有( )棵生成树。（分数：2.00）A.n 2B.nC.n1D.126.如下图所示，在下面的 5个序列中，符合深度优先遍历的序列有( )个。aebfdc acfdeb aedfcb aefdbc aecfdb （分数：2.00）A.5B.4C.3D.227.无向图 G有 23条边，度为 4的顶点有 5个，度为 3的顶点有 4个，其余都是度为 2的顶点，则图 G最多有( )个顶点。（分数：2.00）A.11B.12C.15D.1628.对 AOE网络中有关关键路径的叙述中，正确的是( )。（分数：2.00）A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工
10、程所需的最短时间B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间29.以下关于图的叙述中，正确的是( )。（分数：2.00）A.强连通有向图的任何顶点到其他所有顶点都有弧B.图与树的区别在于图的边数大于或等于顶点数C.无向图的连通分量指无向图中的极大连通子图D.假设有图 G=V，E，顶点集 VV，EE，则 V和E构成 G的子图30.假设有 n个顶点 e条边的有向图用邻接表表示，则删除与某
11、个顶点 v相关的所有边的时间复杂度为( )。（分数：2.00）A.O(n)B.O(e)C.O(n+e)D.O(ne)31.若 G是一个具有 36条边的非连通无向图(不含自回路和多重边)，则图 G的结点数至少是( )。（分数：2.00）A.11B.10C.9D.832.已知有向图 G=(V，A)，其中 V=a，b，c，d，e，A=，。对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。（分数：2.00）A.a，d，c，b，eB.d，a，b，c，eC.a，b，d，c，eD.a，b，c，d，e33.用有向无环图描述表达式(A+B)*(A+B)A)，至少需要顶点的数目为( )。（分数：2.00）A.
12、5B.6C.8D.934.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示： （分数：2.00）A.vertex存储的是结点的数值域的内容B.firstedge域指示第一条依附于该顶点的边C.mark指向下一条依附于结点的边D.info为指向和边相关的各种信息的指针域35.以下关于十字链表的说法中，不正确的是( )。（分数：2.00）A.十字链表是有向图的另一种链式存储结构B.行指针 row为矩阵中的行位置，列指针 col为矩阵中的列位置C.数值 val为矩阵中的值D.right指针指向矩阵中的行位置，down 指针指
13、向矩阵中的列位置二、综合应用题(总题数：16，分数：32.00)36.综合应用题 41-47小题。（分数：2.00）_37.证明：具有 n个顶点和多于 n一 1条边的无向连通图 G一定不是树。（分数：2.00）_38.证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全 0的充要条件是该图为无环图。（分数：2.00）_39.关于图(Graph)的一些问题： (1)有 n个顶点的有向强连通图最多有多少条边?最少有多少条边? (2)表示有 1 000个顶点、1 000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（分数：2.00）_40.如何对有向图中的顶点号重新安排
14、可使得该图的邻接矩阵中所有的 1都集中到对角线以上?（分数：2.00）_41.假定图 G=(V，E)是有向图，V=1，2，N，N1，G 以邻接矩阵方式存储，G 的邻接矩阵为 A，即A是一个二维数组。如果 i到 j有边，则 Ai，j=1，否则 Ai，j=0。请给出一个算法思想，该算法能判断 G是否是非循环图(即 G中是否存在回路)，要求算法的时间复杂性为 O(n 2 )。（分数：2.00）_42.对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?（分数：2.00）_43.G=(V，E)是一个带有权的连通图，如图所示。 (1)什么是 G的最小生成树? (2)G 如图
15、所示，请找出 G的所有最小生成树。 （分数：2.00）_44.对于如下的加权有向图，给出算法 Dijkstra产生的最短路径的支撑树，设顶点 A为源点，并写出生成过程。 （分数：2.00）_45.(1)对于有向无环图，叙述求拓扑有序序列的步骤。(2)对于以下的图，写出它的 4个不同的拓扑有序序列。 （分数：2.00）_46.试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 V i 到顶点 V j 的路径(ij)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)（分数：2.00）_47.假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，
16、则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)（分数：2.00）_48.已有邻接表表示的有向图，请编程判断从第 u顶点至第 v顶点是否有简单路径，若有则打印出该路径上的顶点。（分数：2.00）_49.“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)（分数：2.00）_50.设计一个算法求图的中心点。设 v是有向图 G的一个顶点，把 v的偏心度定义为： MAx从 到 v的最短距离 属于 V(G) 如果 v是有向图 G中具有最小偏心度的顶点，则称顶点 v是 G的中心点。（分数：2.00）_51.对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减 1，并对其未访问的、入度为 0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2)定义在算法中使用的全局辅助数组。 (3)写出在遍历图的同时进行拓扑排序的算法。（分数：2.00）_
