第八章 排序 真题
6.下述几种排序方法中，要求内存量最大的是( )
A.插入排序 B.快速排序 C.归并排序 D.选择排序
7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 28.堆排序需____________个记录大小的辅助存储空间。
33.什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素取最小值)。 35.试写出直接插入排序算法。
9.下列各项键值序列中不是堆的为（ ）
A.{5，23，16，68，94，72，71，73} B.{5，16，23，68，94，72，71，73} C.{5，23，16，73，94，72，71，68} D.{5，23，16，68，73，71，72，94} 10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（ ） A.单链表 B.双链表 C.顺序表 D.单循环链表
28.二路归并排序的平均时间复杂度为_____。
33.写出键值（83，40，63，13，84，35，96，57，39，79，61，15）应用二路归并排序算法从小到
大排序后各趟的结果。
35.设顺序表va中的数据元素递增有序。试编写算法实现将x插入到顺序表的适当位置上，以保持该
表的有序性。 15.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ） A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡
27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是______。 28.冒泡排序最好的时间复杂度为_______，平均时间复杂度为_______，是一种稳定的排序算法。 33.用快速排序法对数据序列(49，38，65，97，16，53，134，27，39)进行排序，写出其第一趟排序的全过程。
34.完善下列折半插入排序算法。
Voidbinasort(structnoder[MAXSIZE]，int n) {for(i=2;i<=n;i++){ r[0]=r[i];low=1;high=i-1; while(low<=high){ mid=(1)_________;
if(r［0］.key for(j=i-1;j>=low;j--) (4)_________; r[low]=r[0]; } } 4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（） 29 A.n B.2n-1 C.2n D.n2 14.一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为（ ） A.80，45，55，40，42，85 B.85，80，55，40，42，45 C.85，80，55，45，42，40 D.85，55，80，42，45，40 26.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为________。 28.对n个元素进行冒泡排序时，最少的比较次数为________。 33.用插入排序算法对数据序列（47，33，61，82，72，11，25，57）进行排序，写出整个插入排序的每一趟过程。 14.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是( ) A.快速排序 B.堆排序 C.插入排序 D.二路归并排序 15.在排序方法中,从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )A.希尔排序B.插入排序C.冒泡排序D.快速排序 27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用____________。 28.对n个元素的序列进行冒泡排序时，最多需进行___________趟。 29.写出利用直接选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行排序时，每趟排序的结果。 34.编写一个函数void insert(int *p,int size,int a)，其功能是将a插入指针变量p指向的长度为size的数组中。设数组中的数据已按升序排序。该函数要求实现的功能是：首先采用折半查找的方法，找出要插入数据的位置；然后按升序将数据插入该数组中。 14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( ) A.选择排序 B.插入排序 C.冒泡排序 D.快速排序 15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( ) A.希尔排序 B.归并排序 C.插入排序 D.选择排序 27.在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法进行排序时，整个排序过程需进行__________趟才能够完成。 28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为__________。 30.设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。 15．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（ ） A．36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81 27．二路归并排序算法的时间复杂度为_______。 31．用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出整个冒泡排序的每一趟过程。 35．试写出直接插入排序算法。 14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ） A.选择排序 B.快速排序 C.冒泡排序 D.插入排序 30 15.排序算法中，不稳定的排序是（ ） A.直接插入排序 B.冒泡排序 C.堆排序 D.归并排序 27.在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用____。 28.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。 33.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。 34.在下面冒泡排序算法中（1）～（4）处填入适当内容，以使该算法在发现有序时能及时停止。 bubble（R） Rectype R［n］； { int i，j，exchang； Rectype temp； i=1； do { exchang=False； for（j=n；j>= （1）________；j--） if（R［j］ { temp=R［j-1］； R［j-1］=R［j］； R［j］=temp； exchang= （2）________； } （3）________； } while（exchang= （4）________）； } 14.当待排序序列中记录数较多时，速度最快的排序方法是（ ） A.冒泡排序法 B.快速排序法 C.堆排序法 D.归并排序法 15.若对序列（15，30，26，22，69，50，53，87）采用二路归并法排序，则进行一趟归并后产生的序列为（ ） A.15，22，26，30，50，53，69，87 B.15，30，22，26，50，69，53，87 C.15，26，30，22，50，69，53，87 D.15，26，22，30，50，53，69，87 28.对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行________________趟起泡。 32.已知一组键值序列（33，37，26，43，55，67，42，38），试采用堆排序法对该组序列作升序排序，给出建立的初始堆，以及第一次输出堆元素后筛选调整的堆。 33.已知一组键值序列（22，24，26，25，27，29，21，28），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 14.当待排序序列中记录数较少或基本有序时，最适合的排序方法为( ) A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法 15.若对序列（26，90，23，53，16，34，69，39，22）进行一趟排序后所得到的结果为（22，16，23，26，53，34，69，39，90），则该排序可能使用的方法是( ) A.插入排序 B.冒泡排序 C.快速排序 D.选择排序 31 28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的__________中 32.已知一组键值序列（32，44，38，65，53，42，29，57），试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的堆。 33.已知一组键值序列（13，12，16，17，15，14，11），试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。 14.堆排序属于一种选择排序，其时间复杂性为( )A.O(1) B.O(nlog2n) C.O(n) D.O(n2) 15.下列排序方法中，属于不稳定的排序方法是( ) A.直接插入排序法 B.冒泡排序法 C.基数排序法 D.归并排序法 28.在各种内部排序中，占用存储空间较大的排序通常是___________排序。 32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列 作升序排序，并给出每一趟的排序结果。 33.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列 作升序排序，并给出每一趟的排序结果。 14.直接插入排序算法，其时间复杂性为（ ） A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 15.下列排序方法中，属于稳定的排序方法是（ ） A.直接插入排序法 B.快速排序法 C.冒泡排序法 D.堆排序法 28.在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为____次。 32.已知一组键值序列（28，47，35，42，53，60，34，22），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 33.已知一组键值序列（3，6，8，9，2，7，4，3），试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。 14．下列关键码序列中，属于堆的是（ ） A．（15，30，22，93，52，71） B．（15，71，30，22，93，52） C．（15，52，22，93，30，71） D．（93，30，52，22，15，71） 15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（ ） A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95 C．28，16，34，54，62，60，73，26，43，95 D．16，28，34，54，62，60，73，26，43，95 27．在排序方法中，依次将每个记录插入到一个有序的子序列中去，即在第i(i≥1)遍整理时，r1,r2,…,ri-1已经是排好顺序的子序列，取出第i个元素ri，在已排好序的子序列里为ri找到一个合适的位置，并把它插到该位置上。这种排序方法被称为___________。 28．快速排序法在待排序数据_____________的情况下最不利于发挥其长处 33．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分） 32