A.Θ（n）和Θ（1）
B.Θ（n）和Θ（n）
C.Θ（n2）和Θ（1）
D.Θ（n2）和Θ（n）
本题需要用3个辅助变量n1、n2和n3来保存数组A中-1、0和1的个数，空间复杂度为Θ（1）。在统计时，需要使用一循环语句遍历数组A。统计完成后，再使用一次循环语句遍历数组A，并将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n个元素赋值为1。数组A的元素个数为n，因此算法的时间复杂度为Θ（n）。
（ 9 ）下面的函数利用递归实现了求 1+2+3+ …… +n 的功能：
int sum （ int n ） {
if （ n==0 ）
return 0;
else
return n+sum （ n-1 ） ；
}
在执行 sum （ 10 ）的过程中，递归调用 sum 函数的次数是【 9 】 。
某算法的时间复杂度可用递归式[*],表示，若用[*]表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。
A．
(nlg2n)
B．(nlgn)
C．(n2)
D．(n3)
用折半查找方式查找N个元素的数组，当查找成功时，其递归执行程序时递归调用的最大次数是(11)。
A．
B．
C．
D．
A、f(1)=0
B、f(1)=1
C、f(0)=1
D、f(n)=f(n-1)+1/n
Chapter2GettingStartInsertionsort2.1.2将Insertion-Sort重写为按非递减顺序排序2.1.3计算两个n位的二进制数组之和Analyzingalgorithms2.2.当k二1时，n二2，显然有T(n)=nlgn假设当k=i时公式成立，即T(n)=nlgn=2ilg2i=i-2i，则当k=i+1，即n=2i+1时，将函数n3/1000-100n2-100n+3用符号0表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n个元素已经是最大的元素了.最好时间和最坏时间均为0(n2)Designingalgorithms2ifn二2T(n)斗2.3.3计算递归方程的解l2T(n/2)+nfn二2k，fork1T(n)=nlgn2.3.4给出insertionsort的递归版本的递归式T()=爲爲)f；=:2.3-6使用二分查找来替代insertion-sort中while循环内的线性扫描，是否可以将算法的时间提高到0(nlgn)?虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是0(n2)2.3-7给出一个算法，使得其能在0(nlgn)的时间内找出在一个n元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间0(nlgn)，然后再进行查找:Search(A,n,x)QuickSort(A,n);i1；jn;whileAi+Aj丰xandijifAi+Aj0，(n+a)b=&(nb)a0时，(n+a)nb对于c=1,c=2b，cnb(n+a)cnb1212a0时，(n+a)-2a，当nn时，(n+a)(n/2)b00对于c=2-b,c=1，cnb(n+a)cnb121231-4判断2n+1与22n是否等于O)316证明如果算法的运行时间为0(g(n)，如果其最坏运行时间为O(g(n)，最佳运行时间为Q(g(n)。最坏时间O(g(n)，即Teg(n)1.T=0(g(n)3,1,7：证明o(g(n)nw(g(n)
设求解某问题的递归算法如下： F(int n){ if n==1{ Move(1); } else{ F(n-1); Move(n); F(n-1); } } 求解该算法的计算时间时，仅考虑算法Move所进行的计算为主要计算，且Move为常数级算法，设算法Move的计算时间为k，当n=5时，算法F的计算时间为(42)。
A．7k
B．15k
C．31k
D．63k
用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。
A．n
B．n/2
C．log2n
D．log2(n+1)
当n值较大时，ASLbs≈log2(n+1)-1。
计算N!的递归算法如下，求解该算法的时间复杂度时，只考虑相乘操作，则算法的计算时间T(n)的递推关系式为(55)；对应时间复杂度为(56)。
int Factorial (int n)
{//计算n!
if(n＜=1)return 1;
else return n * Factorial(n-1);
}
(62)
A．T(n)=T(n-1)+1
B．T(n)=T(n-1)
C．T(n)=2T(n-1)+1
D．T(n)=2T(n-1)-1
设某算法的计算时间表示为递推关系式T(n)＝T(n-1)+n(n＞O)及T(0)＝1，则该算法的时间复杂度为(65)。
A．O(lgn)
B．O (nlgn)
C．O(n)
D．O(n2)
设求解某问题的递归算法如下：
F(int n){
if n=1 {
Move(1)
}else{
F(n-1)；
Move(n)；
F(n-1)；
}
}
求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为(9)；设算法Move的计算时间为k，当 n=4时，算法F的计算时间为(10)。
A．T(n)=T(n-1)+1
B．T(n)=2T(n-1)
C．T(n)=2T(n-1)+1
D．T(n)=2T(n+1)+1