发布时间 : 星期一 文章数据结构习题集2015更新完毕开始阅读
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 29
第10章 内部排序
一、选择题：
1、对n个不同的排序码进行冒泡排序，在元素无序的情况下的次数为（ ） A．n + 1 B．n C．n - 1 D．n（n - 1）/2 2、快速排序算法在最坏情况下的时间复杂度为（ ）
A．Ｏ（n） B．Ｏ（n log2n） C．Ｏ（n2） D．Ｏ（log2n）
3、从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为（ ） 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、若用冒泡排序对关键字序列｛18，16，14，12，10，8｝进行从小到大的排序，所需进行的关键字比较
总次数是（ ）
A．10 B．15 C．21 D．34
9、就平均时间而言，下列排序方法中最差的一种是（ ）
A．堆排序 B．快速排序 C．归并排序 D．选择排序 10、记录的关键字序列为（7,6,8,4,3,5），采用快速排序以第一个记录为基准得到的第一次划分结果是
（ ）。 A．（5,3,6,4,7,8） B．（3,5,6,4,7,8） C．（6,4,3,5,7,8） D．（5,6,3,4,7,8） 11、稳定的排序方法是（ ）。
A．直接插入排序和快速排序 B．直接插入排序和冒泡排序 C．简单选择排序和直接插入排序 D．堆排序和归并排序
12、对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果不好的是（ ）。
A．4，1，2，3，6，5，7 B．4，3，1，7，6，5，2 C．4，2，1，3，6，7，5 D．1，2，3，4，5，6，7
13、若待排序序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应当使用的排序方
法是（ ）。
A．直接插入排序 B. 快速排序 C.直接选择排序 D. 归并排序 14、 若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。
A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38 15、以下稳定的排序方法是（ ）。
A．快速排序 B．冒泡排序 C．直接选择排序 D．堆排序 16、用冒泡排序的方法对n个数据进行排序，第一趟共比较（ ）对元素。
A．1 B．2 C．n-1 D．n 17、一个记录的关键字为（46,79,56,38,40,84），采用快速排序以第一个记录为基准得到的第一次划分结
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 30
果是（ ）。 A．（38,40,46,56,38,79,84） B．（40,38,46,79,56,84） C．（40,38,46,56,79,84） D．（40,38,46,56,79） 18、下列排序算法中不稳定的是（ ）。
A． 直接选择排序 B．折半插入排序 C．冒泡排序 D．快速排序
19、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列进行同样的排序操作，直到子序列为空或只剩下一个元素为止。这样的排序方法是（ ）。
A． 直接选择排序 B．直接插入排序 C．快速排序 D．冒泡排序 20、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）。
A．选择排序 B．快速排序 C．冒泡排序 D．插入排序
21、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）.
A． 希尔排序 B． 冒泡排序 C． 插入排序 D． 选择排序 22、下述几种排序方法中，要求内存最大的是（ ）。
A． 插入排序 B．快速排序 C． 归并排序 D． 选择排序 23、快速排序方法在（ ）情况下最不利于发挥其长处。
A． 要排序的数据量太大 B．要排序的数据中含有多个相同值 C．要排序的数据个数为奇数 D．要排序的数据已基本有序
24、对关键码序列28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为（ ）。
A． (2,5,12,16)26(60,32,72) B．(5,16,2,12)28(60,32,72) C．(2,16,12,5)28(60,32,72) D．(5,16,2,12)28(32,60,72)
二、填空题：
1、在选择排序、堆排序、快速排序、直接插入排序中，稳定的排序方法有（ ）。 2、（ ）排序方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 3、对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是（ ）。
4、在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第7个记录60插入到有序表时，
为寻找插入位置需比较（ ）次。
5、大多数排序算法都有两个基本的操作：（ ） 。
6、给出一组关键字T＝（20,4,34,5,16,33,18,29,2,40,7），要求从下到大进行排序，试给出快速排序（选一个记录为枢纽）第一趟排序结果（ ）。
7、设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：
冒泡排序一趟扫描的结果是（ ）；
初始步长为4的希尔（shell）排序一趟的结果是（ ）； 二路归并排序一趟扫描的结果是（ ）； 快速排序一趟扫描的结果是（ ）；
三、判断题：
1、对于n个记录的集合进行冒泡排序，所需要的平均时间是Ｏ（n） （ ） 2、快速排序是一种稳定的排序方法。 （ ） 3、冒泡排序是不稳定排序。 （ ） 4、在堆排序和快速排序中，若原始记录已基本有序，则较适合采用堆排序。 （ ）
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 31
四、应用题：
1、写出对关键字序列（40，24，80，39，43，18，20）进行冒泡排序的每一趟结果。 答：
2、有一组关键码序列（12,5,9,20,6,31,24），采用直接插入排序方法由小到大进行排序，请写出每趟排序的结果。 答：
3、有一组关键码序列（38,19,65,13,97,49），采用选择排序方法由小到大进行排序，请写出每趟排序的结果。 答：
4、对于给定的一组记录的关键字{ 23,13,17,21,30,60,58,28,30,90},试分别写出冒泡排序、快速排序、归并排序第一趟排序后的结果。
冒泡排序: ____________________________________________________________ 快速排序：____________________________________________________________ 归并排序：____________________________________________________________
5、己知序列 {503，87，512，61，908，170，897，275，653，462}，请给出采用快速排序法对该序列作升序排序时的每一趟结果。
答：原始序列：503，87，512，61，908，170，897，275，653，462
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 32
6、已知{503,87,512,61,908,170,897,275,653,462}，采用二路归并排序法对该序列作升序排序时的每一趟的结果。
答：初始关键字： 503，87，512，61，908，170，897，275，653，462
六、程序设计题：
1、 写出冒泡排序算法。
2、 写出直接插入排序算法。
成绩____________ 日期____________________