《数据库系统l试题库及答案第10章排序》由会员分享，可在线阅读，更多相关《数据库系统l试题库及答案第10章排序（16页珍藏版）》请在金锄头文库上搜索。
1、据库系统l试题库及答案第10章排序第 10 章排序10.1 排序的相关知识一、填空题1. 将一个数据元素（或记录）的任意序列，重新排列成一个按关 键字有序的序列叫。2. 大多数排序算法都有两个基本的操作：和。二、选择题1. （）排序算法的稳定性是指（）。A. 经过排序后，能使关键字相同的元素保持原顺序中的相对位置 不变B. 经过排序后，能使关键字相同的元素保持原顺序中的绝对位置 不变C. 排序算法的性能与被排序元素的个数关系不大D. 排序算法的性能与被排序元素的个数关系密切2. （）关于排序的以下叙述中，正确的是（）。A. 稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法 效率高B. 对
2、同一个线性表使用不同的排序方法进行排序，得到的排序结 果可能不同C. 排序方法都是在顺序表上实现的，在链表上无法实现排序方法 D在顺序表上实现的排序方法都可以在链表上实现3. （）以下不属于内部排序方法的是（）。A. 选择排序B. 插入排序C. 归并排序D. 拓扑排序10.2 插入排序一、填空题1. 在对一组记录（54，38，96，23，15，72，60，45，83）进 行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。二、选择题：1. （）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（
3、 ）。A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序2. （）折半插入排序算法的平均情况下的时间复杂度为（ ）。A. O（n）B. O（nlog2n）C. O（n2）D. O（n 3）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. 插入排序中找插入位置的操作可以通过二
4、分法查找的方法来实现。试据此写一个改进后的插入排序方法。请补充完整以下程序。void sort (SqList A ) /* n 为元素个数，数组下标从1开始，到 n结束。*/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)中的关键码按字 母序的升序重新排
5、列，则：起泡排序一趟扫描的结果是。二、选择题1. ()对n个不同的元素采用冒泡排序方法进行从小到大排序， 在下列哪种情况下比较的次数最多。A. 从小到大排列好的B. 从大到小排列好的C. 元素无序D. 兀素基本有序2. ()对n个不同的序列进行冒泡排序，在元素无序的情况下比 较的次数为()。A. n+1B. nC. n-1D. n(n-1)/23. ()快速排序在下列哪种情况下最易发挥其长处。()A. 被排序的数据中含有多个相同排序码B. 被排序的数据已基本有序C. 被排序的数据完全无序D. 被排序的数据中的最大值和最小值相差悬殊4. ()对有n个记录的表作快速排序，在最坏情况下，算法的时间
6、复杂度是( )。AO(n) BO(n2) CO(nlog2n) DO(n3)5. ()若一组记录的序列为(46, 79, 56, 38, 40, 84)，则利用快 速排序的方法，以第一个记录为基准得到的一次划分结果为()。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三、简答题1. 以关键字序列265 ， 301 ， 751 ， 129 ， 937 ， 863 ， 742 ， 694 ， 076 ， 438为例，写出进行冒泡排序的各趟排序后关
7、键字序列的状态。2. 以关键字序列265 ， 301 ， 751 ， 129 ， 937 ， 863 ， 742 ， 694 ， 076 ， 438为例，写出进行快速排序的各趟排序后关键字序列的状态。10.4选择排序一、填空题1. 堆是一种有用的数据结构。堆排序是一种排序，堆实质上是一 棵。对含有n个元素的序列进行排序时，堆排序的时间复杂度为 ,所需的空间复 杂度为。2. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用； 若初始记录随机分布，则最好选用。在直接插入排序和简单选择排序中，若初始记录基本 有序则选用，若初始记录基本反序，则选用。3. 将无序序列建成一个堆，得到关键字最小(或
8、最大)的记录； 输出堆顶的最小(大)值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执 行，得到一个有序序列，这个过程叫。二、选择题1. （）从未排序序列中挑选元素，并将其依次插入已排序序列 （初始时为空）的一端的方法，称为（）。A. 希尔排序B. 归并排序C. 插入排序D.选择排序2. （）下列关键字序列中，是堆。A. 16, 72, 31, 23, 94, 53B. 94, 23, 31, 72, 16, 53C. 16, 53, 23, 94，31, 72D. 16, 23, 53, 31, 94, 723. （）堆是一种排序。A. 插入B. 选择C. 交换D归并
9、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. 简单选择排序D. 快速排序7. ( )在下列排序方法中，在某一趟排序结束后未
10、必能选出一个元 素放在其最终位置上的是()。A. 堆排序B. 冒泡排序C. 直接插入排序D. 快速排序8. ( )下列排序方法中，在待排序的数据已经基本有序时，花费 时间反而最多的是( )。A. 堆排序B. 冒泡排序C. 希尔排序D. 快速排序9. ( ) 依次将待排序序列中的元素插入到有序子序列中并扩大有序 子序列的排序方法是()。A. 堆排序B. 冒泡排序C. 直接插入排序D. 快速排序10. ()数据表A中有10000个元素，如果仅要求找出其中最大的 10个元素，则采用( )方法最节省时间。A. 堆排序B. 希尔排序C基数排序D. 快速排序11.（）若一组记录的关键字为46，79，56，
11、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三、简答题1. 已知如下关键字的序列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。以上序列哪个不是堆，请把它调整为堆，给出建立初始堆的过程。2. 以关键字序列265，301，751，129，937，8
12、63，742，694， 076，438为例，写出进行直接选择排序的各趟排序后关键字序列的 状态。3. 以关键字序列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
13、. 在堆排序、快速排序和归并排序中，若只从空间复杂度角度考 虑，则应首先选取方法，其次选取方法，最后选取方法；若只从排序 结果的稳定性考虑，则应选取方法；若只从平均情况下最快考虑，则应选取（多选）方法；若只从最坏情况下最快并且要节省内存考虑，则应选取方法。3. 在归并排序中，若待排序记录的个数为 20，则需要进行趟归并， 在第三趟归并时，是把长度为的有序表归并为长度为的有序表。二、选择题1. ()下述几种排序方法中，空间复杂度最大的是( )。A. 插入排序B. 快速排序C. 归并排序D. 选择排序2. ()在待排序的元素序列基本有序的前提下，效率最高的排序 方法是( )。A. 直接插入排序B.
14、 简单选择排序C. 快速排序D归并排序3. ()以下不稳定的排序方法是 ( )。A. 起泡排序B. 直接插入排序C. 希尔排序D归并排序4. ( )以下排序方法中，()是稳定的排序方法。A. 直接插入和快速排序B. 快速排序和堆排序C. 简单选择和归并排序D. 归并排序和冒泡排序5. ()若需在O ( nIog2n )的时间内完成对顺序表的排序，且要求 排序是稳定的，则可选择的排序方法是()。A. 堆排序B. 归并排序C. 直接插入排序D. 快速排序6. ()在以下各排序方法中，辅助空间为O( n)的是()。A. 堆排序B. 归并排序C. 希尔排序D. 快速排序7. ()在以下排序方法中，最好
15、情况下时间复杂度为O(n)的排序 方法是()和()。A. 直接插入排序B. 冒泡排序C. 简单选择排序D. 快速排序8. ()在以下排序方法中，最坏情况下时间复杂度为0( n2)的排 序方法是()和()。A. 直接插入排序B. 堆排序C. 简单选择排序D归并排序9. ()在以下排序方法中，平均情况下时间复杂度为0( n2)的排 序方法是()和()。A. 直接插入排序B. 冒泡排序C. 归并排序D基数排序三、简答题1. 以关键字序列265，301，751，129，937，863，742，694， 076 ， 438为例，写出进行归并排序的各趟排序后关键字序列的状态。第10章排序10.1排序的相关知识一、填空题
