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

天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为。——《孟子》

数据库系统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为元素个数，数组下标从