精品文档
return PARTITION(A; p; r)} PARTITION(A; p; r) { x← A[r] i ←p-1 for j ← p to r-1
do if A[j] ≤ x then i ←i+1 exchange A[i] ?A[j] exchange A[i+1] ? A[r] return i+1 } 六
首先画出它对应的图，加上标号，假设从1出发，每次贪心选择一个权重最小的顶点作为下一个要去的城市。(算法策略5分)
求解过程5分 七
收集于网络，如有侵权请联系管理员删除
精品文档
100 55 a:45 30 25 d:1614 c:12 b:13 30 f:5 e:9
a:1 b:100 c:101 d:111 e:1100 f:1101
八 V={11,21,31,33,43,53,55,65} weight W={1,11,21,23,33,43,45,55} 按照单位重量的价值排序，112131334353551?11?21?23?33?43?6545?55，然后按照该顺序往背包中放。 九
递归方程4分
f1[1]=9 f2[1]=12 f1[2]=18 f2[2]=16 f1[3]=20 f2[3]=22 f1[4]=24 f2[4]=25 f1[5]=32 f2[5]=30 f1[6]=35 f2[6]=37
the fastest time is 38 and the fastest way is: station 1:line 1 station 2:line 2
收集于网络，如有侵权请联系管理员删除
精品文档
station 3:line 1 station 4:line 2 station 5: line 2 station 6: line 1 求解过程6分 十
递归方程4分
m[1,1]=0 m[2,2]=0 m[3,3]=0 m[4,4]=0 m[1,2]=m[1,1]+m[2,3]+p0*p1*p2=60 m[2,3]=m[2,2]+m[3,3]+p1*p2*p3=30 m[3,4]=m[3,3]+m[4,4]+p2*p3*p4=30
m[1,3]=min{m[1,2]+m[3,3]+p0*p2*p3, m[1,1]+m[2,3]+p0*p1*p3}=54 m[2,4]=min{m[2,3]+m[4,4]+p1*p3*p4, m[2,2]+m[3,4]+p0*p2*p4}=48 m[1,4]=min{m[1,1] +m[2,4]+p0*p1*p4, m[1,2]+m[3,4]+p0*p2*p4, m[1,3]+m[4,4]+p0*p3*p4}=78
((A1(A2A3))A4) 求解过程6分 十一
if x[i]?y[j],?c[i?1,j?1]?1 c[i,j]???max(c[i,j?1],c[i?1,j])otherwise 递归方程4分
C A T G C 0 0 0 A 0 0 1 C 0 1 1 T 0 1 1 G 0 1 1 A 0 1 1 T 0 1 1 C 0 1 1 G 0 1 1 2 2 2 2 2 0 1 1 2 3 3 3 3 0 1 2 2 3 3 4 4
收集于网络，如有侵权请联系管理员删除
精品文档
最长公共子序列长度为4 AGTC 求解过程6分
十二 From the preceding discussion, it suffices to determine the height of a decision tree in which each permutation appears as a reachable leaf. Consider a decision tree of height h with l reachable leaves corresponding to a comparison sort on n elements.
从前面讨论,它可以确定一个决策树的高度,每个排列显示为一个可到达的叶子。考虑一个决策树的高度h和l可及的叶子在n个元素对应于一种比较。
Because each of the n! permutations of the input appears as some leaf,
因为每个n !排列的输入出现一些叶子,
we have n! ≤ l.
Since a binary tree of height h has no more than 2h leaves, 因为一个二叉树的高度h没有超
过2 h叶子
we have（分析5分） n! ≤ l≤ 2h ,
which, by taking logarithms, implies
h ? lg(n!) (since the lg function is monotonically increasing) = ?(n lg n) 列式和求解5分 十三
Proof: If we decompose path p into v1? vi? vj? vk, then we have that w(p) = w(p1i) + w(pij) +w(pjk). Now, assume that there is a path p’ij from vi to vj with weight w(p’ij)< w(pij) . Then, v1? vi? vj? vk is a path from v1 to vk whose weight w(p1i) + w(p’ij) +w(pjk)is less than w(p), which contradicts the assumption that p is a shortest path from v1 to vk.
反证法假设5分，分析5分 十四
收集于网络，如有侵权请联系管理员删除
精品文档
列式5分，求解5分 十五
matrix multiplication:
5分
Floyd-Warshall algorithm:
收集于网络，如有侵权请联系管理员删除
精品文档
十六
Heapify(A, i) { l = Left(i); r = Right(i); if (l <= heap_size(A) && A[l] > A[i]) largest = l; else largest = i; if (r <= heap_size(A) && A[r] > A[largest]) largest = r; if (largest != i) Swap(A, i, largest); Heapify(A, largest); }
Fixing up relationships between i, l, and r takes ?(1) time，If the heap at i has n elements, the subtrees at l or r can have 2n/3 elements. So time taken by Heapify() is given by T(n) ? T(2n/3) + ?(1) ,by recursive tree, the solution is T(n) = O(lg n) .算法描述4分 列递归方程3分，求解3分
收集于网络，如有侵权请联系管理员删除
山东建筑大学计算机学院算法分析算法复习题（Yuconan翻译）上课讲义
