数学《内部排序》单元练习

数学《内部排序》单元练习

　　1．请写出应填入下列叙述中（  ）内的正确答案。

排序有各种方法，如插入排序、快速排序、堆排序等。

设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行

一遍排序后的结果。

（ ）排序的结果为：12，13，15，18，20，60

（ ）排序的结果为：13，15，18，12，20，60

（ ）排序的结果为：13，15，20，18，12，60

（ ）排序的结果为：12，13，20，18，15，60

2．对下面数据表，写出采用 SHELL 排序算法排序的每一趟的结果，并标出数据移动情况。

（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）。

排序增量 d0=15,di=di-1/2

3．堆是一种有用的数据结构。试判断下面的.关键码序列中哪一个是堆__________。

①16，72，31，23，94，53

②94，53，31，72，16，23

③16，53，23，94，31，72

④16，31，23，94，53，72

⑤94，31，53，23，16，72

　　4.判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。

（1）100，85，98，77，80，60，82，40，20，10，66

（2）100，98，85，82，80，77，66，60，40，20，10

（3）100，85，40，77，80，60，66，98，82，10，20

（4）10，20，40，60，66，77，80， 82，85，98，100

5．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2 路归并排序方法对该序列进行一趟扫描后的结果_______。

　　6．已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整的如下所示各步骤结果。

建立堆结构：_____________

交换与调整：

（1）87 70 26 61 45 12 3 97;（2）____________________;

（3）61 45 26 3 12 70 87 97;（4）____________________;

（5）26 12 3 45 61 70 87 97;（6）____________________;

（7）3 12 26 45 61 70 87 97;

　　7．给出一组关键字 T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时

第一趟结束时的序列： < br />(1) 希尔排序（第一趟排序的增量为5）

(2) 快速排序（选第一个记录为枢轴（分隔））

(3) 链式基数排序（基数为10）

8. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

(1) 归并排序   每归并一次书写一个次序。

(2) 快速排序   每划分一次书写一个次序。

(3) 堆排序     先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。