计算机三级
对n个记录的文件进行归并排序,所需要的辅助存储空间为A．OB．O(n)C．O(log2n)D．O(n2)
题目
对n个记录的文件进行归并排序,所需要的辅助存储空间为
A．O
B．O(n)
C．O(log2n)
D．O(n2)
相似问题和答案
第1题：
（15）对 n 个记录的文件进行起泡排序，所需要的辅助存储空间为
A）O(1)
B）O(log2n)
C）O(n)
D）O(n2)
（15）【答案】A)
【解析】冒泡法，直接选择法。直接插入法以及堆排序的辅助存储空间都为0（1），快速排序为0（log2n）,归并排序为0（n）。
第2题：
（5）对 n 个记录的文件进行二路归并排序，所需要的辅助存储空间为___________。
（5）【答案】n
【解析】二路归并排序是在折半插入顺序的基础上再改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。
第3题：
对n个记录的文件进行堆排序，最坏情况下的执行时间为
A．O（log2n）
B．O（n）
C．O（n log2n）
D．O（n2）
第4题：
对n个记录的文件进行堆排序，最坏情况下的执行时间为
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
解析：堆排序是完全二叉树结构的一个重要应用，是对直接选择排序的改进。对n个记录的文件进行堆排序，最坏情况下的执行时间与平均执行时间相同，都为O(nlog2n)，所以本题正确，答案为选项C。
第5题：
（ 15 ）对 n 个记录的文件进行归并排序，所需要的辅助存储空间为
A ） O( 1 )
B ） O (log 2 n )
C ） O(n)
D ） O(n2）
第6题：
对N个记录的文件进行快速排序，所需要的辅助存储空间为
A．O( )
B．O
C．O( )
D．O( )
第7题：
n个记录的文件进行快速排序，所需要的辅助存储空间为( )。
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
解析：快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log2n，所以其空间复杂度为O(log2n)。
第8题：
对n个记录的文件进行归并排序，所需要的辅助存储空间为
A．O（1）
B．O（n）
C．O（log2n）
D．O（n2）
第9题：
用二分法进行插入排序，记录移动个数为
A．O(nlog2n)
B．O(n2)
C．O(log2n)
D．O(n)
解析：二分法插入排序关键码比较次数为O (nlog2n)，记录移动个数为O(n2)。
第10题：
用快速排序的方法对包含n个关键字的序列进行排序，最坏情况下执行的时间为
A．O(n)
B．O(log2n)
C．O(nlog2n)
D．O(n2)
解析：快速排序的平均执行时间为O(nlog2n)，优于冒泡排序，直接插入排序方法，但最坏的情况，即记录初始已排好序的情况下，执行时间为O(n2)。