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

1、第10章排序10.1 排序的相关知识一、填空题1 .将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列叫。2 .大多数排序算法都有两个基本的操作：和。二、选择题1 .()排序算法的稳定性是指()。A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变C.排序算法的性能与被排序元素的个数关系不大D.排序算法的性能与被排序元素的个数关系密切2 .()关于排序的以下叙述中，正确的是()。A.稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率高B.对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能

2、不同C.排序方法都是在顺序表上实现的，在链表上无法实现排序方法D.在顺序表上实现的排序方法都可以在链表上实现3 .()以下不属于内部排序方法的是()。A.选择排序B.插入排序C.归并排序D.拓扑排序4 0.2插入排序1、 填空题1. 在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较、次。2、 选择题：1 .()排序方法中，从未排序序列中依次取出元素与已排序序列(初始时空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()。A.希尔排序B.冒泡排序C.插入排序D.选择排序2 .()折半

3、插入排序算法的平均情况下的时间复杂度为()。A.O(n)B.O(nlogzn)C.O(n2)D.O(n3)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

4、)/*n为元素个数，数组下标从1开始，至Un结束。*/for(i=2;i<=n;i+)low=1;high=i-1;/*low,high分为当前元素上、下界*/A0.key=Ai.key;/补充完整10.3交换排序一、填空题1 .对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。2 .设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则：起泡排序一趟扫描的结果是。二、选择题1 .()对n个不同的元素采用冒泡排序方法进行从小到大排序，在下列哪种情况下比较的次数最多。A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序2

5、 .()对9个不同的序列进行冒泡排序，在元素无序的情况下比较的次数为()。A.n+1B.nC.n-1D.n(n-1)/23 .()快速排序在下列哪种情况下最易发挥其长处。()A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊4 .()对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()。23A.O(n)B.O(n)C,O(nlog2n)D.O(n)5.()若一组记录的序列为(46,79,56,38,40,84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A.38,40,46,56,

6、79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79三、简答题1 .以关键字序列265,301,751,129,937,863,742,694,076,438为例，写出进行冒泡排序的各趟排序后关键字序列的状态。2.以关键字序列265,301,排序后关键字序列的状态。751,129,937,863,742,694,076,438为例，写出进行快速排序的各趟10.4选择排序一、填空题1 .堆是一种有用的数据结构。堆排序是一种排序，堆实质上是一棵。对含有n个元素的序列进行排序时，堆排序的时间复杂度为,所需的空间复杂度为。2 .在

7、堆排序和快速排序中，若初始记录接近正序或反序，则选用;若初始记录随机分布，则最好选用。在直接插入排序和简单选择排序中，若初始记录基本有序则选用,若初始记录基本反序，则选用。3 .将无序序列建成一个堆，得到关键字最小(或最大)的记录；输出堆顶的最小(大)值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫。二、选择题1.)从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称A.希尔排序B.归并排序C.插入排序D.选择排序2 .()下列关键字序列中，是堆。A.16,72,31,23,94,53B.94,23,31,72

8、,16,53C.16,53,23,94,31,72D.16,23,53,31,94,723 .()堆是一种排序。A.插入B.选择C.交换D.归并4 .()堆的形状是一棵A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树5 .()若一组记录的序列为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为()。A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,386 .()在下列排序方法中，时间复杂度不受数据初始状态的影响，恒为O(log2n)的是()。A.堆排序B.冒泡排序C.简

9、单选择排序D.快速排序7 .()在下列排序方法中，在某一趟排序结束后未必能选出一个元素放在其最终位置上的是()。A.堆排序B.冒泡排序C.直接插入排序D.快速排序8 .()下列排序方法中，在待排序的数据已经基本有序时，花费时间反而最多的是()。A.堆排序B.冒泡排序C.希尔排序D.快速排序9 .()依次将待排序序列中的元素插入到有序子序列中并扩大有序子序列的排序方法是()。A.堆排序B.冒泡排序C.直接插入排序D.快速排序10 .()数据表A中有10000个元素，如果仅要求找出其中最大的10个元素，则采用()方法最节省时间。A.堆排序B.希尔排序C.基数排序D.快速排序11 .()若一组记录的

10、关键字为46,79,56,38,40,84,则利用快速排序的方法，以第1个记录为基准得到的一次划分的结果为()。A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79三、简答题12 已知如下关键字的序列50,18,12,61,8,17,87,25,87,61,50,25,8,17,12,18,12,32,25,56,87,60,36,68,13,38,27,49,76,65,49,97。以上序列哪个不是堆，请把它调整为堆，给出建立初始堆的过程。13 以关键字序列265,301,751,129,93

11、7,863,742,694,076,438为例，写出进行直接选择排序的各趟排序后关键字序列的状态。14 以关键字序列265,301,751,129,937,863,742,694,076,438为例，写出进行堆排序的各趟排序后关键字序列的状态。10.5归并排序一、填空题1 .设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则：冒泡排序一趟排序的结果是;初始步长为4的希尔(shell)排序一趟的结果是;二路归并排序一趟排序的结果是;快速排序以第1个关键码为基准得到的一次划分的结果是;堆排序初始建堆(小顶堆)的结果2 .在堆排序、快速排序和归并排序中，

12、若只从空间复杂度角度考虑，则应首先选取方法，其次选取方法，最后选取方法；若只从排序结果的稳定性考虑，则应选取方法；若只从平均情况下最快考虑，则应选取(多选)方法；若只从最坏情况下最快并且要节省内存考虑，则应选取方法。3 .在归并排序中，若待排序记录的个数为20,则需要进行趟归并，在第三趟归并时，是把长度为的有序表归并为长度为的有序表。二、选择题1 .()下述几种排序方法中，空间复杂度最大的是()。A.插入排序B.快速排序C.归并排序D.选择排序2 .()在待排序的元素序列基本有序的前提下，效率最高的排序方法是()。A.直接插入排序B.简单选择排序C.快速排序D.归并排序3 .()以下不稳定的排

13、序方法是()。A.起泡排序B.直接插入排序C.希尔排序D.归并排序4 .()以下排序方法中，()是稳定的排序方法。A.直接插入和快速排序B.快速排序和堆排序C.简单选择和归并排序D.归并排序和冒泡排序5 .()若需在O(nlogzn)的时间内完成对顺序表的排序，且要求排序是稳定的，则可选择的排序方法是()。A.堆排序B.归并排序C.直接插入排序D.快速排序6 .()在以下各排序方法中，辅助空间为O(n)的是()。A.堆排序B.归并排序C.希尔排序D.快速排序7 .()在以下排序方法中，最好f#况下时间复杂度为O(n)的排序方法是()和()。A.直接插入排序B.冒泡排序C.简单选择排序D.快速排

14、序8 .()在以下排序方法中，最坏，f#况下时间复杂度为O(n2)的排序方法是()和()。A.直接插入排序B.堆排序C.简单选择排序D.归并排序9 .()在以下排序方法中，平均，f#况下时间复杂度为O(n2)的排序方法是()和()。A.直接插入排序B.冒泡排序C.归并排序D.基数排序三、简答题1.以关键字序列265,301,751,129,937,863,742,694,076,438为例，写出进行归并排序的各趟排序后关键字序列的状态。第10章排序10.1 排序的相关知识一、填空题1 .排序2.比较移动二、选择题1. A2.B3.D10.2 插入排序1、 填空题1.32、 选择题：1 .C2.

15、C3.D三、简答题2 .解：过程如下：第1趟：4,5,1,2,8,6,7,3,10,9第2趟：1,4,5,2,8,6,7,3,10,9第3趟：1,2,4,5,8,6,7,3,10,9第4趟：1,2,4,5,8,6,7,3,10,9第5趟：1,2,4,5,6,8,7,3,10,9第6趟：1,2,4,5,6,7,8,3,10,9第7趟：1,2,3,4,5,6,7,8,10,9第8趟：1,2,3,4,5,6,7,8,10,9第9趟：1,2,3,4,5,6,7,8,9,103 .解：过程如下：gap=5:4,5,1,2,8,6,7,3,10,9gap=2:1,2,4,3,7,5,8,6,10,9gap

16、=1:1,2,3,4,5,6,7,8,9,10四、算法设计题1. while(low<=high)mid=(low+high)/2;if(A0.key<=Amid.key)high=mid-1;/*修改上界*/elselow=mid+1;/*修改下界*/for(j=i-1;j>=mid;j-)Aj+1=Aj;/*移动数据*/Amid=Ai;10.3交换排序1. 填空题2. O(n2)2.HCQPAMSRDFX丫3. 选择题1. B2.D3.C4.B5.C三、简答题1 .冒泡排序的过程如下：初始状态：255.301,751,129.937,863,742,694第1Iffl：0

17、76,265,3Q1,751.129,937,863,742>694,438第2趟！076J29.265*01.751.138.937.863.712,694第3撷：07$.1212(55-30.438.751,694.937,863.712第t超士076.129.265,301,438,694,751.74973,861第5超二第6.129.2鬣，301,438,694,742,75，863+973第6趟:0764129.265.301,13S.694,742,751,863.9732 .快速排序的过程如下:初始状态:第I越：第2趟第3地才第4趟:265,301,751,1Z9f937

18、.86：K742,694,076,438076,129,256,751,937.863.742.694,301,439076J29.256,731,937.863/42,694*01-439076.129256*438.301,694,742,751.863,937076.129,253,301,438,694,742,751,8534937076Tl29*2祝301.438,694,742,751,863.93710.4选择排序一、填空题1.选择完全二叉树O(nlogn)0(1)2.堆排序快速排序直接插入排序简单选择排序3.堆排序二、选择题1.D2.D3.B4.C5.B6.A7.C8.D9.

19、C10.A11.C三、简答题1 .50,18,12,61,8,17,87,25不是堆调整为堆的过程为：61和25交换50,18,12,25,8,17,87,6118和8交换50,8,12,25,18,17,87,6150先和8交换然后和18交换结果为8,18,12,25,50,17,87,612 .直接选择排序的过程如下：初始状态：265,301.751J29,937T863.712,694,076,438第1趟:076,301F75U129,937,863,742,694,265.438第2趟:076,129,751,301,937,863.712,694,265,438第3趟1076.12

20、5,265,301,937T863t742,694T751,438第4患:076,129,265.301,937,863,742,6911751,438第5趟：076429,265,301,438,863,742,694175U937第6卷:076,129,265,301,138,694,742,863,751,937第7趟:076129,265,301,438,694,742,863,751»937第8超!076,129,265,301,438,694,742*751,863937*9暹：<76*123265,301,438,694,742-751.863.9373 .堆排序的过程如下:第1趟：(937,694,863,256,138,751,742,129,076.301)第2趟:(863,-694,751,256,138,301.712.129To76).937第3趟；(751.694,742,256,438-301,076,129).863,937第4场；(742,694,301.256.438,