中国计量学院806数据结构与操作系统2016年考研真题考研专业课真题
● 摘要
一、 单项选择题：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．冒泡排序
《数据结构与操作系统》试卷 第1页 共7页