数据结构-排序

判断题

1.希尔排序是稳定的算法。

T F

稳定的算法：保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

希尔排序会多次进行插入排序，一次插入排序是稳定的，但是因为希尔排序每次插入排序选择的步长不一样，导致希尔排序不稳定。

2.仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。

T F

仅基于比较的算法能得到的最好的“最好时间复杂度”是O(N)，仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。

3.(neuDS)直接插入排序算法在最好情况下的时间复杂度为O(n)。

T F

4.内排序要求数据一定要以顺序方式存储。

T F

内排序是完全在内存中存放待排序元素的排序，存储形式不一定是顺序的。

5.排序算法中的比较次数与初始元素序列的排列无关。

T F

6.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

T F

7.对N个记录进行堆排序，需要的额外空间为O(N)。

T F

不需要额外的空间。

8.堆排序是稳定的排序算法。（）

T F

因为堆没有规定相同的元素应该放在左子树还是右子树，所以堆排序是不稳定的。

9.在堆排序中，若要进行升序排序，则需要建立大根堆。（）

T F

10.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。

T F

11.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlogn )

T F

快速排序的时间复杂度和是否有序无关。

12.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。

T F

13.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。

T F

选择题

1.下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N>2）

    A.冒泡排序
    B.插入排序
    C.堆排序
    D.快速排序

2.对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：

    A.3, 1
    B.3, 2
    C.5, 2
    D.5, 3

index	0	1	2	3	4	5	6	7	8	9	10
first	8	3	9	11	2	1	4	7	5	10	6
second	1	3	7	5	2	6	4	9	11	10	8

红色部分可以看出，第一次的增量是5。

index	0	1	2	3	4	5	6	7	8	9	10

红色部分可以看出，第二次的增量是3。

3.对关键字序列(56，23，78，92，88，67，19，34)，进行增量为3的一趟希尔排序的结果为（）。

    A.(19，23，56，34，78，67，88，92)
    B.(23，56，78，66，88，92，19，34)
    C.(19，23，34，56，67，78，88，92)
    D.(19，23，67，56，34，78，92，88)

4.有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：

    A.79，46，56，38，40，80
    B.84，79，56，46，40，38
    C.84，56，79，40，46，38
    D.84，79，56，38，40，46

5.对N个记录进行堆排序，最坏的情况下时间复杂度是：

    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N²)

最坏的情况下，堆元素下滤都从顶部下滤到底部，为logN，一共N个元素，所以总的时间复杂度是O(NlogN)。

6.对N个记录进行堆排序，需要的额外空间为：

    A.O(1)
    B.O(logN)
    C.O(N)
    D.O(NlogN)

7.在含有n个关键字的小根堆中，关键字最大的记录有可能存储在（）位置上。

    A.n/2 +2
    B.1
    C.n/2 -1
    D.n/2

堆的性质。

8.有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）。

    A.-1，4，8，9，20，7，15，7
    B.-1，7，15，7，4，8，20，9
    C.-1，4，7，8，20，15，7，9
    D.A，B，C均不对。

9.下列关键字序列中，构成大根堆的是（）。

    A.5，8，1，3，9，6，2，7
    B.9，8，1，7，5，6，2，3
    C.9，8，6，3，5，1，2，7
    D.9，8，6，7，5，1，2，3

10.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：

    A.每次划分后，先处理较长的分区可以减少递归次数
    B.每次划分后，先处理较短的分区可以减少递归次数
    C.递归次数与每次划分后得到的分区处理顺序无关
    D.递归次数与初始数据的排列次序无关

11.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：

    A.O(N)
    B.O(NlogN)
    C.O(N²)
    D.O(N²logN)

12.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？

    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N²)

指针停止就会不断交换左右指针的元素，这样虽然多余的交换次数变多，但让子序列的元素相对平均，所以一共有logN次划分，每次时间复杂度是O(N)。

13.在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？

    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N²)

指针不停止，导致所有元素都被放到一个划分中去，一共N个元素，所以一共有N次划分，每次时间复杂度是O(N)。

14.执行一趟快速排序能够得到的序列是（）。

    A.[41，12，34，45，27] 55 [72，63]
    B.[45，34，12，41] 55 [72，63，27]
    C.[63，12，34，45，27] 55 [41，72]
    D.[12，27，45，41] 55 [34，63，72]

15.有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。

    A.9，7，8，4，-1，7，15，20
    B.20，15，8，9，7，-1，4，7
    C.9，4，7，8，7，-1，15，20
    D.4，9，7，8，7，-1，15，20

16.有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（按教材算法操作），以位于最左位置的对象为主元得到的第一次划分结果为：

    A.{38,46,79,56,40,84}
    B.{38,79,56,46,40,84}
    C.{40,38,46,79,84,56}
    D.{40,38,46,56,79,84}

17.用快速排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时,以位于最左位置的对象为主元，得到的第一次划分结果为（按教材算法操作）：

    A.20，15，21，25，47，27，68，35，84
    B.15，20，21，25，35，27，47，68，84
    C.15，20，21，25，27，35，47，68，84
    D.20，15，21，25，84，27，68，35，47

填空题

1.本题要求用冒泡排序将一组整数按增序排序。冒泡排序每次从头到尾扫描待排序列，检查相邻两数的顺序，如果顺序不对就交换。请补全下列冒泡排序的代码。

typedef struct node *nodeptr;
struct node{
    int value;
    nodeptr next;
    /* 一些其他的项，在此忽略 */
};

nodeptr BubbleSort (nodeptr h)
{/* h 是带空头结点的链表的头指针 */
    nodeptr p, q;
    int flag_swap;

    if (!h->next) return h;
    do{
        flag_swap = 0;
        p = h;
        while (p->next->next){
            if (     (3分) ){
                flag_swap++;
                q = p->next;
                    (3分);
                    (3分);
                    (3分);
            }
            else p = p->next;
        }
    } while (flag_swap > 0);
    return h;
}

2.下列代码的功能是利用堆排序将N个元素按非递减顺序排序。

#define leftchild(i) ( 2*(i)+1 )

void PercDown( ElementType A[], int i, int N )
{   int child;
    ElementType Tmp;

    for ( Tmp = A[i]; leftchild(i) < N; i = child ) {
        child = leftchild(i);
        if (    (3分))
            child ++;
        if (    (3分)) A[i] = A[child];
        else break;
    }
        (3分);
}
void Heapsort( ElementType A[ ], int N )
{   int i;
    for ( i = N / 2; i >= 0; i -- ) /* BuildHeap */
        PercDown( A, i, N );
    for ( i = N-1; i > 0; i -- ) {
        Swap( &A[ 0 ], &A[ i ] );
            (3分);
    }
}

3.下列代码的功能是将一列元素{ r[1] … r[n] }按其键值 key 的非递减顺序排序。普通选择排序是每次仅将一个待排序列的最小元放到正确的位置上，而这个另类的选择排序是每次从待排序列中同时找到最小元和最大元，把它们放到最终的正确位置上。

void sort( list r[], int n )
{
    int i, j, mini, maxi;

    for (i=1; i<n-i+1; i++) {
        mini = maxi = i;
        for( j=i+1;     (3分); ++j ){
            if(      (3分) ) mini = j;
            else if(r[j]->key > r[maxi]->key) maxi = j;
        }
        if(     (3分) ) swap(&r[mini], &r[i]);
        if( maxi != n-i+1 ){
            if(     (3分) ) swap(&r[mini], &r[n-i+1]);
            else swap(&r[maxi], &r[n-i+1]);
        }
    }
}

4.本函数的功能是从有N个元素的线性表A中查找第K小的元素。函数的初始调用为Qselect(A, K, 0, N-1)。请完成下列填空。

ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
    ElementType Pivot = A[Left];
    int L = Left, R = Right+1;

    while (1) {
        while ( A[++L] < Pivot ) ;
            (3分);
        if ( L < R ) Swap( &A[L], &A[R] );
        else break;
    }
    Swap( &A[Left], &A[R] );
    if ( K < (L-Left) )
        return Qselect(A, K, Left, R-1);
    else if ( K > (L-Left) )
            (3分);
    else
        return Pivot;
}

5.本题要求实现快速排序操作，待排序列的长度1<=n<=1000。使排序后的数据从小到大排列。

类型定义：

typedef int KeyType;
typedef struct {
KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
int Length;
}SqList;

程序：

#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct {
    KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
    int Length;
}SqList;
void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/
int Partition ( SqList L,int low, int high );
void Qsort ( SqList L,int low, int high );
int main()
{
    SqList L;
    int i;
    CreatSqList(&L);
    Qsort(L,1,L.Length);
    for(i=1;i<=L.Length;i++)
    {
        printf("%d ",L.elem[i]);
    }
    return 0;
}
int Partition ( SqList L,int low, int high )
{ /*一趟划分*/
    KeyType pivotkey;
    L.elem[0] = L.elem[low];
    pivotkey = L.elem[low];
    while(low<high)
    {
        while ( low < high && L.elem[high] >= pivotkey )
            --high;
        L.elem[low] = L.elem[high];
        while ( low < high && L.elem[low] <= pivotkey )
            ++low;
        L.elem[high] = L.elem[low];
    }
    L.elem[low]=L.elem[0];
    return low;
}
void Qsort ( SqList L,int low, int high )
{
    int pivotloc;
    if (     (2分) )
    {
        pivotloc = Partition(L, low, high ) ;
        Qsort (     (2分)) ;
            (2分);
    }
}

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12