n个关键码构成的序列{kk2 ...K}当且仅当满足下列关系时称其为堆。<br /> 以下关键码..

2021年下半年上午试卷综合知识

第 58 题


知识点	堆堆排序
章/节	计算机软件知识

n个关键码构成的序列{k,k2, ...K,}当且仅当满足下列关系时称其为堆。

以下关键码序列中，（）不是堆。

A. 15,25,21,53,73, 65,33

B. 15,25,21,33,73,65,53

C. 73,65,25,21,15,53,33

D. 73,65,25,33,53,15,21

相关试题排序

第38题

2021年上半年

对于一个初始无序的关键字序列，在下面的排序方法中，( ）第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。
①直接插入排序②冒泡排序③简单选择排序④堆排..

第61题

2010年上半年

对以下四个序列用直接插入排序方法由小到大进行排序时，元素比较数最少的是 (61).

第64题

2015年下半年

在某应用中，需要先排序一组大规模的记录，其关键字为整数。若这组记录的关键字基本上有序，则适宜采用（64）排序算法。若这组记录的关键字的取值均在0到9之间（含），则适宜采用（65）排序算法..

知识点讲解

· 堆

· 堆排序

堆

1）定义

n个元素的序列{k₁, k₂, …, k_n｝当且仅当满足以下的关系式时才称之为堆：

或

，并相应地称为小顶堆或大顶堆。

2）判断办法

判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。

3）典型应用

堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点k_i都没有子节点，以这样的k_i为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k_[n/2]， k_［n/2]-1, …, k₂, k₁为根的子树满足堆的定义。

注意：堆与一棵完全二叉树对应，但堆本身是线性表。

堆排序

对于n个元素的关键字序列K₁,K₂,…,K_n，当且仅当所有关键字都满足下列性质时称其为堆，即

若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。

堆排序的基本思想是：对一组待排序记录的关键字，首先把它们按堆的定义排成一个堆序列，从而输出堆顶的最小关键字（对于小根堆而言），然后将剩余的关键字再调整成新堆，便得到次小的关键字，如此反复进行，直到全部关键字排成有序序列为止。

对于记录数较少的文件来说，堆排序的优越性并不明显，但对大量的记录来说堆排序是很有效的。堆排序的整个算法时间是由建立堆和不断调整堆这两部分时间代价构成的，堆排序算法的时间复杂度为O(nlog₂n)。此外，堆排序只需要一个记录大小的辅助空间。但是堆排序是一种不稳定的排序方法。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5