早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
A.O(n2)和O(1)B.O(nlog2n)和O(1)C.O(nlog2n)和O(n)D.O(n2)和O(1)
题目
A.O(n2)和O(1)
B.O(nlog2n)和O(1)
C.O(nlog2n)和O(n)
D.O(n2)和O(1)
参考答案
正确答案:B
解析:堆排序是一种树形选择排序,是对直接选择排序的有效改进。堆排序来源于一种称为比赛树的排序方法。用比赛树进行排序的方法是:先对n个结点的键值进行两两比较,再对其中n/2个较大的键值之间作两两比较,依此类推,直至选出键值最大的结点。这个过程可用一棵有2n-1个结点的丰满二叉树来表示,二叉树的叶子结点是待排序的结点序列,二叉树的非叶子结点是层层比较产生的结点。除第一个最大者需比较n-1次外,选其他任一结点都只需从叶结点到根结点路径上那些结点的比较,其比较次数与二叉树的高度相对应,比较次数为O(log2n)。总比较次数为O(nlog2n)。堆排序的过程为:(假设是大顶堆)初始时调整n个结点的存储顺序,使之成为一个堆,这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换,并对少了一个结点后的n-1结点重新作调整,使之再次成为堆。这样,在根结点得到结点序列键值次最大者。再次将堆的根结点与堆的最后一个结点交换,并重新使又少了一个结点的序列调整成为堆。依此类推,直至只有两个结点的堆,并对它们作交换,最后得到有序的n个结点序列。所以堆排序的思想是:选择最大的结点与最后一个结点交换,然后选择次最大结点与倒数第二个结点交换,…,所以堆排序是选择类排序,它只需要1个附加的存储空间。
解析:堆排序是一种树形选择排序,是对直接选择排序的有效改进。堆排序来源于一种称为比赛树的排序方法。用比赛树进行排序的方法是:先对n个结点的键值进行两两比较,再对其中n/2个较大的键值之间作两两比较,依此类推,直至选出键值最大的结点。这个过程可用一棵有2n-1个结点的丰满二叉树来表示,二叉树的叶子结点是待排序的结点序列,二叉树的非叶子结点是层层比较产生的结点。除第一个最大者需比较n-1次外,选其他任一结点都只需从叶结点到根结点路径上那些结点的比较,其比较次数与二叉树的高度相对应,比较次数为O(log2n)。总比较次数为O(nlog2n)。堆排序的过程为:(假设是大顶堆)初始时调整n个结点的存储顺序,使之成为一个堆,这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换,并对少了一个结点后的n-1结点重新作调整,使之再次成为堆。这样,在根结点得到结点序列键值次最大者。再次将堆的根结点与堆的最后一个结点交换,并重新使又少了一个结点的序列调整成为堆。依此类推,直至只有两个结点的堆,并对它们作交换,最后得到有序的n个结点序列。所以堆排序的思想是:选择最大的结点与最后一个结点交换,然后选择次最大结点与倒数第二个结点交换,…,所以堆排序是选择类排序,它只需要1个附加的存储空间。
看了A.O(n2)和O(1)B.O...的网友还看了以下:
等比数列an的前n项和味Sn,已知对任意的n属于正整数,点(n,Sn)均在函数y=b^x+r(b> 数学 2020-05-13 …
1、等比数列中,知道a3=1,S3=13,怎么得出q=1/3?2、已知nS(n+1)>(n+1)S 数学 2020-06-04 …
已知向量p=(an,n),向量q=(a(n+1),n+1),(n∈N*),若a1=3,向量p‖向量 数学 2020-07-12 …
紧急!设数列bn满足b1=1,bn>0(n=2,3.)其前n项乘积Tn=(a^(n-1)bn)^n 数学 2020-07-18 …
数列求通项的问题数列a1=1a(n+1)=2Sn+1(打括号的n-1是下标)求{an}用S(n+1 数学 2020-07-29 …
时间复杂度对数阶是什么样的T(n)=T(n-1)+1/n=T(n-2)+1/(n-1)+1/n=T 数学 2020-07-30 …
一道关于极限的高数题设x(n+1)=ln(1+xn),x1>0第一个问题:求lim(n趋于正无穷) 数学 2020-07-30 …
对于不等式<n+1(n∈N*),某同学用数学归纳法的证明过程如下:(1)当n=1时,<1+1,不等 其他 2020-08-03 …
证明组合性质:C(n+1,m)=C(n,m)+C(n,m-1)C(n+1,m)=(n+1)!/m!( 数学 2020-11-01 …
一次函数y=k1x+b和反比例函数y=k2/x的图像相交与P(n-1,n+1).点Q(0,a)在函数 数学 2021-02-01 …