数据库系统l试题库及答案 第10章排序 .pdfVIP

第10章排序

10.1排序的相关知识

一、填空题

1.将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫。

2.大多数排序算法都有两个基本的操作：和。

二、选择题

1.（）排序算法的稳定性是指（）。

A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变

B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变

C.排序算法的性能与被排序元素的个数关系不大

D.排序算法的性能与被排序元素的个数关系密切

2.（）关于排序的以下叙述中，正确的是（）。

A.稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率高

B.对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能不同

C.排序方法都是在顺序表上实现的，在链表上无法实现排序方法

D.在顺序表上实现的排序方法都可以在链表上实现

3.（）以下不属于内部排序方法的是（）。

A.选择排序B.插入排序C.归并排序D.拓扑排序

10.2插入排序

一、填空题

在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7

个记录60插入到有序表时，为寻找插入位置至少需比较次。

二、选择题：

1.（）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时空）中的元素进行比较，

将其放入已排序序列的正确位置上的方法，称为()。

A.希尔排序B.冒泡排序C.插入排序D.选择排序

2.（）折半插入排序算法的平均情况下的时间复杂度为()。

23

A.O(n)B.O（nlogn）C.O（n）D.O（n）

2

3.（）对含有n个元素的顺序表采用直接插入排序方法进行排序，在最坏情况下所需的比较次数是

()。

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

三、简答题

1.给出关键字序列{4,5,1,2,8,6,7,3,10,9}的直接插入排序过程。

2.给出关键字序列{4,5,1,2,8,6,7,3,10,9}的希尔排序过程（步长分别为5,2,1）。

四、算法设计题

1.插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序方

法。请补充完整以下程序。

voidsort(SqListA){/*n为元素个数，数组下标从1开始，到n结束。*/

for(i=2;i=n;i++){

low=1;high=i–1;/*low,high分为当前元素上、下界*/

A[0].key=A[i].key;

//补充完整

}

10.3交换排序

一、填空题

1.对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。

2.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：起

泡排序一趟扫描的结果是。

二、选择题

1.（）对ｎ个不同的元素采用冒泡排序方法进行从小到大排序，在下列哪种情况下比较的次数最

多。

A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序

2.