设有一个数组中存放了一个无序的关键字序列K1，K2，…，Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

admin2019-08-15 42

问题设有一个数组中存放了一个无序的关键字序列K₁，K₂，…，K_n。现要求将K_n放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

选项

答案 int Partition(RecType K[ ]，int m，int n){ ／／交换记录子序列K[1．．n]中的记录，使枢轴记录到位，并返回其所在位置／／此时，在它之前(后)的记录均不大(小)于它 int i=m，j=n，K[0]=K[j]，x=K[j]．key； while(i＜j){ while(i＜j&＆K[i]．key＜=x)i++； if(i＜j)K[j]=K[i]； while(i＜j&&K[j]．key＞=x)j一一； if(i＜j)K[i]=K[j]； }／／while K[i]=K[0]； return i： } 提示：此题考查的知识点是快速排序的思想。以K_n为枢轴的一趟快速排序。以最后一个关键字为枢轴先从前向后再从后向前快速排序。

解析

转载请注明原文地址:https://kaotiyun.com/show/XKCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设有一个数组中存放了一个无序的关键字序列K1，K2，…，Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

计算机408

学硕统考专业

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题最后废除节度使的是()

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化以及相关考古遗址的发现和研究，是近年来史学界关注的一个热点。二里头文化的年代断限是()

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

与客户沟通的技巧是()。

填然鼓之，兵刃既接。接：

患者，男，32岁，近两个月来腰腹部有隐痛钝痛，今天上午7时突然发作阵发性刀割样疼痛，患者辗转不安，呻吟呼痛，面色苍白，镜下血尿，应考虑为()。

以下关于作业指导书编写要求的描述中错误的是

若透射光强度为入射光的1／100时，照片密度应为

患者，男，39岁。全口牙出血，咀嚼无力，且刚完成彻底的牙周炎系统治疗，无明显系统性疾病。口腔检查：牙周袋深度较之前增加，X线片示牙槽骨吸收有明显发展。口腔卫生情况良好。初步诊断为

《山东省2013—2020年大气污染防治规则》提出要积极调整能源结构，实施煤炭总量控制，力争到()年年底实现煤炭消费总量“不增反降”的历史性转折。

小学生容易把“b”写成“d”，这说明小学生的______还不成熟。()

Inmanycountries,authorityisseldomquestioned,eitherbecauseitishighlyrespected,orbecauseitisfeared.Sometimes,to