一、已知下列递推式： C(n) = 1 若n =1 = 2C（n/2） + n – 1 若n ≥ 2
请由定理1 导出C(n)的非递归表达式并指出其渐进复杂性。 定理1：设a,c为非负整数，b,d,x为非负常数，并对于某个非负整数k, 令n=ck, 则以下递推式
f(n) =d 若 n=1 =af(n/c)+bnx 若 n>=2
的解是
f(n)= bnxlogcn + dnx 若 a=cx
?bcxf(n)= ??d?a?cx?
?logca?bcx????n?a?cx???x??n ?若 a≠cx
二、由于Prim算法和Kruskal 算法设计思路的不同，导致了其对不同问题实例的效率对比关系的不同。请简要论述：
1、如何将两种算法集成，以适应问题的不同实例输入； 2、你如何评价这一集成的意义？
三、分析以下生成排列算法的正确性和时间效率： HeapPermute(n) //实现生成排列的Heap算法 //输入：一个正正整数n和一个全局数组A[1..n] //输出：A中元素的全排列 if n = 1 write A else for i ←1 to n do HeapPermute(n-1) if n is odd swap A[1]and A[n] else swap A[i]and A[n]
四、对于求n 个实数构成的数组中最小元素的位置问题，写出你设计的具有减治思想算法的伪代码，确定其时间效率，并与该问题的蛮力算法相比较。
五、请给出约瑟夫斯问题的非递推公式 J（n），并证明之。其中，n 为最初总人数，J(n) 为最后幸存者的最初编号。