现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负

试卷名称 2012年上半年软件设计师考试上午真题试题（综合知识）

考试中心《2012年上半年软件设计师考试上午真题试题（综合知识）》在线考试

试卷年份2012年上半年

试题题型【单选题】

试题内容

现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度分别为（）。
i=0; j=n-1;
while i＜jdo
while A[i]＜0 do
i=i+1;
while A[j]＞0 do
j=j-1;
if i＜j do
交换A[i]和A[j];

A. A
B. B
C. C
D. D

查看答案

相关试题

第47题：

递增序列A(a1，a2，…，an)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为（）时，归并过程中元素的比较次数最多。
A．a1，a2，…，an，b1，b2，…，bn
B．b1，b2，…，bn，a1，a2，…，an
C．a1，b1，a2，b2，…，aibi，…，anbn
D．a1，a2，…，ai/2，b1，b2，…，bi/2，ai/2+1，ai/2+2，…，an，bi/2+1，bi/2+2，…，bn

答案解析与讨论：www.cnitpm.com/st/2478029200.html

第48题：

以下关于渐进符号的表示中，不正确的是（）。
A．n²=Θ(n²)
B．n²=O(n²)
C．n²=O(n)
D．n²=O(n³)

答案解析与讨论：www.cnitpm.com/st/2478128113.html

第49题：

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用C_ij。为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2，…，每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。该算法采用了（1）算法设计策略，其时间复杂度为（2）。
（1） A．分治
B．动态规划
C．贪心
D．回溯
（2）A.Θ（n²）
B.Θ（n）
C.Θ（nlgn）
D.Θ（1）