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

admin2009-02-15 34

问题堆排序是(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)业务的支持。

数据加密标准(DES)是一种分组密码，将明文分成大小(33)位的块进行加密，密钥长度为(34)位。

布线实施后需要进行测试，在测试线路的主要指标电，(23)是指一对线对相邻的另一对线通过电磁感应所产生的偶合信号。(24)是由于集肤效应、绝缘损耗、阻抗不匹配、连接电阻等因素，造成信号沿链路传输时的损失。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位，若每秒钟传送100个字符，采用4相相位调制，则码元速率为(16)，有效数据速率为(17)。

在网络的拓扑结构中，处于上层的结点称为(36)。只要有一个结点发生故障，网络通信就无法进行的结构是(37)；数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。

在网络的拓扑结构中，处于上层的结点称为(36)。只要有一个结点发生故障，网络通信就无法进行的结构是(37)；数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

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

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

A,心电轴+60。B,心电轴+20。C,心电轴+110。D,心电轴-45。E,心电轴+210。心电轴重度右偏

适于反映慢性病尤其是恶性肿瘤远期治疗效果的指标是

设计合同示范文本规定，发包人应向设计人提供的设计依据文件和资料包括(　　)。

其他因素不变的情况下，产品单价上升会带来的结果有()。

在资产化期间内，对于专门借款闲置资金产生的利息收入或投资收益应()。

下列关于正式承兑的必要记载事项说法正确的有()。

1954年12月，毛泽东在一次党内外人士座谈会上指出，政协仍有存在的必要，但是我们不能把政协搞成国家权力机关，此话的主要背景是()。

如果对通胀预期不加以正确管理、引导和化解的话，就可能被积累放大，最终导致通胀的实现。这说明()。

物权法所称的物权是指权利人依法对特定的物享有直接支配和排他的权利，因此物权是一种()。

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

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

软考中级

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

数据加密标准(DES)是一种分组密码，将明文分成大小(33)位的块进行加密，密钥长度为(34)位。

布线实施后需要进行测试，在测试线路的主要指标电，(23)是指一对线对相邻的另一对线通过电磁感应所产生的偶合信号。(24)是由于集肤效应、绝缘损耗、阻抗不匹配、连接电阻等因素，造成信号沿链路传输时的损失。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位，若每秒钟传送100个字符，采用4相相位调制，则码元速率为(16)，有效数据速率为(17)。

在网络的拓扑结构中，处于上层的结点称为(36)。只要有一个结点发生故障，网络通信就无法进行的结构是(37)；数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。

在网络的拓扑结构中，处于上层的结点称为(36)。只要有一个结点发生故障，网络通信就无法进行的结构是(37)；数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。

物理层的电气特性有多种标准，其中非平衡型标准规定(65)，电缆最大长度为(66)m。新的非平衡标准规定(67)，距离为10m时的最高数据率为(68)。在多种标准中，数据率最高的是新的平衡型标准，近距离传输其最高数据率可达(69)。

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

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

A,心电轴+60。B,心电轴+20。C,心电轴+110。D,心电轴-45。E,心电轴+210。心电轴重度右偏

适于反映慢性病尤其是恶性肿瘤远期治疗效果的指标是

设计合同示范文本规定，发包人应向设计人提供的设计依据文件和资料包括( )。

其他因素不变的情况下，产品单价上升会带来的结果有()。

在资产化期间内，对于专门借款闲置资金产生的利息收入或投资收益应()。

下列关于正式承兑的必要记载事项说法正确的有()。

1954年12月，毛泽东在一次党内外人士座谈会上指出，政协仍有存在的必要，但是我们不能把政协搞成国家权力机关，此话的主要背景是()。

如果对通胀预期不加以正确管理、引导和化解的话，就可能被积累放大，最终导致通胀的实现。这说明()。

物权法所称的物权是指权利人依法对特定的物享有直接支配和排他的权利，因此物权是一种()。

设计合同示范文本规定，发包人应向设计人提供的设计依据文件和资料包括(　　)。