资源描述：
《数据结构第章习题课.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1．下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序3．排序趟数与序列的原始状态有关的排序方法是()排序法。A．插入B.选择C.冒泡D.快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447（4）152
2、1254784则采用的排序是()。A.选择B.冒泡C.快速D.插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。A.选择B.快速C.希尔D.冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（）排序。A．选择B.堆C.直接插入D.冒泡7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之
3、前，所有元素都不在其最终的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序9.下列排序算法中，占用辅助空间最多的是：()A.归并排序B.快速排序C.希尔排序D.堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。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,4011.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进
4、行（）次比较。A.3B.10C.15D.2512．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）A．每次分区后，先处理较短的部分B．每次分区后，先处理较长的部分C．与算法每次分区后的处理顺序无关D．以上三者都不对13．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（）位置上。A．ën/2ûB．ën/2û-1C．1D．ën/2û+214．对n个记录的文件进行堆排序，最坏情况下的执行时间是多少？（）A．O（log2n）B．O（n）C．O（nlog2n）D．O（n*n）15．就排序算法所用的
5、辅助空间而言，堆排序，快速排序，归并排序的关系是 （）A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈快速排序C．堆排序〉归并排序〉快速排序 D．堆排序>快速排序>归并排序16．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。A．选择排序B.冒泡排序C.插入排序D.堆排序18．分别采用堆排序，快速排序，冒泡排序和归并排
6、序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。答：冒泡，快速19.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。答：3，(10,7,-9,0,47,23,1,8,98,36)20．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆__________。①16，72，31，23，94，53②94，53，31，72，16，23③1
7、6，53，23，94，31，72④16，31，23，94，53，72⑤94，31，53，23，16，72堆排序是一种_(1)_类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyd提出的_(2)_，对含有n个元素的序列进行排序时,堆排序的时间复杂度是_(3)_，所需要的附加结点是_(4)_。答：④是堆(1)选择(2)筛选法(3)O(nlog2n)(4)O(1)21．关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是
8、_____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。答：（Q,A,C,S,Q,D,F,X,R,H,M,Y），(F,H,C,D,Q,A,M,Q,R,S,Y,X)22．算法模拟
