1、全国自考数据结构导论（内部排序）模拟试卷 1 及答案与解析一、单项选择题1 排序方法的稳定性是指_。（A）排序算法能在规定的时间内完成排序（B）排序算法能得到确定的结果（C）排序算法不允许有相同关键字的数据元素（D）以上都不对2 排序的目的是为了以后对已排序的数据元素进行_操作。（A）打印输出（B）分类（C）合并（D）查找3 在对一组关键字序列70，55，100，15，33，65，50，40，95)进行直接插人排序时，把 65 插入到有序序列需要比较_次。（A）2（B） 4（C） 6（D）84 若有关键字序列42，70 ，50，33，40，80 ，则利用快速排序的方法，以第一个关键字为基准元素
2、得到的一次划分结果为_。（A）40，33，42，50，70，80（B） 40，33，80，42，50，70（C） 40，33，42，80，50，70（D）33，40，42，50，70，805 快速排序方法在_情况下最不利于发挥其长处。（A）要排序的数据量太大（B）要排序的数据中含有多个相同值（C）要排序的数据个数为奇数（D）要排序的数据已基本有序6 用某种排序方法对线性表(35，90，15，50，10，30，75，28，13)进行排序时得到以下中间结果，则所采用的排序方法是_。13，28， 15， 30， 10， 35， 75， 50， 9010， 13， 15， 30， 28， 35， 50
3、， 75， 9010， 13， 15， 28， 30， 35， 50， 75， 90（A）希尔排序（B）二路归并排序（C）快速排序（D）堆排序7 以下_序列不是堆。（A）98，90，84，82，80，70，64，60，30，20 ，15（B） 98，84，90，70，80，60，82，30，20，15，64（C） 90，84，30，70，80，60，64，98，82，15，20（D）15，20，30，60，64，70，80，82，84，90 ，988 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用_方法能够最快地找出其中最大的正整数。（A）快速排序（B）插入排序（C）选择
4、排序（D）二路归并排序9 在排序过程中，键值比较的次数与初始序列的排列顺序无关的是_。（A）直接插入排序和快速排序（B）直接插入排序和二路归并排序（C）直接选择排序和二路归并排序（D）快速排序和二路归并排序10 以下排序方法中，不能保证每趟排序至少能将一个数据元素放到其最终位置上的排序方法是_。（A）堆排序（B）冒泡排序（C）希尔排序（D）快速排序11 以下四种排序方法中，要求附加的内存空量最大的是_。（A）插入排序（B）选择排序（C）快速排序（D）二路归并排序12 若有关键字序列20， 80，10，50，60，95，15，55，30，40 ，并且该序列是由 5 个长度为 2 的子序列组成，则
5、用二路归并排序方法对该序列进行一趟二路归并后的结果为_。（A）10，20，50，80，15，55，60，95，30，40（B） 20，80，10，50，60，95，15，55，30，40（C） 20，80，10，50，60，95，15，30，40，55（D）10，15，20，30，40，50，55，60，80。9513 以下_排序方法是不稳定的排序方法。（A）冒泡（B）堆（C）直接插入（D）二路归并排序14 快速排序在最坏情况下昀时间复杂度是_。（A）O(log 2n)（B） O(nlog2n)（C） O(n2)（D）O(n 3)15 当文件局部有序或文件长度较小的情况下，最佳的排序方法是 2
6、。（A）直接插入排序（B）直接选择排序（C）冒泡排序（D）二路归并排序二、填空题16 根据在排序过程中使用的存储器将排序方法分为：_和_。17 常用的插入排序有_和_。18 对于直接插入排序和直接选择排序，若待排序序列基本有序，则选用_较好；若待排序序列为逆序，则选用_较好。19 直接插入排序在最好情况下的时间复杂度为_，在最坏情况下的时间复杂度为_。20 若堆中某一数据元素在数组中的下标为 30，则它的左孩子的下标为_，右孩子的下标为_。21 对于堆排序和快速排序，若待排序序列基本有序，则选用_较好；若待排序序列无序，则选用_较好。22 常用的选择排序方法有_和_。23 设有字母序列P，D，
7、F，Z，E，P，N，B，X，M，G ，w，请写出按二路归并排序方法对该序列进行一趟扫描后的结果_。24 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和二路归并排序方法对其仍按递增顺序进行排序，则_最省时间_最费时间。25 对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是_。三、应用题26 在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么? 请举一例说明。27 举例说明本章介绍的各排序方法中哪些是不稳定的?28 对于给定的一组键值：83，40，63，13，84，35，96，57
8、，39，79，61，15，分别画出应用直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、二路归并排序对上述序列进行排序中各趟的结果。29 设有 10000 个无序的数据元素，可供选择的排序方法有：二路归并排序、堆排序、希尔排序和快速排序。现在希望用最快速度挑选出前 10 个最大的数据元素，问采用什么方法最好? 为什么 ?30 试比较直接插入排序、直接选择排序、快速排序、堆排序、二路归并排序的时空性能。31 采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的函数。32 设计一个用链表表示的直接选择排序算法。33 设计一个用链表表示的直接插入排序算法。34 插入排序中找插入位置的
9、操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。35 写出非递归调用的快速排序算法。全国自考数据结构导论（内部排序）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 D【知识模块】 内部排序2 【正确答案】 D【试题解析】 排序的目的主要是为了查找方便，因为在很多场合下，查找是最常见的操作之一。对于一个已排序过的表或文件来说，可以使用二分查找等一些高效率的方法来进行查找操作。【知识模块】 内部排序3 【正确答案】 A【知识模块】 内部排序4 【正确答案】 A【知识模块】 内部排序5 【正确答案】 D【知识模块】 内部排序6 【正确答案】 C【知识模块】 内部排序7 【
10、正确答案】 C【知识模块】 内部排序8 【正确答案】 C【试题解析】 选择排序的基本思想是：每趟在待排序序列中选取当前最小的元素，并将它插入有序序列的后面，因此稍加修改，该排序方法就可以用于解决本题的问题。【知识模块】 内部排序9 【正确答案】 C【试题解析】 初始序列的排列顺序对直接插入排序和快速排序有影响，而对直接选择排序和二路归并排序则没有影响，故正确的答案是 C。【知识模块】 内部排序10 【正确答案】 C【知识模块】 内部排序11 【正确答案】 D【试题解析】 对前三种排序方法来讲，对附加内存容量几乎没有要求，但二路归并排序中，由于在二路归并过程中需要有两个同样大小的数组，用于来回对
11、倒。因此，这种排序方法要求附加的内存容量最大。【知识模块】 内部排序12 【正确答案】 A【知识模块】 内部排序13 【正确答案】 B【试题解析】 稳定排序有直接插入、冒泡排序、二路归并排序；不稳定排序有快速排序、直接选择排序、堆排序、希尔排序。【知识模块】 内部排序14 【正确答案】 C【试题解析】 当待排序空间事先已基本有序时，每趟快速排序后得到的左、右两个待排序小空间严重不对称，因此，差不多要进行 n 趟次快速排序，每趟排序又要进行 n 级次数的比较，故最坏情况下，总的比较次数将达到 O(n2)。【知识模块】 内部排序15 【正确答案】 B【试题解析】 在本章介绍的几种排序方法中，冒泡排
12、序算法里设置了一个标志，以判别某趟排序过程中，待排序空间是否自然有序。因此它适用于局部有序的文件。另外，冒泡排序属于内部排序，在文件较小时，允许用内部排序算法进行排序，故本题的正确答案是 B。【知识模块】 内部排序二、填空题16 【正确答案】 内部排序 外部排序【知识模块】 内部排序17 【正确答案】 直接插入排序 希尔排序【知识模块】 内部排序18 【正确答案】 直接插入 直接选择【知识模块】 内部排序19 【正确答案】 O(n) O(n2)【知识模块】 内部排序20 【正确答案】 61 62【知识模块】 内部排序21 【正确答案】 堆排序 快速排序【知识模块】 内部排序22 【正确答案】
13、直接选择排序 堆排序【知识模块】 内部排序23 【正确答案】 DPFZEPBNMXGW【知识模块】 内部排序24 【正确答案】 冒泡排序 快速排序【试题解析】 对冒泡排序来讲，由于算法中设置了一个标志 fIag，用于记载一趟排序中是否出现了记录交换，以便判断当前待排序区域是否已自然有序。因此本题中用冒泡排序最省时间。当初始时记录已按键值递增有序，若采用快速排序法，每次所选取的中间元素都是最小的，故划分出的左右两个区域一个为空，另一个比原区域少一个元素，使得元素的比较次数只比上一趟少 1，所以总的时间消耗是O(n2)，因此在本题中用快速排序法最费时间。【知识模块】 内部排序25 【正确答案】 O
14、(nlog 2n) O(n2)【试题解析】 快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需 log2n 趟划分即可。每趟划分所需时间复杂度为 O(n)，最好情况下的时间复杂度是 O(nlog2n)。 最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n 一 1 趟划分。每趟划分的时间复杂
15、度为 O(n)，因此，最坏情况下的时间复杂度为 O(n2)。【知识模块】 内部排序三、应用题26 【正确答案】 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。例如，对 4，3，2，1 冒泡排序就可否定本题结论。【知识模块】 内部排序27 【正确答案】 稳定排序有直接插入、冒泡排序、二路归并排序。不稳定排序有快速排序、直接选择排序、堆排序。不稳定排序举例：(1)快速排序。初始状态 39 67 35 50 99 67 10 55排序后 10 35 39 50 55 67 67 99(2)堆排序。初始状
16、态 67 38 75 97 80 13 27 67排序后 13 27 38 67 67 75 80 97(3)直接选择排序。初始状态 39 67 35 50 99 67 10 55排序后 10 35 39 50 55 67 67 99(其中 67 表示记录初始位置在 67 记录位置之后)【知识模块】 内部排序28 【正确答案】 (1)直接插入排序。序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15i=1 83 40 63 13 84 35 96 57 39 79 61 15i=2 40 83 63 13 84
17、 35 96 57 39 79 61 15i=3 40 63 83 13 84 35 96 57 39 79 61 15i=4 13 40 63 8384 35 96 57 39 79 61 15i=5 13 40 63 83 84 35 96 57 39 79 61 15i=6 13 35 40 63 83 8496 57 39 79 61 15i=7 13 35 40 63 83 84 96 57 39 79 61 15i=8 13 35 40 57 63 83 84 9639 79 61 15i=9 13 35 39 40 57 63 83 84 96 79 61 15i=10 13 3
18、5 39 40 57 63 79 83 84 96 61 15i=11 13 35 39 40 57 61 63 79 83 84 96 15i=12 13 15 35 39 40 57 61 63 79 83 84 96(2)希尔排序。序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15第 1 趟(d1=6) 后 83 40 39 13 61 15 96 57 63 79 84 35第 2 趟(d2=3) 后 13 40 15 79 57 35 83 61 39 96 84 63第 3 趟(d3=1) 后 1
19、3 15 35 39 40 57 61 63 79 83 84 96(3)冒泡排序。序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15第 1 趟排序后 40 63 13 83 35 84 57 39 79 61 1596第 2 趟排序后 40 13 63 35 83 57 39 79 61 15 84 96第 3 趟排序后 13 40 35 63 57 39 79 61 15 83 84 96第 4 趟排序后 13 35 40 57 39 63 61 15 79 83 84 96第 5 趟排序后 13 35
20、40 39 57 61 15 63 79 83 84 96第 6 趟排序后 13 35 39 40 57 15 61 63 79 83 84 96第 7 趟排序后 13 35 39 40 15 57 61 63 79 83 84 96第 8 趟排序后 13 35 39 15 40 57 61 63 79 83 84 96第 9 趟排序后 13 35 15 39 40 57 61 63 79 83 84 96第 10 趟排序后 13 15 35 39 40 57 61 63 79 83 84 96第 11 趟无元素交换，则排序结束。(4)快速排序。序号 1 2 3 4 5 6 7 8 9 10
21、11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15第 1 趟排序后15 40 63 13 61 35 79 57 398396 841第 2 趟排序后131563 13 61 35 79 57 39 83 96 84第 3 趟排序后 13 1539 40 61 35 573 63798396 84第 4 趟排序后 13 15 F353961 40 57-1 63 79 8396 84第 5 趟排序后 13 15 35 3957 4061 63 79 8396 84第 6 趟排序后 13 15 35 39 4057 61 63 79 8396 84第 7 趟
22、排序后 13 15 35 39 40 57 61 63 79 83 84 96(5)直接选择排序。序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15i=1 1340 63 83 84 35 96 57 39 79 61 15i=2 13 1563 83 84 35 96 57 39 79 61 40i=3 13 15 3583 84 63 96 57 39 79 61 40i=4 13 15 35 3984 63 96 57 83 79 61 40i=5 13 15 35 39 40 63 96 57 83
23、79 61 84i=6 13 15 35 39 40 57 96 63 83 79 61 84i=7 13 15 35 39 40 57 6163 83 79 96 84i=8 13 15 35 39 40 57 61 6383 79 96 84i=9 13 15 35 39 40 57 61 63 79 83 96 84i=10 13 15 35 39 40 57 61 63 79 83 96 84i=11 13 15 35 39 40 57 61 63 79 83 84 96(7)二路归并排序。序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84
24、35 96 57 39 79 61 15第 1 趟排序后40 83313 6335 8457 9639 7915 61第 2 趟排序后13 40 63 8335 57 84 9615 39 61 79第 3 趟排序后13 35 40 57 63 83 84 9615 39 61 79第 4 趟排序后 13 15 35 39 40 57 61 63 79 83 83 96【知识模块】 内部排序29 【正确答案】 这几种方法速度都很快，但二路归并排序、希尔排序和快速排序都是在排序结束后才能确定数据元素的顺序，无法提前知道数据元素的有序性。只有堆排序，每次均输出最大(或最小)的数据元素，因此采用它比
25、较合适。【知识模块】 内部排序30 【正确答案】 直接插入排序、直接选择排序、快速排序、堆排序和二路归并排序时空性如下表：从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下，时间性能不如堆排序和二路归并排序。而后两者相比的结果是，当 n 较大时，二路归并排序所需时间优于堆排序，但它所需辅助空间最多。 注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于 n 较大的情况，有的适用于 n 较小的情况，还有的与关键字的分布和初始位置有关因此，在实际使用时，需要根据不同情况适当选用排序方法，甚至可将多种方法结合使用。【知识模块】 内部排序31 【正确答案】
26、依题意，单链表定义如下：struct nodeint key；struct node*ljak；;因此，实现本题功能的函数如下：struct*selectsort(struct node*h)struct：node*p，*q，*r，*s，*t；t=NULL；while(h!=NULL)P=h；q=NULL；s=h；r=NULL；while(p!=NULL)if(p 一keykey)s=p;p=q;q=pjP=P 一link；if(s=h)h=h 一link；elseh=s;s 一link=t;t=s：h=t；return(h);【知识模块】 内部排序32 【正确答案】 Voidselesort
27、(1klistL)*设链表 L 带头结点*q=L； *指向第一数据前趋 *while(q 一next!=NULL)p1=q 一next；minp=p1； *minp 指向当前已知的最小数*while(p1 一next!=NULL)if(p1 一next 一datadata)minp=pl 一 next, *找到了更小数*pl=pl-next； *继续往下找 *if(minp!=q 一 next) *将最小数交换到第一个位置上*r1=minp 一next；minp 一next=r1 一next； *删除最小数*r2=q 一next；q 一next=r2 一next； *删除当前表中第一个数 *r
28、l 一next=q 一next；q 一next=r1； *将最小插入到第一位置上 *r2 一 next=minp 一next；minp 一next=r2； *将原第一个数放到最小数原位置上*q=qnext； *选择下一个最小数*【试题解析】 每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当前的有序表区的最后。【知识模块】 内部排序33 【正确答案】 Void sort(dlklinkh)*链表 h 采用带头结点的双循环链表*pre=h 一next；while(p!=h)P=pre 一next； *P 是有序表的末尾*q=P 一next； *保存下一个插入元素*while(pr
29、e!=h)(P 一 datadata)pre=pre 一prior ； *从后往前找插入位置*if(pre!=P 一prior)P 一prior 一next=P 一next；P 一next 一prior=Pprior ；*删除 P*P 一next=pre 一next；pre 一next 一prior=p；P 一prior=pre；pre 一next=p； *插入到 pre 之后*p=q；【试题解析】 本算法采用的存储结构是带头结点的双循环链表。首先找元素插入位置，然后把元素从原链表中删除，插入到相应的位置处。请注意双链表上插入和删除操作的步骤。【知识模块】 内部排序34 【正确答案】 Void
30、 sort(datatype an)*n 为元素个数，数组下标从 1 开始，到 n 结束* for(i=2；iamid：low=mid+1； *修改下界*for(j=i 一 1;j=mid；j 一一)aj+1=aj;amid=ai;【试题解析】 插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小括入到前面的有序区中。对于有序区，当然可以用二分查找来确定插入位置。【知识模块】 内部排序35 【正确答案】 Voidqksort(datatypeAn)*n 为元素个数* Setnuli(s)； *设置一个栈保存有关参数和变量*l=1； h=n； *l，h 分别指向表头和表尾 *while(1h)|(!emptu(s)( while(1h)quickpass(A，1，h，i);push(s，l，h，i); *保存变量值*h=i 一 1; *设置对左边进行划分的参数*if(!empty(s)pop(s，l， h，i) ； *取出变量值*l=i+1： *设置对右边进行划分的参数*【试题解析】 先调用划分函数 quickpass()，以确定中间元素的位置，然后再借助栈分别对中间元素左、右两边的区域进行快速排序。【知识模块】 内部排序
