全国硕士研究生招生考试（计算机统考）试题
姓名：__________班级：__________成绩：__________
1.下列关于数据结构的叙述中，正确的是（）
A.数组是同类型值的集合
B.递归算法的程序结构比迭代算法的程序结构更为精炼
C.树是一种线性结构
D.用一维数组存储二叉树，总是以先序遍历的顺序存储各节点
答案：A
2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和
删除运算，则利用（）存储方式最节省时间。
A.顺序表
B.双链表
C.带头结点的双循环链表
D.单循环链表
答案：A
3.若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,
2,1，则该二叉树的中序遍历序列不会是（）
A.1,2,3,4
B.2,3,4,1
C.3,2,4,1
D.4,3,2,1
答案：C
4.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完
全二叉树的结点个数最多是（）
A.39
B.52
C.111
D.119
答案：C
5.对一组数据（2,12,16,88,5,10）进行排序，若前三趟排序结果如下：
第一趟：2,12,16,5,10,88
第二趟：2,12,5,10,16,88
第三趟：2,5,10,12,16,88
则采用的排序方法可能是（）
A.起泡排序
B.希尔排序
C.归并排序
D.基数排序
答案：A
6.下列选项中，不可能是快速排序第2趟排序结果的是（）
A.2,3,5,4,6,7,9
B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9
D.4,2,3,5,7,6,9
答案：C
7.下列关于最小生成树的叙述中，正确的是（）
Ⅰ.最小生成树的代价唯一
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ.使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相
同
A.仅Ⅰ
B.仅Ⅱ
C.仅Ⅰ、Ⅲ
D.仅Ⅱ、Ⅳ
答案：A
8.已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半
查找法查找一个L中不存在的元素，则关键字的比较次数最多是（）
A.4
B.5
C.6
D.7
答案：B
9.下列二叉排序树中，满足平衡二叉树定义的是（）
（此处可插入相应二叉排序树的图片或详细描述）
答案：B
10.下列关于图的叙述中，正确的是（）
Ⅰ.回路是简单路径
Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列，则该图不存在回路
A.仅Ⅱ
B.仅Ⅰ、Ⅱ
C.仅Ⅲ
D.仅Ⅰ、Ⅲ
答案：C
11.下列选项中，属于多级页表优点的是（）
A.加快地址变换速度
B.减少缺页中断次数
C.减少页表项所占字节数
D.减少页表所占的连续内存空间
答案：D
12.下列关于虚拟存储的叙述中，正确的是（）
A.虚拟存储只能基于连续分配技术
B.虚拟存储只能基于非连续分配技术
C.虚拟存储