对长度为n的关键字序列进行堆排序的空间复杂度为 ( )A．O(log2n)B．O(1)C．O(n)D．O(n*log2n)
题目
对长度为n的关键字序列进行堆排序的空间复杂度为 ( )
A．O(log2n)
B．O(1)
C．O(n)
D．O(n*log2n)
相似考题
更多“对长度为n的关键字序列进行堆排序的空间复杂度为 ( )A．O(log2n)B．O(1)C．O(n)D．O(n*log2n)”相关问题
-
第1题：
设平衡二叉排序树(AVL树)的节点个数为n，则其平均检索长度为
A．O(1)
B．O(log2n)
C．O(n)
D．O(n log2n)
正确答案：B
解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。只要二叉树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何节点的左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(n为节点个数)。因此，它的平均查找长度也和log2n同数量级。 -
第2题：
堆排序最坏情况下的时间复杂度为()。
A.O(n1.5)
B.O(nlog2n)
C.O{[n(n-1)]｝
D.O(log2n)
正确答案：B
-
第3题：
下列程序段的时间复杂度为()。
A.O(n)
B.O(log2n)
C.O(n3)
D.O(n2)
正确答案：A
-
第4题：
对n个记录的文件进行堆排序，最坏情况下的执行时间为
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
正确答案：C
解析：堆排序是完全二叉树结构的一个重要应用，是对直接选择排序的改进。对n个记录的文件进行堆排序，最坏情况下的执行时间与平均执行时间相同，都为O(nlog2n)，所以本题正确，答案为选项C。 -
第5题：
设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为
A．O(1)
B．O(log2n)
C．O(n)
D．O(n log2n)
正确答案：B
解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log2n同数量级。 -
第6题：
用堆排序方法，在最坏情况下的时间复杂度为( )。
A．O(n+1)
B．O(n2)
C．O(log2n)
D．O(n log2n)
正确答案：D
-
第7题：
用归并排序方法，在最坏情况下的时间复杂度为( )。
A．O(n+1)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
正确答案：D
解析：一个完整的归并排序需要进行[log2n)次，实现归并排序需要和代派序列元素个数等量的辅助空间，其时间复杂度为O(nlog2n)。 -
第8题：
设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_______。
A.O(1)
B.O(log2n)
C.O(n)
D.O(n2)
正确答案：C
-
第9题：
向堆中插入一个元素的时间复杂度为________。
A.O(log2n)
B.O(n)
C.O(1)
D.O(nlog2n)
正确答案：A
-
第10题：
对n个元素进行堆排序时，最坏情况下的时间复杂度为(53)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
正确答案：C
解析：堆排序性能比较稳定，即使在最坏情况下的时间复杂度也是O(nlog2n)。 -
第11题：
对n个记录的文件进行堆排序，最坏情况下的执行时间为
A．O(log2n)
B．0(n)
C．O(n log2n)
D．O(n2)
正确答案：C
解析：堆排序是完全二又树结构的一个重要应用，是对直接选择排序的改进。对n个记录的文件进行堆排序，最坏情况下的执行时间与平均执行时间相同，都为O(nlog2n)。 -
第12题：
冒泡排序在最好情况下的时间复杂度为（ ）。A.O（1）
B.O（log2n）
C.O（n）
D.O（n2）答案：C解析：若初始序列为“正序”，则只需进行一趟排序，在排序过程中进行n-l次比较，且不移动记录，因此时间复杂度为n。 -
第13题：
n个记录的文件进行快速排序，所需要的辅助存储空间为( )。
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
正确答案：B
解析：快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log2n，所以其空间复杂度为O(log2n)。 -
第14题：
下列程序段的时间复杂度为()。
A.O(n)
B.O(n-1)
C.O(n2)
D.O(log2n)
正确答案：B
-
第15题：
在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为
A．O(n)
B．O(1)
C．O(n2)
D．O(log2n)
正确答案：B
解析：在一个长度为n的顺序表的表尾插入一个新元素不需要进行节点移动，直接插入即可。对应的渐进时间复杂度为O(1) 。 -
第16题：
用快速排序的方法对包含n个关键字的序列进行排序，最坏情况下执行的时间为
A．O(n)
B．O(log2n)
C．O(nlog2n)
D．O(n2)
正确答案：D
解析：快速排序的平均执行时间为O(nlog2n)，优于冒泡排序，直接插入排序方法，但最坏的情况，即记录初始已排好序的情况下，执行时间为O(n2)。 -
第17题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(55)。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
正确答案：D
解析：快速排序在最坏情况下的时间复杂度退化到一般的交换排序，即为O(n2)。 -
第18题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为(65)。
A．O(log2n)
B．O(n)
C．O(nlog2/t)
D．O(n2)
正确答案：D
解析：比较常用的排序算法的平均时间复杂度，以及最坏情况下的时间复杂度，可以知道快速排序最坏情况下的时间复杂度为O(n2)。 -
第19题：
对n个记录的文件进行起泡排序，所需要的辅助存储空间为
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
正确答案：A
解析：本题考查起泡排序的概念。起泡排序是将排序的记录顺次两两比较，若为逆序则进行交换。不管对多少个记录的文件进行起泡排序，所需要的辅助存储空间都为 O(1)。正确答案为选项A。 -
第20题：
对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______
A.O（1）
B.O（logn）
C.O（n）
D.O（nlogn）
正确答案：D
-
第21题：
对n个元素进行堆排序时，其空间复杂度为( )。
A．O(log2n)
B．O(n log2n)
C．O(n)
D．O(1)
正确答案：D
解析：堆排序每次都选出最大或最小的结点，需要的辅助空间始终只需要一个。 -
第22题：
对n个记录的序列进行快速排序，所需的辅助存储空间为( )。
A．O(1)
B．O(log2n)
C．O(n)
D．O(n2)
正确答案：B
解析：快速排序对待排序序列的划分大约为log2n次，而快速排序是通过递归算法来完成的，递归深度大约为log2n，因此所需的辅助存储空间为O(log2n)。 -
第23题：
对n个元素进行快速排序时，最坏情况下的时间复杂度为______。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
正确答案：D
解析：最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。其时间复杂度为0(n2)。