对数组A=(28713564）构建大顶堆为( )(用数组表示)

免费智能真题库 > 历年试卷 > 软件设计师 > 2021年上半年软件设计师上午试卷综合知识

第39题

知识点：堆数组

关键词：数组章/节：计算机软件知识

对数组A=(2,8,7,1,3,5,6,4）构建大顶堆为( )(用数组表示)

A. (1,2,3,4,5,6,7,8)

B. (1,2,5,4,3,7,6,8)

C. (8,4,7,2,3,5,6,1)

D. (8,7,6,5,4,3,2,1)

相关试题：数组

更多>

第22题 2016年下半年

14%

二维数组a[1..N，1..N]可以按行存储或按列存储。对于数组元素a[i,j]（1<=i,j<=N），当（22）时，在按行和按列两种存储方式..

第65题 2012年上半年

34%

现要对n个实数（仅包含正实数和负实数）组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪..

第61题 2017年上半年

23%

在12个互异元素构成的有序数组a[1..12] 中进行二分查找(即折半查找，向下取整)，若待查找的元素正好等于a[9]，则在此过程中，依次..


知识点讲解
· 堆 · 数组

堆

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维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。

对数组进行的基本运算有以下两种。

（1）给定一组下标，存取相应的数据元素。

（2）给定一组下标，修改相应的数据元素中某个数据项的值。

数组的顺序存储

一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((i-1)n+(j-1))L

同样的，以列为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((j-1)m+(i-1))L

题号导航 2021年上半年软件设计师上午试卷综合知识

本试卷我的完整做题情况



	第39题在手机中做本题