中国计量大学806数据结构与操作系统2021年考研真题
免费
2024-11-19
999+
687.8KB
10 页
侵权投诉
《数据结构与操作系统》试卷 第1页共9页
中国计量大学
2021年硕士研究生招生考试试题
考试科目代码：806 考试科目名称：数据结构与操作系统
所有答案必须写在报考点提供的答题纸上，做在试卷或草
稿纸上无效。
一、单项选择题（共30题，每小题2分，共60分）
1. 关于时间复杂度的描述，正确的是（ ）。
A.两个程序段的时间复杂度相同，则其实际运行时间也相同
B.如下时间复杂度是递增的：O(1),O(log2N),O(N),O(nlog2N)
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
《数据结构与操作系统》试卷 第2页共9页
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
《数据结构与操作系统》试卷 第3页共9页
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
标签： #中国计量大学 #806数据结构与操作系统
摘要：
展开>>
收起<<
《数据结构与操作系统》试卷第1页共9页中国计量大学2021年硕士研究生招生考试试题考试科目代码：806考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。一、单项选择题（共30题，每小题2分，共60分）1.关于时间复杂度的描述，正确的是（）。A.两个程序段的时间复杂度相同，则其实际运行时间也相同B.如下时间复杂度是递增的：O(1),O(log2N),O(N),O(nlog2N)C.1000N+N2/99999=O(N)D.如果两个算法在最坏情况下时间复杂度相同，则平均情况下，其时间复杂度也相同2.对线性表的描述，正确的是（）。A.在顺序表上的插入操作，...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
