[考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编2及答案与解析.doc
《[考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编2及答案与解析.doc》由会员分享,可在线阅读,更多相关《[考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编2及答案与解析.doc(14页珍藏版)》请在麦多课文档分享上搜索。
1、计算机专业基础综合数据结构(图)历年真题试卷汇编 2 及答案与解析一、单项选择题1 下列关于无向连通图特性的叙述中,正确的是( )。【2009 年全国试题 7(2 分)】I所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1(A)只有 I(B)只有 (C) I 和(D)I 和2 若无向图 G=(V,E)中含有 7 个顶点,要保证图 G 在任何情况下都是连通的,则需要的边数最少是( ) 。【2010 年全国试题 7(2 分)】(A)6(B) 15(C) 16(D)213 对下图进行拓扑排序,可以得到不同拓扑序列的个数是( )。【2010 年全国试题8(2 分)】(A)4(B) 3
2、(C) 2(D)14 下列关于图的叙述中,正确的是( )。【2011 年全国试题 8(2 分)】I回路是简单路径存储稀疏图,用邻接矩阵比邻接表更省空间若有向图中存在拓扑序列,则该图不存在回路(A)仅(B)仅 I、(C)仅 (D)仅 I、5 对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是( ) 。【2012 年全国试题 5(2 分) 】(A)O(n)(B) O(e)(C) O(n+e)(D)O(ne)6 若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是( ) 。【2012 年全国试题 6(2 分) 】(A)存在,且唯一(B
3、)存在,且不唯一(C)存在,可能不唯一(D)无法确定是否存在7 对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点口到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是 6,第二条最短路径的目标顶点是 c,后续得到的其余各最短路径的目标顶点依次是( )。K2012 年全国试题 7(2 分)】(A)d,e, f(B) e,d,f(C) f,d,e(D)f,e,d8 下列关于最小生成树的叙述中,正确的是( )。【2012 年全国试题 8(2 分)】I最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相
4、同使用普里姆算法和克鲁斯卡尔(Kruskal) 算法得到的最小生成树总不相同(A)仅 I(B)仅 (C)仅 I、(D)仅、9 设图的邻接矩阵 A 如下所示。各顶点的度依次是 ( )。【2013 年全国试题 7(2 分)】(A)1,2,1,2(B) 2,2,1,1(C) 3,4,2,3 (D)4,4,2,210 若对如下无向图进行遍历,则下列选项中,不是广度优先遍历序列的是( )。【2013 年全国试题 8(2 分)】(A)h,c, a,b,d,e,g,f(B) e,a,f,g,b,h,c,d(C) d,b,c,a ,h,e ,f,g(D)a,b, c,d,h,e,f,g11 下面AOE 网表示
5、一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中,加快其进度就可以缩短工程工期的是( )。2013 年全国试题 9(2 分) 】(A)c 和 e(B) d 和 c(C) f 和 d (D)f 和 h12 对如下所示的有向图进行拓扑排序,得到的拓扑序列可能是( )。【2014 年全国试题 7(2 分) 】(A)3,1,2,4,5,6(B) 3,1,2,4,6,5(C) 3,1,4,2,5,6(D)3,1,4,2,6,513 设有向图 G=(V,E),顶点集 V=V0,V 1,V 2,V 3,边集庐0,v 1, 0,v 2, 0,v 3, 1,v 3,若从顶
6、点 V0 开始对图进行深度优先遍历,则可能得到的不同遍历序列个数是( )。【2015 年全国试题 5(2 分)】(A)2(B) 3(C) 4(D)514 求下面带权图的最小(代价)生成树时,可能是克鲁斯卡尔(Kruskal)算法第二次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是( )。【2015 年全国试题6(2 分)】(A)(V 1,V 3)(B) (V1,V 4)(C) (V2,V 3)(D)(V 3,V 4)15 以下图的叙述中,正确的是( )。【华南理工大学 2006 一、1(2 分)】(A)图与树的区别在于图的边数大于或等于顶点数(B)假设有图 G=(V,E
7、),顶点集 VV,EE ,则 V 和E构成 G 的子图(C)无向图的连通分量指无向图中的极大连通子图(D)图的遍历就是从图中某一顶点出发访遍图中其余顶点16 图中有关路径的定义是( )。【北方交通大学 2001 一、24(2 分)】(A)由顶点和相邻顶点序偶构成的边所形成的序列(B)由不同顶点所形成的序列(C)由不同边所形成的序列(D)上述定义都不是17 设无向图的顶点个数为 n,则该图最多有( )条边。【清华大学 1998 一、5(分)】(A)n 一 1(B) n(n-1) 2(C) n(n+1)2(D)0(E)n 218 具有 n 个顶点的有向完全图有( )条边。【湖南大学 2008】(A
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考研 试卷 计算机专业 基础 综合 数据结构 历年 汇编 答案 解析 DOC
