2020全国硕士研究生招生考试计算机学科专业基础试题参考答案一、单项选择题01.C02.D03.A04.C05.B06.B07.A08.B09.C10.B11.A12.B13.A14.D15.D16.A17.B18.A19.C20.C21.B22.C23.B24.A25.D26.D27.B28.D29.B30.D31.B32.C33.C34.B35.C36.D37.A38.D39.C40.D01.【解析】上三角矩阵按列优先存储，先存储仅1个元素的第一列，再存储有2个元素的第二列，以此类推。加7,2位于左下角，对应右上角的元素为加2,7,在加2,7之前存有第1列：1第2列：2第6列：6第7列：1前面共存有1+2+3+4+5+6+1=22个元素（数组下标范围为0〜21）,注意数组下标从0开始，故加工7在数组N中的下标为22,即加7,2在数组N中的下标为22。02.【解析】按题意，出入栈操作的过程如下：操作栈内元素出栈元素PushaPushabPopabPushacPopacPushadPushadePopade故出栈序列为“c,e。03•【解析】二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树，为了满足任意性，其1〜5层的所有结点都要被存储起来，即考虑为一棵高度为5的满二叉树，总共需要存储单元的数量为1+2+4+8+16=31。04•【解析】森林厂的先根遍历序列对应其二叉树T的先序遍历序列，森林尸的中根遍历序列对应其二叉树T的中序遍历序列。即T的先序遍历序列为中序遍历序列为6,凡&工内co根据二叉树T的先序序列和中序序列可以唯一确定它的结构，构造过程如下：可以得到二叉树T的后序序列为瓦工e,d,c,a.05.【解析】每个选项都逐一验证，选项B生成二叉排序树的过程如下:显然选项B错误。06.【解析】DFS是一个递归算法，在遍历过程中，先访问的顶点被压入栈底。设在图中有顶点匕，它有后继顶点蚱即存在边根据DFS的规则，修入栈后，必先遍历完其后继顶点后片才会出栈，也就是说“会在v/之后出栈，在如题所指的过程中，必在％后打印。由于修和U具有任意性，从上面的规律可以看出，输出顶点的序列是逆拓扑有序序列。07.【解析】Kruskal算法：按权值递增顺序依次选取勿-1条边，并保证这〃-1条边不构成回路。初始构造一个仅含〃个顶点的森林；第一步，选取权值最小的边SJ)加入最小生成树；第二步,剩余边中权值最小的边为(瓦加入最小生成树，第二步操作后权值最小的边3J)不能选,因为会与之前已选取的边形成回路；接下来依次选取权值9,10,11对应的边加入最小生成树，此时6个顶点形成了一棵树，最小生成树构造完成。按照上述过程，加到最小生成树的边依次为(6J),3,m,(a,e),(c,e),3,e)。其生成过程如下所示。•031•第一步选砂他/>第二步选取边
第三步选取边第四步选取边第五步选破〈ae>08.【解析】关键路径是指权值之和最大而非边数最多的路径，故选项A错误。选项B正确，是关键路径的概念。无论是存在一条还是存在多条关键路径，增加任一关键活动的时间都会延长工程的工期，因为关键路径始终是权值之和最大的那条路径，选项C错误。仅有一条关键路径时，减少关键活动的时间会缩短工程的工期；存在多条关键路径时，缩短一条关键活动的时间不一定会缩短工程的工期，缩短了路径长度的那条关键路径不一定还是关键路径，选项D错误。09•【解析】这是一道简单的概念题。堆是一棵完全树，采用一维数组存储，故I正确，II正确。大根堆只要求根结点值大于左右孩子值，并不要求左右孩子值有序，in错误。堆的定义是递归的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，IV正确。10•【解析】一个4阶B树的任意非叶结点至多含有加-1=3个关键字，在关键字依次插入的过程中,会导致结点的不断分裂，插入过程如下所示。得到根结点包含的关键字为6,9o11.【解析】考虑较极端的情况，对于有序数组，直接插入排序的比较次数为〃-1,简单选择排序的比较次数始终为1+2+…1=1)/2,I正确。两种排序方法的辅助空间都是0(1),无差别，II错误。初始有序时，移动次数均为0；对于通常情况，直接插入排序每趟插入都•032•需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，in错误。12.【解析】机器字长是指CPU内部用于整数运算的数据通路的宽度。CPU内部数据通路是指CPU内部的数据流经的路径及路径上的部件，主要是CPU内部进...
