本题是下午题中最难的一部分，主要考察算法相关
1）算法策略：动态规划法、回朔法、分治法、贪心法
动态规划法和分治法的区别：动态规划的子问题不是独立的，一般用数组保存；分治法的子问题是独立的。
动态规划法时间复杂度：自顶向下：O(2^n)；自底向上：O(n^a)
动态规划法举例：斐波那契数列，矩阵乘法，0-1背包问题，LCS最长公共子序列，钢条切割问题
排序算法：不稳定——快，选，堆，希
特别：快（最坏n^2），选（最坏最好n^2），希（平均n^1.3）
分治法举例：归并排序（O(n log2 n)）
2）2022年真题
阅读下列说明和C代码，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
排序是将一组无序的数据元素调整为非递减顺序的数据序列的过程，堆排序是一种常用的排序算法。用顺序存储结构存储堆中元素，非递减堆排序的步骤是：
（1）将含n个元素的待排序数列构造成一个初始大项堆，存储在数组 R（R［L］，R［2］R［n］）中。此时堆的规模n，堆项元素 R［1］就是序列中最大的元素，R［n］是堆中最后一个元素；
（2）将堆顶元素和堆中最后一个元素交换，最后一个元素脱离堆结构，堆的规模減1，将堆中剩余的元素调整成大顶堆；
（3）重复步骤（2）直到只剩下最后一个元素在堆结构中，此时数组R是一个非递减的数据序列
【C代码】
下面是该算法的C语言实现。
（1） 主要变量说明
n：待排序的数组长度
R[］：待排序数组，n个数放在 R［1］，R［2］……R［n］中
（2）代码
#include <stdio.h>
#define MAXITEN 100
/*
调整堆
R：待排序数组；
v：结点编号，以v为根的二叉树，R[v]>=R[2v],R[v]>=R[2v+1],且其左子树和右子树都是大顶堆；
n：堆结构的规模，即堆中的元素数
*/
void Heapify(int R[MAXITEM],int v,int n){
int i,j;
i=v;
j=2*I;
R[0]=R[i];
while(j<=n){
if(j<n&&R[j]<R[j+1]){
j++;
}
if(____(1)____){
R[i]=R[j];
i=j;
j=2*i;
}
else{
j=n+1;
}
}
R[i]=R[0];
}
/*堆排序，R为待排序数组；n为数组大小*/
void HeapSort(int R[MAXITEM],int n){
int i;
for(i=n/2;i>=1;i--){
____(2)____;
}
for(i=n;___(3)___;i--){
R[0]=R[i];
R[i]=R[1];
___(4)___;
Heapify(R,1,i-1);
}
}
【问题1】（8分）
根据以上说明和C代码，填充C代码中的空 （1）~（4）。
【问题2】（2分）
根据以上说明和C代码，算法的时间复杂度为_____（用O符号表示）。
【问题3】（5分）
考虑数据序列 R=（7，10，13，15，4,20,19，8），n=8，则构建的初始大顶堆为（6），第一个元素脱离堆结构，对剩余元素再调整成大顶堆后的数组R为（7）
一般来说，第一问表面考察代码补全，但其实实在考察对算法的理解度；第二问一般考察时间复杂度，第三问是一个实际问题