【考研类试卷】计算机专业基础综合数据结构（排序）-试卷2及答案解析.doc

《【考研类试卷】计算机专业基础综合数据结构（排序）-试卷2及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机专业基础综合数据结构（排序）-试卷2及答案解析.doc（9页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业基础综合数据结构（排序）-试卷 2 及答案解析(总分：56.00，做题时间：90 分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.采用简单选择排序，比较次数与移动次数分别为( )。（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n)D.O(nlog 2 n)，O(n)3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（分数：2.00）A.堆排序快速排序归并排序B.堆排序归并

2、排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（分数：2.00）A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，825.已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)

3、，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（分数：2.00）A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，956.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35

4、，27，47，68，84 (4)15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00）A.直接选择排序B.希尔排序C.归并排序D.快速排序7.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较( )次。（分数：2.00）A.1B.2C.3D.48.将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是( )。（分数：2.00）A.NB.2N 一 1C.2ND.N 一 19.已知待排序的 n 个元素可分为 nk 个组，每个组包含 k 个元素

5、，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 k)C.O(klog 2 n)D.O(klog 2 k)10.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1911.归并排序

6、中，归并的趟数是( )。（分数：2.00）A.O(n)B.O(log 2 n)C.O(nlog 2 n)D.O(n 2 )12.有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，15，7，9D.A、B、C 均不对13.基于比较方法的 n 个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。（分数：2.00）A.O(nlog 2 n)B.O(log 2 n)C.O(n)D.D(n 2 )14.以下排序方法中，

7、稳定的排序方法是( )。（分数：2.00）A.直接插入排序B.直接选择排序C.堆排序D.基数排序15.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定 d 0 =9，d 1 =4，d 2 =2，d 3 =1，则第二趟排序结束后前 4 条记录为( )。（分数：2.00）A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40)D.(15，20，80，70)16.在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（分数：2.00）A.5，4，

8、8B.6，3，9C.7，4，3D.3，8，2二、综合应用题(总题数：12，分数：24.00)17.综合应用题 41-47 小题。（分数：2.00）_18.已知关键字序列(K 1 ，K 2 ，K 3 ，K n-1 )是大根堆。试写出一算法将(K 1 ，K 2 ，K 3 ，K n-1 ，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。（分数：2.00）_19.最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 （分数：2.00）_20

9、.输入 N 个只含一位数字的整数，试用基数排序的方法，对这 N 个数排序。（分数：2.00）_21.设有 15 000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素。 在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?（分数：2.00）_22.对一个具有 7 个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。（分数：2.00）_23.判断下列序列是否为堆，若不是堆，则把它们调整为堆。 (1)(100，85，95，75，80，60，82，40，

10、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)（分数：2.00）_24.将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?（分数：2.00）_25.写出快速排序的非递归算法。（分数：2.00）_26.试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。（分数：2.00）_27.写一个 H

11、eapInsen(R,key)算法，将关键字插入到堆 R 中，并保证插入后 R 仍是堆。请分析算法的时间复杂度。提示：将 key 先插入 R 中已有元素的尾部(即原堆的长度加 1 的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。（分数：2.00）_28.写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。（分数：2.00）_计算机专业基础综合数据结构（排序）-试卷 2 答案解析(总分：56.00，做题时间：90 分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最

12、符合题目要求的。（分数：2.00）_解析：2.采用简单选择排序，比较次数与移动次数分别为( )。（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n) D.O(nlog 2 n)，O(n)解析：解析：简单选择排序的关键字比较次数 KCN 与对象的初始排列无关。第 i 趟选择具有最小关键字对象所需的比较次数总是 ni1 次(此处假定整个待排序对象序列有 n 个对象)。因此，总的关键字比较次数为：3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（分数：2.00）A.堆排序快速排序归并排序 B.堆排序归并排

13、序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序解析：解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为 O(1)，快速排序为 O(log 2 n)，归并排序为 O(n)。应选 A。4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（分数：2.00）A.16，25，35，48，23，40，79，82，36，72 B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，

14、25，35，48，79，23，36，40，72，82解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为 A。5.已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（分数：2.00）A.16，28，34，54，73，

15、62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95 C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，95解析：解析：冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选 B。6.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (

16、4)15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00）A.直接选择排序 B.希尔排序C.归并排序D.快速排序解析：解析：可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为 A。7.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较( )次。（分数：2.00）A.1B.2C.3 D.4解析：解析：第 6 趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入 60，要与 95、70 和 50进行比较，共比较 3 次，本

17、题答案为 C。8.将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是( )。（分数：2.00）A.N B.2N 一 1C.2ND.N 一 1解析：解析：此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为 N。9.已知待排序的 n 个元素可分为 nk 个组，每个组包含 k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 k) C.O(klog 2 n)D.O(klog

18、2 k)解析：解析：此题考查的知识点是分块排序的思想。因组与组之间已有序，故将 nk 个组分别排序即可，基于比较的排序方法每组的时间下界为 O(klog 2 k)。可以用二叉树分治形式描述，最好的情况是树的高度为 log 2 k。全部时间下界为 O(nlog 2 k)。应选 B。10.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，

19、28，20，15，22，19解析：解析：根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：11.归并排序中，归并的趟数是( )。（分数：2.00）A.O(n)B.O(log 2 n) C.O(nlog 2 n)D.O(n 2 )解析：解析：此题考查的知识点是归并排序。第 1 遍归并的子序列长度为 2 0 ，第 2 遍为 2 1 ，第i 遍为 2 i-1 ，所以由 2 i-1 n 知，对 n 个记录的数据集合，总共需要归并 log 2 n 次。应选 B。12.有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（分数：2.00）A.一 1，

20、4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，15，7，9 D.A、B、C 均不对解析：解析：此题考查的知识点是堆排序。应选 C。13.基于比较方法的 n 个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。（分数：2.00）A.O(nlog 2 n) B.O(log 2 n)C.O(n)D.D(n 2 )解析：解析：此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行 log 2 (n!)次比较。由 Stirling 公式可知，log 2 (n!)=nlog 2 n

21、一144n+O(log 2 n)。所以基于关键字比较的分类时间的下界是 O(nlog 2 n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选 A。14.以下排序方法中，稳定的排序方法是( )。（分数：2.00）A.直接插入排序 B.直接选择排序C.堆排序D.基数排序解析：解析：下表为各种排序方法的性能比较。由表可知，本题答案为 A。15.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定 d 0 =9，d 1 =4，d 2 =2，d 3 =1，则第二趟排序结束后前 4 条记录为( )。（分数：2.00）A.(50，20，15，70)B.(60

22、，45，80，50)C.(15，20，50，40) D.(15，20，80，70)解析：解析：t=3，d 0 =9，d 1 =4，d 2 =2，d 3 =1，第 1 趟(d 1 =4)后的结果为(15，40，60，20，50，70，95，45，80)，第 2 趟(d 2 =2)后的结果为(15，20，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。16.在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（分数：2.00）A.5，4，8 B.6，3，9C.7，4，3D.3，8，

23、2解析：解析：n=20，共需进行log 2 n=5 趟归并，第 1 趟归并后成为 10 个有序表，第 2 趟归并后成为 5个有序表(每个长度为 4)，第 3 趟归并将长度为 4 个的有序表归并为长度为 8 的有序表，本题答案为：5，4，8.二、综合应用题(总题数：12，分数：24.00)17.综合应用题 41-47 小题。（分数：2.00）_解析：18.已知关键字序列(K 1 ，K 2 ，K 3 ，K n-1 )是大根堆。试写出一算法将(K 1 ，K 2 ，K 3 ，K n-1 ，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。（分数：2.00）_正确答案：(正确答案：void s

24、ift(RecType R，int n) 把 Rn调成大堆 int j=n；R0=Rj； for(i=n2；i=1；i=i2) if(R0keyRikey)Rj=Ri；j=i； else break； Rj=R0； void HeapBuilder(RecType R，int n) for(i=2；i=n；i+)sift(R，i)； 提示：此题考查的知识点是堆的插入算法。从第 n 个记录开始依次与其双亲(n2)比较，若大于双亲则交换，继而与其双亲的双亲比较，以此类推直到根为止。)解析：19.最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最

25、大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 （分数：2.00）_正确答案：(正确答案：此题考查的知识点是堆的算法。将插入的元素放到最后，然后调整，方法同第 13题。 (1)加入关键字值为 5 的结点后，最小最大堆如下图。 (2)加入关键字值为 80 的结点后，最小最大堆如下图。 )解析：20.输入 N 个只含一位数字的整数，试用基数排序的方法，对这 N 个数排序。（分数：2.00）_正确答案：(正确答案：typedef struct int key； int next； SLRecType； SLRecType RN+1； typede

26、f struct int f，e： SLQueue； SLQueue B10； int Radixsort(SLRecType R，int n) 设各关键字已输入到 R 数组中 for(i=1；in；i+)Rinext=i+l； Rnnext=一 1；P=1； 一 1 表示静态链表结束 for(i=0；i=9：i+) 设置队头队尾指针初值 Bif=一1；Bie=一 1； while(p!=一 1) 一趟分配 k=Rpkey； 取关键字 if(Bkf=一 1)Bkf=p； 修改队头指针 else RBkenext=p： Bke=p； p=Rpnext； 下一记录 i=0： 一趟收集 while(

27、Bif=一 1)i+； t=Bie；p=Bif： while(i9) i+： if(Bif!=一 1)Rtnext=Bif；t=Bie： Rtnext=一 1； return p；返回第一个记录指针 提示：此题考查的知识点是基数排序。基数排序法又称“桶子法”(Bucket Sort)，它是透过键值的部分信息，将要排序的元素分配至某些“桶”中，达到排序的目的。基数排序法是属于稳定性的排序，其时间复杂度为 O(dn)，其中 d 为所采取的基数，而 n 为关键字数。本题是基数排序的特殊情况，关键字只含一位数字的整数。若关键字含 d 位，则要进行 d 趟分配和 d 趟收集。关键字最好放入字符数组，以便

28、取关键字的某位。)解析：21.设有 15 000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素。 在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?（分数：2.00）_正确答案：(正确答案：上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，如果在一个大量数据的文件中，如含有 15 000 个元素的记

29、录文件中选取前 10 个最大的元素，宜采用堆排序。)解析：22.对一个具有 7 个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。（分数：2.00）_正确答案：(正确答案：(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为 n=2k 一 1，显然，第一遍划分得到两个长度均为n2的子文件。第二遍划分得到 4 个长度均为n4的子文件，以此类推，总共进行 k=log 2 (n+1)遍划分，各文件的长度均为 l，此时排序结束。由于 n

30、=7，k=3，在最好情况下，第一遍经过 6 次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为 3)进行排序，各需要 2 次，这样就可将整个文件排序完毕，从而知 n=7 的最好情况下需进行 10 次比较。例如：4，7，5，6，3，1，2。 (2)在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小)，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为 O(n 2 )，反而不快了。对于 n=7 的记录

31、文件，显然最坏情况下的比较次数为 21。例如：7，6，5，4，3，2，1.)解析：23.判断下列序列是否为堆，若不是堆，则把它们调整为堆。 (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)（分数：2.00）_正确答案：(正确答案：依据堆定义可知：序列(1)、(2)、(4)是堆，(3)不是堆，从而可对其调整使之成为大根堆(100，95，6

32、5，85，80，60，40，75，82，10，20)。)解析：24.将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?（分数：2.00）_正确答案：(正确答案：因为基数排序所需的时间不仅与文件的大小 n 有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为 r，显然，十进制数基数为 10，二进制数的基数为 2。要建立 r 个空队列所需时间为 O(r)；把 n 个记录分放到各个队列中，重新收集起来需要的时间为 O(n)，因此一趟排序所需的时间复杂度为 O(n+r)；若每个关键字有 d 位，则总共要进行 d 遍排序，所以基数排序的时间复杂度为 O(d(

33、n+r)。由于关键字的位数 d 与基数 r 和最大关键字取值有关。因此不同的 r 和关键字将需要不同的时间。所以，本题中总的时间复杂度为 O(d(n+2)，d 为关键字最大值对应的二进制数位数，即将十进制的关键字用二进制数表示时，复杂度增大了。另外只需要设置两个指针队列，即将十进制的关键字用二进制数表示时，空间复杂性减少了。)解析：25.写出快速排序的非递归算法。（分数：2.00）_正确答案：(正确答案：设对记录 R1n进行快速排序，要求用非递归算法。利用一个包含有 low 和high 两个整数成员的记录数组 stack作为栈，low 和 high 成员分别指示某个子文件的首、尾记录的下标号。

34、算法如下： void quicksort(SeqList R，int n)设待排序记录放在 R1n中，下标从 1开始 int i，j，low，high，top=0； struct int low，high； stackMax； Max 为一个大于 n的常量 RecType temp； top=1；stacktoplow=1；stacktophigh=n；入栈 while(top0) 栈非空，则取出一个子文件进行划分 low=stacktoplow；high=stacktophigh；top 一一；出栈 i=low；j=high；temp=Ri； do while(ij&Rikeytempkey

35、)j-； if(ij) Ri=Rj；i+； while(ij&Rikeytempkey)i+； if(ij)Rj=Ri；j 一一； while(i=j)； 划分结束 Ri=temp； 基元元素插入 if(i+1high) 右子文件有两个以上记录，则首、尾位置入栈 top+：stacktoplow=i+1；stacktophigh=high； if(lowi 一 1) 左子文件有两个以上记录，则首、尾位置入栈 top+；stacktoplow=low；stacktophigh=i 一 1； )解析：26.试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之

36、前，并分析算法的时间复杂度。（分数：2.00）_正确答案：(正确答案：采用类似于快速排序中的划分思想。算法如下： void part(KeyType A，int n) int i=1；j=n； KeyType temp； while(ij) while(ij&Aj=0)j-一； 从右向左找负数 while(ij&Ai0)i+； 从左向右找非负数 if(ij) 交换元素 Ai和 Aj temp=Ai；Ai=Aj；Aj=temp； i+；j 一一； 该算法的时间复杂度为 O(n)。)解析：27.写一个 HeapInsen(R,key)算法，将关键字插入到堆 R 中，并保证插入后 R 仍是堆。请分析

37、算法的时间复杂度。提示：将 key 先插入 R 中已有元素的尾部(即原堆的长度加 1 的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。（分数：2.00）_正确答案：(正确答案：算法如下： typedef struct KeyType key； InfoType otherinfo； RecType； typedef struct RecType RecMaxNum； MaxNum 是一个常量 int len； SeqList； HeapInsert(SeqList R，KeyType key) int i，j： RRec+Rlenkey=key； 增加新值到原堆中已

38、有元素的尾部且堆的长度加 1 i=R1en2；j=Rlen； while(i0) 调整为堆 if(RRecikeyRRecjkey) RRec0=RReci；RReci=RRecj；RReci=RRec0； j=i；i=i2； 继续自底向上查找 设该堆对应的树高为 h，则满足 hlog 2 Rlen，调整是自底向上查找，最多查找到树根，所以时间复杂度为 O(log 2 Rlen)。)解析：28.写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。（分数：2.00）_正确答案：(正确答案：建立堆的算法如下： void BuildHeap(SeqList R，KeyType An) 类型定义 int i： Rlen=0； 初始化 for(i=0：in；i+)Heaplnsert(R，Ai)： )解析：