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

admin2019-08-15 49

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

选项

答案采用类似于快速排序中的划分思想。算法如下： 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

学硕统考专业

希特勒打出民族主义的旗号而获得群众的广泛支持，主要原因是()。

明清时期专制主义空前加强，据此回答问题：清代在散文方面，声势最大、影响最广的是桐城派，不属于该派的是()

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

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

某DRAM芯片内部存储元排列成1024．×1024的矩阵，且已知其存取周期为0．1μs，最大刷新间隔为2ms。当采用异步刷新方式时，死时间()。

为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，()不是一定需要。

操作外圆磨床时应先打开总油门，后开动砂轮。()

任何单位和个人需要在依法划定的电力设施保护区内进行可能危及电力设施安全的作业时，必须()才可进行作业。

根据《劳动合同法》，在劳务派遣用工方式中，订立劳务派遣协议的主体是()。

某投资方案，基准收益率为15％，若该方案的内部收益率为18％，则该方案()。

期货投资者保障基金|的资金来源包括()。

加工贸易进口料件及其制成品需征税或内销补税的，海关按照一般进口货物，审定完税价格。内销的进料加工进口料件或其制成品，海关审定的完税价格是(　　)。

名义货币供给如果超过了实际货币需求，就会引起()。

教师享有按时获取工资报酬，享受国家规定的福利待遇以及寒暑假带薪休假的权利。()

Faces,likefingerprints,areunique.Didyoueverwonderhowitispossibleforustorecognizepeople?Evenaskilledwriterp

In1784,fiveyearsbeforehebecamepresidentoftheUnitedStates,GeorgeWashington,52,wasnearlytoothless.Sohehiredadent

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

计算机408

学硕统考专业

希特勒打出民族主义的旗号而获得群众的广泛支持，主要原因是()。

明清时期专制主义空前加强，据此回答问题：清代在散文方面，声势最大、影响最广的是桐城派，不属于该派的是()

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

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

某DRAM芯片内部存储元排列成1024．×1024的矩阵，且已知其存取周期为0．1μs，最大刷新间隔为2ms。当采用异步刷新方式时，死时间()。

为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，()不是一定需要。

操作外圆磨床时应先打开总油门，后开动砂轮。()

任何单位和个人需要在依法划定的电力设施保护区内进行可能危及电力设施安全的作业时，必须()才可进行作业。

根据《劳动合同法》，在劳务派遣用工方式中，订立劳务派遣协议的主体是()。

某投资方案，基准收益率为15％，若该方案的内部收益率为18％，则该方案()。

期货投资者保障基金|的资金来源包括()。

加工贸易进口料件及其制成品需征税或内销补税的，海关按照一般进口货物，审定完税价格。内销的进料加工进口料件或其制成品，海关审定的完税价格是( )。

名义货币供给如果超过了实际货币需求，就会引起()。

教师享有按时获取工资报酬，享受国家规定的福利待遇以及寒暑假带薪休假的权利。()

Faces,likefingerprints,areunique.Didyoueverwonderhowitispossibleforustorecognizepeople?Evenaskilledwriterp

In1784,fiveyearsbeforehebecamepresidentoftheUnitedStates,GeorgeWashington,52,wasnearlytoothless.Sohehiredadent

加工贸易进口料件及其制成品需征税或内销补税的，海关按照一般进口货物，审定完税价格。内销的进料加工进口料件或其制成品，海关审定的完税价格是(　　)。