2016年中国海洋大学信息科学与工程学院数据结构考研复试题库
● 摘要
一、选择题
1． 求整数
阶乘的算法如下，其时间复杂度是（ ）。
A.
B. C. D. 答:B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是法运算的时间。
因此，
当
时
，
当
即fact （n
）的时间复杂度为
2． 对矩阵压缩存储是为了（ ）。
A. 方便运算 B. 方便存储 C. 提高运算速度 D. 减少存储空间 答:D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
3． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法 答:A
【解析】选择排序的基本思想是：
第 2 页，共 47 页
其中O （1）为乘
则
，
时
，
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和 4． 有
A. B. C. D.
答:C
分别变为新的有序区和新的无序区。 个分支结点的满二叉树的深度是（ ）。
和该趟排序
交换，使
将它与无序区的第1个记录
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树， 所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
5． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
答:B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换； 第二次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为一次划分结束。
6． 程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
答:D
【解析】这个是冒泡排序，最坏的情况下需要进行
次交换，即时间复杂度是
第 3 页，共 47 页
相关内容
相关标签