计算机专业基础综合数据结构历年真题试卷汇编1

《计算机专业基础综合数据结构历年真题试卷汇编1》由会员分享，可在线阅读，更多相关《计算机专业基础综合数据结构历年真题试卷汇编1（5页珍藏版）》请在装配图网上搜索。

1、计算机专业基础综合数据结构（图）历年真题试卷汇编 1（总分：60.00，做题时间：90 分钟）、 单项选择题（ 总题数：20 ，分数：40.00）1下列关于无向连通图特性的叙述中，正确的是（）。【2009年全国试题7（2分）】I所有顶点的度之和 为偶数II.边数大于顶点个数减1III至少有一个顶点的度为1（分数：2.00）A. 只有I丿B. 只有IIC. I 和 IID. I 和III解析：解析：无向图中一条边要连接两个顶点，因此顶点的度数之和必为偶数。n个顶点的无向连通图至 少需要n-1条边。无向连通图并不要求“至少有一个顶点的度为1”。2. 若无向图G=（V,E）中含有7个顶点，要保证图G

2、在任何情况下都是连通的，则需要的边数最少是（）。【2010 年全国试题7（2分）】（分数： 2.00）A. 6B. 15C. 16 丿D. 21解析：解析：要保证n个顶点的无向图G在任何情况下都是连通的，则需要先由n-1个顶点组成完全图， 从第n个顶点引一条到n-1任一顶点的边，则图肯定是连通的。本题先由6个顶点组成完全图，需要6（6-1） /2=15条边，故按题目要求“需要的边数最少”是15+1=16。3. 对下图进行拓扑排序，可以得到不同拓扑序列的个数是（ ）。【2010年全国试题8（2分）】（分数： 2.00）A. 4B. 3 丿C. 2D. 1解析：4下列关于图的叙述中，正确的是（）。

3、【2011年全国试题8（2分）】I回路是简单路径II.存储稀疏图， 用邻接矩阵比邻接表更省空间III若有向图中存在拓扑序列，则该图不存在回路（分数： 2.00）A. 仅 IIB. 仅 I、IC. 仅III丿D. 仅 I、I 解析：解析：图中第1个顶点和最后一个顶点相同的路径称为回路或环。序列中所有顶点不重复出现的路 径称为简单路径，邻接矩阵的大小只和顶点个数相关，存储稀疏图，用邻接表比邻接矩阵更省空间。拓扑 序列成功的前提是有向图中不存在回路。5对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。【2012 年全国试题5（2分）】（分数： 2.00）A. O（

4、n）B. O（e）C. 0（n+e）丿D. O（nXe）解析：6. 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。【2012 年全国试题6（2 分）】（分数：2.00）A. 存在，且唯一B. 存在，且不唯一C. 存在，可能不唯一丿D. 无法确定是否存在 解析：7. 对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点口到其他各顶点的最短路径，则得到的 第一条最短路径的目标顶点是6，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。K2012年全国试题7（2分）】分数：2.00）A. d， e， fB. e， d

5、,fC. f,d,e 丿D. f,e， d解析：8下列关于最小生成树的叙述中，正确的是（）。【2012年全国试题8（2分）】I最小生成树的代价唯一 II 所有权值最小的边一定会出现在所有的最小生成树中III使用普里姆（Prim）算法从不同顶点开始得到 的最小生成树一定相同IV.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同 （分数：2.00）A. 仅I丿B. 仅 IIC. 仅 I、ID. 仅 II、IV解析：解析：若有较小的相等权值，最小生成树可能不唯一，但是其代价是唯一的。II的错误在于“所有 权值最小的边一定会出现在”，这可能形成环。III的错误在于“最小生成树一

6、定相同”，IV的错 误在于两种算法“最小生成树总不相同”。若无相同权值，生成树一定相同；若有较小相等权值，生A.1 ，2，1，2B.2，2，1，1C.3，4，2，3VD.4，4，2，2解析：解析：有向图的邻接矩阵中，第i行非零元素个数是第i个顶点的出度，第i列非零元素个数是第 i个顶点的入度，第i个顶点的度是其出度和入度之和。10.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）。【2013年全国试题8（2分）】A. h， c， a， b， d,e， g,fB. e， a,f,g， b， h， c， dC. d,b， c， a， h， e， f,gD. a， b， c， d，

7、 h， e,f,g V 解析：11.下面 AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（ ）。2013 年全国试题9（2分）】 （分数：2.00）A. c 和 eB. d 和 cC. f和d 丿D. f 和 hA.3，1，2，4，5，6B.3，1，2，4，6，5C.3，1，4，2，5，6D.3，1，4，2，6，5 V解析：13设有向图 G=（V,E）,顶点集 V=V , V , V , V ，边集庐 0, V，0, V，0, v，1, v ,01231233若从顶点 V 开始对图进行深度优先遍历，则可能得到的

8、不同遍历序列个数是（ ） 。 【2015年全国试题 5（2 0分）】（分数：2.00）A. 2B. 3C. 4D. 5 丿解析：解析：不同的遍历序列（只列出下标）是：0321， 0312， 0132， 0231， 0213。14.求下面带权图的最小（代价）生成树时，可能是克鲁斯卡尔（Kruskal）算法第二次选中但不是普里姆（Prim）A. （V， V ）13B. （V， V ）14C. （V，V ）丿23D. （V， V ）34解析：解析：Kruskal算法是按权值升序选择边的，首先选权值为5的边（V1，V4），接着选择权值为8的 边，这时有3种选择：（V1, V3）、（V3, V4）和（V

9、2, V3）。Prim从V4开始，首先选择权值为5的边（V1，V4）， 接着可以选择（V1, V3）或（V3, V3），不可能选择（V2, V3）。15. 以下图的叙述中，正确的是（ ）。【华南理工大学2006一、 1（2 分）】（分数： 2.00）A. 图与树的区别在于图的边数大于或等于顶点数B. 假设有图G=（V,E），顶点集VWV,EWE,则V和E构成G的子图C. 无向图的连通分量指无向图中的极大连通子图 丿D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点解析：解析：树是一对多的关系，图是多对多的关系，所以A错。若E中两个顶点不在V中，则V和F 无法构成图，所以B错。D没强调对图的各

10、顶点遍历一次且仅一次。16. 图中有关路径的定义是（ ）。【北方交通大学2001 一、 24（2 分）】（分数： 2.00）A. 由顶点和相邻顶点序偶构成的边所形成的序列丿B. 由不同顶点所形成的序列C. 由不同边所形成的序列D. 上述定义都不是解析：17. 设无向图的顶点个数为n,则该图最多有（）条边。【清华大学1998 、5（分）】 （分数：2.00）A. n 一 1B. n（n-l） / 2 丿C. n（n+1）2D. 0E. n 2解析：18. 具有n个顶点的有向完全图有（）条边。【湖南大学2008】 （分数：2.00）A. n（n 一 1） / 2B. n（n 一 1）丿C. n（n

11、+1）/ 2D. n（n+1）解析：19. 一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学1999四、4（4分）】 （分数：2.00）A. g 1丿B. nC. n+1D. nlogn解析：20. 要连通具有n个顶点的有向图，至少需要（）条边。【北京航空航天大学2000 一、6（2分）】 （分数：2.00）A. n-1B. n 丿C. n+1D. 2n解析：解析：强连通图是指在有向图中，对于每一对不同的顶点v , V , V MV ,都存在从V 到i j i j iV 及v /到v 的路径。n个顶点用弧向同一方向连接形成一个环时，就是强连通图，需要弧最少。j j i二、 判断题（总

12、题数：10，分数：20.00）21. n个结点的无向图，若不允许结点到自身的边，也不允许结点到结点的多重边，且边的总数为n（n1） /2，则该无向图一定是连通图。 （ ）【中南大学2003一、 18（1分）】（分数： 2.00）A. 正确丿B. 错误解析：22在n个结点的无向图中，若边数n1，则该图必是连通图。（）【中国海洋大学2006二、10（1分）】 （分数： 2.00）A. 正确B. 错误丿解析：23. n个结点的有向图，若它有n（n 一 1）条边，则它一定是强连通的。（）【吉林大学2006 一、7（1分）】 （分数： 2.00）A. 正确丿B. 错误解析：24. 强连通图的各顶点间均可

13、达。（ ）【北京邮电大学 2000 一、3（1 分）】 （分数：2.00）A. 正确丿B. 错误 解析：25. 强连通分量是无向图的极大强连通子图。（ ）【北京邮电大学2002 一、7（1分）】 （分数：2.00）A. 正确B. 错误丿 解析：解析：连通分量和连通图是无向图所具有的，凡带“强”字的都是有向图，例如，强连通分量、强 连通图。26. 若有向图有n个顶点，则其强连通分量最多有，z个。（）【北京邮电大学2006二、7（1分）】 （分数：2.00）A. 正确丿B. 错误解析：解析：当有向图没有弧（边）时，n个顶点的有向图有最多的n个强连通分量。27. 无向图中任何一个边数最少且连通所有顶

14、点的子图都是该图无向图的生成树。 （ ）【武汉大学2004】 （分数： 2.00）A. 正确丿B. 错误解析：28有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）【合肥工业大学2001二、7（1分）】 （分数： 2.00）A. 正确B. 错误丿解析：解析：有向图中顶点V的度等于V的出度和入度之和，出度是其邻接矩阵中第V行中的1的个数， 而入度是其邻接矩阵中第V列中的1的个数。29图g的顶点v的入度等于其邻接矩阵中第1,列中的1的个数。（）【北京邮电大学2006二、7（1分）】 （分数： 2.00）A. 正确丿B. 错误 解析：30.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 （）【东南大学2001 一、 4（1 分）】【中 山大学1994一、 3（2分）】（分数： 2.00）A. 正确B. 错误丿解析：