堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。

admin2009-02-15 29

问题堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。

选项 A、O(n²)和O(1)
B、O(nlog₂n)和O(1)
C、O(nlog₂n)和O(n)
D、O(n²)和O(1)

答案B

解析堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆排序来源于一种称为比赛树的排序方法。用比赛树进行排序的方法是：先对n个结点的键值进行两两比较，再对其中n/2个较大的键值之间作两两比较，依此类推，直至选出键值最大的结点。这个过程可用一棵有2n-1个结点的丰满二叉树来表示，二叉树的叶子结点是待排序的结点序列，二叉树的非叶子结点是层层比较产生的结点。除第一个最大者需比较n-1次外，选其他任一结点都只需从叶结点到根结点路径上那些结点的比较，其比较次数与二叉树的高度相对应，比较次数为O(log₂n)。总比较次数为O(nlog₂n)。
堆排序的过程为：(假设是大顶堆)初始时调整n个结点的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大者。再次将堆的根结点与堆的最后一个结点交换，并重新使又少了一个结点的序列调整成为堆。依此类推，直至只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。所以堆排序的思想是：选择最大的结点与最后一个结点交换，然后选择次最大结点与倒数第二个结点交换，…，所以堆排序是选择类排序，它只需要1个附加的存储空间。

转载请注明原文地址:https://kaotiyun.com/show/5TxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。

软件设计师上午基础知识考试

软考中级

ATM网络的协议数据单元称为(21)。ATM适配层分为2个子层，这2个子层是(22)子层。(23)是对应于A类业务的ATM适配层，它提供的业务特点是(24)。如果要传送IP数据报，则需要(25)业务的支持。

甲、乙两人在同一时间就同样的发明创造提交了专利申请，专利局将分别向各申请人通报有关情况，并提出多种解决这一问题的办法，不可能采用(21)的办法。

两个公司希望通过Internet传输大量敏感数据，从信息源到目的地之间的传输数据以密文形式出现，而且不希望由于在传输结点使用特殊的安全单元而增加开支，最合适的加密方式是()，使用会话密钥算法效率最高的是()。

两个公司希望通过Internet传输大量敏感数据，从信息源到目的地之间的传输数据以密文形式出现，而且不希望由于在传输结点使用特殊的安全单元而增加开支，最合适的加密方式是()，使用会话密钥算法效率最高的是()。

在异步通信中，每个字符包含1位起始位，7位数据位，1位奇偶位和2位终止位，每秒传送100个字符，则有效数据速率为____________。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶校验位和1位终止位，每秒钟传送100个字符，则有效数据速率为()。

Wheredoesthespeakercomefrom?

注射剂的质量要求不包括

“五五”普法规划实施的时间是()。

下列关于注册城市规划师的权利义务，不正确的是()。

根据《城市居民委员会组织法》的规定，居民会议的召集者是()。

由卢扎诺夫创立的()注重强化联想，利用人的可暗示性，使理智与感情统一，有意识功能与无意识功能统一，使学生在愉快的气氛中接受有效的更多的信息。

()是公安工作贯彻群众路线的重要方面，是公安机关执法思想的核心。

下列成员中不属于主窗口的是

EGG:CHICKEN