数据结构习题精编：排序

资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载数据结构第九章排序习题及答案地点：__________________时间：__________________说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时请详细阅读内容习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序3．对一组数据（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则采用的排序是 ( )。

A. 选择B. 冒泡C. 快速D. 插入4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B. 冒泡C. 归并D. 堆5．一组记录的关键码为（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)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

第八章排序：习题习题一、选择题1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序2．设有1000个无序的记录，希望用最快的速度挑选出其中前10个最大的记录，最好选用( )排序法。

A.冒泡排序B.快速排序C.堆排序D.基数排序3．在待排序的记录序列基本有序的前提下，效率最高的排序方法是( )。

A.插入排序B.选择排序C.快速排序D.归并排序’4．不稳定的排序方法是指在排序中，关键字值相等的不同记录的前后相对位置( )。

A.保持不变B.保持相反C.不定D.无关5．内部排序是指在排序的整个过程中，全部数据都在计算机的( )中完成的排序。

A. 内存储器B.外存储器C.内存储器和外存储器D.寄存器6．用冒泡排序的方法对n个数据进行排序，第一趟共比较( )对记录。

A.1B.2C.n-lD.n7．直接插入排序的方法是从第( )个记录开始，插入前边适当位置的排序方法。

A.1B.2C.3D.n8．用堆排序的方法对n个数据进行排序，首先将n个记录分成( )组。

A.1B.2C.n-lD.n9．归并排序的方法对n个数据进行排序，首先将n个记录分成( )组，两两归并。

A.1B.2C.n-lD.n10．直接插入排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树11．冒泡排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树12．快速排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树13．排序方法中，从未排序序列中依次取出记录与已排序序列（初始时为空）中的记录进行比较，将其放入已排序序列的正确位置上的方法，称为( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序14．每次把待排序的记录划分为左、右两个子序列，其中左序列中记录的关键字均小于等于基准记录的关键字，右序列中记录的关键字均大于基准记录的关键字，则此排序方法叫做( )。

习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D.简单选择排序E. 起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为 O(n?n) 的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（ 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则采用的排序是 ()。

A. 选择B.冒泡C.快速D.插入4．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B.冒泡C.归并D.堆5．一组记录的关键码为（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)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。

A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。

A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。

一、单选题1、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，5，2，37)B.(19，21，37，5，2)C.(19，21，2，5，37)D.(19，21，5，37，2)正确答案：B2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，37，5，2)B.(19，21，2，5，37)C.(19，21，5，37，2)D.(19，21，5，2，37)正确答案：D3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。

A.(113，165，176，197，127，138，149)B.(113，165，176，127，197，138，149)C.(113，127，138，149，165，176，197)D.(149，138，165，197，176，113，127)正确答案：A4、下列各项键值（）序列不是堆的。

A.(5，23，68，16，94)B.(5，23，16，94，68)C.(5，16，23，68，94)D.(5，23，16，68，94)正确答案：A5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。

A.(24，62，36，19)(24，36，62，19)(19，24，36，62)B.(24，62，19，36)(19，24，36，62)C.(62，24，36，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)正确答案：B6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（）。

A.归并排序B.快速排序C.冒泡排序D.选择排序正确答案：A7、对于下列排序，（）的时间效率与关键字初始序列有直接关系。

数据结构排序历年考研练习题库试卷及答案数据结构排序历年考研练习题库试卷及答案一、冒泡排序冒泡排序是一种基本的排序算法，它通过重复地交换相邻两个元素的位置来实现排序。

算法的基本思想是从待排序的元素中比较相邻的两个元素大小，并根据需要交换它们的位置，直到整个序列有序为止。

冒泡排序的原理如下：首先从序列的第一个元素开始，比较相邻的两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置；否则，继续比较下一对相邻元素，直到比较到序列的最后一个元素。

这样一趟比较下来，序列中最大的元素就会被交换到最后一个位置。

接着，对序列中剩下的 n-1 个元素重复上述过程，执行 n-1 趟比较，直到整个序列有序。

在实践中，冒泡排序的时间复杂度为 O(n^2)，其中 n 为待排序序列的长度。

尽管冒泡排序存在其它更好的排序算法，但它具有编码简单、实现容易以及对小规模数据排序的优势。

二、选择排序选择排序也是一种简单直观的排序算法，它的思想是将待排序序列分为已排好序的部分和未排序的部分，每次选取未排序部分中最小（或最大）的元素，将其放置在已排好序的部分的末尾。

重复此过程，直到整个序列有序。

选择排序的具体步骤如下：首先从待排序序列中找到最小（或最大）的元素，然后将其与序列的第一个元素交换位置，将该元素视为已排序部分；接着，在剩下的未排序部分中找到最小（或最大）的元素，将其与第二个元素交换位置，将该元素视为已排序部分的最后一个元素；以此类推，每次选择序列中最小（或最大）的元素，并将该元素放置在已排序部分的末尾。

最终完成排序。

选择排序的时间复杂度同样为 O(n^2)，其中 n 为待排序序列的长度。

相比于冒泡排序，选择排序的交换操作较少，因此在实际应用中，选择排序的性能要优于冒泡排序。

三、插入排序插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素逐个插入已排好序的部分中，直到整个序列有序。

与冒泡排序和选择排序不同，插入排序是一种原地排序算法。

数据结构习题精编：排序一、选择题1．下列排序方法中，稳定的排序方法是A．堆排序B．希尔排序C．快速排序D．直接插入排序2．下列排序方法中，不稳定的排序方法是A．冒泡排序B．归并排序C．直接插入排序D．简单选择排序3．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是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．O（nlog2n）和O（1）B．O（n2）和O（1）C．O（nlog2n）和O（n）D．O（n2）和O（n）9．直接插入排序在最好情况下的时间复杂度为A．O（log2n）B．O（n）C．O（nlog2n）D．O（n2）10．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A．堆排序B．归并排序C．插入排序D．冒泡排序11．如果在排序过程中，每次从未排序的记录中挑出最小（或最大）关键字的记录，加入到已排序记录的末尾，该排序方法是A．堆排序B．冒泡排序C．直接插入排序D．简单选择排序12．在采用下列某种排序方法进行排序时，出现这样一个情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

该排序方法是A．堆排序B．冒泡排序C．快速排序D．直接插入排序13．在待排序数据已有序时，花费时间反而最多的排序方法是A．堆排序B．冒泡排序C．快速排序D．希尔排序14．设某数据表中有10000个无序的元素，如果仅要求选出其中最大的10个元素，最好采用的排序方法为A．堆排序B．快速排序C．冒泡排序D．直接选择排序15．下列排序方法中，需要辅助存储空间为O（n）的是A．堆排序B．希尔排序C．快速排序D．归并排序16．借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为A．O（log2n）B．O（n）C．O（nlog2n）D．O（n2）17．用直接插入排序方法对下面四个序列进行非递减有序排序，元素比较次数最少的是A．21,32,46,40,80,69,90,94 B．32,40,21,46,69,94,90,80C．90,69,80,46,21,32,94,40 D．94,32,40,90,80,46,21,6918．对关键字序列（56，23，78，92，88，67，19，34）进行增量为3的一趟希尔排序的结果为A．(19，23，34，56，67，78，88，92) B．(19，23，56，34，78，67，88，92) C．(19，23，67，56，34，78，92，88) D．(23，56，78，66，88，92，19，34) 19．对序列{15，9，7，8，20，1，4} 用希尔排序方法排序，经一趟后序列变为{15，l，4，8，20，9，7}，则该次采用的增量是A．l B．2 C．3 D．420．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该序列按从小到大排序，经过一趟冒泡排序后的序列为A．16，28，34，54，62，60，73，26，43，95B．16，28，34，54，73，62，60，26，43，95C．28，16，34，54，62，60，73，26，43，95D．28，16，34，54，62，73，60，26，43，9521．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为A．36，44，49，55，81，88 B．44，36，49，55，81，88C．44，36，49，81，55，88 D．44，36，49，55，88，8122．对下列关键字序列用快速排序法进行排序时，速度最快的情形是A．{1，2，3，4，5，6，7} B．{4，2，3，7，6，5，1}C．{4，6，1，3，2，5，7} D．{6，5，7，3，4，1，2}23．采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是A．递归次数与初始数据的排列次数无关B．递归次数与每次划分后得到的分区处理顺序无关C．每次划分后，先处理较长的分区可以减少递归次数D．每次划分后，先处理较短的分区可以减少递归次数24．为实现快速排序算法，待排序序列宜采用的存储方式是A．顺序存储B．链式存储C．散列存储D．索引存储25．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为A．i B．i+1 C．n-i D．n-i+126．一组记录的关键字值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为A．（14，18，20，38，40，46，53，65，74，86）B．（14，18，38，46，65，40，20，53，86，74）C．（14，38，18，46，65，20，40，53，86，74）D．（14，86，20，38，40，46，53，65，74，18）27．下列关键码序列中，属于堆的是A．（15，30，22，93，52，71）B．（15，52，22，93，30，71）C．（15，71，30，22，93，52）D．（93，30，52，22，15，71）28．已知序列25、13、10、12、9是大根堆，在序列尾部插入新元素，将其再调整为大根堆，调整过程中元素之间进行的比较次数是A．1 B．2 C．4 D．5 29．已知关键字序列5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，1930．对记录序列（314，298，508，123，486，145）依次按个位和十位进行两趟基数排序之后所得结果为A．123，145，298，314，486，508 B．298，123，508，486，145，314C．486，314，123，145，508，298 D．508，314，123，145，486，298 31．对数据序列（10，9，6，8，20，1，3）进行排序，第一趟排序后的序列变为（3，9，1，8，20，6，10），则采用的排序方法是A．冒泡排序B．希尔排序C．快速排序D．简单选择排序32．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果为（18，12，19，22，49，30，65，35，86），则采用的排序方法是A．冒泡排序B．快速排序C．直接插入排序D．简单选择排序33．若数据元素序列11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是A．冒泡排序B．直接插入排序C．简单选择排序D．二路归并排序34．若数据元素序列2，1，4，9，8，10，6，20是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是A．快速排序B．冒泡排序C．直接插入排序D．简单选择排序35．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下：第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法可能是A．冒泡排序B．希尔排序C．归并排序D．基数排序二、填空题1．排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的__________中。

07排序【单选题】1. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。

A、直接插入B、简单选择C、希尔D、二路归并2. 直接插入排序在最好情况下的时间复杂度为（B）。

A、O(logn)B、O(n)C、O(n*logn)D、O(n2)3. 设有一组关键字值（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,384. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。

A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84D、40,38,46,84,56,795. 将两个各有n个元素的有序表归并成一个有序表，最少进行（A）次比较。

A、nB、2n-1C、2nD、n-16. 下列排序方法中，排序趟数与待排序列的初始状态有关的是（C）。

A、直接插入B、简单选择C、起泡D、堆7. 下列排序方法中，不稳定的是（D）。

A、直接插入B、起泡C、二路归并D、堆8. 若要在O(nlog2n)的时间复杂度上完成排序，且要求排序是稳定的，则可选择下列排序方法中的（C）。

A、快速B、堆C、二路归并D、直接插入9. 设有1000个无序的数据元素，希望用最快的速度挑选出关键字最大的前10个元素，最好选用（C）排序法。

A、起泡B、快速C、堆D、基数10. 若待排元素已按关键字值基本有序，则下列排序方法中效率最高的是（A）。

A、直接插入B、简单选择C、快速D、二路归并11. 数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（C）的两趟排序后的结果。

习题精选一、选择题1．★某内排序方法的稳定性是指（）。

【排序的基本概念】A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法D．以上都不对【答案】D2．★★下面给出的四种排序法中（）排序法是不稳定性排序法。

【排序的基本概念】A. 插入B. 冒泡C. 二路归并D. 堆积【答案】D3．★★若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

【排序的基本概念】A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【答案】C4．★★在初始序列已基本有序（除去n 个元素中的某k 个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（）【排序的基本概念】A．快速排序B.直接插入排序C. 二路归并排序D. 简单选择排序E. 堆排序【答案】B5．★★排序趟数与序列的原始状态有关的排序方法是（）排序法。

【排序的基本概念】A．插入B. 选择C. 冒泡D. 归并【答案】C6．★★数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后的结果。

【知识点综合】A．选择排序B.冒泡排序C.插入排序D.堆排序【答案】C7．★★一组记录的关键码为（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)【答案】C8. ★★在下面的排序方法中，辅助空间为O（n）的是( ) 。

【知识点综合】A．希尔排序B. 堆排序C. 选择排序D. 归并排序【答案】D9.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。

1、以下关于排序的叙述中正确的是（）。

A.排序方法都是在顺序表上实现的，在链表上无法实现排序方法B.稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高C.在顺序表上实现的排序方法在链表上也同样适合D.对同一个顺序表使用不同的排序方法进行排序，得到的排序结果可能不同正确答案：D解析： D、稳定的排序方法的效率不一定都比不稳定的排序方法高。

有些排序方法既可以上顺序表上实现，也可以在链表上实现，但不是所有的排序方法都如此。

由于排序方法具有不同的稳定性，所以对同一个顺序表（存在相同的多个关键字记录）使用不同的排序方法进行排序，得到的排序结果可能不同。

2、以下不属于内排序方法的是（）。

A.直接插入排序B.拓扑排序C.二路归并排序D.堆排序正确答案：B解析： B、拓扑排序是一种产生拓扑序列的方法，不属内排序方法。

3、目前来讲，基于比较的内排序方法最好的平均时间复杂度为（）。

A. O(log2n)B. O(n2)C. O(nlog2n)D. O(n)正确答案：C解析： C、目前来讲，基于比较的内排序方法最好的平均时间复杂度为O(nlog2n)。

4、对有n个记录的表进行直接插入排序，在最好情况下需比较（）次关键字。

A.n(n-1)/2B.n-1C.n/2D.n+1正确答案：B解析： B、直接插入排序在初始数据正序时效率最好，此时只需要n-1次关键字比较。

5、数据序列{8，9，10，4，5，6，20，1，2}只能是（）算法的两趟排序后的结果。

A.堆排序B.简单选择排序C.冒泡排序D.直接插入排序正确答案：D解析： D、采用排除法，因为两趟排序后结果中的有序区不是全局有序的，所以只能是直接插入排序，不可能是其他三种排序方法。

6、对数据序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排序变为{4，9，-1，8，20，7，15}，则采用的是（）算法。

A.冒泡排序B.希尔排序C.快速排序D.简单选择排序正确答案：B解析： B、因为一趟排序后结果中的有序区不是全局有序的，所以不可能是简单选择排序和冒泡排序。

一、单选题12．设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。

A．冒泡排序B．快速排序C．堆排序D．归并排序1．已知持排序的n个元素可分为n/k个组，每个组包含k个元素，各组间分块有序，若采用基于比较的排序，其时间下界应为：( )A．O(nlog2n) B．O(nlog2k) C．O(klog2n) D．O(klog2k))且稳定的排序方法是( )。

2．最好和最坏时间复杂度均为O(nnlog2A．快速排序B．堆排序C．归并排序D．基数排序3．下列排序算法中，当初始数据有序时，花费时间反而最多的是( )。

A．起泡排序B．希尔排序C．堆排序D．快速排序4．若需在O（nlog2n）的时间内完成排序，且要求稳定，则可选择（）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. 若要从1000个元素中得到4个最小值元素，最好采用（）方法。

A．直接插入排序B．直接选择排序C．堆排序D．快速排序10. 若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。

A．直接插入排序B．归并排序C．堆排序D．快速排序11. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。

A．直接插入排序B．归并排序C．堆排序D．快速排序12. 在下列排序方法中，空间复杂性为O(log2n)的方法为（）。

A．直接选择排序B．归并排序C．堆排序D．快速排序13. 在平均情况下速度最快的排序方法为（）。

《数据结构》习题汇编09-第九章-排序-试题数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（）。

A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。

A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。

A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。

A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。

A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

数据结构图,查找,内排序的练习及答案数据结构课后练习习题要求：此次练习不要求上交，只是帮助⼤家掌握知识点，便于复习。

第⼋章图⼀．单项选择题（20分）1. 带权有向图G ⽤邻接矩阵A 存储，则Vi 的⼊度等于A 中___D______A. 第i ⾏⾮∞的元素只和B. 第i 列⾮∞的元素之和C. 第i ⾏⾮∞且⾮0的元素之和D. 第i 列⾮∞且⾮0的元素个数2. ⽆向图的邻接矩阵是⼀个___A____A. 对称矩阵B. 零矩阵C. 上三⾓阵D. 对⾓矩阵3. 在⼀个⽆向图中，所有顶点的度之和等于边数的__C____倍A. 1/2B. 1C. 2D. 44. ⼀个有n 个顶点的⽆向图最多有___C____条边。

A. nB. n(n-1)C. n(n-1)/2D.2n5. 对于⼀个具有n 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵⼤⼩是__D_____A. nB. 2)1(?nC. n-1D. 2n6. ⼀个有向图G 的邻接表存储如右图所⽰，现按深度优先搜索遍历，从V1出发，所得到的顶点序列是___B_____。

A. 1，2，3，4，5B. 1，2，3，5，4C. 1，2，4，5，3D. 1，2，5，3，47. 对右图所⽰的⽆向图，从顶点V1开始进⾏深度优先遍历，可得到顶点访问序列__A______（提⽰：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6B. 1 2 4 3 5 6 7C. 1 2 4 5 6 3 7D. 1 2 3 4 5 6 78. 如果从⽆向图的任⼀顶点出发进⾏⼀次深度优先搜索即可访问所有顶点，则该图⼀定是__B_____A. 完全图B. 连通图C.有回路D. ⼀棵树9. 任何⼀个⽆向连通图___B___最⼩⽣成树（提⽰：注意最⼩⽣成树的定义，此题易错）A. 只有⼀棵B. ⼀棵或多棵C. ⼀定有多棵D.可能不存在11. 若图的邻接矩阵中主对⾓线上的元素全是0，其余元素全是1，则可以断定该图⼀定是_D_____。

第八章排序：习题习题一、选择题1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序2．设有1000个无序的记录，希望用最快的速度挑选出其中前10个最大的记录，最好选用( )排序法。

A.冒泡排序B.快速排序C.堆排序D.基数排序3．在待排序的记录序列基本有序的前提下，效率最高的排序方法是( )。

A.插入排序B.选择排序C.快速排序D.归并排序’4．不稳定的排序方法是指在排序中，关键字值相等的不同记录的前后相对位置( )。

A.保持不变B.保持相反C.不定D.无关5．内部排序是指在排序的整个过程中，全部数据都在计算机的( )中完成的排序。

A. 内存储器B.外存储器C.内存储器和外存储器D.寄存器6．用冒泡排序的方法对n个数据进行排序，第一趟共比较( )对记录。

A.1B.2C.n-lD.n7．直接插入排序的方法是从第( )个记录开始，插入前边适当位置的排序方法。

A.1B.2C.3D.n8．用堆排序的方法对n个数据进行排序，首先将n个记录分成( )组。

A.1B.2C.n-lD.n9．归并排序的方法对n个数据进行排序，首先将n个记录分成( )组，两两归并。

A.1B.2C.n-lD.n10．直接插入排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树11．冒泡排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树12．快速排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树13．排序方法中，从未排序序列中依次取出记录与已排序序列（初始时为空）中的记录进行比较，将其放入已排序序列的正确位置上的方法，称为( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序14．每次把待排序的记录划分为左、右两个子序列，其中左序列中记录的关键字均小于等于基准记录的关键字，右序列中记录的关键字均大于基准记录的关键字，则此排序方法叫做( )。

1、二叉树前序 中序遍历（序列与图的相互转化） 例题1：中序序列BDCEAFHG前序序列 ABCDEFGH例题2AB FC GDE HABCDFEGHKJILOMNPRQ前序序列：ABCDEFGHIJKLMPQRNO（参考：后序序列：BDEFCAIJKHGQRPMNOL）中序序列：BDEFCAIJKHGPQRMNOL2、哈夫曼树。

其对应字母分别为a,b,c,e,f,g,h 例题1：7,19,2,6,32,3,21,10哈夫曼编码： a：0010b：10c：00000d：0001e：01f：00001g：11h：0011例题2： w={5, 29, 7, 8, 14, 23, 3, 11}例题3例如，设一组电文的字符集D及其概率分布W为：D={a,b,c,d，e}，W={0.12，0.40，0.15，0.08，0.25}，用哈夫曼算法构造哈夫曼树及其对应的编码如下图所示。

3、最小生成树Prim算法4、邻接矩阵（图<->邻接矩阵<->遍历序列（深度、宽度遍历））5、二分法检索又称为折半查找，采用二分法检索可以大大提高查找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用顺序存储结构。

采用二分搜索时，先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:➢ l[mid]. Key = x，搜索成功；➢ l[mid]. Key > x，把搜索区间缩小到表的前半部分，再继续进行对分搜索；➢ l[mid]. Key < x，把搜索区间缩小到表的后半部分，再继续进行对分搜索。

➢每比较一次，搜索区间缩小一半。

如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。

例题1：有一组有序的线性表如下：（10，14，20，32，45，50，68，90，100，120）下面分析在其中二分检索关键字20的过程。

下面分析二分检索关键字95的过程:下面给出二分检索法的非递归与递归实现算法，算法中使用seqlist.h中定义的顺序查找表。

第9章排序习题答案1. 假设含n个记录的序列为{ R1, R2, …，R n}，其相应的关键字序列为{ K1, K2, …，K n}，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ks n，按此固有关系将n个记录序列重新排列为{ Rs1, Rs2, …，Rs n }。

若整个排序过程都在内存中完成，则称此类排序问题为内部排序。

2.3. 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。

即将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i] ，最终使整个文件有序。

共进行n-1趟插入。

最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。

简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1<=i<n)趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。

共进行n-1趟选择。

最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。

二路并归排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到⎡n/2⎤个长度为2的有序序列，再进行两两归并，得到⎡n/4⎤个长度为4的有序序列。

如此重复，经过⎡log2n⎤趟归并，最终得到一个长度为n的有序序列。

最坏时间复杂度和平均时间复杂度都是0(nlog2n)，空间复杂度是O(n)，是稳定排序。

4. 错误。

快速排序，堆排序和希尔排序是时间性能较好的排序方法，但都是不稳定的排序方法。

5. (1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序6. 不是。

数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（）。

A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。

A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。

A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。

A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。

A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

第九章查找一、选择题1、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（）次。

A.1B.2C.3D.43、解决哈希冲突的主要方法有（）。

A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、再哈希法D.线性探测法、再哈希法、链地址法4、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。

A.nB.log2nC.(h+1)/2D.h5、已知表长为25的哈希表，用除留取余法，按公式H(key)=key MOD p建立哈希表，则p应取（）为宜。

A.23B.24C.25D.266、设哈希表长m=14,哈希函数H(key)=key MOD11。

表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（）。

A.8B.3C.5D.99、m阶B-树中的m是指（）。

A.每个结点至少具有m棵子树B.每个结点最多具有m棵子树C.分支结点中包含的关键字的个数D.m阶B-树的深度10、一个待散列的线性表为k={18,25,63,50,42,32,9}，散列函数为H(k)=k MOD9，与18发生冲突的元素有（）个。

A.1B.2C.3D.411、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中，这种方式主要适合于（）。

A.静态查找表B.动态查找表C.静态查找表和动态查找表D.两种表都不适合12、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，（B）次比较后查找成功。

A.1B.4C.2D.813、在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（）。

A.顺序查找B.折半查找C.哈希查找D.分块查找14、下列二叉树中，不．平衡的二叉树是（）。

一、选择题1、在所有的排序方法中，关键字比较的次数与记录的初始排序无关的是（）A、希尔排序B、冒泡排序C、插入排序D、选择排序2、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）A、冒泡排序B、快速排序C、堆排序D、基数排序3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）A、插入排序B、选择排序C、快速排序D、归并排序4、一组记录为（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，385、一组记录为（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，796、一组记录为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一次归并后的结果为（）A、16，25，35，48，23，40，79，82，36，72B、16，25，35，48，79，82，23，36，40，72C、16，25，48，35，79，82，23，36，40，72D、16，25，35，48，79，23，36，40，72，827、排序方法中，从未排序序列中依次取出元素与已排序序列（初始化为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A、希尔排序B、冒泡排序C、插入排序D、选择排序8、用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则采用的排序方法是（）A、选择排序B、希尔排序C、归并排序D、快速排序9、下述几种排序方法中，平均查找长度最小的是（）A、插入排序B、选择排序C、快速排序D、归并排序10、下述几种排序方法中，要求内存量最大的是（）A、插入排序B、选择排序C、快速排序D、归并排序11、快速排序方法在（）情况下，最不利于发挥其长处。