CMS专题
相似问题和答案
第1题：
对N个记录的文件进行快速排序，所需要的辅助存储空间为
A．O( )
B．O
C．O( )
D．O( )
第2题：
n个记录的文件进行快速排序，所需要的辅助存储空间为( )。
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
解析：快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log2n，所以其空间复杂度为O(log2n)。
第3题：
对n个记录的文件进行归并排序，所需要的辅助存储空间为
A．O（1）
B．O（n）
C．O（log2n）
D．O（n2）
第4题：
对由n个记录所组成的有序关键码排序时，下列各常用排序算法的平均比较次数分别是：二路归并排序为(29)，冒泡排序(30)，快速排序为(31)。其中，归并排序和快速排序所需要的辅助存储分别是(32)和(33)。
A．O(1)
B．O(nlog2n)
C．O(n)
D．O(n2)
E．O(n(log2n)2)
第5题：
对n个记录的文件进行起泡排序，所需要的输助存储空间为( )。
A．O(1)
B．O(1og2n)
C．O(n)
D．O(n2)
解析：下表给出了主要排序方法的性能比较：
根据上表，对n个记录的文件进行起泡排序，所需要的辅助存储空间为O(1)。
第6题：
（5）对 n 个记录的文件进行二路归并排序，所需要的辅助存储空间为___________。
（5）【答案】n
【解析】二路归并排序是在折半插入顺序的基础上再改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。
第7题：
（ 15 ）对 n 个记录的文件进行归并排序，所需要的辅助存储空间为
A ） O( 1 )
B ） O (log 2 n )
C ） O(n)
D ） O(n2）
第8题：
（15）对 n 个记录的文件进行起泡排序，所需要的辅助存储空间为
A）O(1)
B）O(log2n)
C）O(n)
D）O(n2)
（15）【答案】A)
【解析】冒泡法，直接选择法。直接插入法以及堆排序的辅助存储空间都为0（1），快速排序为0（log2n）,归并排序为0（n）。
第9题：
按排序策略分类，冒泡排序属于(59)。对n个记录的文件进行排序时，如果待排序文件中的记录初始时为所要求次序的逆序，则冒泡排序过程中需要进行(60)次元素值的比较。
(50)
A．插入排序
B．选择排序
C．交换排序
D．归并排序
第10题：
对n个记录的文件进行起泡排序，所需要的辅助存储空间为
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
解析：本题考查起泡排序的概念。起泡排序是将排序的记录顺次两两比较，若为逆序则进行交换。不管对多少个记录的文件进行起泡排序，所需要的辅助存储空间都为 O(1)。正确答案为选项A。