发布时间 : 星期一 文章数据结构试题集（含答案）更新完毕开始阅读5a9f850b81c758f5f71f6729
空间中对该关键字序列构造哈希表。 答案：
027311121423551468258436191720189103102311111112771131415161718
ASL成功 =（3+1+2+1+2+3+1+1+3+1+1+1）/12=5/3
第十章 内部排序
一、选择题
1、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 2、下列排序方法中（ C ）方法是不稳定的。
A. 冒泡排序 B. 选择排序 C. 堆排序 D. 直接插入排序
3、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（ B ）方法。
A. 快速排序 B. 堆排序 C. 插入排序 D. 归并排序 4、一组待排序序列为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（ B ）。
A. 79,46,56,38,40,80 B. 84,79,56,38,40,46 C. 84,79,56,46,40,38 D. 84,56,79,40,46,38 5、快速排序方法在（ C ）情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数
6、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（ D ）排序的基本思想。
A. 堆排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序 7、在任何情况下，时间复杂度均为O(nlogn)的不稳定的排序方法是（ C ）。 A.直接插入 B. 快速排序 C. 堆排序 D. 归并排序 8、如果将所有中国人按照生日来排序，则使用（ D ）算法最快。
A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序 9、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ B ）。
A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)
10、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。
A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 11、一组记录的的序列未（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ B ）。
A. 79，46，56，38，40，80 B. 84，79，56，38，40，46
45
C. 84，79，56，46，40，38 D. 84，56，79，40，46，38
12、用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
⑴ 25，84，21，47，15，27，68，35，20 ⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ）。
A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 13、设有1024个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（ D ）。
A. 冒泡排序 B. 选择排序 C. 快速排序 D. 堆排序
14、下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ B ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序 15、希尔排序的增量序列必须是（ D ）。
A. 递增的 B. 递减的 C. 随机的 D. 非递减的
二、填空题
1、在插入和选择排序中，若初始数据基本正序，则选用 递减排序 ，若初始数据基本反序，则选用 递减排序 。
2、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 希尔排序，快速排序，堆排序 。
三、判断题
1、直接选择排序是一种稳定的排序方法。对
2、快速排序在所有排序方法中最快，而且所需附加空间也最少。错 3、直接插入排序是不稳定的排序方法。错 4、选择排序是一种不稳定的排序方法。 对
四、程序分析题
五、综合题
1、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。
46
答案：初始： 54，23，89，48，64，50，25，90，34
1：（23，54），89，48，64，50，25，90，34 2：（23，54，89），48，64，50，25，90，34 3：（23，48，54，89），64，50，25，90，34 4：（23，48，54，64，89），50，25，90，34 5：（23，48，50，54，64，89），25，90，34 6：（23，25，48，50，54，64，89），90，34 7：（23，25，48，50，54，64，89，90），34 8：（23，25，48，50，54，64，89，90，34）
2、设待排序序列为{10,18,4,3,6,12,1,9,15,8}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。
答案：初始： 10，18，4，3，6，12，1，9，15，8
d=5： 10，1，4，3，6，12，18，9，15，8 d=3： 3，1，4，8，6，12，10，9，15，18 d=2： 3，1，4，8，6，9，10，12，15，18 d=1： 1，3，4，6，8，9，10，12，15，18
3、已知关键字序列{418，347，289，110，505，333，984，693，177}，按递增排序，求初始堆（画出初始堆的状态）。
答案：418，347，289，110，505，333，984，693，177
418984347289693418110505333984347505333289693177110177
4、有一关键字序列（265，301，751，129，937，863，742，694，076，438），写出希尔排序的每趟排序结果。（取增量为5，3，1） 答案：
初始： 265，301，751，129，937，863，742，694，076，438 d=5： 265，301，694，076，438，863，742，751，129，937 d=3： 076，301，129，265，438，694，742，751，863，937 d=1： 076，129，265，301，438，694，742，751，863，937
5、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：
（1）平均时间复杂度低于O（n2）的排序方法； （2）所需辅助空间最多的排序方法；
答案：(1) 希尔、快速、堆、归并 (2) 归并
6、对关键子序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列（最小堆），请写出排序过程中得到的初始堆和前三趟的序列状态。
47
答案：
初始堆7287235994166105875923947205166105592394728716610559239472第1趟166187第2趟872359059472611605875994722361160587599423726116第3趟5972870594236116
附：
48