[考研类试卷]计算机专业基础综合(图)模拟试卷2及答案与解析.doc
《[考研类试卷]计算机专业基础综合(图)模拟试卷2及答案与解析.doc》由会员分享,可在线阅读,更多相关《[考研类试卷]计算机专业基础综合(图)模拟试卷2及答案与解析.doc(19页珍藏版)》请在麦多课文档分享上搜索。
1、计算机专业基础综合(图)模拟试卷 2 及答案与解析一、单项选择题1-40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。1 在有向图 G 的拓扑序列中,若顶点 vi 在顶点 vj 之前,则下列情形不可能出现的是( )。(A)G 中有弧 i,v h(B) G 中有一条从 vi 到 vj 的路径(C) G 中没有弧 i,v j(D)G 中有一条从 vj 到 vi 的路径2 以下关于图的说法中正确的是( )。一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关无向图的邻接矩阵一定是
2、对称的,有向图的邻接矩阵一定是不对称的(A),(B) ,(C) ,(D)仅有3 下列关于 AOE 网的叙述中,不正确的是( )。(A)关键活动不按期完成就会影响整个工程的完成时间(B)任何一个关键活动提前完成,那么整个工程将会提前完成(C)所有的关键活动提前完成,那么整个工程将会提前完成(D)某些关键活动提前完成,那么整个工程将会提前完成4 一个二部图的邻接矩阵 A 是一个( )类型的矩阵。(A)rtxn 矩阵(B)分块对称矩阵(C)上三角矩阵(D)下三角矩阵5 求解最短路径的 Floyd 算法的时间复杂度为( )。(A)O(n)(B) O(n+C)(C) O(n2)(D)O(n 3)6 下列
3、 4 组含 C1C7 的结点序列中,( )是下图所示的有向图的拓扑序列。(A)Cl,C2,C6,C7, C5,C4,C3(B) C1,C2,C6,C3, C4,C5,C7(C) C1,C4,C2,C3, C5,C6,C7(D)C5,C7 ,C4,C1,C2,C3,C67 如果具有 n 个顶点的图是一个环,则它有( )棵生成树。(A)n 2(B) n(C) n 一 1(D)18 如下图所示,在下面的 5 个序列中,符合深度优先遍历的序列有( )个。aebfdc acfdebaedfcb aefdbc aecfdb(A)5(B) 4(C) 3(D)29 无向图 G 有 23 条边,度为 4 的顶点
4、有 5 个,度为 3 的顶点有 4 个,其余都是度为 2 的顶点,则图 G 最多有( )个顶点。(A)11(B) 12(C) 15(D)1610 对 AOE 网络中有关关键路径的叙述中,正确的是( )。(A)从开始顶点到完成顶点的具有最大长度的路径,关键路径长度是完成整个工程所需的最短时间(B)从开始顶点到完成顶点的具有最小长度的路径,关键路径长度是完成整个工程所需的最短时间(C)从开始顶点到完成顶点的具有最大长度的路径,关键路径长度是完成整个工程所需的最长时间(D)从开始顶点到完成顶点的具有最小长度的路径,关键路径长度是完成整个工程所需的最长时间11 以下关于图的叙述中,正确的是( )。(A
5、)强连通有向图的任何顶点到其他所有顶点都有弧(B)图与树的区别在于图的边数大于或等于顶点数(C)无向图的连通分量指无向图中的极大连通子图(D)假设有图 G=V,E,顶点集 VV,EE,则 V 和E构成 G 的子图12 假设有 n 个顶点 e 条边的有向图用邻接表表示,则删除与某个顶点 v 相关的所有边的时间复杂度为( ) 。(A)O(n)(B) O(e)(C) O(n+e)(D)O(ne)13 若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边),则图 G 的结点数至少是( ) 。(A)11(B) 10(C) 9(D)814 已知有向图 G=(V,A),其中 V=a,b,c,d,
6、e,A=, , 。对该图进行拓扑排序,下面序列中不是拓扑排序的是( )。(A)a,d, c,b,e(B) d,a,b,c ,e(C) a,b,d,c ,e(D)a,b, c,d,e15 用有向无环图描述表达式(A+B)*(A+B) A),至少需要顶点的数目为( )。(A)5(B) 6(C) 8(D)916 邻接多重表的存储结构和十字链表类似,也是由顶点表和边表组成,每一条边用一个结点表示,其顶点表结点结构和边表结点结构如下图所示:关于图中各个域的说明,不正确的是( )。(A)vertex 存储的是结点的数值域的内容(B) firstedge 域指示第一条依附于该顶点的边(C) mark 指向下
7、一条依附于结点的边(D)info 为指向和边相关的各种信息的指针域17 以下关于十字链表的说法中,不正确的是( )。(A)十字链表是有向图的另一种链式存储结构(B)行指针 row 为矩阵中的行位置,列指针 col 为矩阵中的列位置(C)数值 val 为矩阵中的值(D)right 指针指向矩阵中的行位置,down 指针指向矩阵中的列位置_二、综合应用题41-47 小题,共 70 分。18 对于如下的加权有向图,给出算法 Dijkstra 产生的最短路径的支撑树,设顶点A 为源点,并写出生成过程。19 对于有向无环图,叙述求拓扑有序序列的步骤。20 对于以下的图,写出它的 4 个不同的拓扑有序序列
8、。21 试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径(ij) 。( 注意:算法中涉及的图的基本操作必须在存储结构上实现。)22 假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注意:图中不存在顶点到自己的弧)23 已有邻接表表示的有向图,请编程判断从第 u 顶点至第 v 顶点是否有简单路径,若有则打印出该路径上的顶点。24 “破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“ 破圈法 ”求解给定的带权连通无向图的一棵最小代价
9、生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)25 设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点,把 v 的偏心度定义为:MAX从 w 到 v 的最短距离 w 属于 V(G)如果 v 是有向图 G 中具有最小偏心度的顶点,则称顶点 v 是 G 的中心点。25 对于一个使用邻接表存储的有向图 G,可以利用深度优先遍历方法,对该图中结点进行拓扑排序。其基本思想是:在遍历过程中,每访问一个顶点,就将其邻接到的顶点的入度减 1,并对其未访问的、入度为 0 的邻接到的顶点进行递归。26 给出完成上述功能的图的邻接表定义。27 定义在算法中使用的全局辅助数组。28 写出在
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考研 试卷 计算机专业 基础 综合 模拟 答案 解析 DOC
