习　题　9

一、选择题

1.在下述的排序方法中,不属于内排序方法的是＿＿＿＿。

A.插入排序法　　B.选择排序法　　C.拓扑排序法　　D.归并排序法

2.第i趟排序对排序的前n－i＋1个元素做如下工作:从第一个元素开始,相邻两个元素比较,若前者大于后者,这两个元素交换位置,否则这两个元素不交换位置。这种排序称为＿＿＿＿。

A.插入排序法　　B.选择排序法　　C.冒泡排序法　　D.堆积排序法

3.通过依次将序列中位置相邻且已经按值有序的子序列两两合并为一个按值有序的子序列的方式来达到排序目的的排序方法是＿＿＿＿。

A.冒泡排序法　　　　B.直接插入排序法

C.堆积排序法　　　　D.二路归并排序法

4.对数据元素序列（49,72,68,13,38,50,97,27）进行排序,前三趟排序结果时的结果依次为第一趟:49,72,68,13,38,50,97,27；第二趟:49,68,72,13,38,50,97,27；第三趟:13,49,68,72,38,50,97,27。该排序采用的方法是＿＿＿＿。

A.插入排序法　　B.选择排序法　　C.冒泡排序法　　D.堆积排序法

5.对序列（49,38,65,97,76,13,47,50）采用直接插入排序法进行排序,要把第七个元素47插入到已排序中,为寻找插入的合适位置需要进行＿＿＿＿次元素间的比较。

A.3　　　　B.4　　　　C.5　　　　D.6

6.下面四种排序方法中,＿＿＿＿是一种稳定性排序方法。

A.插入排序法　　B.选择排序法　　C.快速排序法　　D.希尔排序法

7.堆积可以表示为一棵＿＿＿＿。

A.满二叉树　　B.完全二叉树　　C.二叉排序树　　D.线索二叉树

二、填空题

1.假设一组记录的排序码为（46,79,56,38,40,84）,则利用堆排序方法建立的初始堆为＿＿＿＿。

2.假定一组记录的排序码为（46,79,56,38,40,80）,对其进行快速排序的一次划分的结果为＿＿＿＿。

三、分析题

1.已知序列（35,78,12,26,90,41,66,58）,分别对其采用以下操作。

（1）请写出对此序列采用插入排序方法进行升序排序时各趟的结果。

（2）请写出对此序列采用选择排序方法进行升序排序时各趟的结果。

（3）请写出对此序列采用冒泡排序方法进行升序排序时各趟的结果。

（4）请写出对此序列采用堆积排序方法进行升序排序时各趟的结果。

2.已知一组记录的关键字序列为:46,74,16,53,14,26,40,38,86,65,27,34,写出详细的堆排序过程,画出每一步得到的完全二叉树。

3.已知序列{71,18,83,100,65,17,23,76},请给出采用直接插入排序法对该序列进行升序排序时的每一趟结果。

4.已知序列{17,18,66,44,77,23,76,65,89},请给出采用起泡排序法对该序列进行升序排序时的每一趟结果。

5.已知序列{503,87,512,62,907,173,895,275},请给出采用快速排序法对该序列进行升序排序时的每一趟结果。

6.已知序列{617,118,6,40,27,203,16,69,329},请给出采用简单选择排序法对该序列进行升序排序时的每一趟结果。

7.设待排序的关键字序列为{11,4,18,33,28,9,18＊,21,5,19},请画出堆排序时形成初始堆和第一次堆顶元素第一次交换后堆的变化过程。

8.已知序列{89,18,54,43,76,12,22,9,38,65},请给出采用归并排序法对该序列进行升序排序时的每一趟结果。

9.已知序列{86,217,151,242,6,13,302,169,258,69},请给出采用基数排序法对该序列进行升序排序时的每一趟结果。