中国计量大学-806数据结构与操作系统【2016】考研真题
2023-06-21
999+
129.1KB
7 页
侵权投诉
《数据结构与操作系统》试卷 第 1页 共 7页
一、 单项选择题：1～40 小题，每小题 2 分，共 80 分。在每小题给出的四
个选项中，请选出一项最符合题目要求的。
1. 函数 fun 的时间复杂度为（ ）。
float fun(float x, int n)
{ float result = 1.0f;
for( i=0; i < n*n/2; ++i)
{
result *= x;
}
return result
}
A．O( (n2/2)! ) B．0(2log2n) C．0(n2/2) D．O(n2)
2. 下列排序算法中，需要额外辅助存储空间最多的是（ ）。
A．归并排序 B．快速排序 C．堆排序 D．直接插入排序
3. 以下数据结构中，不属于线性表的是（ ）。
A. 队列 B. 栈 C. 图 D. 循环链表
4. 下面关于栈的描述中，错误的是（ ）。
A．先进后出
B．两头都可以插入和删除
C．可以用数组来实现
D．可以用链表来实现
5. 关于环形（循环）队列，错误的是（ ）。
A．先进先出 B．用数组来实现
C．可以提高空间的利用率 D．用循环链表来实现
6. 层数为 8 的二叉树其结点个数最多有（ ）。
A．1023 B．511 C．255 D．127
7. 有 100 个结点的无向图要确保是一个连通图至少应有（ ）。
A．101 条边 B．99 条边 C．50 条边 D．6 条边
8. 关于图的描述，错误的是（ ）。
A．有向图的邻接矩阵一定是对称矩阵
B. 完全图中的边一定比连通图中的边多
C．深度优先搜索的结果可能不唯一
D．广度优先搜索的结果可能不唯一
9. 下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个
数据，排序后它们的先后位置会变化）（ ）。
A．希尔排序 B．简单选择排序 C．插入排序 D．冒泡排序
《数据结构与操作系统》试卷 第 2页 共 7页
10. 二叉查找树中有 1023 个结点，查找其中一个数据时，描述正确的是（ ）。
A．至少要比较 10 次
B．最多比较 10 次
C．不可能超过 10 次
D．如果是平衡二叉查找树，可能要比较 1023 次
11. 图 1 所示这棵树的中序遍历结果是（ ）。
A．ABCDEF B. DBACEF C. DBAECF D. BACCEF
B C
A
D E F
图 1.树
12. 往栈中输入序列{1,2,……，n}后再逐个输出，则输出序列的最后一个元
素是( )。
A．不确定 B．n-1 C．n D．1
13. 假设 N 个数据已经放在不同的数据结构，然后进行查找，下列描述错误
的是：（ ）。
A．如果采用合适的散列表，其查找速度最快
B．用二叉查找树来查找比用折半查找要快
C．链表上的查找要比二叉查找树 快
D．平衡二叉查找树上的查找要比普通二叉查找树 快
14. 若数据序列 5, 96, 12, 64, 78, 23, 49 是采用下列方法之一得到的第
一趟排序后的结果，则该排序算法是（ ）。
A．冒泡排序 B．直接插入排序 C．快速排序 D．归并排序
15. 对数据 8，1，4，9，6，3，5，2，7，0 进行排序时，第一趟的排序结果
如下：0,1,4,2,5,3,6,9,7,8；
则采用的排序算法是（ ）。
A．快速排序 B．直接插入排序 C．冒泡排序 D．归并排序
《数据结构与操作系统》试卷 第 3页 共 7页
16. 把数据 1，2，3，4，5，6，7 通过插入操作构造一棵二叉查找树，下列
描述错误的是（ ）。
A．按照 3,4,1,2,6,7,5 的插入顺序构造的二叉查找树，树高为 3
B．按照 4,2,1,3,6,5,7 的插入顺序构造的二叉查找树的查找效率最高
C．按照 3,4,1,2,6,7,5 的插入顺序构造的二叉查找树是平衡二叉树
D．按照 4,2,1,3,6,5,7 的插入顺序构造的二叉查找树是平衡二叉树
17. 已知一个数据序列中有 1024 个数据，且其已经有序排列，若采用最快的
查找算法和必要的存储结构，在该序列中要查找一个数据元素，则平均
比较次数最少要多少次（ ）。
A．512 B. 256 C. 10 D. 1
18. 一棵满二叉树共有 11 层（树根为第一层），则叶子节点个数为（ ）。
A. 0 B. 2048 C. 1024 D. 512
19. 若要检查文件中的括号是否匹配，采用的数据结构应该是（ ）。
A． 图 B. 二叉树 C. 栈 D. 栈
20. 快递员每天要送很多包裹给客户，为了提高效率，缩短总路程长度，请
问该选用什么样的数据结构来设计路线（ ）。
A．线性表 B. 图 C.队列 D. 二叉树
21．操作系统是一种( )
A．实用软件 B.系统软件 C. 应用软件 D. 工具软件
22. 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间 B. 节省内存空间
C. 加快文件的检索速度 D. 加快文件的读/写速度
23. 进程从阻塞状态进入就绪状态的原因可能是( )
A. 被选中占有处理机 B. 等待某一事件发生
C. 等待的事件已发生 D. 时间片用完
24. 在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与
相邻空闲区合并，为此需修改空闲区表，造成空闲区数无变化的情况是( )
A.无上邻空闲区，也无下邻空闲区
B.有上邻空闲区，也有下邻空闲区
C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区
D. 以上三种都可以
25. 假设某一机器的内存有 2G,硬盘为 300G,请问使用虚拟内存技术后，其虚拟
内容的容量为（ ）
A. 2G B. 4G C. 300G D.302G
标签： #中国计量大学 #806数据结构与操作系统
摘要：
展开>>
收起<<
《数据结构与操作系统》试卷第1页共7页一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。1.函数fun的时间复杂度为（）。floatfun(floatx,intn){floatresult=1.0f;for(i=0;i
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
