数据结构复习题-第10章2013-12-16

第10章 内部排序

一、选择题（每小题2分，共20分）

1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A.插入排序 B.选择排序 C.希尔排序 D.二路归并排序

2.下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A.选择 B.冒泡 C.归并 D.堆 3.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

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

4.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。

A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 5.为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。

A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 6.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ ）。

A. 79, 46, 56, 38, 40, 84 B. 84, 79, 56, 38, 40, 46 C. 84, 79, 56, 46, 40, 38 D. 84, 56, 79, 40, 46, 38 二、判断题（每小题1分，共10分）

1.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlogn)。（ ） 2.（101，88，46，70，34，39，45，58，66，10）是堆。( ) 三、填空题（每空1分，共10分）

1.不仅需要使用内存，而且还要使用外存的排序称为 。

2.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 和记录的 。

四、应用题（共40分）

1.（6分）简述快速排序算法的基本思想。

2.（6分）写出快速排序的思想，并写出下列序列快速排序的结果（49，38，65，97，76，13，27，50）

3.（6分）对一组记录（54，38，96，23，15，72，60，45，83）执行希尔排序（D=5，3，1），记录每一趟排序结果。

4.（6分）对一组记录（54，38，96，23，15，72，60，45，83）执行冒泡排序，记录每一趟排序结果。

5.（6分）已知一组元素的排序码为（36，25，48，12，65，20），写出用直接插入排序法每次向前面有序表插入一个元素后的排列结果。

6.（6分）写出用堆排序算法对(12,15,3,30,28,9)进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态。

7.（6分）判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。

（1）100，85，98，77，80，60，82，40，20，10，66 （2）100，85，40，77，80，60，66，98，82，10，20

1

（3）10，20，40，60，66，77，80， 82，85，98，100

8. (6分)画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 五、算法题（共20分）

1.（6分）编写起泡排序的算法。

2.（6分）写出一趟快速排序的算法。 3.（6分）编写直接插入排序的算法。 4.（6分）编写折半插入排序的算法。 5.（6分）编写简单选择排序的算法。 6.（6分）编写归并排序的算法。（可选）

答案：

一、选择题 1-6 ACCCAB 二、判断题 1-2 对对

三、填空题 1.外部排序 2. 比较、移动 四、应用题 无答案 五、算法题

1.（6分）编写起泡排序的算法。 答案一：

void BubbleSort(Elem R[ ], int n) { i = n;

while (i >1) {

lastExchangeIndex = 1;

for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) {

Swap(R[j], R[j+1]); // temp=R[j] ; R[j]= R[j+1]; R[j+1]= temp; lastExchangeIndex = j; //记下进行交换的记录位置 } //if

i = lastExchangeIndex; // 本趟进行过交换的最后一个记录的位置 } // while } // BubbleSort 答案二：

void paixu(int a[],int n) {

for(i=0;i

{ for (i=0;i<10-j;i++) 2分 if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;}

} 6分 for(i=1;i<11;i++)

2

printf(\printf(\}

2.（6分）写出一趟快速排序的算法。

int partition(sqlist L, int low, int high) {L.r[0]=L.r[low];

pivotkey=L.r[low].key; 1分 while(low

{

while(low=pivotdey) –high;

L.r[low]=L.r[high]; 3分 while(low

}

L.r[low]=L.r[0];

return low; 7分 }

3.（6分）编写直接插入排序的算法。 void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i<=L.length; ++i )

if (L.r[i].key < L.r[i-1].key) {

L.r[0] = L.r[i]; // 复制为监视哨 for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置

}

} // InsertSort

4.（6分）编写折半插入排序的算法。 void BiInsertionSort ( SqList &L ) {

for ( i=2; i<=L.length; ++i ) {

L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] low = 1; high = i-1; while (low<=high) {

m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key)

high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 }//在 L.r[1..i-1]中折半查找插入位置； for ( j=i-1; j>=high+1; --j )

L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } // for } // BInsertSort

3

5.（6分）编写简单选择排序的算法。 void SelectSort (int R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; i

// 选择第 i 小的记录，并交换到位

j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换 }

} // SelectSort

6.（6分）编写归并排序的算法。（可选）

void Merge (int R[], int R2[], int l, int m, int h) { // 将有序的记录序列 R[l..m] 和 R[m+1..h] // 归并为有序的记录序列 R2[l..h]

for (i=l , j=m+1; i<=m && j<=h; ++k) { // 将R中记录由小到大地并入R2 if (R[i] <=R[j]) R2[k] = R[i]; else R2[k] = R[j]; }

if (i<=m) R[k..h] = R[i..m];

// 将剩余的 R[i..m] 复制到 R2

if (j<=h) R2[k..h] = R[j..h];

// 将剩余的 R[j..h] 复制到 R2 } // Merge

4

本文来源：https://www.bwwdw.com/article/6gm8.html