第九章华工数据结构试卷资料电信学院.doc

第九章华工数据结构试卷资料电信学院.doc

ID:59464092

大小:32.50 KB

页数:7页

时间:2020-11-02

第九章华工数据结构试卷资料电信学院.doc_第1页
第九章华工数据结构试卷资料电信学院.doc_第2页
第九章华工数据结构试卷资料电信学院.doc_第3页
第九章华工数据结构试卷资料电信学院.doc_第4页
第九章华工数据结构试卷资料电信学院.doc_第5页
资源描述:

《第九章华工数据结构试卷资料电信学院.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、习题9.1一、选择题1、一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为(B)。A、79,46,56,38,40,80B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,382、排序趟数与序列原始状态(原始排列)有关的排序方法是(ACD)方法。A、插入排序B、选择排序     C、冒泡排序   D、快速排序3、下列排序方法中,(B)是稳定的排序方法。A、直接选择排序B、二分法插入排序C、希尔排序D、快速排序4、数据序列(8,9,10,4,5,6,20,1

2、,2)只能是下列排序算法中(C)的两趟排序后的结果。A、选择排序B、冒泡排序C、插入排序D、堆排序5、对序列(15,9,7,8,20,-1,4)进行排序,进行一趟排序后,数据的排列变为(4,9,-1,8,20,7,15),则采用的是(C)排序。A、选择B、快速C、希尔D、冒泡6、一组待排序记录的关键字为(46,79,56,38,40,84),则利用快速排序,以第一个记录为基准元素得到的一次划分结果为(C)。A、(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46

3、,84,56,79)7、用直接插入排序对下面四个序列进行排序(由小到大),元素比较次数最少的是(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,408、若用冒泡排序对关键字序列(18,16,14,12,10,8)进行从小到大的排序,所需进行的关键字比较总次数是(B)。A、10B、15C、21D、349、就排序算法所用的辅助空间而言,堆排序、快速排序和归并排序的关系(A)。A、堆排序<快速排序<归并排序

4、 B、堆排序<归并排序<快速排序C、堆排序>归并排序>快速排序 D、堆排序>快速排序>归并排序E、以上答案都不对10、采用败者树进行k路平衡归并的外部排序算法,其总的归并效率与k()。A、有关B、无关9.2填空题1、在直接插入排序和直接选择排序中,若初始数据基本有序,则选用(直接插入排序),若初始数据基本反序,则选用(直接选择排序)。2、在归并排序中,若待排序记录的个数为20,则共需要进行(5)趟归并,在第三趟归并中,是把长度为(4)的有序表归并为长度为(8)的有序表。3、在内排序中,平均比较次数最多的是(快速排序),要求附加的内存空间最大的是(归并排

5、序),排序时不稳定的有(希尔排序)、(选择排序)、(快速排序)和(堆排序)等几种方法。4、对n个元素的序列进行冒泡排序,最少的比较次数是(n-1),此时元素的排列情况(从小到大排列),在(从大到小排列)情况下比较次数最多,其比较次数为(n(n-1)/2)。5、对一组记录(50,40,95,20,15,70,60,45,80)进行直接插入排序时,当把第7条记录60插入到有序表中时,为寻找插入位置需比较(3)次。9.3应用题1、在各种排序方法中,哪些是稳定的?哪些是不稳定的?并为每一种不稳定的排序方法举出一个不稳定的实例。答:稳定的排序算法有直接插入排序、

6、折半插入排序、冒泡排序、归并排序和基数排序。不稳定的排序算法有希尔排序、直接选择排序、堆排序、快速排序。例子:讲课是的例子。2、设待排序的关键码分别为28,13,72,85,39,41,6,20。按折半插入排序已使前七个记录有序,中间结果如下:613283941728520i=1m=4r=7试在此基础上,沿用上述表达方式,给出继续采用折半插入第八条记录的比较过程,并回答以下问题:(1)使用折半插入排序所要进行的比较次数,是否与待排序的记录的初始状态有关?(2)在一些特殊情况下,二分法插入排序比直接插入排序要执行更多的比较。这句话对吗?答:插入20的过程

7、:①39>20:r=m-1=3;i<=r;m=(i+r)/2=4/2=2②13<20:i=m+1=3;i>r;查找过程结束,插入位置为i。最终结果为:613202839417285(1)插入排序所要进行的比较次数与待排序的记录的初始状态有关。若初始状态基本有序,每次查找时都会搜索到有序表的最后一个元素才找到插入位置。若每次插入的元素在有序表中的插入位置靠中间,则查找次数最少。(2)在一些特殊情况下,二分法插入排序比直接插入排序要执行更多的比较。这句话是对的。若初始状态基本有序,则折半插入排序,每次查找时都会搜索到有序表的最后一个元素才找到插入位置。直接

8、插入排序则每次只比较一次就找到合适位置。3、已知一关键码序列为:3,87,12,61,70,9

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。