中国计量大学
2021年硕士研究生招生考试试题
考试科目代码：806考试科目名称：数据结构与操作系统
教育投诉平台在哪里投诉>云南省公务员招录网所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。
一、单项选择题（共30题，每小题2分，共60分）
A.两个程序段的时间复杂度相同，则其实际运行时间也相同
B.如下时间复杂度是递增的：O(1),O(log
2N),O(N),O(nlog
2
N)
C.1000N+N2/99999=O(N)
D.如果两个算法在最坏情况下时间复杂度相同，则平均情况下，其时间复杂度也相同
2.对线性表的描述，正确的是（）。
A.在顺序表上的插入操作，其平均时间复杂度为O(N)
B.在链表上的插入操作，其平均时间复杂度为O(N)
C.在顺序表上访问第i个元素的操作，其平均时间复杂度为O(N)
D.在链表上访问第i个元素的操作，其平均时间复杂度为O(1)
3.在一个空栈上进行如下操作：PUSH1，PUSH2，PUSH3，POP，PUSH4，PUSH5，POP，
POP，以下描述正确的是（）。
A.最终的栈顶元素是1
B.出栈的顺序是：1，2，3
C.最终的栈底元素是1
D.最终留在栈中的元素是：3，4，5
4.在一个空队列中依次进行如下操作：ENQUEUQE1,ENQUEUQE2,ENQUEUQE3，DEQUEUE,
ENQUEUQE4，ENQUEUQE5，DEQUEUE，DEQUEUE，以下描述正确的是（）。
A．队列中还剩下的元素是：1 B.最先出队的元素是：3
C.最后出队的元素是：4
D.出队顺序是：1，2，3
5.对图1的二叉树，描述正确的是（）。
A．树的高度为2 B.中序遍历结果为：ABCEF
C.这是一棵AVL树
D.节点C的度为3
图1.二叉树
6.对图2的二叉查树，描述正确的是（）。
A．该树的深度是4
B．这是一棵AVL树
C．删除节点E时，可用把节点D移到原E的位置
D．节点A到G的路径长度是4
图2.二叉查树
7.如果把图2当作图(Graph)，则描述正确的是（）。
A．节点E的度是3
B.该图是有向图
C．从节点B出发的深度优先搜索的一个结果为：BAEFGCD
D．从节点A出发的广度优先搜索的一个结果为：ABECDFG
8.关于图(Graph)的描述，正确的是（）。
A．从邻接矩阵计算一个顶点的度的时间复杂度是O(N)
B.计算一个顶点的度，用邻接表的时间复杂度大于用邻接矩阵的
C．一个图的拓扑排序结果肯定是唯一的
D．无向图的邻接矩阵可能是不对称的
9.对数据序列{3,5,8,2,4,9,7}进行一趟排序，以下描述正确的是（）。
A.用7为轴值的一趟快速排序结果是{3,4,2,5,8,9,7}辽宁省考试之窗网站
B.一趟选择排序的结果是{2,3,5,8,4,9,7}
C.一趟插入排序的结果是{2,3,5,8,4,9,7}
D.用增量为3的一趟Shell排序结果是{2,4,8,3,5,9,7}
10.不同数据结构上的查算法的时间复杂度，描述正确的是（）。
A.最坏情况下：二叉树肯定比线性表小
B.最坏情况下：二叉查树肯定比线性表小
C.最坏情况下：AVL树肯定比线性表小
D.最坏情况下：散列表肯定比二叉查树小
11.关于散列表的描述，正确的是（）。
A．双散列是采用分离链接法表示散列表时，解决冲突的一种方法
B．线性探测是采用开放定址法表示散列表时，解决冲突的一种方法
C．装载因子表示散列表上的冲突数量占整个散列表的比例
D．分离链接法表示散列表时，解决冲突的方法是把冲突的数据放在二叉树中
12.一个栈的输入序列是{1,2,3,4}，则不可能的输出序列是（）。
A.{4,3,2,1}
B.{1,2,3,4}
C.{1,4,3,2}
D.{4,1,2,3}
13.已知某二叉树的前序遍历序列是abdcef，中序遍历序列是dbaecf，则其后续遍历是
（）。
A.dbefca
B.abcdef
C.dbaecf
D.abdcef
14.深度为9的二叉树最多有多少个节点（）。
A.1023
B.512
C.1024
D.511
15.表达式a+b*c-d的后缀表达式为（）。
A.abc*+d-
B.ab*c+d-
C.abcd-*+
D.ab+c*d-
16.在进程的状态转换中，以下哪种是错误的（）。
A.就绪->运行
B.运行->阻塞
C.阻塞->就绪
D.阻塞->运行
17.在一个单CPU系统中，如果系统中有7个用户进程，那么，运行的进程最多几个
（）？
A.1
B.0
C.7
D.以上都不对
18.在一个单CPU系统中，如果系统中有7个用户进程，那么，处在就绪状态的进程最多
几个（）？
A.7
B.0
C.6
D.以上都不对
19.在一个单CPU系统中，如果系统中有7个用户进程，那么，处在阻塞状态的进程最多
几个（）？
A.6
B.7
C.0
D.以上都不对
20.根据系统管理员或用户可规定文件的存取控制属性，以下不属于存取控制属性的文件
是（）。
A.只执行文件
B.只读文件
C.源文件
D.可读写文件
21.以下哪种特性不是操作系统的基本特性？（）
A．异步性 B.可扩展性
第一颗原子爆炸成功是哪一年C.并发性
D.共享性
22.假设某计算机系统中有K台打印机，由5个进程竞争使用，每个进程最少需要3台打
印机才能完成任务。若要该系统不发生死锁，K的最小值是（）。
A.15
B.10
C.11
D.以上都不对
23.虚拟内存管理中，假设物理内存为3G，外存硬盘有300G，那么虚拟内存容量为（）。
A.3G
B.303G
C.300G
D.以上都不对
24.位示图法可用于（）。
A.请求分页虚拟管理中的页面置换
B.磁盘的驱动调度
C.文件目录的查
D.磁盘空闲盘块的组织
25.在基本分页存储管理中，逻辑地址转换为物理地址时，若页号超过页表长度，则会引
起（）。
教师资格证培训机构排名前十A.缺页中断
B.缺段中断
C.越界中断
D.输入输出I/O中断
26.假设磁头当前位于100道，现有一个磁道访问请求序列为55，22，88，120，15，130，
188，采用先来先服务（FCFS算法）得到的磁道访问序列是（）。
21年国考行测答案及解析A.15，22，55，88，120，130，188
B.120，130，188，88，55，22，15
C．88，55，22，15，120，130，188
D.55，22，88，120，15，130，188
发布评论