中国计量大学-806数据结构与操作系统【2021】考研真题
2023-06-21
999+
259.75KB
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. 在一个空栈上进行如下操作：PUSH 1，PUSH 2，PUSH 3，POP，PUSH 4，PUSH 5，POP，
POP，以下描述正确的是（ ）。
A. 最终的栈顶元素是 1 B. 出栈的顺序是：1，2，3
C. 最终的栈底元素是 1 D. 最终留在栈中的元素是：3，4，5
4. 在一个空队列中依次进行如下操作：ENQUEUQE 1, ENQUEUQE 2, ENQUEUQE 3，DEQUEUE,
ENQUEUQE 4，ENQUEUQE 5，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.在顺序表上的插入操作，...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
