问答题

最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。
(1)画出在图中插入关键字为5的结点后的最小最大堆。 (2)画出在图中插入关键字为80的结点后的最小最大堆。 (3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。

答案：正确答案：此题考查的知识点是堆的算法。将插入的元素放到最后，然后调整，方法同第13题。 (1)加入关键字值为5的结点后，...

你可能感兴趣的试题

已知关键字序列(K ₁ ，K ₂ ，K ₃ ，…，K _n-1 )是大根堆。试写出一算法将(K ₁ ，K ₂ ，K ₃ ，…，K _n-1 ，K _n )调整为大根堆，并利用调整算法写一个建大根堆的算法。

答案：正确答案：void sift(RecType R[]，int n){ ／／把R[n]调成大堆 int j=n；R[0]=...

最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。
(1)画出在图中插入关键字为5的结点后的最小最大堆。 (2)画出在图中插入关键字为80的结点后的最小最大堆。 (3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。

答案：正确答案：此题考查的知识点是堆的算法。将插入的元素放到最后，然后调整，方法同第13题。 (1)加入关键字值为5的结点后，...

输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。

答案：正确答案：typedef struct{ int key； int next； }SLRecType； SLRecTyp...

设有15 000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由

答案：正确答案：上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据...

对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较为什么请给出相应实例。

答案：正确答案：(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度...

判断下列序列是否为堆，若不是堆，则把它们调整为堆。 (1)(100，85，95，75，80，60，82，40，20，10，65) (2)(100，95，85，82，80，75，65，60，40，20，10) (3)(100，85，40，75，80，60，65，95，82，10，20) (4)(10，20，40，60，65，75，80，82，85，95，100)

答案：正确答案：依据堆定义可知：序列(1)、(2)、(4)是堆，(3)不是堆，从而可对其调整使之成为大根堆(100，95，65...

将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响各是多少

答案：正确答案：因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为r，显然，...

写出快速排序的非递归算法。

答案：正确答案：设对记录R[1．．n]进行快速排序，要求用非递归算法。利用一个包含有low和high两个整数成员的记录数组st...

试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

答案：正确答案：采用类似于快速排序中的划分思想。算法如下： void part(KeyType A[]，int n){ int...

写一个HeapInsen(R,key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。

答案：正确答案：算法如下： typedef struct{ KeyType key； InfoType otherinfo； ...

写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。

答案：正确答案：建立堆的算法如下： void BuildHeap(SeqList R，KeyType A[n]){ ／／类型定...