ImageVerifierCode 换一换
格式:DOC , 页数:20 ,大小:333KB ,
资源ID:844558      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
注意:如需开发票,请勿充值!
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-844558.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文([考研类试卷]计算机专业基础综合历年真题试卷汇编3及答案与解析.doc)为本站会员(progressking105)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

[考研类试卷]计算机专业基础综合历年真题试卷汇编3及答案与解析.doc

1、计算机专业基础综合历年真题试卷汇编 3 及答案与解析一、单项选择题1-40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。1 若无向图 G=(V,E)中含有 7 个顶点,要保证图 G 在任何情况下都是连通的,则需要的边数最少是_。(A)6(B) 15(C) 16(D)212 下列关于图的叙述中,正确的是_。回路是简单路径存储稀疏图,用邻接矩阵比邻接表更省空间若有向图中存在拓扑序列,则该图不存在回路(A)仅(B)仅 、(C)仅 (D)仅、3 设图的邻接矩阵 A 如下所示。各顶点的度依次是 _。(A)1,2,1,2(B) 2,2,1,1(C) 3,4

2、,2,3(D)4,4,2,24 对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是_。(A)O(n)(B) O(e)(C) O(n+e)(D)O(n*e)5 若对如下无向图进行遍历,则下列选项中,不是广度优先遍历序列的是_。(A)b,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,g6 设有向图 G=(V,E),顶点集 V=V0,V 1,V 2,V 3),边集E=v 0,v 1, v0,v 2,v 0,v 3,v 1,v 3。若从顶点 V0 开始对图进行深度优

3、先遍历,则可能得到的不同遍历序列个数是_。(A)2(B) 3(C) 4(D)57 下列关于最小生成树的叙述中,正确的是_。最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同使用普里姆算法和克鲁斯卡尔(Kmskal) 算法得到的最小生成树总不相同(A)仅(B)仅 (C)仅 、(D)仅、8 求下面带权图的最小(代价)生成树时,可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是_。(A)(V 1,V 3)(B) (V1,V 4)(C) (V2,V 3)(D

4、)(V 3,V 4)9 对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各项点的最短路径,则得到的第一条最短路径的目标顶点是 b,第二条最短路径的目标顶点是 c,后续得到的其余各最短路径的目标顶点依次是_。(A)d,e, f(B) e,d,f(C) f,d,e(D)f,e,d10 对下图进行拓扑排序,可以得到不同拓扑序列的个数是_。(A)4(B) 3(C) 2(D)111 若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是_。(A)存在,且唯一(B)存在,且不唯一(C)存在,可能不唯一(D)无法确定是否存在12 对如下所示的有向图进

5、行拓扑排序,得到的拓扑序列可能是()。(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 下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中,加快其进度就可以缩短工程工期的是_。(A)c 和 e(B) d 和 c(C) f 和 d(D)f 和 h14 已知一个长度为 16 的顺序表 L,其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素,则关键字的比较次数最多的是 _。(A)4(B) 5(C) 6(D)715 下列选项中,不能构成折半查找中关键字比较

6、序列的是_。(A)500,200,450,180(B) 500,450,200,180(C) 180,500,200,450(D)180,200,500,450二、综合应用题41-47 小题,共 70 分。16 已知有 6 个顶点(顶点编号为 05)的有向带权图 G,其邻接矩阵 A 为上三角矩阵,按行为主序(行优先) 保存在如下的一维数组中。要求:1)写出图 G 的邻接矩阵 A。2)画出有向带权图 G。16 已知含有 5 个顶点的图 G 如下图所示。 请回答下列问题:17 写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。18 求 A2,矩阵 A2 中位于 0 行 3 列元素值的含义是什么

7、?19 若已知具有 n(n2)个顶点的图的邻接矩阵为 B,则 Bm(2mn)中非零元素的含义是什么?19 某网络中的路由器运行 OSPF 路由协议,表 5-1 是路由器 R1 维护的主要链路状态信息(LSI),图 5-3 是根据表 5-1 及 R1 的接口名构造出来的网络拓扑。请回答下列问题:20 本题中的网络可抽象为数据结构中的哪种逻辑结构?21 针对表 5-1 中的内容,设计合理的链式存储结构,以保存表 5-1 中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义,并画出对应表 5-1 的链式存储结构示意图(示意图中可仅以 ID 标识结点)。22 按照迪杰斯特拉(Dijkstra

8、) 算法的策略,依次给出 R1 到达图 5-3 中子网1921xx 的最短路径及费用。23 带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:设最短路径初始时仅包含初始顶点,令当前顶点 u 为初始顶点;选择离 u 最近且尚未在最短路径中的一个顶点 v,加入到最短路径中,修改当前顶点 u=v;重复步骤,直到 u 是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。23 已知有 6 个顶点(项点编号为 05)的有向带权图 G,其邻接矩阵 A

9、为上三角矩阵,按行为主序(行优先) 保存在如下的一维数组中。要求:24 写出图 G 的邻接矩阵 A。25 画出有向带权图 G。26 求图 G 的关键路径,并计算该关键路径的长度。26 一个长度为 L(L1)的升序序列 S,处在第 个位置的数称为 s 的中位数。例如,若序列 S1=(11,13,15,17,19),则 Sl 的中位数是 15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若 S2=(2,4,6,8,20),则 Sl和 S2 的中位数是 11。现有两个等长升序序列 A 和 B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列 A 和 B 的中位数。要求:27

10、 给出算法的基本设计思想。28 根据设计思想,采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。29 说明你所设计算法的时间复杂度和空间复杂度。计算机专业基础综合历年真题试卷汇编 3 答案与解析一、单项选择题1-40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 要保证无向图 G 在任何情况下都是连通的,即任意变动图 G 中的边,G 始终保持连通,首先需要 G 的任意 6 个结点构成完全连通子图 G1,需 n(n-1)2=6(6-1)2=15 条边,然后再添一条边将第 7 个结点与 G1 连接起来,

11、共需16 条边。【知识模块】 数据结构2 【正确答案】 C【试题解析】 第一个顶点和最后一个顶点相同的路径称为回路;序列中顶点不重复出现的路径称为简单路径;回路显然不是简单路径,故错误;稀疏图是边比较少的情况,此时用邻接矩阵的空间复杂度为 O(n2),必将浪费大量的空间,而邻接表的空间复杂度为 O(n+e),应该选用邻接表,故错误。存在回路的有向图不存在拓扑序列,若拓扑排序输出结束后所余下的顶点都有前驱,则说明只得到了部分顶点的拓扑有序序列,图中存在回路,故正确。【知识模块】 数据结构3 【正确答案】 C【试题解析】 邻接矩阵 A 为非对称矩阵,说明图是有向图,度为入度加出度之和。各顶点的度是

12、矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和。【知识模块】 数据结构4 【正确答案】 C【试题解析】 广度优先遍历需要借助队列实现。邻接表的结构包括:顶点表;边表(有向图为出边表) 。当采用邻接表存储方式时,在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历),故时间复杂度为 O(n),在搜索所有顶点的邻接点的过程中,每条边至少访问一次(出边表遍历),故时间复杂度为 O(e),算法总的时间复杂度为 O(n+e)。【知识模块】 数据结构5 【正确答案】 D【试题解析】 只要掌握 DFS 和 BFS 的遍历过程,便能轻易解决。逐个代入,手工模拟,选项 D 是深度优先遍历,而

13、不是广度优先遍历。【知识模块】 数据结构6 【正确答案】 D【试题解析】 画出该有向图图形如下: 采用图的深度优先遍历,共 5种可能:v 0,v 1,v 3,v 2,v 0,v 2,v 3,v 1,v 2,v 0,v 3,v 0,v 3,v 2,v 1,v 0,v 3,v 1,v 2,选 D。【知识模块】 数据结构7 【正确答案】 A【试题解析】 对于,最小生成树的树形可能不唯一(这是因为可能存在权值相同的边),但是代价一定是唯一的,正确。对于,如果权值最小的边有多条并且构成环状,则总有权值最小的边将不出现在某棵最小生成树中,错误。对于,设 N 个结点构成环,N-1 条边权值相等,则从不同的顶

14、点开始普里姆算法会得到 N-1 中不同的最小生成树,错误。对于 N,当最小生成树唯一时(各边的权值不同),普里姆算法和克鲁斯卡尔算法得到的最小生成树相同,错误。【知识模块】 数据结构8 【正确答案】 C【试题解析】 从 V4 开始,Kruskal 算法选中的第一条边一定是权值最小的(V1,V 4),B 错误。由于 V1 和 V4 已经可达,第二条边含有 V1 和 V4 的权值为 8 的一定符合 Prim 算法,排除 A、D。【知识模块】 数据结构9 【正确答案】 C【试题解析】 从 a 到各顶点的最短路径的求解过程:后续目标顶点依次为 f,d,e。【知识模块】 数据结构10 【正确答案】 B【

15、试题解析】 拓扑排序的过程如下图所示。可以得到 3 个不同的拓扑序列,分别为:abced、abecd、aebcd。【知识模块】 数据结构11 【正确答案】 C【试题解析】 对角线以下元素均为零,表明只有顶点 i 到顶点 j(ij)可能有边,而顶点 j 到顶点 i 一定没有边,即有向图是一个无环图,因此一定存在拓扑序列。对于拓扑序列是否唯一,试举一例:设有向图的邻接矩阵 ,则存在两个拓扑序列,因此该图存在可能不唯一的拓扑序列。结论:对于任一有向图,如果它的邻接矩阵中对角线以下(或以上)的元素均为零,则存在拓扑序列(可能不唯一)。反正,若图存在拓扑序列,却不一定能满足邻接矩阵中主对角线以下的元素均

16、为零,但是可以通过适当地调整结点编号,使其邻接矩阵满足前述性质。【知识模块】 数据结构12 【正确答案】 D【试题解析】 按照拓扑排序的算法,每次都选择入度为 0 的结点从图中删去,此图中一开始只有结点 3 的入度为 0;删掉结点 3 后,只有结点 1 的入度为 0;删掉结点 1 后,只有结点 4 的入度为 0;删掉结点 4 后,结点 2 和结点 6 的入度都为0,此时选择删去不同的结点,会得出不同的拓扑序列,分别处理完毕后可知可能的拓扑序列为 3,1,4,2,6,5 和 3,1,4,6,2,5,选 D。【知识模块】 数据结构13 【正确答案】 C【试题解析】 找出 AOE 网的全部关键路径为

17、(b、d 、c 、g)、(b 、d、e、h)和(b、f、h)。根据定义,只有关键路径上的活动时间同时减少时,才能缩短工期,即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条:(b、d、c、g)、(b、d、e、h)和(b 、f、h)。由此可知,选项 A 和 B 中并不能包含(b、f、h)这条路径,选项 c 中,并不能包含(b、d、c 、g)和(b、d 、e、h)这两条路径,只有 C 包含了所有的关键路径,因此只有加快 f 和 d 的进度才能缩短工期。【知识模块】 数据结构14 【正确答案】 B【试题解析】 折半查找法在查找成功时进行的关键字比较次数最多

18、为 log2n+1,即判定树的高度;折半查找法在查找不成功时进行的关键字比较次数最多为log2n+1。题中 n=16,因此最多比较 log216+1=5 次。也可以画出草图求解。【知识模块】 数据结构15 【正确答案】 A【试题解析】 画出查找路径图,因为折半查找的判定树是一棵二叉排序树,看其是否满足二叉排序树的要求。很显然,选项 A的查找路径不满足。【知识模块】 数据结构二、综合应用题41-47 小题,共 70 分。16 【正确答案】 1)由题得图 G 的邻接矩阵 A 如下图所示。2)根据上面的邻接矩阵,画出有向带权图 G,如下图所示。【知识模块】 数据结构【知识模块】 数据结构17 【正确

19、答案】 图 G 的邻接矩阵 A 如下:【试题解析】 考查图的邻接矩阵的性质。【知识模块】 数据结构18 【正确答案】 A 2 如下: 0 行 3 列的元素值 3 表示从顶点 0 到顶点3 之间长度为 2 的路径共有 3 条。【知识模块】 数据结构19 【正确答案】 B m(2mn)中位于 i 行 j 列(0i, jn-1)的非零元素的含义是:图中从顶点 i 到顶点 j 长度为 m 的路径条数。【知识模块】 数据结构【知识模块】 数据结构20 【正确答案】 图题中给出的是一个简单的网络拓扑图,可以抽象为无向图。【知识模块】 数据结构21 【正确答案】 链式存储结构的如下图所示。其数据类型定义如下

20、:typedef structunsigned int ID,IP,LinkNode;Link 的结构 typedef structunsigned int Prefix,Mask ;NetNode ;Net 的结构 typedef struct Nodeint Flag;Flag=l为 Link;Flag=2 为 NetunionLinkNode Lnode;NetNode NnodeLinkORNet;Unsigned int Metric;struct Node *next,ArcNode;弧结点typedef struct HNodeunsigned int RouterID;对应表

21、5-1 的链式存储结构示意图如下。【知识模块】 数据结构22 【正确答案】 计算结果如下表所示。【试题解析】 考查在具体模型中数据结构的应用。该题本身并没有涉及太多的网络知识点,只是应用了网络的模型,实际上考查的还是数据结构的内容。【知识模块】 数据结构23 【正确答案】 该方法不一定能(或不能)求得最短路径。举例说明:图(a)中,设初始顶点为 1,目标顶点为 4,欲求从顶点 1 到顶点 4 之间的最短路径,显然这两点之间的最短路径长度为 2。利用给定方法求得的路径长度为 3,但这条路径并不是这两点之间的最短路径。图(1)中,设初始顶点为 1,目标顶点为 3,欲求从顶点l 到顶点 3 之间的最

22、短路径。利用给定的方法,无法求出顶点 1 到顶点 3 的路径。【知识模块】 数据结构【知识模块】 数据结构24 【正确答案】 由数组得图 G 的邻接矩阵 A 如下图所示。【知识模块】 数据结构25 【正确答案】 根据上面的邻接矩阵,画出有向带权图 G,如下图所示。【知识模块】 数据结构26 【正确答案】 按照算法,先计算各个事件的最早发生时间,计算过程如下:ve(0)=0;ve(1)=ve(0)+a 01 =4;ve(2)=maxve(0)+a 01 ,ve(1)+a 12 =max(6,4+5)=9;ve(3)=ve(2)+a 23 =9+4=13;ve(4)=ve(2)+a 24 =9+3

23、=12;ve(5)=maxve(3)+a35 ,ve(4)+a 45 =max(16,15:)=16 ;接下来求各个时间的最迟发生时间,计算过程如下:vl(5)=ve(5)=16;vl(4)=vl(5)-a 45 =16-3=13;vl(3)=vl(5)-a 35 =16-3=13; vl(2)=minvl(3)-a23 ,vl(4)-a 24 =min(9,10)=9;vl(1)=vl(2)-a 12 =4;v1(0)=minvl(2)-a02 ,Vl(1)-a 01 =min(3,0);即 ve()和 vl()数组如下表所示:接下来计算所有活动的最早和最迟发生时间 e()和 l():e(a

24、 01 )=e(a02 )=ve(0)=0;e(a 12 )ve(1)=4;e(a 23 )=e(a24 )=ve(2)=9;e(a 35 )-ve(3)=13;e(a 45 )=ve(4)=12;l(a 45 )=vl(5)-a45 =16-3=13; l(a35 )=vl(5)-a35 =16-3=13;l(a 24 )=vl(4)a24 =13-3=10;l(a 23 )-vl(3)-a=23 13-4=9;l(a 12 )=vl(2)-a12 =9-5=4:l(a 02 )=vl(2)-a02 =9-6=3;l(a 01 )=vl(1)-a01 =4-4=0; e()和 l()数组与它

25、们的差值如下表所示:满足 l()-e()=0 的路径就是关键路径,所以关键路径为 a0-1 、a 1-2 、a 2-3 、a 3-5 ,如下图所示(粗线表示) 。【知识模块】 数据结构【知识模块】 数据结构27 【正确答案】 求两个序列 A 和 B 的中位数最简单的办法就是将两个升序序列进行归并排序,然后求其中位数。这种解法虽可求解,但在时间和空间两方面都不大符合高效的要求,但也能获得部分分值。根据题目分析,分别求两个升序序列 A 和 B 的中位数,设为 a 和 b。若 a=b,则 a 或 b 即为所求的中位数。原因:容易验证,如果将两个序列归并排序,则最终序列中,排在子序列 ab 前边的元素

26、为先前两个序列中排在 a 和 b 前边的元素;排在子序列 ab 后边的元素为先前两个序列中排在 a 和 b 后边的元素。所以子序列 ab 一定位于最终序列的中间,又因为 a=b,显然 a 就是中位数。否则(假设 ab) ,中位数只能出现(a,b)范围内。原因:同样可以用归并排序后的序列来验证,归并排序后必然有形如ab的序列出现,中位数必出现在(a,b) 之间。因此可以做如下处理:舍弃 a 所在序列 A 的较小一半,同时舍弃 b 所在序列 B 的较大一半。在保留两个升序序列中求出新的中位数 a 和 b,重复上述过程,直到两个序列中,只含一个元素时为止,则较小者即为所求的中位数。每次总的元素个数变

27、为原来的一半。算法的基本设计思想如下。分别求出序列 A 和 B 的中位数,设为 a 和 b,求序列 A 和 B 的中位数过程如下:若 a=b,则 a 或 b 即为所求中位数,算法结束。若 ab,则舍弃序列 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求舍弃的长度相等。若 ab,则舍弃序列 A 中较大的一半,同时舍弃序列 B 中较小的一半,要求舍弃的长度相等。在保留的两个升序序列中,重复过程、 、,直到两个序列中只含一个元素时为止,较小者即为所求的中位数。【知识模块】 数据结构28 【正确答案】 算法的实现如下:int M Search(int A,intB,int n)int s1=0

28、,d1=n-1 ,m1,s2=1,d2=n-1,m2,分别表示序列 A 和 B 的首位数、末位数和中位数while(s1!=d1s2 !=d2)(m1=(S1+d1)2,m2=(s2+d2)2;if(Am1;=Bm2)return Am1,满足条件 1)if(Am1Bm2)满足条件 2)if(s1+d1)2=0)若元素个数为奇数s1=m1;舍弃 A 中间点以前的部分,且保留中间点d2=m2;舍弃 B 中间点以后的部分,且保留巾间点else f元素个数为偶数s1=m1+1;舍弃 A 中间点及中间点以前部分d2=m2;舍弃 B 中间点以后部分且保留中间点elsef满足条件 3)if(sl+d1)2=0)若元素个数为奇数d1=m1,舍弃 A 中间点以后的部分,且保留中间点s2=m2;舍弃 B 中间点以前的部分,且保留中间点else元素个数为偶数d1=m1;舍弃 A 中问点以后部分,且保留中间点s2=m2+1;舍弃 B 中间点及中间点以前部分return As1 Bs2?As1:Bs2,【知识模块】 数据结构29 【正确答案】 算法的时间复杂度为 O(log2n),空间复杂度为 O(1)。【试题解析】 综合考查了顺序表的折半查找和归并的思想。【知识模块】 数据结构

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1