2、【北方交通大学2000二、2（2分）】A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(c)的两趟排序后的结果。【合肥工业大学1999一、3（2分）】A．选择排序B.冒泡排序C.插入排序D.堆排序4．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(a)的两趟排序后的结果。快速排序B.冒泡排序C.选择排序D.插入排序5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1
3、，8，20，7，15}；则采用的是（c）排序。【南京理工大学1998一、8（2分）】A.选择B.快速C.希尔D.冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（c）排序.【南京理工大学1998一、9（2分）】A．选择B.堆C.直接插入D.冒泡7.下列排序算法中(c)排序在一趟结束后不一定能选出一个元素放在其最终位置上。选择B.冒泡C.归并D.堆8.下列排序算法中，（d）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学2000一、4】【
4、西北大学2001二、1】A.堆排序B.冒泡排序C.快速排序D.插入排序9．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（c）。A．94,32,40,90,80,46,21,69B．32,40,21,46,69,94,90,80C．21,32,46,40,80,69,90,94D．90,69,80,46,21,32,94,40【北方交通大学2001一、15（2分）】10．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（d）位置上。A．n/2B．n/2
5、-1C．1D．n/2+2【中科院计算所2000一、4（2分）】11．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（b）。【西安电子科技大学2001应用一、10（2分）】A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)12．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（a）A．堆排序〈快速排序〈归并排序B．堆排序〈归并排序〈快速排序C．堆排序〉归并排序〉快速排序D．堆排序>快速排序>归并排序E．以上答案都不对【西安交通大学1996三、1(3分)】13．将两个
6、各有N个元素的有序表归并成一个有序表,其最少的比较次数是(a)A．NB．2N-1C．2ND．N-1二、判断题1．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（f）【上海交通大学1998一、18】2.中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（t）【中山大学1994一、4（2分）】3．在任何情况下，归并排序都比简单插入排序快。（f）【北京邮电大学2000一、4（1分）】4．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（t）【合
7、肥工业大学2000二、10（1分）】5．内排序要求数据一定要以顺序方式存储。（f）【南京理工大学1997二、2（2分）】三、填空题1.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。【南京理工大学1997三、5（2分）】2．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。【北京邮电大学2001二、
8、7（4分）】3．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。【福州大学1998二、10(2分)】4.用链表表示的数据的简单选择排序，结点的域为数据域data，指针域next；链表首指针为head，链表无头结点。selectsort(head)｛p=head;while(p______){q=p;r=(2)_
