单项选择题

对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n ₁ 、n ₂ 和n ₃ ，然后将A中的前n ₁ 个元素赋值为-1，第n ₁ +1到n ₁ +n ₂ 个元素赋值为0，最后n ₃ 个元素赋值为1。该算法的时间复杂度和空间复杂度分别为______。

A.Θ(n)和Θ(1)
B.Θ(n)和Θ(n)
C.Θ(n²)和Θ(1)
D.Θ(n²)和Θ(n)

你可能感兴趣的试题

单项选择题

以下关于渐近符号的表示中，不正确的是______。

A.n²=Θ(n²)
B.n²=O(n²)
C.n²=O(n)
D.n³=O(n³)

单项选择题

某算法的时间复杂度可用递归式
表示，若用Θ表示该算法的渐进时间复杂度的紧致界，则正确的是______。

A.Θ(nlg²n)
B.Θ(nlgn)
C.Θ(n²)
D.Θ(n²)

单项选择题

对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n ₁ 、n ₂ 和n ₃ ，然后将A中的前n ₁ 个元素赋值为-1，第n ₁ +1到n ₁ +n ₂ 个元素赋值为0，最后n ₃ 个元素赋值为1。该算法的时间复杂度和空间复杂度分别为______。

A.Θ(n)和Θ(1)
B.Θ(n)和Θ(n)
C.Θ(n²)和Θ(1)
D.Θ(n²)和Θ(n)

单项选择题

对n个元素的有序表A[1..n]进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为______。

A.n
B.(n+1)/2
C.log₂n
D.n²

单项选择题

用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大的排序，则分别需要进行______次数组元素之间的比较。

A．12，14
B．10，14
C．12，16
D．10，16

单项选择题

对于关键字序列(26，25，72，38，8，18，59)，采用散列函数H(Key)=Key mod 13构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字59所在散列表中的地址为______。

A．6
B．7
C．8
D．9

单项选择题

某算法的时间复杂度可用递归式
表示，若用Θ表示，则正确的是______。

B．Θ(n ² )
C．Θ(n)
D．

单项选择题

某一维数组中依次存放了数据元素15、23、38、47、55、62、88、95、102、123，采用折半(二分)法查找元素95时，依次与______进行了比较。

A．62、88、95
B．62、95
C．55、88、95
D．55、95

单项选择题

递增序列A(a ₁ ，a ₂ ，…，a _n )和B(b ₁ ，b ₂ ，…，b _n )的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为______时，归并过程中元素的比较次数最多。

A．a1，a2，…，an，b1，b2，…，bn
B．b1，b2，…，bn，a1，a2，…，an
C．a1，b1，a2，b2，…，ai，bi，…，an，bn
D．a1，a2，…，ai/2，b1，b2，…，bi/2，ai/2+1，ai/2+2，…，an，bi/2+1，…，bn

单项选择题

现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度分别为______。
i=0; j=n-1;
while i＜j do
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．Θ(n)和Θ(n)
B．Θ(1)和Θ(n)
C．Θ(n)和Θ(1)
D．Θ(1)和Θ(1)

单项选择题

迪杰斯特拉(Diikstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于______策略的算法。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于______策略的算法。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用______来实现。

A．分治法
B．动态规划法
C．贪心法
D．回溯法

单项选择题

分治算法设计技术______。

A．一般由3个步骤组成：问题划分、递归求解、合并解
B．一定用递归技术来实现
C．将问题划分为k个规模相等的子问题
D．划分代价很小而合并代价很大

单项选择题

用动态规划策略求解矩阵连乘问题M ₁ M ₂ M ₃ M ₄ ，其中M ₁ (205)、M ₂ (535)、M ₃ (354)和M ₄ (4*25)，则最优的计算次序为______。

A．((M1*M2)*M3)*M4
B．(M1*M2)*(M3*M4)
C．(M1*(M2*M3))*M4
D．M1*(M2*(M3*M4))

单项选择题

______不能保证求得0-1背包问题的最优解。

A．分支限界法
B．贪心算法
C．回溯法
D．动态规划策略

单项选择题

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用C _ij 。为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2……每次在需访问的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。该算法采用了算法设计策略，其时间复杂度为。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用C _ij 。为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地1，然后选择离运输目的地1最近的运输目的地2……每次在需访问的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。该算法采用了算法设计策略，其时间复杂度为。

A.Θ(n²)
B.Θ(n)
C.Θ(nlgn)
D.Θ(1)