中国计量大学806数据结构与操作系统2020年考研真题
2024-11-19
999+
448.31KB
9 页
侵权投诉
《数据结构与操作系统》试卷 第1页 共9 页
中国计量大学
2020 年硕士研究生招生考试试题
考试科目代码：806 考试科目名称：数据结构与操作系统
所有答案必须写在报考点提供的答题纸上，答在试卷
或草稿纸上无效。
一、单项选择题（共 30 题，每小题 2 分，共 60 分）
1. 关于下面两个程序段，描述正确的是（ ）。
程序段 1：
double fun1(int n)
{ if( n = = 1 )
return 1;
return n * fun( n - 1 );
}
程序段 2：
double fun2(int n)
{ double s = 1;
for(int i=2; i<=n; i++)
s *= i;
return s;
}
A. 两个程序段的时间复杂度相同 B．fun1 的时间复杂度小于 fun2
C．fun1 的时间复杂度大于 fun2 D．fun1 的实际运行时间小于 fun2
2. 对一个已经有序的数据序列进行排序操作，下面的描述正确的是（ ）。
A. 快速排序的时间复杂度是 O(N) B. 归并排序的时间复杂度是 O(N)
C．选择排序的时间复杂度是 O(N) D.插入排序的时间复杂度是 O(N)
3. 对于只在表的一端进行删除和插入操作的线性表，宜采用的存储结构为（ ）。
A. 队列 B. 顺序表 C. 栈 D. 双向链表
《数据结构与操作系统》试卷 第2页 共9 页
4. 往队列中依次输入序列{1,2,3,......,n}，经过若干入队与出队操作后队列为
空，则最后出队的数据是（ ）。
A．1 B．不确定 C．N D．有无数个可能
5. 已知一棵完全二叉树的第 4 层有 4 个叶子节点（树根为第 1 层），则这棵完全二
叉树的节点个数最多有几个（ ）。
A．11 B．23 C．24 D．28
6. 下列关于查找算法的描述，错误的是（ ）。
A．折半查找的时间复杂度比线性表的小
B．AVL 树的查找时间复杂度与折半查找的相同
C．二叉查找树的查找时间复杂度肯定比线性表小
D．散列表的查找时间复杂度不一定比线性表小
7. 关于图 1 的邻接矩阵，如果顶点 A 的出度为 2，则描述错误的是（ ）。
A．顶点 A 到顶点 D 的最短路径长度为 9
B. 顶点 A 的度为 3
C．顶点A到C只有1条路径
D．顶点 E 的度为 2
A B C D E F
A 19
B 3 4
C 5 3
D 7
E 8
F 2
图 1. 题 7 的邻接矩阵
8. 对数据序列{3，6，2，8，5，1，9，7，4}进行快速排序时，关于轴值的选择，
描述正确的是（ ）。
A. 轴值选择 3 的排序速度最快 B. 轴值选择 5 的排序速度最快
C. 轴值选择 4 的排序速度最快 D.轴值选择 1 的排序速度最快
《数据结构与操作系统》试卷 第3页 共9 页
9. 关于图 2 所示无向图的描述正确的是（ ）。
A. 从A到C只有2条路
B. 顶点A到D的最短距离为 4
C. 从 A 点出发的广度优先遍历结果只有一种结果，即 ABEFCD
D. 这是无向连通图
图 2. 题 9 的无向图
10. 图 3 所示这棵二叉树的前序遍历结果是（ ）。
A．BAECF B. BEFCA C. ABCEF D. ACFEB
图 3. 题 10 的二叉树
11. 下列排序算法中，占用额外空间最多的是 ( )。
A．快速排序 B．归并排序 C．Shell 排序 D．堆排序
12. 关于线性表，描述正确的是（ ）。
A．链表上可以进行折半查找，时间复杂度是 O(log2N)
B．链表上在第 i 个位置进行插入操作的时间复杂度是 O(1)
C．顺序表上在第 i 个位置进行插入操作的时间复杂度是 O(1)
D．链表上的插入操作比顺序表上的插入操作快
标签： #中国计量大学 #806数据结构与操作系统
摘要：
展开>>
收起<<
《数据结构与操作系统》试卷第1页共9页中国计量大学2020年硕士研究生招生考试试题考试科目代码：806考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，答在试卷或草稿纸上无效。一、单项选择题（共30题，每小题2分，共60分）1.关于下面两个程序段，描述正确的是（）。程序段1：doublefun1(intn){if(n==1)return1;returnn*fun(n-1);}程序段2：doublefun2(intn){doubles=1;for(inti=2;i...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
