数据结构第10章习题.ppt

第10章习题一、选择题1．下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（dc）（2）不稳定的排序算法是（adf）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（b）（4）排序的平均时间复杂度为O(n?logn)的算法是（acf）为O(n?n)的算法是（bde）2．比较次数与排序的初始状态无关的排序方法是(d)。【北方交通大学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，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】【西北大学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/2?B．?n/2?-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．将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是(a)A．NB．2N-1C．2ND．N-1在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（f）【上海交通大学1998一、18】1中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（t）【中山大学1994一、4（2分）】2在任何情况下，归并排序都比简单插入排序快。（f）【北京邮电大学2000一、4（1分）】3在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（t）【合肥工业大学2000二、10（1分）】4内排