对于含有n个元素的关键码序列{k1k2...kn}当且仅当满..

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

第 42 题


知识点	堆排序堆
关键词	关键码
章/节	常用算法

对于含有n个元素的关键码序列{k₁,k₂,...,k_n},当且仅当满足关系k_i≤k_2i且k_i≤k_2i+1(i=1,2,...,[n/2])时称为小根堆。下面关键码序列中，（42)是小根堆。

A. 131,158,288,325,763,522,451,617

B. 131,325,451,617,522,288,158,763

C. 763,617,325,522,451,288,131,158

D. 763,451,522,617,131,288,325,158

相关试题常用算法

第39题

2016年下半年

若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选..

第9题

2023年下半年

若构造哈希表时不发生冲突，则给定的关键字与其哈希地址之间的对应关系是 (43) 。 (其中n>1且m>1)

第43题

2010年下半年

排序和快速排序方法中，能在第一趟排序结束后就得到最大（或最小）元素的排序方法是（43)。

知识点讲解

· 堆排序

· 堆

堆排序

1）堆的概念

对于n个元素的关键字序列｛k_1,k_2,…,k_n｝，当且仅当所有关键字都满足下列关系时称其为堆：

或

从序列元素间的关系来看，堆是一棵完全二叉树的层次序列。显然，堆顶元素为序列中n个元素的最小值（或最大值）。若堆顶为最小元素，则称为小根堆；若堆顶为最大元素，则称为大根堆。

2）堆排序的基本思想（小根堆）

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

堆

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₁为根的子树满足堆的定义。

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

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

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