2016年浙江省中国计量大学数据结构与操作系统考研真题.doc

2016年浙江省中国计量大学数据结构与操作系统考研真题
一、单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。
1. 函数fun的时间复杂度为（）。
floatfun(floatx,intn)
{floatresult=1.0f;
for(i=0;i<n*n/2;++i)
{
result*=x;
}
returnresult
}
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．1023B．511C．255D．127
7. 有100个结点的无向图要确保是一个连通图至少应有（）。
A．101条边B．99条边C．50条边D．6条边
8. 关于图的描述，错误的是（）。
A．有向图的邻接矩阵一定是对称矩阵
B.完全图中的边一定比连通图中的边多
C．深度优先搜索的结果可能不唯一
D．广度优先搜索的结果可能不唯一
9. 下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个数据，排序后它们的先后位置会变化）（）。
A．希尔排序B．简单选择排序C．插入排序D．冒泡排序
10. 二叉查找树中有1023个结点，查找其中一个数据时，描述正确的是（）。
A．至少要比较10次
B．最多比较10次
C．不可能超过10次
D．如果是平衡二叉查找树，可能要比较1023次
11. 图1所示这棵树的中序遍历结果是（）。
A．ABCDEF B.DBACEF C.DBAECF D.BACCEF
图1.树
12. 往栈中输入序列{1,2,……，n}后再逐个输出，则输出序列的最后一个元素是()。
A．不确定B．n-1C．nD．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．归并排序
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.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数无变化的