2020年408计算机学科专业基础考研真题答案及解析

本文提供2020年408计算机学科专业基础考研真题答案及解析，以下为具体内容

1、 将一个10x10对称矩阵M的上三角部分的元素mi，j （1≤i≤j≤10）按列优先存入C语言的一维数组N中，元素m7，2在N中的下标是（ ）。

A、 15

B、 16

C、 22

D、 23

2、对空栈S进行Push和Pop操作，入栈序列为a， b， c， d， e，经过Push， Push， Pop， Push， Pop， Push， Push， Pop 操作后得到的出栈序列是（ ）。

A、 b，a，c

B、 b，a，e

C、 b，c，a

D、 b，c，e

3、对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ ）。

A、 31

B、 16

C、 15

D、 10

4、已知森林F及与之对应的二叉树T，若F的先根遍历序列是a， b， c， d， e， f，中根遍历序列是b， a， d，f， e， c，则T的后根遍历序列是（ ）。

A、 b，a，d，f，e，c

B、 b，d，f，e，c，a

C、 b，f，e，d，c，a

D、 f，e，d，c，b，a

5、下列给定的关键字输入序列中，不能生成如下二叉排序树的是（ ）。

A、 4，5，2，1，3

B、 4，5，1，2，3

C、 4，2，5，3，1

D、 4，2，1，3，5

6、修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图G，若输出结果中包含G中的全部顶点，则输出的顶点序列是G的（ ）。

A、 拓扑有序序列

B、 逆拓扑有序序列

C、 广度优先搜索序列

D、 深度优先搜索序列

7、已知无向图G如下所示，使用克鲁斯卡尔（Kruskal） 算法求图G的最小生成树，加到最小生成树中的边依次是（ ）。

A、 （b， f）， （b， d）， （a， e）， （c， e）， （b， e）

B、 （b， f）， （b， d）， （b， e）， （a， e）， （c， e）

C、 （a， e）， （b， e）， （c， e）， （b， d）， （b， f）

D、 （a， e）， （c， e）， （b， e）， （b， f）， （b， d）

8、若使用AOE网估算工程进度，则下列叙述中正确的是（ ）。

A、 关键路径是从原点到汇点边数最多的一条路径

B、 关键路径是从原点到汇点路径长度最长的路径

C、 增加任一关键活动的时间不会延长工程的工期

D、 缩短任一关键活动的时间将会缩短工程的工期

9、下列关于大根堆（至少含2个元素）的叙述中，正确的是（ ）。I.可以将堆看成一棵完全二叉树II.可以采用顺序存储方式保存堆III.可以将堆看成一棵二叉排序树IV.堆中的次大值一定在根的下一层

A、 仅I、II

B、 仅II、III

C、 仅I、II和IV

D、 I、III和IV

10、依次将关键字5，6，9，13，8，2，12，15 插入初始为空的4阶B树后，根结点中包含的关键字是（ ）。

A、 8

B、 6，9

C、 8，13

D、 9，12

1、试题答案：C

试题解析：

【考点】本题考查三角矩阵的存储
【解析】该对称矩阵按照上三角存储，因此m7，2在上三角中对应的存储位置为m2，7。按列优先存储时，m2，7之前需要存储的元素为：第一列有1个元素，第二列有2个元素，……，第六列有6个元素，第7列有1个元素。在一维数组中存储时，数组从0开始存储，因此第23个元素在数组N中的下标为22。因此故本题选C。

2、试题答案：D

试题解析：

【考点】本题考查出栈和入栈操作
【解析】根据栈的基本操作得出栈每一个步骤的操作如下：

故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查二叉树的存储
【解析】由于该二叉树是任意一棵高度为5的二叉树，因此考虑该二叉树的最坏情况，即二叉树为满二叉树。此时，高度为5的满二叉树的节点个数=1+2+4+8+16=31。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查二叉树的遍历
【解析】
树、森林转换为二叉树时遍历的对应关系为：
（1）树的遍历与其对应的二叉树的遍历：
① 树的先根遍历对应树的先序遍历；② 树的后根遍历对应二叉树的中序遍历。
（2）森林的遍历与其对应的二叉树的遍历：
① 森林的先序遍历对应二叉树的先序遍历；② 森林的中序遍历对应二叉树的中序遍历。
森林的先根序列对应转化后的二叉树的先序序列，森林的中根序列对应转化后的二叉树的中序序列。二叉树的先序序列与中序序列可以唯一确定一棵树，知其先序序列和后序序列无法唯一确定一棵二叉树。综上，本题题意可以理解为已知二叉树的先序序列和中序序列，求二叉树的后序序列。根据二叉树T的先序和中序序列画出该二叉树如下：

根据上述二叉树的结构，得出该二叉树的后序序列为：b，f，e，d，c，a。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查二叉排序树的插入操作
【解析】二叉排序树的基本概念为二叉排序树或者为空树，或者为具有如下特性的树：① 若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；② 若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；③ 其左右子树也分别为二叉排序树。根据二叉排序树的定义，若1在2、3之前插入，则1应该为4的左孩子，与题干中的二叉排序树结构不符。故本题选B。

6、试题答案：B

试题解析：

【考点】本题考查图遍历算法和拓扑序列算法
【解析】根据题干可知，修改后的深度优先搜索算法的实现方式为退出递归前输出当前结点。退出递归的条件是当前结点无法再深入，即出度为0。因此，修改后的深度优先搜索算法会次序输出图中出度为0的点。而拓扑排序是输出入度为0的点，因此上述算法输出的顶点序列为逆拓扑有序序列。故本题选B。

7、试题答案：A

试题解析：

【考点】本题考查最小生成树算法
【解析】Kruskal算法求最小生成树的步骤是先将权值按从小到大的顺序排列，然后依次取权值最小的边但不能形成环，直到所有顶点已经连接，则不再取边。按照此规则选择权值，分别为5（对应边（b，f）），6（对应边（b，d）），7不可取，否则会形成环，接下来取9（对应边（a，e）），接下来选择10（对应边（c，e））， ，接下来选择11（对应边（b，e））。至此，所有顶点已经添加到生成树中，加入到最小生成树中的边依次为（b，f），（b，d），（a，e），（c，e），（b，e）。故本题选A。

8、试题答案：B

试题解析：

【考点】本题考查AOE网特性
【解析】关键路径是从源点到汇点路径长度最长的路径，这个路径长度不是指边数，因此A错误。路径长度是指花费的时间，即边的权值。而完成工程的最短时间是从开始点到完成点的最长路径的长度，因此B正确。AOE网指在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间；若任意一个关键活动延期，则工期一定延长。因此C错误。若任意一个关键活动加快，则工期不一定加快，因此D错误。若任意一个非关键活动延期，则工期可能延长；若任意一个非关键活动加快，则工期不加快。故本题选B。

9、试题答案：C

试题解析：

【考点】本题考查堆的特性
【考法】判断选项是否符合堆的特性
【解析】堆是一棵完全二叉树，因此I正确。二叉树可以采用顺序存储结构保存，因此II正确。一棵二叉排序树的左右子树之间存在大小关系，左子树上的结点小于根结点，右子树的结点大于等于根结点。而大根堆的根结点的值大于等于其左右子树的值，因此C错误。堆的左右子树仍然是堆，其左右子树的根结点仍然是本身的左右子树中的最大值。因此堆中的次大值在根结点的下一层。故D正确。综上，I、II、IV均正确，故本题选C。

10、试题答案：B

试题解析：

【考点】本题考查B树的构造
【解析】一棵4阶B树，每个结点最多有4个子结点，每个结点最多有3个关键字。当关键字个数超出上限，则引起结点的分裂。画出上述关键字依次插入后B的结构如下图所示：