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

admin2019-08-15 58

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

选项

答案采用类似于快速排序中的划分思想。算法如下： 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://kaotiyun.com/show/9KCi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

19世纪曾形成了以()为中心的资本主义世界经济体系；二战后，逐渐形成了以()为中心的资本主义世界经济体系。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

下列关于计算机中指令和数据存放位置的叙述，正确的是()。

测量控制系统中的数据采集任务把所采集的数据送一个单缓冲区，计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。

下列作品中代表两汉时期散文最高成就的是()

中国人膳食中最主要的供能物质是体内绝大多数生理活动所需的能量都直接来源于

振动法索力测定需准确测定索自振频率值，同时还须确定自振频率的阶数。()

为了指导投标人正确编制投标书，招标文件应包括的内容是(　　)。

目前，欧共体主要国家的旅行社也都表现出明显的垄断化趋势，其中以()最为明显。

通过国家立法的社会政策和政府通过行政手段制定的社会政策法规，在实施中的作用和意义不同在于国家立法的社会政策具有()。

BreastCancerDeathsRecordLowThenumberofwomendyingfrombreastcancerhasfallentoarecordlowbydroppingunder12

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

计算机408

学硕统考专业

19世纪曾形成了以()为中心的资本主义世界经济体系；二战后，逐渐形成了以()为中心的资本主义世界经济体系。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

下列关于计算机中指令和数据存放位置的叙述，正确的是()。

测量控制系统中的数据采集任务把所采集的数据送一个单缓冲区，计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。

下列作品中代表两汉时期散文最高成就的是()

中国人膳食中最主要的供能物质是体内绝大多数生理活动所需的能量都直接来源于

振动法索力测定需准确测定索自振频率值，同时还须确定自振频率的阶数。()

为了指导投标人正确编制投标书，招标文件应包括的内容是( )。

目前，欧共体主要国家的旅行社也都表现出明显的垄断化趋势，其中以()最为明显。

通过国家立法的社会政策和政府通过行政手段制定的社会政策法规，在实施中的作用和意义不同在于国家立法的社会政策具有()。

BreastCancerDeathsRecordLowThenumberofwomendyingfrombreastcancerhasfallentoarecordlowbydroppingunder12

为了指导投标人正确编制投标书，招标文件应包括的内容是(　　)。