《计算机专业基础综合历年真题试卷汇编2.pdf》由会员分享，可在线阅读，更多相关《计算机专业基础综合历年真题试卷汇编2.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！计算机专业基础综合历年真题试卷汇编 2(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_ 解析：2.若无向图 G=(V，E)中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是_。（分数：2.00）A.6 B.15 C.16 D.21 解析：解析：要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，
2、首先需要 G 的任意 6 个结点构成完全连通子图 G1，需 n(n-1)2=6(6-1)2=15 条边，然后再添一条边将第 7个结点与 G1 连接起来，共需 16 条边。3.下列关于图的叙述中，正确的是_。回路是简单路径存储稀疏图，用邻接矩阵比邻接表更省空间若有向图中存在拓扑序列，则该图不存在回路 （分数：2.00）A.仅 B.仅、C.仅 D.仅、解析：解析：第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为 O(n 2)，必将浪费大量的空间，而邻接表的空间复杂度为 O(n+e)
3、，应该选用邻接表，故错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故正确。4.设图的邻接矩阵A 如下所示。各顶点的度依次是_。（分数：2.00）A.1，2，1，2 B.2，2，1，1 C.3，4，2，3 D.4，4，2，2 解析：解析：邻接矩阵 A 为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行(对应出度)和列(对应入度)的非零元素之和。5.对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是 _。（分数：2.00）A.O(n)B.O(e)
4、C.O(n+e)D.O(n*e)解析：解析：广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表(有向图为出边表)。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历)，故时间复杂度为 O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次(出边表遍历)，故时间复杂度为 O(e)，算法总的时间复杂度为O(n+e)。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！6.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是 _。（分数：2.00）A.b，c，a，b，d，e，g，f B.e，a，f，g，
5、b，h，c，d C.d，b，c，a，h，e，f，g D.a，b，c，d，h，e，f，g 解析：解析：只要掌握 DFS和 BFS的遍历过程，便能轻易解决。逐个代入，手工模拟，选项 D 是深度优先遍历，而不是广度优先遍历。7.设有向图 G=(V，E)，顶点集 V=V 0，V 1，V 2，V 3)，边集 E=v 0，v 1，v 0，v 2，v 0，v 3，v 1，v 3 。若从顶点 V 0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是_。（分数：2.00）A.2 B.3 C.4 D.5 解析：解析：画出该有向图图形如下：采用图的深度优先遍历，共5 种可能：v 0，v 1，v 3，v 2，
6、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。8.下列关于最小生成树的叙述中，正确的是_。最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同（分数：2.00）A.仅 B.仅 C.仅、D.仅、解析：解析：对于，最小生成树的树形可能不唯一(这是因为可能存在权值相同的边)，但是代价一定是唯一的，正确。对于，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某
7、棵最小生成树中，错误。对于，设N 个结点构成环，N-1条边权值相等，则从不同的顶点开始普里姆算法会得到 N-1中不同的最小生成树，错误。对于 N，当最小生成树唯一时(各边的权值不同)，普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，错误。9.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是_。（分数：2.00）A.(V 1，V 3)B.(V 1，V 4)C.(V 2，V 3)D.(V 3，V 4)解析：解析：从 V 4 开始，Kruskal算法选中的第一条边一定是权值最小的(V 1，V 4)
8、，B 错误。由于 V 1 和 V 4 已经可达，第二条边含有 V 1 和 V 4 的权值为 8 的一定符合 Prim算法，排除 A、D。10.对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各项点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是_。（分数：2.00）欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！A.d，e，f B.e，d，f C.f，d，e D.f，e，d 解析：解析：从 a 到各顶点的最短路径的求解过程：后续目标顶点依次为
9、f，d，e。11.对下图进行拓扑排序，可以得到不同拓扑序列的个数是_。（分数：2.00）A.4 B.3 C.2 D.1 解析：解析：拓扑排序的过程如下图所示。可以得到 3 个不同的拓扑序列，分别为：abced、abecd、aebcd。12.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是_。（分数：2.00）A.存在，且唯一 B.存在，且不唯一 C.存在，可能不唯一 D.无法确定是否存在 解析：解析：对角线以下元素均为零，表明只有顶点i 到顶点 j(ij)可能有边，而顶点 j 到顶点 i 一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否
10、唯一，试举一例：设有向图的邻接矩阵，则存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。结论：对于任一有向图，如果它的邻接矩阵中对角线以下(或以上)的元素均为零，则存在拓扑序列(可能不唯一)。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。13.对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是()。（分数：2.00）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，5 解析：解析：按照拓扑排序的算法，每次都选择入度为0 的结点从图中删去，此图中一开
11、始只有结点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。14.下列 AOE网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是_。（分数：2.00）A.c和 e B.d和 c C.f和 d D.f和 h 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系
12、删除！我们将竭诚为您提供优质的文档！解析：解析：找出 AOE网的全部关键路径为(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 的进度才能缩短工期。15.已知一个长度为 16 的顺序表
13、L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多的是_。（分数：2.00）A.4 B.5 C.6 D.7 解析：解析：折半查找法在查找成功时进行的关键字比较次数最多为 log 2 n +1，即判定树的高度；折半查找法在查找不成功时进行的关键字比较次数最多为 log 2 n+1。题中 n=16，因此最多比较 log 2 16+1=5次。也可以画出草图求解。16.下列选项中，不能构成折半查找中关键字比较序列的是_。（分数：2.00）A.500，200，450，180 B.500，450，200，180 C.180，500，200，450 D.180，
14、200，500，450 解析：解析：画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。很显然，选项 A 的查找路径不满足。二、综合应用题(总题数：7，分数：28.00)17.综合应用题 41-47小题。_ 解析：18.已知有 6 个顶点(顶点编号为 0 5)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：1)写出图 G 的邻接矩阵 A。2)画出有向带权图G。（分数：2.00）_ 正确答案：(正确答案：1)由题得图 G 的邻接矩阵 A 如下图所示。2)根据上面的邻接矩阵，画出有向带权图 G，如下图所示。)解析：已
15、知含有 5 个顶点的图 G 如下图所示。请回答下列问题：（分数：6.00）(1).写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。（分数：2.00）_ 正确答案：(正确答案：图 G 的邻接矩阵 A 如下：)解析：解析：考查图的邻接矩阵的性质。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！(2).求 A 2，矩阵 A 2 中位于 0 行 3 列元素值的含义是什么?（分数：2.00）_ 正确答案：(正确答案：A 2 如下：0 行 3 列的元素值 3 表示从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。)解析：(3).若已知具有 n(
16、n2)个顶点的图的邻接矩阵为 B，则 B m(2mn)中非零元素的含义是什么?（分数：2.00）_ 正确答案：(正确答案：B m(2mn)中位于 i 行 j 列(0i，jn-1)的非零元素的含义是：图中从顶点 i到顶点 j 长度为 m 的路径条数。)解析：某网络中的路由器运行OSPF路由协议，表 5-1是路由器 R1 维护的主要链路状态信息(LSI)，图 5-3是根据表 5-1及 R1 的接口名构造出来的网络拓扑。请回答下列问题：（分数：6.00）(1).本题中的网络可抽象为数据结构中的哪种逻辑结构?（分数：2.00）_ 正确答案：(正确答案：图 题中给出的是一个简单的网络拓扑图，可以抽象为无
17、向图。)解析：(2).针对表 5-1中的内容，设计合理的链式存储结构，以保存表 5-1中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应表 5-1的链式存储结构示意图(示意图中可仅以 ID 标识结点)。（分数：2.00）_ 正确答案：(正确答案：链式存储结构的如下图所示。其数据类型定义如下：typedef struct unsigned int ID，IP，LinkNode；Link 的结构 typedef struct unsigned int Prefix，Mask；NetNode；Net的结构 typedef struct Node int Flag；Flag=l
18、为 Link；Flag=2为 Net union LinkNode Lnode；NetNode Nnode LinkORNet；Unsigned int Metric；struct Node*next，ArcNode；弧结点 typedef struct HNode unsigned int RouterID；对应表 5-1的链式存储结构示意图如下。)解析：(3).按照迪杰斯特拉(Dijkstra)算法的策略，依次给出 R1 到达图 5-3中子网 1921 x x 的最短路径及费用。（分数：2.00）_ 正确答案：(正确答案：计算结果如下表所示。)解析：解析：考查在具体模型中数据结构的应用。该
19、题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考查的还是数据结构的内容。19.带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v；重复步骤，直到 u 是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。（分数：2.00）_ 正确答案：(正确答案：该方法不一定能(或不能)求得最短
20、路径。举例说明：图(a)中，设初始顶点为 1，目标顶点为 4，欲求从顶点 1 到顶点 4 之间的最短路径，显然这两点之间的最短路径长度为 2。利用给定方欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！法求得的路径长度为 3，但这条路径并不是这两点之间的最短路径。图(1)中，设初始顶点为 1，目标顶点为 3，欲求从顶点 l 到顶点 3 之间的最短路径。利用给定的方法，无法求出顶点 1 到顶点 3 的路径。)解析：已知有 6 个顶点(项点编号为 05)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：（分
21、数：6.00）(1).写出图 G 的邻接矩阵 A。（分数：2.00）_ 正确答案：(正确答案：由数组得图 G 的邻接矩阵 A 如下图所示。)解析：(2).画出有向带权图 G。（分数：2.00）_ 正确答案：(正确答案：根据上面的邻接矩阵，画出有向带权图 G，如下图所示。)解析：(3).求图 G 的关键路径，并计算该关键路径的长度。（分数：2.00）_ 正确答案：(正确答案：按照算法，先计算各个事件的最早发生时间，计算过程如下：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
22、23=9+4=13；ve(4)=ve(2)+a 24=9+3=12；ve(5)=maxve(3)+a 35，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)-a 23，vl(4)-a 24=min(9，10)=9；vl(1)=vl(2)-a 12=4；v1(0)=minvl(2)-a 02，Vl(1)-a 01=min(3，0)；即 ve()和 vl()数组如下表所示：接下来计算所有活动的
23、最早和最迟发生时间 e()和 l()：e(a 01)=e(a 02)=ve(0)=0；e(a 12)ve(1)=4；e(a 23)=e(a 24)=ve(2)=9；e(a 35)-ve(3)=13；e(a 45)=ve(4)=12；l(a 45)=vl(5)-a 45=16-3=13；l(a 35)=vl(5)-a 35=16-3=13；l(a 24)=vl(4)a 24=13-3=10；l(a 23)-vl(3)-a=23 13-4=9；l(a 12)=vl(2)-a 12=9-5=4：l(a 02)=vl(2)-a 02=9-6=3；l(a 01)=vl(1)-a 01=4-4=0；e()
24、和 l()数组与它们的差值如下表所示：满足 l()-e()=0的路径就是关键路径，所以关键路径为 a 0-1、a 1-2、a 2-3、a 3-5，如下图所示(粗线表示)。)解析：一个长度为 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 的中位数。要求：（分数：6.00
25、）(1).给出算法的基本设计思想。（分数：2.00）_ 正确答案：(正确答案：求两个序列 A 和 B 的中位数最简单的办法就是将两个升序序列进行归并排序，然后求其中位数。这种解法虽可求解，但在时间和空间两方面都不大符合高效的要求，但也能获得部分分值。根据题目分析，分别求两个升序序列 A 和 B 的中位数，设为 a 和 b。若 a=b，则 a 或 b 即为所求的中位数。原因：容易验证，如果将两个序列归并排序，则最终序列中，排在子序列 ab 前边的元素为先前两个序列中排在 a 和 b 前边的元素；排在子序列 ab 后边的元素为先前两个序列中排在 a 和 b 后边的元素。所以子序列ab 一定位于最终
26、序列的中间，又因为 a=b，显然 a 就是中位数。否则(假设 ab)，中位数只能出现(a，b)范围内。原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如ab的序列出现，中欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！位数必出现在(a，b)之间。因此可以做如下处理：舍弃 a 所在序列 A 的较小一半，同时舍弃 b 所在序列 B的较大一半。在保留两个升序序列中求出新的中位数 a 和 b，重复上述过程，直到两个序列中，只含一个元素时为止，则较小者即为所求的中位数。每次总的元素个数变为原来的一半。算法的基本设计思想如下。分别求出序列 A 和 B
27、 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下：若 a=b，则 a 或 b 即为所求中位数，算法结束。若 a b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求舍弃的长度相等。若 a b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度相等。在保留的两个升序序列中，重复过程、，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。)解析：(2).根据设计思想，采用 C 或 C+或 Java语言描述算法，关键之处给出注释。（分数：2.00）_ 正确答案：(正确答案：算法的实现如下：int M Search(int A，int
28、B，int n)int s1=0，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 As1Bs2?As1：Bs2，)解析：(3).说明你所设计算法的时间复杂度和空间复杂度。（分数：2.00）_ 正确答案：(正确答案：算法的时间复杂度为 O(log 2 n)，空间复杂度为 O(1)。)解析：解析：综合考查了顺序表的折半查找和归并的思想。