中国计量大学
2019年硕士研究生招生考试试题
考试科目代码：806    考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。
一、 单项选择题：1～30小题，每小题2分，共60分。
1.以下T(n)表示各算法中最耗时操作的执行次数，n表示数据量，请按照时间复
杂度从小到大排列，正确的是（）。
T1(n) = 100n + 200log
n
2
T2(n) = 3n2
T3(n) = 10000000
n
T4(n) = 300log
2
A.T1<T2<T3<T4 B．T2<T1<T4<T3
C．T3<T4<T1<T2 D．T3<T1<T4<T2
2.在一个无序数据序列上进行查，分别采用以下算法，速度最快的是（    ）。
A．折半查 B．顺序查    C．二叉排序树查  D．哈希表查
3.下列关于线性表的描述，错误的是（    ）。
A.顺序表不能进行插入操作
B.顺序表可以进行插入操作
C.顺序表适宜于随机存取
D.链表适宜于顺序存取
4.往队列中依次输入序列{1,2,3,4}，经过若干入队与出队操作，队列中剩下的数
据可能是（  ）。
A．1 B．2 C．3 D．4
《数据结构与操作系统》试卷第1页共9 页
5.往栈中依次输入序列{1,2,3,4}，经过若干入栈队与出栈操作，关于栈中剩下的
数据正确的是（  ）。
A.不可能是4 B．无法确定
C．不可能是2  D．不可能是1
6.已知一棵完全二叉树的第3层有3个叶子节点（树根为第1层），则这棵完全二
叉树的节点个数最多有几个（    ）。
A．6 B．8 C．9 D．12
7.下列关于堆的描述，错误的是（    ）。
A．堆是满二叉树
B．大根堆的树根关键字大于其子树中的所有结点的关键字
C．堆一般用数组来表示
D．大根堆的右子树中所有结点的关键字小于树根关键字
8.关于图1的邻接矩阵，如果结点A的出度为2，则描述错误的是（    ）。
A．结点A到结点C的最短路径长度为4
B. 结点A的度为3
C．结点A到C只有2条路径
D．结点E的度为2
A B C    D    E F
A    1 2
B 34
C 5 6
D 7
E 8
F 9
图1. 题8的邻接矩阵
9.下列排序算法中，时间复杂度与快速排序相同的是（    ）。
A．希尔排序    B. 直接插入排序    C．冒泡排序    D．堆排序
10.在一个无序序列上进行查，如果采用折半查算法，则整个处理过程的时间
复杂度是（  ）。
A．O(log
2n)    B．O(n)  C．O(nlog
2
n)  D．O(n+log
2
n)
《数据结构与操作系统》试卷第2页共9 页
11.图2所示这棵二叉树的前序遍历结果是（    ）。
A．CBEAD    B. CBAED    C. ABCDE    D. ABDEC
图2.二叉树
12.在软件的操作过程中，一般都有撤销或返回的操作，如果要实现该功能，必须
保存历史操作的信息，应该用什么数据结构来保存这些历史操作信息 (    )。
A．队列        B．查二叉树      C．有向图 D．栈
13.关于快速排序算法，描述正确的是（  ）。
n)
A．时间复杂度为O(nlog
2
B．是稳定的
C．是所有排序算法中，速度最快的算法
D．轴值可以任意选择，对排序性能无影响
14.关于插入排序，描述正确的是（    ）。
A．时间复杂度是O(n3)
B．在顺序表上进行插入排序时，可以用折半查算法来加快查插入位 置的过程
C．在有序序列上进行插入排序时，其时间复杂度与无序序列上的插入排 序时间复杂度是相同的
D．链表上不能进行插入排序
《数据结构与操作系统》试卷第3页共9 页
15.关于算法与数据结构的表示，正确的是（    ）。
A．线性表、二叉树和图都可以用数组表示
B．在二叉查树上的查速度肯定比线性表上快
C．链表是用数组表示的
D．图只能用数组表示
16.某计算机系统中有K台打印机，由4个进程竞争使用，每个进程最多需要 3台
打印机。该系统不可能发生死锁的K的最小值是（  ）。
A.12
B. 6
C. 8
D. 9
17.根据文件的组织方式，以下哪种不是有结构文件的组织方式（  ）？
A.顺序文件
B.流式文件
C.索引文件
D.顺序索引文件
18.在基本分页存储管理中，若采用最优页面置换算法OPT，则当进程分配到的物理
块数增加时，那么缺页中断的次数将（  ）。
A. 一定会减少
B.一定不会增加
C. 无影响
D.可能减少也可能增加
19.SPOOLing技术中，其中输入井和输出井是（  ）。
A. 硬盘的一部分
B. 内存的一部分
C. 缓冲区
D.以上都是
20.假设某一机器的内存有8G，硬盘为300G，请问使用虚拟内存技术后，其虚拟内存
的容量为（  ）。
A.300G
B. 8G
C. 308G
D.16G
21.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻
数据结构与算法考研真题
空闲区合并，为此需修改空闲区表，造成空闲区总数减少一个的情况是(  )。
A. 释放的区域无上邻空闲区，也无下邻空闲区
B. 释放的区域有上邻空闲区，也有下邻空闲区
C. 释放的区域有下邻空闲区但无上邻空闲区；或有上邻空闲区但无下邻空 闲区
D. 以上都可以
《数据结构与操作系统》试卷第4页共9 页
22.考虑以下页表结构：
页号 块号
0    2
1    5
2    1
3    6
假设页的大小为1024字节, 即页内地址长度为 10 位，请把以下以十六进制表示的逻辑地址0x1567，通过页表转换为物理地址（也用十六进制表示）是 （  ）。
A.地址转换错误
B. 0x967
C. 0x367
D. 0x567
23.假设磁头当前位于100道，现有一个磁道访问请求序列为55，95，110，33，180，
140，195，请问最短寻道时间优先SSTF算法得到的磁道访问序列是（  ）。
A.55，95，110，33，180，140，195
B.110，140，180，195，95，55，33
C.95，110，140，180，195，55，33
D.110，140，180，195，33，55，95
24.假设磁头当前位于100道，现有一个磁道访问请求序列为55，95，110，33，180，
140，195，请问先来先服务FCFS算法得到的磁道访问序列是（  ）。
A.55，95，110，33，180，140，195
B.95，110，140，180，195，55，33
C.110，140，180，195，95，55，33
D.110，140，180，195，33，55，95
25.假设磁头当前位于100道，准备向磁道序号增加的方向移动。现有一个磁道访
问请求序列为55，95，110，33，180，140，195，请问基于扫描的磁盘调度算法SCAN得到的磁道访问序列是（  ）。
A.55，95，110，33，180，140，195
B.95，110，140，180，195，55，33
C.110，140，180，195，95，55，33
D.110，140，180，195，33，55，95
《数据结构与操作系统》试卷第5页共9 页

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。