北航研究生算法答案

判断题： 1-5: T F F F F 6-10: F T F F F 11-16: F T T F T F 问答题： 1.（1）属于减可变规模变种的应用。（2）当节点个数等于二叉查找树的高度时表现出最差的效率。（3）此时查找和插入算法在最坏情况的时间复杂度都是O(n)。 2.（1）伪多项式时间算法是一种在L值的多项式时间内运行的算法，其中L是输入实例中的最大数值。 （2）Monte Carlo算法每次都能得到问题的解，但不保证所得解的准确性；Las Vegas算法是每次不一定得到问题的解，只要得到的解一定是正确的解；可以在Monte Carlo算法后加上一个验证算法，如果正确就得到解，如果错误就不能生成问题的解，这样Monte Carlo算法便转化为了Las Vegas算法。 3. AVL树和2-3树能够维持树的平衡，避免树的退化，它们在最坏情况下插入和查找的时间复杂度均为O(log2n)。 4. 0/1背包问题的一个多项式等价判定问题是给定价值为V1, V2, …, Vn，重量为W1, W2, …, Wn的n个项和两个整数v*和w*，问是否存在一个子集S，使得 ，且 。 若存在0/1背包问题的多项式算法，则可用其在多项式时间内求解该判定问题，令背包容量等于W*，求出0/1背包问题的最优子集S，则可以通过判断S是否满足 来确定判定问题的解。 若存在该判定问题的多项式算法，则可以在可能的价值范围内进行二分搜索，在各搜索点上解判定问题以确定0/1背包问题的最优解，令V= 可在O(log(V)) 时间内求得解。 5. 属于NP问题。因为可以在多项式的时间验证一个候选路径是否符合条件。 分治题： 1. // num : 逆序数 num = 0; Merge(Type a[], Type left, Type mid, Type right) { Type b[]; k=left; i = left, j = mid+1; while( i <= mid && j <= right) { if(a[i] > a[j]) { num += mid – i + 1; b[k++]=a[j++]; } else { b[k++]=a[i++]; } } while(i<=mid) b[k++]=a[i++]; while(j<=right) b[k++]=a[j++]; for(i=left; i<=right ; i++) a[i]=b[i]; } MergeSort(Type a[], Type left, Type right) { if(left < right) { mid = (left + right) / 2; MergeSort(a, left, mid); MergeSort(a, mid + 1, right); Merge(a, left, mid, right); } } 算法思路：以归并排序为基础，在两两集合合并的时候如果前一个集合的元素a[i]>a[j]，那么说明需要调整次序，逆序数num=num+mid-i。 时间复杂度的迭代公式为 EMBED Equation.DSMT4 
 因此算法的时间复杂度为T(n)=O(nlogn)； 蛮力法的时间复杂度为O(n2)，当n数目较大时，分治法计算规模远小于蛮力法。 2. 蛮力算法时间复杂度：O(n2)；空间复杂度：O(1) /** *对长度为len的数组A，找出它的多数元素 */ majority(A[], len) { HeapSort(A); // 对数组A中元素按从小到大顺序进行堆排序 i = 0; flag = false; while i < len { tmp = A[i] count = 1; while i + count < len && A[i+count] == tmp { count++; } if count > len/2 { print(tmp+“是多数元素”) flag = true; break; } i + = count; } if flag == false print(“没有多数元素”) } 采用减治的思想每一个减去一个元素，时间复杂度为O(nlgn)，蛮力法的时间复杂度为O(n2)。 , 动态规划题： 项目投资 k为项目的编号1,2,3； 状态变量：Xk为投资项目k到n的总的投资金额。（其中n为项目总数。） 决策变量：Uk为项目k的投资金额，gk（Uk）为项目k投资Uk后的收益。 允许决策集合：Dk（Xk）={ Uk|0<=Uk<=Xk} 状态转移方程：Xk+1=Xk-Uk 递推关系式为：fk（Xk）=max{ gk（Uk）+fk+1（Xk-Uk）} k=1，，，n-1。 fn(Xn)=gn(Xn) 其中fk（Xk）表示投资项目k到n总投资额Xk后的收益。 最后的结果为f1（X1）； 在本题中n=3，X1=8，并且0<=Xk<=8。 手工求解过程： k=3， X3 0 1 2 3 4 5 6 7 8 f3(X3) 0 4 26 40 45 50 51 52 53 2. k=2 X2 U2 X3=U2-X2 g2(U2) f3(X3) g2(u2)+f3(x3) 0 0 0 0 0 0 1 0 1 0 4 4 1 0 5 0 5=f2(1) 2 0 2 0 26 26=f2(2) 1 1 5 4 9 2 0 15 0 15 3 0 3 0 40 40=f2(3) 1 2 5 26 31 2 1 15 4 19 3 0 40 0 40 4 0 4 0 45 45 1 3 5 40 45 2 2 15 26 41 3 1 40 4 44 4 0 60 0 60=f2(4) 5 0 5 0 50 50 1 4 5 45 50 2 3 15 40 55 3 2 40 26 66 4 1 60 4 64 5 0 70 0 70=f2(5) 6 0 6 0 51 51 1 5 5 50 55 2 4 15 45 60 3 3 40 40 80 4 2 60 26 86=f2(6) 5 1 70 4 74 6 0 73 0 73 7 0 7 0 52 52 1 6 5 51 56 2 5 15 50 65 3 4 40 45 85 4 3 60 40 100=f2(7) 5 2 70 26 96 6 1 73 4 77 7 0 74 0 74 8 0 8 0 53 53 1 7 5 52 57 2 6 15 51 66 3 5 40 50 90 4 4 60 45 105 5 3 70 40 110=f2(8) 6 2 73 26 99 7 1 74 4 78 8 0 75 0 75 f2(1)=5,f2(2)=26,f2(3)=40,f2(4)=60,f2(5)=70,f2(6)=86,f2(7)=100,f2(8)=110; 3. k=1 X1 U1 X2=X1-U1 g1(U1) f2(x2) g1(U1)+f2(x2) 0 0 0 0 0 0=f1(0) 1 0 1 0 5 5 1 0 5 0 5=f1(1) 2 0 2 0 26 26=f1(2) 1 1 5 5 10 2 0 15 0 15 3 0 3 0 40 40 1 2 5 26 31 2 1 15 5 20 3 0 40 0 40=f1(3) 4 0 4 0 60 60 1 3 5 40 45 2 2 15 26 41 3 1 40 5 45 4 0 80 0 80=f1(4) 5 0 5 0 70 70 1 4 5 60 65 2 3 15 40 55 3 2 40 26 66 4 1 80 5 85 5 0 90 0 90=f1(5) 6 0 6 0 86 86 1 5 5 70 75 2 4 15 60 75 3 3 40 40 80 4 2 80 26 106=f1(6) 5 1 90 5 95 6 0 95 0 95 7 0 7 0 100 100 1 6 5 86 91 2 5 15 70 85 3 4 40 60 100 4 3 80 40 120=f1(7) 5 2 90 26 116 6 1 95 5 100 7 0 98 0 98 8 0 8 0 110 110 1 7 5 100 105 2 6 15 86 101 3 5 40 70 110 4 4 80 60 140=f1(8) 5 3 90 40 130 6 2 95 26 121 7 1 98 5 103 8 0 100 0 100 由以上的结果的f1（8）=140. 其中x1=8，u1=4，u2=4，u3=0. 2 产品需求的 每个月的需求量为N1=2，N2=3，N3=2，N4=4; 状态变量：每个月初的库存量为Xk, 则 0<=Xk<=min{(k-1)*6-(N1+..N（k-1）)，Nk+...N4}（k=2,3,4）;X1=0; 决策变量：每个月的生产量为Yk，则max{0，Xk-Nk}