全国自考数据结构导论（内部排序）模拟试卷1

全国自考数据结构导论（内部排序）模

拟试卷1

一、单项选择题（本题共75题，每题7.0分，共75

分。）

1、排序方法的稳定性是指。

A、排序算法能在规定的时间内完成排序

B、排序算法能得到确定的洁果

C、排序算法不允许有相同关键字的数据元素

D、以上都不对

标准答案：D

知识点解析：暂无解析

2、排序的目的是为了以后对已排序的数据元素进行操作。

打印

A、

分类

B、

合并

C、

查找

D、

标准答案：D

知识点解析：排序的目的主要是为了查找方便，因为在很多场合下，查找是最常见

的操作之一。对于一个已排序过的表或文件来说，可以使用二分查找等一些高效率

的方法来进行查找操作。

3、在时一组关键字序列［70,55,100,15,33,65,50,40,95）进行直接插入排

序时，把65插入到有序序列需要比较次。

A、2

B、4

C、6

D、8

标准答案：A

知识点解析：暂无解析

4、若有关键字序列{42,70,50,33,40,80},则利用快速排序的方法，以第一

个关键字为基准元素得到的一次划分结果为o

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,80

标准答案：A

知识点解析：暂无解析

5、快速排序方法在_____情况下最不利于发挥其长处。

A、要排序的数据量太大

B、要排序的数据中含有多个相同值

C、要排序的数据个数为奇数

D、要排序的数据已基本有序

标准答案：D

知识点解析：暂无解析

6、用某种排序方法对线性表(35,90,15,50,10,30,75,28,13)进行排序时

得到以下中间结果，则所采用的排序方法是o13,28,15,30,10,

35,75,50,9010,13,15,30,28,35,50,75,9010,13,15,28,

30,35,50,75,90

A、希尔排序

B、二路归并排序

C、快速排序

D、堆排序

标准答案：C

知识点解析：暂无解析

7、以下序列不是堆c

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,98

标准答案：C

知识点解析：暂无解析

8、将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用

方法能够最快地找出其中最大的正整数。

A、快速排序

B、插入排序

C、选择排序

D、二路归并排序

标准答案：C

知识点解析：选择排序的基本思想是：每趟在待排序序列中选取当前最小的元素，

并将它插入有序序列的后面，因此稍加修改，该排序方法就可以用于解决本题的问

题。

9、在排序过程中，键值比较的次数与初始序列的排列顺序无关的是。

A、直接插入排序和快速排序

B、直接插入排序和二路归并排序

C、直接选择排序和二路归并排序

D、快速排序和二路归并排序

标准答案：C

知识点解析：初始序列的排列顺序对直接插入排序和快速排序有影响，而对直接选

择排序和二路归并排序则没有影响，故正确的答案是Co

10、以下排序方法中，不能保证每趟排序至少能将一个数据元素放到其最终位置上

的排序方法是。

A、堆排序

B、冒泡排序

C、希尔排序

D、快速排序

标准生宝.C

知识,解析：暂无解析

11、以下四种排序方法中，要求附加的内存空量最大的是。

A、插入排序

B、选择排序

C、快速排序

D、二路归并排序

标准答案：D

知识点解析：对前三种排序方法来讲，对附加内存容量几乎没有要求，但二路归并

排序中，由于在二路归并过程中需要有两个同样大小的数组，用于来回对倒。困

此，这种排序方法要求附加的内存容量最大。

12、若有关键字序列{20,80,10,50,60,95,15,55,30,40},并且该序列是

由5个长度为2的子序列组成，则用二路归并排序方法对该序列进行一趟二路归并

后的结果为。

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。95

标准答案：A

知识点解析：暂无解析

13、以下排序方法是不稳定的排序方法。

A、冒泡

B、堆

C、直接插入

D、二路归并排序

标准答案：B

知识点解析：稳定排序有直接插入、冒泡排序、二路归并排序；不稳定排序有快速

排序、直接选择排序、堆排序、希尔排序。

14、快速排序在最坏情况下的时间复杂度是。

A、O(log2n)

B、O(nlog2n)

C、0(n2)

D、0(n3)

标准答案：C

知识点解析：当待排序空间事先己基本有序时，每趟快速排序后得到的左、右两个

待排序小空间严重不对称，因此，差不多要进行n趟次快速排序，每趟排序又要进

行n级次数的比较，故最坏情况下，总的比较次数将达到0(户)。

15、当文件局部有序或文件长度较小的情况下，最佳的排序方法是2。

A、直接插入排序

B、直接选择排序

C、冒泡排序

D、二路归并排序

标准答案：B

知识点解析：在本章介绍的几种排序方法中，冒泡排序算法里设置了一个标志，以

判别某趟排序过程中，待排序空间是否自然有序。因此它适用于局部有序的文件。

另外，冒泡排序属于内部排序，在文件较小时，允许用内部排序算法进行排序，故

本题的正确答案是B。

二、填空题(本题共10题，每题1.0分，共10分。)

16、根据在排序过程中使用的存储器将排序方法分为：和o

标准答案：内部排序外部排序

知识点解析：哲无解析

17、常用的插入排序有和。

标准答案：直接插入排序希尔排序

知识点解析：暂无解析

18、对于直接插入排耳和直接选择排序，若待排序序列基本有序，则选用较

好；若待排序序列为逆序，则选用较好。

标准答案：直接插入直接选择

知识点解析：暂无解析

19、直接插入排序在最好情况下的时间复杂度为:在最坏情况下的时间复

杂度为o

标准答案：0(n)0(/)

知识点解析：暂无解析

20、若堆中某一数据元素在数组中的下标为30,则它的左孩子的下标为,

右孩子的下标为0

标准答案：6162

知识点解析：暂无解析

21、对于堆排序和快速排序，若待排序序列基本有序，则选用较好；若待排

序序列无序，则选用较好。

标准答案：堆排序快速排序

知识点解析：暂无解析

22、常用的选择排序方法有和o

标准答案：直接选择排序堆排序

知识点解析：暂无解析

23、设有字母序列｛P,D,F,Z,E,P,N,B,X,M,G,w),请写出按二路

归并排序方法对该序列进行一趟扫描后的结果o

标准答案：DPFZEPBNMXGW

知识点解析：暂无解析

24、设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序

和二路归并排序方法对其仍按递增顺序进行排序，则最省时间最费时

间。

标准答案：冒泡排序快速排序

知识点解析：对冒泡排序来讲，由于算法中设置了一个标志flag,用于记载一趟排

序中是否出现了记录交换，以便判断当前待排序区域是否已自然有序。因此本题中

用冒泡排序最省时间。当初始时记录已按键值递增有序，若采用快速排序法，每次

所选取的中间元素都是最小的，故划分出的左右两个区域一个为空，另一个比原区

域少一个元素，使得元素收比较次数只比上一趟少1，所以总的时间消耗是

O(n2),因此在本题中用快速排序法最费时间。

25、刈快速排序来讲，其最好情况下的时间夏杂度是，其最坏情况下的M

间复杂度是o

标准答案：O(nlog2n)0(/)

知识点解析：快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、

右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区

域中元素的关键字都不小于中间元素的关健字，接卜.来再按上述思路继续对各个区

域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎•等长的

两个区域，这样仅需log2n趟划分即可。每趟划分所需时间复杂度为0(n),最好情

况下的时间复杂度是O(nlog2n)。最坏情况下，每次选取的中间元素不是最大就是

最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要

n1趟划分。每趟划分的时间复杂度为0(n),因此，最坏情况下的时间复杂度为

0(/)。

三、应用题(本题共70题，每题7.0分，共70分。)

26、在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移

动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?请举一例说明。

标准答案：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相

对次序在排序前、后发生了变化，而题中叙述和排序中稔定性的定义无关，所以此

说法不对。例如，对4,3,2,1冒泡排序就可否定本题结论。

知识点解析：暂无解析

27、举例说明本章介绍的各排序方法中哪些是不稳定的？

标准答案：稳定排序有直接插入、冒泡排序、二路归并排序。不稳定排序有快速

排序、直接选择排序、堆排序。不稳定排序举例：(1)快速排序。初始状态3967

355099671055排序后1035395055676799(2)堆排序。初始状态67387597

80132767排序后1327386767758097(3)直接选择排序。初始状态39673550

99671055排序后1035395055676799(其中67表示记录初始位置在67记录位

置之后)

知识点解析：暂无解析

28、对于给定的一组键值:83,40,63,13,84,35,96,57,39,79,61,15,

分别画出应用直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、二

路归并排序对上述序列进行排序中各趟的结果。

标准答案：(1)直接插入排序。序号123456789101112关键字8340631384

35965739796115i=I83[4063138435965739796115]i=24083|63138435

965739796115]i=3406383|138435965739796115]i=413406383[843596

5739796115]i=51340638384[35965739796115|i=6133540638384[9657

39796115]i=713354063838496[5739796115]i=81335405763838496(39

7961I5ji=9133539405763838496(796115]1=1013353940576379838496

[6115]i=ll1335394057616379838496[15]i=1213153539405761637983

8496(2)希尔排序。序号I23456789101112关键字834063138435965739

796115第1趟(d1=6)后834039136115965763798435第2趟(d2=3)后1340

15795735836139968463第3趟(d3=l)后131535394057616379838496⑶

冒泡排序。序号12345678910II12关键字834063138435965739796115

第1趟排序后4063138335845739796115[96]第2趟排序后401363358357

39796115[8496]第3趟排序后134035635739796115[838496]第4趟排序后

1335405739636115[79838496]第5趟排序后13354039576115[63798384

96]第6趟排序后133539405715[616379838496]第7趟排序后1335394015

[57616379838496]第8趟排序后13353915|4057616379838496]第9趟排

序后133515[394057616379838496]笫10趟排序后1315(35394057616379

838496]第11趟无元素交换，则排序结束。(4)快速排序。序号123456789

10II12关键字834063138435965739796115第1趟排序后[154063136135

795739]83[96841第2趟排序后[13]15[63136135795739]83[9684]第3趟排序

后1315(3940613557363[79]83[9684]第4趟排序后1315F35]39[614057-163

798319684]第5趟排序后13153539[5740]61637983(9684]第6趟排序后1315

353940(57]61637983[9684]第7趟排序后131535394057616379838496(5)

直接选择排序。序号123456789101112关键字83406313843596573979

6115i=l13(4063838435965739796115]i=21315[638384359657397961

40]i=3131535(838463965739796140]i=413153539[8463965783796140]

i=51315353940[63965783796184]A6131535394057[966383796184]i=7

13153539405761(6383799684]i=81315353940576163(83799684]i=913

1535394057616379[839684]i=1013153539405761637983[9684]i=ll13

15353940576163798384[96](7)二路归并排序。序号I23456789101112

关键字834063138435965739796115第1趟排序后[40833口363][3584][57

96][3979Hl561]第2趟排序后[13406383][35578496][15396179]第3趟排序后

[1335405763838496][15396179]第4趟排序后1315353940576163798383

96

知识点解析：暂无解析

29、设有10000个无序的数据元素，可供选择的排序方法有：二路归并排序、堆排

序、希尔排序和快速排序。现在希望用最快速度挑选出削10个最大的数据元素，

问采用什么方法最好?为什么？

标准答案：这几种方法速度都很快，但二路归并排序、希尔排序和快速排序都是在

排序结束后才能确定数据元素的顺序，无法提前知道数据元素的有序性。只有堆排

序，每次均输出最大(或最小)的数据元素，因此采用它比较合适。

知识点解析：暂无解析

30、试比较直接插入排序、直接选择排序、快速排序、堆排序、二路归并排序的时

空性能。

标准答案：直接插入排序、直接选择排序、快速排序、堆排序和二路归并排序时空

性如下表：

排序方法平均时间最坏时间辅助空间

直接插人O(n2)O(n2)O(D

直接选界O(n2)()(n:)O(1)

快速排序()(nlogxn)O(n:)O(nlogtn)

堆排序0(nlogjn)()(nlogan)O())

二路归并排序()(nlog?n)O(nlog2n)()(n)

从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速

排序在最坏情况下，时间性能不如堆排序和二路归并排序。而后两者相比的结果

是，当n较大时，二路归并排序所需时间优于堆排序，但它所需辅助空间最多。

注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于n较大的情况，

有的适用于n较小的情况，还有的与关键字的分布和初始位置有关……因此，在实

际使用时，需要根据不同情况适当选用排序方法，其至正将多种方法结合使用。

知识点解析：暂无解析

31、采用单链表作存储结构，编写一个采用选择排序方法进行升耳排耳的函数。

标准答案：依题意，单链表定义如下：structnode{intkey；structnode*ljak；);

因此，实现本题功能的函数如卜：struct*sclcctsort(structnodc*h){struct：nodc*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(lklistL)/*设链表L带头结点*/{q=L；/*指向第一数

据前趋*/while(q->next!=NULL){pl=q->next；minp=pl：/*minp指向当前

已知的最小数*/while(pl_*>next!=NULL){if(pl->nexi—>daiada(a)minp=pl

一〉next,/*找到了更小数*/pl=pl->ncxt；/*继续往下找*/}if(minp!=q

一：>next)/*将最小数交换到第一个位置上*/{rl=minp->next：minp—>next=rl

一〉next；/*删除最小数*/r2=q—>nexl；q_*>next=r2-">next；/*删除当前

表中第一个数*/rl—>ncxt=q-*>ncxt；q—>ncxt=rl；/*将最小插入到第一位置

上*/r2—>next=minp->next；minp一>next=r2；/*将原第一个数放到最小数

原位置上*/)q=q>next；/*选择下一个最小数*/()

知识点解析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插

入到当前的有序表区的最后。

33、设计一个用链表表示故直接插入排序算法。

标准答案：Voidsort(dlklinkh)/*链表h采用带头结点的双循环链表*/{pr