数据结构第七章章节测试

选择：bdcaacdcbbabcbac
填空：
1、A[Child]<A[Child+1]
X<A[Child]
A[Parent]=X
PercDown(A,0,i)
2、2
3、简单插入排序
4、简单插入排序
5、堆
6、堆
快速
归并
7、j<=n-i-1
r[j]< r[mini]
mini != i
maxi == i
判断：
错错错对错对错错错对
简答：

![](/media/202212/146C41E1BAD4C7B063EE6E6D21C8BD97_1670496668.jpg)
![](/media/202212/5B3E6D4AA620E8C8EB01B89EFF23A587_1670496675.jpg)
![](/media/202212/24B8E3DA0D05E200806961F7B787FACF_1670496681.jpg)

最后一题：
```c
#include <stdio.h>
#include "stdlib.h"
#include "malloc.h"

void HeapSort(int a[], int n);
void HeapAdjust(int a[], int m, int n);

int main(){
    // main function .
    int N, M, i, j, tmp,check;
    int * Monopoly;
    printf("Please input N and M( poosition of element to delete ) : ");
    scanf("%d %d", &N, &M);
    Monopoly = (int *)malloc(sizeof(int) * N);
    printf("Then, input them : \n");
    for(i = 0; i < N; i++){
        j = i + 1;
        scanf("%d", &Monopoly[i]);
        while(j != 1){
            if(Monopoly[j - 1] > Monopoly[(j / 2) - 1]){
                tmp = Monopoly[j - 1];
                Monopoly[j - 1] = Monopoly[(j / 2) - 1];
                Monopoly[(j / 2) - 1] = tmp;
            }
            else{
                break;
            }
            j = j / 2;
        }
    }

// check the input max_heap
    printf("Initial max_heap :\n");
    for(check = 0; check < N; check++){
        printf("%d  ", Monopoly[check]);
    }
    printf("\n");

// heap_sort
    // HeapSort(Monopoly, N);
    tmp = Monopoly[M - 1];
    Monopoly[M - 1] = Monopoly[N - 1];
    Monopoly[N - 1] = tmp;
    HeapAdjust(Monopoly, M - 1, N - 2);

// check the result
    printf("Result heap :\n");
    for(check = 0; check < N; check++){
        printf("%d  ", Monopoly[check]);
    }

return 0;
}

void HeapAdjust(int a[], int m, int n){
	int i;
	int t = a[m];

for(i = 2 * m;i <= n;i = 2 * i){
		if(i < n && a[i + 1] > a[i])
            ++i;
		if(t >= a[i])
            break;
		a[m] = a[i];
		m = i;
	}
	a[m] = t;
}
```