八排序 练习题答案
更新时间:2024-01-04 21:40:01 阅读量: 教育文库 文档下载
- 八大旗排序推荐度:
- 相关推荐
排序 练习题(八) 参考答案
习题解答 2010-06-25 15:15:45 阅读33 评论0 字号:大中小
一、【答案】
在内部排序方法中,选择排序、堆排序、归并排序、基数排序的效率与原始待排序数据的排列顺序基本上无关,而快速排序适合于原始待排序数据完全无序,不适合于数据基本有序的情况。直接插入排序和Shell排序虽然平均效率不高,但当原始待排序数据基本有序时效率较高,考虑到要选择比较和移动次数少的排序方法,可选择直接插入排序或Shell排序。如还需考虑稳定性或简单性,就只能选择直接插入
排序。
二、【答案】
对序列{50,30,60,80,70,20,40}进行冒泡排序时,第一趟排序结果为:
{20,50,30,60,80,70,40} 元素30往它最终位置的相反方向移动了。
快速排序不可能出现这种现象。因为在每一趟排序过程中,以枢轴为基准,比它小的元素往前移,比它大的元素往后移。但可能出现局部的波动现象,比如对序列{50,40,90,10,20,35}进行一趟快速排序的结果为:{35,40,20,10,50,90},元素35移过了最终位置,在后面某趟排序过程中需要往后
移。
三、【答案】
(1)当步长d=5时,序列变为:
(5,12,20,4,l,30,44,66,31,8,100,80,150,61,200)
(2)当步长d=3时,序列变为:
(4,1,20,4,l2,30,8,61,31,44,66,80,150,100,200)
(3)当步长d=1时,序列变为:
(1,4,5,8,12,20,30,31,44,61,66,80,100,150,200)
四、【解答】
(1)快速排序第一次分割的结果为: {2,0,5,3,4} 6 {8,7,9,10}
(2)建堆及调整的结果,如图所示。
大根堆及选出最大关键字
若以3为基数,则数组A的10个元素依次变为{20,2,30,21,10,22,11,12,0,31},第一次分配(LSD排序)和收集后的结果为:{20,30,10,0,21,11,31,2,22,12},即{6,9,3,0,
7,4,10,2,8,5}。
五、【解答】
(1)快速排序第一趟后的状态:{20,38,10} 49 {75,90,66}。 快速排序第二趟后的状态:{10} 20 {38} 49 {75,90,66}。 (2)把关键字集合key调整成堆顶元素取最小值的堆,如图所示。
小根堆
(3) 能用队列代替栈。
使用栈保存子序列首、尾记录的地址(下标),其目的是为了处理某个子序列时,能知道其首、尾记录的地址,这样才能对该子序列进行快速排序。但这与处理子序列的先后没有什么关系,仅起保存作
用。因此,用队列也可起到栈的作用,故可取代。
(4) 归并排序要求的内存容量最多。
六、 【分析】
· 试题主要考核有关快速排序的基本思想,要求熟悉快速排序的主要特点和算法的主要步骤。 · 算法思想:设查找区间是low~high,一趟快速排序后,得到划分位置low,若low=k,则问题解决;若low>k,则在前面的子序列范围内查找;若low 【解答】 int QuickSort_Find(SqList &R, int first, int last, int k) { int low=first, high=last; KeyType pivotKey; R.r[0] = R.r[first]; pivotKey = R.r[first].key; while(low < high){ while(low high--; R.r[low] = R.r[high]; while(low low++; R.r[high] = R.r[low]; } R.r[low] = R.r[0]; if(low-first+1 == k) return low; else if(low-first+1 > k) return QuickSort_Find(R, first, low-1, k); else return QuickSort_Find(R, low+1, last,k-low+first-1); } void FindValue(SqList &R, int k) { int location; location = QuickSort_Find(R, 1, R.length, k); printf(R.r[location]); }
正在阅读:
八排序 练习题答案01-04
优秀教师专业发展的个案研究 - 学生自主探究学习的探索与实践03-28
2017广东省中考名著精选文段与答案05-30
CAD中的系统变量及说明01-08
贫困小学的作文06-15
维果斯基的儿童人格发展思想11-30
2017-2018上高三课标(GDY)第11-12期参考答案及部分解析11-13
国际企业价值评估师分析师04-06
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 练习题
- 排序
- 答案