对于n个元素的关键字序列｛k1k2，…Kn｝，当且仅当..

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

第 43 题


知识点	二叉树的应用堆
章/节	常用数据结构

对于n个元素的关键字序列｛k₁,k₂，…K_n｝，当且仅当满足K_i≤K_2i；且Ki≤K_2i+₁称该序列为小顶堆。由此可知( )小顶堆。

A. 17, 12, 13, 14, 15, 16, 11

B. 11, 15, 13, 17, 16, 14, 12

C. 17, 16, 14, 12, 15, 13, 11

D. 11, 14, 12, 15, 16, 13, 17

相关试题常用数据结构

第35题

2011年下半年

设数组a[1..m，1..n] (m>1, n>2)中的元素以行为主序存放，每个元素占用1个存储单元，则最后一个数组元素a[m.n]相对于数组空间首地址的偏移量为(35)。

第37题

2013年上半年

不适合采用栈结构的是（37)。

第42题

2014年下半年

对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是（42）；若将该图用邻接矩阵存储，则矩阵中的非0元素数目为（43）。

知识点讲解

· 二叉树的应用

· 堆

二叉树的应用

二叉树运算是数据结构的重要内容，为加深对二叉树内容的理解，这里给出一些应用实例。为方便描述，二叉树的顺序存储结构用一维数组R表示，而二叉链表的节点存储结构定义如下：

（1）以二叉链表为存储结构，写一个算法用括号形式（key, LT, RT）打印二叉树，其中key是根节点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一个节点x的树打印形式是x，而不应是（X,）的形式。相应的算法如下：

（2）建立哈夫曼树和哈夫曼编码。

建立哈夫曼树和哈夫曼编码的代码如下：

（3）将已知二叉树改建为中序线序树。

将已知二叉树改建为中序线序树算法的主要思路是：对二叉树进行中序遍历，若当前被访问节点的左子节点指针为空，则让它指向当前节点的前驱节点；若其前驱节点的右子节点指针为空，则让它指向当前节点。相应的算法如下：

堆

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