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)。【试题解析】 综合考查了顺序表的折半查找和归并的思想。【知识模块】 数据结构
