试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

admin2019-08-15 65

问题试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

选项

答案采用类似于快速排序中的划分思想。算法如下： void part(KeyType A[]，int n){ int i=1；j=n； KeyType temp； while(i＜j){ while(i＜j&&A[j]＞=0)j一一；／／从右向左找负数 while(i＜j&&A[i]＜0)i++；／／从左向右找非负数 if(i＜j){ ／／交换元素A[i]和A[j] temp=A[i]；A[i]=A[j]；A[j]=temp； i++；j一一： } } } 该算法的时间复杂度为O(n)。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

计算机408

学硕统考专业

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。(1)原码定点小数；(2)补码定点小数；(3)反码定点小数；(4)IEEE754标准短

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；

关于单纯疱疹病毒，正确的是

A．24hB．36hC．48hD．72hE．96h断肢(指)再植术后多少时间内较易发生血管危象?

对于犯罪情节轻微不需要判处刑罚的，可以免予刑事处罚，但是可以根据案件的不同情况，采取下列哪几种措施?()

信息管理的目的就是通过有组织的信息流通，使决策者能及时、准确地获得相应的信息。为了达到信息管理的目的，就要把握信息管理的各个环节，并做到()。

材料费的可索赔费用中正确的是(　　)。

法人、个体工商户也享有人身权，包括()。

在整个教学过程中，教师是教育的主导，学生是学习的主体。()

三峡工程的首倡者是毛泽东。()

公安指挥工作，是指公安指挥实施系统的工作，主要负责领导指令的具体下达，各业务部门和专业工作的统一协调、调度和具体指挥，接受“110”报警，突发事件和治安灾害事故的现场指挥、处置与救助等工作。()

根据《婚姻法》的有关规定，下列选项中，男方不得提出离婚的情形是()。

试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

计算机408

学硕统考专业

(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。(1)原码定点小数；(2)补码定点小数；(3)反码定点小数；(4)IEEE754标准短

分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间，请简要解释之。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；

关于单纯疱疹病毒，正确的是

A．24hB．36hC．48hD．72hE．96h断肢(指)再植术后多少时间内较易发生血管危象?

对于犯罪情节轻微不需要判处刑罚的，可以免予刑事处罚，但是可以根据案件的不同情况，采取下列哪几种措施?()

信息管理的目的就是通过有组织的信息流通，使决策者能及时、准确地获得相应的信息。为了达到信息管理的目的，就要把握信息管理的各个环节，并做到()。

材料费的可索赔费用中正确的是( )。

法人、个体工商户也享有人身权，包括()。

在整个教学过程中，教师是教育的主导，学生是学习的主体。()

三峡工程的首倡者是毛泽东。()

公安指挥工作，是指公安指挥实施系统的工作，主要负责领导指令的具体下达，各业务部门和专业工作的统一协调、调度和具体指挥，接受“110”报警，突发事件和治安灾害事故的现场指挥、处置与救助等工作。()

根据《婚姻法》的有关规定，下列选项中，男方不得提出离婚的情形是()。

材料费的可索赔费用中正确的是(　　)。