⑴ 对题目所给关键字序列进行置换-选择排序：

初始FI：51，94，37，92，14，63，15，99，48，56，23，60，31，17，43，8，90，166，100；

WA和FO均为空。

第一趟：

从FI读4个记录到WA：51，94，37，92

从WA选择最小的值，记不MINIMAX，输出到FO：37

从FI读1个记录到WA：51，94，92，14

从WA选择最小，但不小于当前MINIMAX的值，输出到FO：37，51

重复上面两步操作，依次得：

WA：94，92，14，63

FO：37，51，63

WA：94，92，14，15

FO：37，51，63，92

WA：94，14，15，99

FO：37，51，63，92，94

WA：14，15， 99，48

FO：37，51，63，92，94，99

WA：14，15，48，56

此时已选不出新的MINIMAX，得第一个归并段：37，51，63，92，94，99

第二趟：

WA：14，15，48，56

FO：14

WA：15，48，56，23

FO：14，15

WA：48，56，23，60

FO：14，15，23

WA：48，56，60，31

FO：14，15，23，31

WA：48，56，60，17

FO：14，15，23，31，48

WA：56，60，17，43

FO：14，15，23，31，48，56

WA：60，17，43，8

FO：14，15，23，31，48，56，60

WA：17，43，8，90

FO：14，15，23，31，48，56，60，90

WA：17，43，8，166

FO：14，15，23，31，48，56，60，90，166

WA：17，43，8，100

此时已选不出新的MINIMAX，得第二个归并段：14，15，23，31，48，56，60，90，166

第三趟：

WA：17，43，8，100

FO：8

WA：17，43，100

FO：8，17

WA：43，8，100

FO：8，17，43

WA：100

FQ：8，17，43，100

最后分成三个归并段：

37，51，63，92，94，99

14，15，23，31，48，56，60，90，166

8，17，43，100

(2) 设输入序列为x₁,x₂,...,x_n，且所有关键字互不相同。

考虑最大值的情况：

显然，刚开始进入WA的m个关键字一定能被输出，如果后面每次进入WA的关键字都能被输出，只要该关键字恰巧大于刚刚输出的关键字即可。特殊地，取x₁<x₂<...<x_n，则所有的关键字都能被输出到第一个归并段，此时第一归并段的长度取最大值n。

再考虑最小值的情况：

同样，刚开始进入WA的m个关键字一定能被输出，如果后面每次进入WA的关键字都不能被输出，只要该关键字恰巧小于刚刚输出的关键字即可。特殊地，取x₁>x₂>...>x_n，则只有前m个关键字被输出到第一个归并段，此时第一归并段的长度取最小值m。

假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA初始为空，设内存工作区WA的容量可容纳w个记录。则置换-选择排序的操作过程为：

① 从FI输入w个记录到缓冲区WA；

② 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录；

③ 将MINIMAX记录输出到FO中去；

④ 若FI不空，则从FI输入下一个记录到WA中；

⑤ 从WA中所有比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录；

⑥ 重复③~⑤，直到在WA中选不出新的MINIMAX为止，由此得到一个初始归并段，输出归并段结束标志到FO中；

⑦ 重复②~⑥，直到WA为空，由此得到全部初始归并段。

⑴ 有向图G采用邻接矩阵G.Edge表示，G.Edge[i][j]=1表示存在有向边(i,j)，G.Edge[i][j]=0 表示不存在有向边(i,j).

本题算法基本设计思想如下：

第一步：统计所有顶点的入度和出度。若存在边(i,j)，即G.Edge[i][j]=1，则顶点i 的出度加1，顶点j的入度加1。若不存在边(i,j)，即G.Edge[i][j]=0 ，则顶点i 的出度不变，顶点j 的入度不变。

第二步：统计所有顶点中出度大于入度的顶点的个数，并输出。

(2) C语言代码：

int printVertices(MGraph G) {

    int indegrees[G.numVertices];

    int outdegrees[G.numVertices];

    memset(indegrees, 0, sizeof(indegrees));

    memset(outdegrees, 0, sizeof(outdegrees));

    // 遍历无向图统计所有点的出度和入度

    for (int i = 0; i < G.numVertices; i++) {

        for (int j = 0; j < G.numVertices; j++) {

            outdegrees[i] += G.Edge[i][j];

            indegrees[j] += G.Edge[i][j];

        }

    }

    int count = 0;

    // 遍历indegrees和outdegrees数组统计出度大于入度的顶点

    for (int i = 0; i < G.numVertices; i++) {

        if (outdegrees[i] > indegrees[i]) {

            printf("%d", i);

            count++;

        }

    }

    return count;

}

快速排序算法通过多次比较和交换来实现，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。 

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

A选项，枢轴为11 ，左边 68 > 11 。错误。

B选项，枢轴为70 ，右边 23 < 70 。错误。

C选项，枢轴为80，右边 48 < 80 。错误。

D选项，枢轴为81。正确。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

在八大排序算法中，

稳定的排序有：插入排序、冒泡排序、归并排序、基数排序。

不稳定的排序有：选择排序、希尔排序、快速排序、堆排序。

1)插入2022，H(2022)=(2022+4) mod 5 =1；1位为空，可插入；

2)插入12，H(12)=(12+4) mod 5 =1，冲突，采用线性探测法，每次向右探索一位，当前为空，可插入；

3)插入25，H(25)=(25+4) mod 5 =4，4位为空，可插入。

4)删除25，该散列表采用线性探测再散列法，属于开放寻址法，从中删除关键字时，不能简单地置NIL，而是作一个标记，如DELETED，简记为D。

5)计算查找失败时的平均查找长度：

查找元素失败统计项数目与散列表空间大小和散列函数均有关，这里取5。

按照冲突处理方法，计算出每种情况查找失败需要的次数，即失败查找长度：

散列到0：

查找次数为1；

散列到1：

查找次数为3；

散列到2：

查找次数为2；

散列到3：

查找次数为1；

散列到4：

查找次数为2。

查找失败时的平均查找长度为：(1+3+2+1+2)/5=1.8