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

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

第10章排序

10.1排序的相关知识

一、填空题

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

键字有序的序列叫。

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

二、选择题

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

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

不变

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

不变

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

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

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

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

效率高

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

果可能不同

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

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

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

A.选择排序

B.插入排序

C.归并排序

D.拓扑排序

10.2插入排序

一、填空题

1.在对一组记录（54，38，96，23，15，72，60，45，83）进

行直接插入排序时，当把第7

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

二、选择题：

1.（）排序方法中，从未排序序列中依次取出元素与已排序序列

（初始时空）中的元素进行比较，

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

A.希尔排序

B.冒泡排序

C.插入排序

D.选择排序

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

A.O(n)

B.O（nlog2n）

C.O（n2）

D.O（n3）

3.（）对含有n个元素的顺序表采用直接插入排序方法进行排序，

在最坏情况下所需的比较次数是

()。

A.n-1

B.n+1

C.n/2

D.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.（）对ｎ个不同的序列进行冒泡排序，在元素无序的情况下比

较的次数为（）。

A.n+1

B.n

C.n-1

D.n(n-1)/2

3.（）快速排序在下列哪种情况下最易发挥其长处。（）

A.被排序的数据