数据结构排序习题

一、选择：(每题2分，共30分) 简单选择排序 冒泡排序 归并排序 稳定1、下列排序算法中，其中（ ）是稳定的。

堆排序 希尔排序 快速排序 基数排序 不稳定A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序 2、下列排序方法中，哪一个是稳定的排序方法？（ ）A)堆排序 B)二分法插入排序 C)希尔排序 D)快速排序3、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。

A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2 4、非空循环链表head 的尾结点 *p 满足下列( )条件A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 5、下列编码中属前缀码的是( )A){1,01,000,001} B){1,01,011,010} C){0,10,110,11} D){0,1,00,11} 6、对于哈希函数H(key)=key % 7,被称为同义词的关键字是( )A)36和50 B)23和39 C)15和44 D)25和517、将一个长度为n 的向量的第i 个元素删除时，需要前移( )个元素。

A) i B) n-i C) n+1 D) n-i+18、有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找62，要经过( )次比较。

A. 3 B. 6 C. 4 D. 5 9、高度为 K 的二叉树最大的结点数为（ ）。

A)2k B)2k-1 C)2k -1 D)2k-1-110、对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )A) (n-1)/2 B) n/2 C) (n+1)/2 D) n11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim 算法 D)拓扑排序算法12、已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( )。

计算机专业基础综合数据结构（排序）历年真题试卷汇编3(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。

【北京航空航天大学1999一、10(2分)】A.插入B.冒泡C.二路归并D.堆√2.下列排序算法中，其中( )是稳定的。

【福州大学1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序√3.稳定的排序方法是( )。

【北方交通大学2000二、3(2分)】A.直接插入排序和快速排序B.折半插入排序和起泡排序√C.简单选择排序和四路归并排序D.树形选择排序和Shell排序4.下列排序方法中，哪一个是稳定的排序方法?( )。

【北方交通大学2001一、8(2分)】A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。

【北京理工大学2007一、10(1分)】A.希尔排序B.快速排序C.堆排序D.直接插入排序√6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

( )就是不稳定的排序方法。

【清华大学1998一、3(2分)】A.起泡排序B.归并排序C.Shell排序√D.直接插入排序E.简单选择排序√7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。

【中科院计算所2000一、5(2分)】A.直接插入√B.直接选择C.堆D.快速E.基数8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】A.快速排序B.堆排序C.归并排序√D.直接插入排序9.下面的排序算法中，不稳定的是( )。

【北京工业大学1999一、2(2分)】A.起泡排序B.折半插入排序C.简单选择排序√D.希尔排序√E.基数排序下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B．直接插入排序C．二路归并排序D．简单选择排序E．起泡排序（分数：8.00）(1).其比较次数与序列初态无关的算法是( )A.B.C. √D. √E.(2).不稳定的排序算法是( )A. √B.C.D. √E.(3).在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<A.B. √C.D.E.(4).排序的平均时间复杂度为O(n*10gn)的算法是( )，为O(n*n)的算法是( )A. √B. √C. √D. √E. √10.排序趟数与序列的原始状态有关的排序方法是( )排序法。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

计算机学科专业基础综合数据结构-内部排序(总分80,考试时间90分钟)一、单项选择题1. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15)；则采用的是____排序。

A. 选择B. 快速C. 希尔D. 冒泡2. 下列4个序列中，哪一个是堆____。

A. 75，65，30，15，25，45，20，10B. 75，65，45，10，30，25，20，15C. 75，45，65，30，15，25，20，10D. 75，45，65，10，25，30，20，153. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为____。

A. (38，40，46，56，79，84)B. (40，38，46，79，56，84)C. (40，38，46，56，79，84)D. (40，38，46，84，56，79)4. 数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中____的两趟排序后的结果。

A. 选择排序B. 冒泡排序C. 插入排序D. 堆排序5. 对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为____。

(1)84 47 25 15 21 (2)1 5 47 25 84 21(3)15 21 25 84 47 (4)1 5 21 25 47 84则采用的排序是____。

A. 选择B. 冒泡C. 快速D. 插入6. 若用冒泡排序对关键字序列{18，16，14，12，10，8}，进行从小到大的排序，所需进行的关键字比较总次数是____。

A. 10B. 15C. 21D. 347. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为____。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第八章）1、若数据元素序列{11,12,13,78,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )A、冒泡排序B、插入排序C、选择排序D、归并排序2、若将两个各有n个元素的有序表归并成一个有序表，则最少比较次数是()。

A、 nB、 2*n-1C、 2nD、 n-13、已知数据表中每个元素距其最终位置不远，则采用（）方法最节省时间A、堆排序B、插入排序C、快速排序D、直接选择排序4、下列排序算法中，（）算法可能会出现下面情况：在后一趟开始之前，所有元素都不在其终的位置上。

A、堆排序B、冒泡排序C、快速排序D、插入排序5、下述几种排序方法中，要求内存量最大的是()。

A、插入排序B、快速排序C、归并排序D、选择排序6、就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A、堆排序<快速排序<归并排序B、堆排序<归并排序<快速排序C、堆排序>归并排序>快速排序D、堆排序>快速排序>归并排序7、快速排序方法在( )情况下最不利于发挥其长处。

A、要排序的数据量太大B、要排序的数据中含有多个相同值C、要排序的数据已基本有序D、要排序的数据个数为奇数8、对关键字由大到小进行冒泡排序，在下列（）情况下比较的次数最多。

A、从小到大排序B、从大到小排序C、元素无序D、元素基本有序9、对5个不同的数据元素进行直接插入排序，最多需要进行()次比较。

A、 8B、 10C、 15D、 2510、如果只想得到1000个元素组成的序列中第5个小元素之前的部分排序的序列，用（）方法快。

A、起泡排序B、快速排列C、堆排序D、简单选择排序11、设有1000个无序的元素，希望用最快的速度挑选出其中前十个最大的元素，在以下的排序方法中采用哪一种最好？()A、快速排序B、归并排序C、堆排序D、基数排序12、下列排序算法中，（）可能会出现下面情况：在最后一趟开始之前，所有元素都不在最终位置上。

第8 章排序技术课后习题讲解1. 填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。

【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。

⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。

在（）情况下比较次数最多，其比较次数为（）。

【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。

⑷对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。

【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。

【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。

【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。

【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。

2. 选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。

A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。

⑵下列序列中，（）是执行第一趟快速排序的结果。

A [da，ax，eb，de，bb] ff [ha，gc]B [cd，eb，ax，da] ff [ha，gc，bb]C [gc，ax，eb，cd，bb] ff [da，ha]D [ax，bb，cd，da] ff [eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。

《数据结构》练习题一、解答题（共50分）1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所示。

请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算WPL 。

2. （8分）若一棵二叉树中序遍历和后序遍历序列分别为：DBEHGAFIC 和DHGEBIFCA 。

试画出这棵二叉树，并写出其先序遍历和层序遍历序列。

3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的顶点表按字母a 、b 、c 、d 、e 、f 、g 、h 的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。

请画出其邻接表，并写出从顶点f 出发，分别进行深度和广度优先遍历的序列，写出用Prime 方法从顶点c开始产生最小生成树的边的序列。

4.（8分）已知键值序列为(44，39，67，25， 52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。

⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（ ）。

⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进行排序，第一趟的排序结果是（ ）。

二、完善程序（共20分，每空2分）1.假设一组递减有序的原始数据存储在数组r 中，存放元素的下标下限为low,下标上字符 出现频率 a 0.05 b 0.03 c 0.24 d 0.16 e 0.08 f 0.24 g 0.18 h0.02限为high,以下是在数组中查找数值为k的折半查找算法。

请填空完善程序。

int BinSearch(int r[ ], int low,int high,int k){ int l,h,m;l= low; h= high;while ( ⑴){m= ⑵;if (k < r[m]) ⑶;else if (k > r[m]) ⑷;else return m;}return 0;}2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。

计算机专业基础综合数据结构（排序）历年真题试卷汇编5(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。

【2009年全国试题9(2分)】A.3，5，12，8，28，20，15，22，19 √B.3，5，12，19，20，1 5，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，1 5，22，19首先按所给关键字序列画出完全二叉树，关键字3插入结点22的后边。

沿结点3到根的路径调整堆，直到满足堆的定义为止。

2.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。

【2009年全国试题10(2分)】A.起泡排序B.插入排序√C.选择排序D.二路归并排序起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。

3.采用递归方式对顺序表进行快速排序。

下列关于递归次数的叙述中，正确的是( )。

【2010年全国试题10(2分)】A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关√快速排序和数据的初始排列次序相关。

每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。

4.对一组数据(2，12，1 6，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是( )。

数据结构(C语言版)习题及答案第九章数据结构(C语言版)习题及答案习题一、选择题1、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为( B )。

A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，382、排序趟数与序列原始状态(原始排列)有关的排序方法是（ACD ）方法。

A、插入排序B、选择排序C、冒泡排序D、快速排序3 、下列排序方法中，（B ）是稳定的排序方法。

A、直接选择排序B、二分法插入排序C、希尔排序D、快速排序4、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。

A、选择排序B、冒泡排序C、插入排序D、堆排序5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（C ）排序。

A、选择B、快速C、希尔D、冒泡6 、一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（C ）。

A、(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)7、用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（C ）。

A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,408、若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（B ）。

A、10B、15C、21D、349、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（ A ）。

第九章内部排序
1．以关键字序列（503,087,512,061,908,170,897,275,653,426）为例，手工执行以下排序方法，写出每一趟排序结束时的关键字状态。

（1）直接插入排序；（2）希尔排序（增量5,3,1）；（3）快速排序；
（4）堆排序；（5）归并排序；（6）基数排序。

2．对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始序列。

（1）n=7时的最好情况下需进行多少次比较？说明理由。

（2）对n=7给出一个最好情况的初始排序实例。

3．已知一个单链表由3000个元素组成，每个元素是一个整数，其值在1~1000000之间。

试考察在所学的几种排序方法中，哪些方法可用于解决这个链表的排序问题？哪些不能，简述理由。

4．比较各种排序方法的时间复杂度、空间复杂度和稳定性。

线性表1.下列有关线性表的叙述中，正确的是（A）。

A）线性表中元素之间的关系是线性关系B）线性表中至少有一个元素C）线性表中的任一元素有且仅有一个直接前趋D）线性表中的任一元素有且仅有一个直接后继2.下述哪一条是顺序存储结构的优点？（A）A）存储密度大B）插入方便C）删除方便D）可方便地用于各种逻辑结构的存储表示3.在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动（D）个元素。

A）1 B）n-i C）n-i-1 D）n-i+14.如果某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，那么采用（A）存储方式最节省时间。

A）顺序表B）单链表C）双链表D）循环链表5.对顺序存储的线性表，设其长度为n，且在任何位置上插入或删除操作都是等概率的。

则插入一个元素时平均要移动表中的（A）个元素。

A）n/2 B）(n+1)/2 C）(n-1)/2 D）n6.下述哪一条是顺序存储结构的缺点？（C）A）存储密度太大B）随机存取C）一般要估计最大的需要空间D）只能应用于少数几种逻辑结构的存储表示7.在单链表中，增加头结点的目的是（C）。

A）使单链表至少有一个结点B）标志表中首结点的位置C）方便运算的实现D）说明单链表是线性表的链式存储表示8.单链表不具有的特点是（A）。

A)可随机访问任一元素B)插入和删除不需要移动元素C)不必事先估计存储空间D)所需空间和线性表长度成正比9.循环链表的主要优点是（D）。

A）不再需要头指针了B）已知某个结点的位置后，能够容易找到他的直接前趋C）在进行插入、删除运算时，能更好的保证链表不断开D）从表中的任意结点出发都能扫描到整个链表10.链表对于数据元素的插入与删除是（B）。

A）不需移动结点，不需改变结点指针B）不需移动结点，只需改变结点指针C）只需移动结点，不需改变结点指针D）既需移动结点，又需改变结点指针11.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若要在q 和p 所指结点之间插入s所指的结点,则执行（B）。

（2）当n较大时，应该选用先进的排序方法。

对于先进的排序方法，从平均时间性能而言，快速排序最佳，是目前基于比较的排序方法中最好的方法。

但在最坏情况下，即当关键字基本有序时，快速排序的递归深度为n，时间复杂度为O(n2)，空间复杂度为O(n)。

堆排序和归并排序不会出现快速排序的最坏情况，但归并排序的辅助空间较大。

这样，当n较大时，具体选用的原则是：①当关键字分布随机，稳定性不做要求时，可采用快速排序；②当关键字基本有序，稳定性不做要求时，可采用堆排序；③当关键字基本有序，内存允许且要求排序稳定时，可采用归并排序。

（3）可以将简单的排序方法和先进的排序方法结合使用。

例如，当n较大时，可以先将待排序序列划分成若干子序列，分别进行直接插入排序，然后再利用归并排序，将有序子序列合并成一个完整的有序序列。

或者，在快速排序中，当划分子区间的长度小于某值时，可以转而调用直接插入排序算法。

（4）基数排序的时间复杂度也可写成O(d·n)。

因此，它最适用于n值很大而关键字较小的序列。

若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则亦可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。

但基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围，即只适用于像整数和字符这类有明显结构特征的关键字，当关键字的取值范围为无穷集合时，则无法使用基数排序。

（5）由于大多数情况下排序是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。

若排序按记录的次关键字进行，则必须采用稳定的排序方法。

一般来说，如果排序过程中的“比较”是在“相邻的两个记录关键字”间进行的，则排序方法是稳定的。

值得提出的是，稳定性是由方法本身决定的，证明一种排序方法是稳定的，要从算法本身的步骤中加以证明；而证明排序方法是不稳定的，只需举出一个不稳定的实例来说明。

（6）在本章讨论的排序方法中，多数是采用顺序表实现的。

计算机学科专业基础综合数据结构-排序(一)(总分：44.00，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：19，分数：32.00)1.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。

采用不同的排序方法将产生不同的排序中间结果，设要将集合{tang，deng，an，wan，shi，bai，fang，li}中的排序码按升序排列，则______是初始步长为4的希尔排序一趟扫描的结果。

∙ A.an，bai，deng，fang，li，shi，tang，wan∙ B.an，tang，deng，wan，shi，bai，fang，li∙ C.li，deng，an，shi，bai，fang，tang，wan∙ D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C.D. √解析：[解析] 希尔排序是按增量将关键字分组。

首先取增量d1＜n把全部关键字分成d1个组，所有距离为d1的元素放在一组中，各组内用直接插入排序法排序；然后取d2＜d1，重复上述分组和排序工作，直至取d t=1。

选项D是取d1=4的一趟排序的结果。

2.以下关于希尔排序的说法中，正确的是______。

∙ A.当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快∙ B.当待排序元素序列的初始排列基本逆序时，希尔排序比直接插入排序快∙ C.当待排序元素序列的初始排列基本有序时，希尔排序比起泡排序快∙ D.当待排序元素序列的初始排列基本逆序时，希尔排序比起泡排序慢（分数：2.00）A.B. √C.D.解析：[解析] 当待排序元素序列的初始排列基本有序时，希尔排序的排序码比较次数为n*(log2n-1)+1，元素移动次数为0。

直接插入排序的排序码比较次数为n-1，元素移动次数为0，起泡排序的排序码比较次数为n-1，元素移动次数为0。

因此希尔排序不比直接插入排序和起泡排序快，选项A和选项C不正确。

计算机专业基础综合数据结构（排序）历年真题试卷汇编7(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下述几种排序方法中，要求内存量最大的是( )。

【中南大学2005一、6(2分)】A.归并排序√B.快速排序C.插入排序D.选择排序2.快速排序方法在( )情况下最不利于发挥其长处。

【华南理工大学2007】A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序√3.当待排序列基本有序时，下列排序方法中( )最好。

【北京邮电大学2005一、10 (2分)】A.直接插入排序√B.快速排序C.堆排序D.归并排序4.设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( )。

【上海交通大学2005四、5(2分)】A.O(N)，O(N)，O(N)B.O(N)，O(N*log 2 N)，O(N*log 2 N)C.O(N)，O(N*log 2 N)，O(N 2 ) √D.O(N 2 )，O(N*log 2 N)，O(N 2 )5.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的( )的两趟排序后的结果。

【合肥工业大学1999一、3(2分)】A.选择排序B.冒泡排序C.插入排序√D.堆排序对于A、B和D三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。

6.一个排序算法的时间复杂度与( )有关。

【华中科技大学2004一、8(1分)】A.排序算法的稳定性B.所需比较关键字的次数√C.所采用的存储结构D.所需辅助存储空间的大小7.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47 (4)15 21 25 47 84则采用的排序是( )。