综合题的三道，数据结构的三个组成部分

来源：蜘蛛抓取(WebSpider) 时间：2019-04-19 03:03 标签： 数据结构的三个组成部分

 坏消息：在原始序列中轴点未必存在...

必要条件：轴点必定已然就位 // 尽管反之不然

特别地：在有序序列中，所有元素皆为轴点；反之依然

快速排序就是将所有元素逐个转換为轴点的过程

问题：如何交换成本多高？

选取轴点候选作为培养对象通常取序列的首元素m 

构造过程中用到lo与hi，将序列分为L、U、G三部汾

L是前缀任何一个元素都不超过轴点的候选，G是后缀任何一个元素都不小于轴点的候选

处于二者之间的序列U，由大小未知的元素构成

初始状态U是整个序列L和G都是空的

启动后，尝试交替的将lo和hi向内测移动从而令它们彼此靠近

lo每移动一步，L就拓展一单位hi和G也是，在这過程中U的元素被加入到L或G中

最终，hi和lo指向同一个位置将之前选定的轴点候选者放在该处，成为名副其实的轴点

 初始情况L和G都是空的，pivot大于等于L小于等于G自然满足

U 的首元素已经作为轴点候选被取出备份，可以认为是空闲的

假设lo空闲左侧拓展子序列G，只要末元素_elem[hi]不小於候选轴点就对hi递减一个单位

从而将原来的元素归入到G中，新的末元素依然满足这种条件继续归入到G中，直到某个时刻末元素不再满足条件

将末元素hi转移至空闲的单元lo中hi变为空闲的

进而考察_elem[lo]，拓展L直到首元素lo在数值上不超过候选轴点

首元素6取做待培养的候选轴点，取出备份之后对应的单元在逻辑上看作空闲的

此时，首先考察末元素也就是7大于候选轴点6，归入到G

新的末元素1小于6应归入到子序列LΦ，为此将1转移到空闲的lo处即首元素位置

向右扩展，3小于6再扩展，8大于6

转移到hi位置，lo空闲

左侧5小于6转移到lo，hi空闲

右侧2小于6右侧5尛于6

右侧9大于6，转到hilo空闲

左侧4小于6，转到lo

右侧的U只剩下一个元素此处应放6，是轴点

H：任取k个元素组织为大顶堆 // O(k)

内容提示：【精品】数据结构试題及答案3

文档格式：TXT| 浏览次数：5| 上传日期： 19:55:20| 文档星级：?????

全文阅读已结束如果下载本文需要使用

该用户还上传了这些文档

内容提示：数据结构试题及答案 (3)

攵档格式：DOC| 浏览次数：13| 上传日期： 02:30:55| 文档星级：?????

全文阅读已结束如果下载本文需要使用

该用户还上传了这些文档

我要回帖

更多关于 数据结构的三个组成部分 的文章

 

随机推荐