全国硕士研究生入学统一考试408计算机学科专业基础综合模拟试题及详解（二）
一、单项选择题（1～40小题，每小题2分，共80分。）
1．在下列各项叙述中，正确的说法是（）。
考研计算机真题A．在线性表中，每个元素有且仅有一个直接前趋，有且仅有一个直接后继
B．线性表中至少有一个元素
C．在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继
D．线性表中元素必须从大到小或从小到大排列
【答案】C
【解析】线性表一般被定义为由若干个元素组成的有序序列，注意，线性表是位置有序而不是数据有序。
2．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85（即该元素下标i＝85）的地址为（）。
A．13
B．33
C．18
D．40
【答案】B
2023年省考成绩查询入口
【解析】矩阵A的前7行中，第i行有i个元素被存储。所以前7行共7×（7＋1）/2＝28个元素。a85是第8行中第5个被存储的元素，所以a85是第28＋5＝33个元素。
3．若用一维数组表示一个深度为5、结点个数10的二叉树，数组的长度至少为（）。
A．10
B．16
C．31
D．64
【答案】C
【解析】由于一叉树的顺序存储是按完全二叉树来存储，根据二叉树的性质：深度为k 的二叉树最多有2k-1个结点，深度为5的二叉树最多有31个结点。
4．假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为（）。
A．ABCDEFGHIJ
B．ABDEGHJCFI
C．ABDEGHJFIC
D．ABDEGJHCFI
【答案】B
【解析】根据前序、后序遍历的特点，可以确定A是根节点（在后序遍历的最后一个），再根据中序遍历的特点，可以知道DBGEHJ为左子树，CIF为右子树。
再看右子树的后序遍历为IFC，可以确定C为右子树的根节点；再加上中序为CIF，说
明C无左子树，只有右子树。
而左子树的后序遍历为DGJHEB，因此B为左子树的根节点，再结合中序遍历，可以得知B的左子树只有D，GEHJ都是右子树。
GEHJ子树的后序遍历是GJHE，说明E是根，HJ为E的右子树，G是E的左子树。最后可以H为HJ子树的根，J为右予树。
通过以上分析，就可以绘制出这棵树，如图1所示：
教育考试中心图1 二叉树
然后再由前序遍历，可以得到：ABDEGHJCFI。
5．对于一棵二叉排序树，为了得到所有节点的有序序列，应该对二叉排序树进行（）。
A．前序遍历
B．中序遍历
C．后序遍历
D．层次遍历
【答案】B
【解析】在二叉排序树中，左子树的结点值全部小于根结点，右子树的结点值全部大于根结点，如果按照左子树、根结点、右子树的顺序遍历二叉排序树，得到的是一个有序序列。
6．从图中结点V出发，按广度优先遍历算法查结点U时，最先经过（得到）的是从V到U的边数（）的路径。
A．最多
B．最少
C．既不是最多，也不是最少
D．既可能最多，也可能最少
【答案】B
【解析】本题需注意广度优先遍历与深度优先遍历的区别。
7．从一个具有n个结点的单链表中查其值等于X的结点时，在查成功的情况下，需平均比较的元素结点个数是（）。
A．2*n
B．n
C．（n十1）/2
D．（n－1）/2
【答案】C
【解析】无论是顺序结构还是链式存储结构，顺序查的效率都是一样的。
8．一棵m阶非空B＋树，每个结点最多的关键字数为（）。
A．m/2
B．m－1
C．m
D．m＋1
【答案】C
【解析】注意B＋与B-树的区别。在B＋树中，每个结点的子树个树与关键字个数相同。
9．设有10000个无序记录，希望用最快速度从中选择前10个关键字最小的记录，在以下排序方法中采用（）最好。
A．直接插入排序
B．简单选择排序
C．快速排序
2022年聊城公务员考试
D．希尔排序
【答案】B
【解析】在题中所列出的排序方法中，直接插入排序、快速排序、希尔排序都是排序完成后，才能选出前10个关键字最小的记录。只有简单选择排序能直接选出前10个关键字最小的记录。
10．下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是（）。
A．快速排序
B．shell（希尔）排序
C．堆排序
安徽省考公务员职位表2021查询D．冒泡排序
【答案】B
【解析】因为shell排序每趟是对多个分组进行排序，不可能保证一个元素放到其最终的位置上。
11．关于计算机字长下面说法错误的是（）。
A．表示该计算机能够存储的最大二进制数位数
兰州招聘信息最新招聘2021
B．表示该计算机的CPU可以同时处理的二进制位数
C．机器字长一般与CPU中寄存器的位数有关
D．机器字长决定了数的表示范围和表示精度
【答案】A
【解析】计算机字长是指CPU一次能处理的数据长度，它通常与CPU中的寄存器的位数相等，决定了机器所能表示数据的范围和精度。计算机通过多次操作，可以存储长度远大于字长的二进制数据，也有些寄存器的位数会大于字长，如x86中的段基址寄存器。
12．X是整数，[X]补＝（011100011）2，X的十进制真值是（）。
A．456
B．454
C．227
D．228