资源描述：
《数据结构课后习题第十章.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1.在下列排序算法中，稳定的事（），平均速度最快的是（），所需辅助存储空间最多的是（）。A.希尔排序B.快速排序C.堆排序D.归并排序2.若要在O(n)数量级的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方式应该是（）。A.快速排序B.堆排序C.归并排序D.希尔排序3.在下列排序算法中，（）算法的时间复杂度与初始排序无关。A.直接插入排序B.起泡排序C.快速排序D.直接选择排序4.一组记录关键字序列是（46,79,56,38,40,84），则用堆排序方法建立的初始大根堆是（）。A.79,46,56,38,40,84B.84,79,56
2、,38,40,46C.84,79,56,46,40,38D.94,56,79,40,46,385.一组记录的关键字序列是（46,79,56,38,40,84），则用快速排序方法，以第一个关键字为支点，得到的第一次划分结果是（）。A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,796.一组记录的关键字序列是（25,48,16,35,79,82,26,40,36,72），用二路归并排序方法进行排序，则第二趟归并的结果是（）。A.16,25,35,48,2
3、3,40,79,82,36,72B.16,25,35,48,79,82,23,36,40,72C.16,25,35,46,23,36,40,79,82,72D.16,25,35,48,79,23,36,40,72,827.在以下排序方法中，关键字比较的次数与记录的初始排列次序有关的是（）A.归并排序B.堆排序C.插入排序D.选择排序8.下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A.堆排序B.冒泡排序C.希尔排序D.快速排序9.数据序列（8,9,10,4,5,6,20,1,2）只能是下列排序算法中的（）的两趟排序
4、后的结果。A.选择排序B.冒泡排序C.插入排序D.堆排序10.直接插入排序在最好的情况下，其时间复杂度为（）A.O(logn)B.O(n)C.O()D.O(nlogn)11.对一组数据（84,47,25,15,21）排序，数据的排列次序在排序的过程中的变化如下。初始状态：8447251521第一趟：1547258421第二趟：1521258447第三趟：1521254784则采用的是（）排序方法A.选择B.冒泡C.快速D.插入9.下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.Shell排序C.堆排序D.冒泡
5、排序13．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.冒泡排序C.简单选择排序D.快速排序14.如果只想得到1000个元素组成的序列中第5个最小元素之间的部分排列序列，用（）方法最快。A.起泡排序B.快速排序C.Shell排序D.堆排序E.简单选择排序15.对初始状态为递增序列的表按递增顺序排序，最省时间的是（）算法，最费时间的是（）算法。A.堆排序B.快速排序C.插入排序D.归并排序16.起泡排序在最好情况下的时间杂度为（）。A.O（logn）B.O(n)C.O(nlogn)D.O(n²)17.若需在O
6、(nlog2n)的时间内完成对数组的排序，且要求排序方法与初态无关，则可选择的排序方法是（）。A．快速排序B.堆排序C.归并排序D.直接插入排序19.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。A．递归次序与初始数据的排列次序无关B．每次划分后先处理较长的分区可以减少递归次数C．每次划分后先处理较短的分区可以减少递归次数D．递归次数与每次划分后得到的分区处理次序无关20.对一组数据(2,12,16,85,5,10)进行排序，若前三趟排序结果如下。第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,8
7、8第三趟：2,5,10,12,16,88则采用的排序方法可能是（）。A.冒泡排序法B.希尔排序法C.归并排序法D.基数排序法二、填空题1.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的（）和记录的（）。2.不受待排序初始序列的影响，时间复杂度为（）的排序算法是（）。3.分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，最省时间的是（）算法，最费时间的是（）算法。4.设有字符序列（Q,H,C,Y,P,A,M,S,E,D,F,X），则用初始步长为4的希尔排序方法将其按字符升序排序，第一趟扫描的结果是（）。5.快速排序的
8、最大递归深度是（），最小递归深度是（）。6.对n个元素的序列利用起泡法排序时，最好情况时的最少比较次数是（）。7.在插入排
