计算机二级
对n个记录的序列进行快速排序，所需的辅助存储空间为( )。A．O(1)B．O(log2n)C．O(n)D．O(n2)
题目
对n个记录的序列进行快速排序，所需的辅助存储空间为( )。
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
相似问题和答案
第1题：
直接选择排序的时间复杂度为()。（n为元素个数）
A.O（n）
B.O（log2n）
C.O（nlog2n）
D.O（n2）
第2题：
用二分法进行插入排序，记录移动个数为
A．O(nlog2n)
B．O(n2)
C．O(log2n)
D．O(n)
解析：二分法插入排序关键码比较次数为O (nlog2n)，记录移动个数为O(n2)。
第3题：
对n个记录的文件进行堆排序，最坏情况下的执行时间为
A．O（log2n）
B．O（n）
C．O（n log2n）
D．O（n2）
第4题：
用快速排序的方法对包含n个关键字的序列进行排序，最坏情况下执行的时间为
A．O(n)
B．O(log2n)
C．O(nlog2n)
D．O(n2)
解析：快速排序的平均执行时间为O(nlog2n)，优于冒泡排序，直接插入排序方法，但最坏的情况，即记录初始已排好序的情况下，执行时间为O(n2)。
第5题：
对于快速排序，元素有序排列时的时间复杂度为(57)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：对于快速排序，元素有序排列是其最坏情况，时间复杂度为O(n2)。当每次划分都可以将待排序列分为均匀的两部分时，进行的排序趟数最少，时间复杂度为O(nlog2n)。
第6题：
n个记录的文件进行快速排序，所需要的辅助存储空间为( )。
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
解析：快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log2n，所以其空间复杂度为O(log2n)。
第7题：
对长度为n的关键字序列进行堆排序的空间复杂度为 ( )
A．O(log2n)
B．O(1)
C．O(n)
D．O(n*log2n)
解析：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1)，但它是不稳定的。
第8题：
对n个记录的文件进行归并排序，所需要的辅助存储空间为
A．O（1）
B．O（n）
C．O（log2n）
D．O（n2）
第9题：
对n个记录的文件进行堆排序，最坏情况下的执行时间为
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：堆排序是完全二叉树结构的一个重要应用，是对直接选择排序的改进。对n个记录的文件进行堆排序，最坏情况下的执行时间与平均执行时间相同，都为O(nlog2n)，所以本题正确，答案为选项C。
第10题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(55)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：快速排序在最坏情况下的时间复杂度退化到一般的交换排序，即为O(n2)。