1、回答下列问题:

①从未排序序列中挑选元素,并将其依次放入到已排序序列中(初始时为空)的一端的方法是什么?

②在待排序的元素基本有序的前提下,效率最高的排序方法是什么?

③从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置方法是什么?

④设有1000个元素,希望采用最快的速度挑选出其中前10个最大的元素,最好的方法是什么?

  ①选择排序。
  ②希尔排序。
  ③直接插入排序。
  ④堆排序。

2、若对关键字序列为(54,37,93,25,17,68,58,41,76)的一组记录进行快速排序时,递归调用使用的栈所能达到的最大深度是多少?共需递归调用多少次?其中第二次递归调用是对哪组记录进行排序?

  最大深度为4,共需递归调用5次。第二次递归调用是对序列(41,37,17,25)进行排序。

3、在堆排序,快速排序和归并排序中,若只从存储空间考虑,应选择哪种方法;若只从排序结果的稳定性考虑,应选择哪种方法;若只从平均情况下排序最快考虑,应选择哪种方法。

  堆排序;归并排序;快速排序。

4、设有关键字序列为(14,17,53,35,9,32,68,41,76,26)的一组记录,请给出用希尔排序法(增量序列是5,3,1)排序时的每一趟结果。

  第一趟:14,71,41,35,9,32,68,53,76,26
  第二趟:14,9,32,26,17,41,35,53,76,68
  第三趟:9,14,17,26,32,35,41,53,68,76

5、设有关键字序列为(14,17,53,35,9,37,68,21,46)的一组记录,请给出冒泡排序法排序时的每一趟结果。

  第一趟:14,17,35,9,37,53,21,46,68
  第二趟:14,17,9,35,37,21,46,53,68
  第三趟:14,9,17,35,21,37,46,53,68
  第四趟:9,14,17,21,35,37,46,53,68

6、设有关键字序列为(14,17,53,35,9,37,68,21,46)的一组记录,利用快速排序法进行排序时,请给出以第一个记录为基准得到的一次划分结果。

  9,14,53,35,17,37,68,21,46

7、设有关键字序列为(14,17,53,35,9,37,68,21)的一组记录,请给出按非递增采用堆排序时的每一趟结果。

  建立初始堆并进行调整,得出大顶堆。

  输出68,并进行堆调整。

  输出53,并进行堆调整。

  输出37,并进行堆调整。

  输出35,并进行堆调整。

  输出21,并进行堆调整。

  输出17,并进行堆调整。

  输出14,最后输出9。

  最后的输出序列为 68,53,37,35,21,17,14。

8、设有关键字序列为(314,617,253,335,19,237,464,121,46,231,176,344)的一组记录,请给出采用基数排序时的每一趟结果。

  第一趟:121,231,253,314,464,344,335,46,176,617,237,19
  第二趟:314,617,19,121,231,335,237,344,46,253,464,176
  第三趟:19,46,121,176,231,237,253,314,335,344,464,617

9、将哨兵放在R[n]中,被排序的记录存放在R[1…n-1]中,重写直接插入排序算法。

void InsertSort(DataType R[], int n){
    for(int i = n-2; i > 0; i--){
        R[n] = R[i];
        for(int j = i+1; R[j] > R[n]; j++){
            R[j-1] = R[j];
        }
        R[j-1] = R[n];
    }
}

10、实际中常采用单链表存储数据记录,请写出排序记录的结构的定义并修改。

//顺序表
struct SeqList{
    DataType data[];
    int length;
}SeqList;


//单链表
struct Node{
    DataType data;
    struct Node *next;
}Node;