2015算法设计与分析考试复习刚要及习题(4)

数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。 32 什么是哈密顿环问题？ 参考解答：哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。 33 用回溯法求解哈密顿环，如何定义判定函数？ 参考解答：当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,?,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。 34 请写出prim算法的基本思想。 参考解答：思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。

三、算法设计题 7

1.【最长上升子序列问题】（8分）—— 提示：此题可采用动态规划算法实现 对于给定的一个序列，。我们可以得到一些递增

上升的子序列，

7,

3, 5, 9, 4, 8)，有它的一些上

升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务：就是这里。比如，对于序列(1,

对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。. 参考解答：设表示：从左向右扫描过来直到以元素结尾的序列，获得的

f(i)a[i]最长上升子序列的长度，

且子序列包含元素（）。

当

都有

即，

是从，??到中找最大的一个值，再加1。或者

就是1。主要是看a[i]这个元素能否加入

到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。 最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n} 例如，对于序列：4 2 6 3 1 5 2 i 1 2 3 4 5 6 7 array 4 2 6 3 1 5 2 f(i) 1 1 2 2 1 3 2 评分准则： 答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，1) 边界设定清晰，本题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不唯一） 说明使用动态规划算法，但对递推函数表达错误或含糊，扣2分以上； 2) 其它情况酌情考虑。

3)

2．（10分）对下图所示的连通网络G，用克鲁斯

卡尔(Kruskal)算法求G的最小生成树T,请写出在算法

执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。 8

18 2 1 7 21 19 11 9 6 3 26 15 6 4 5 17 参

考解答 TE={(3,4), (2,3),(1,5),（4,6）（4,5）} （5分） 贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。 基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。（4分） 时间复杂度为：O(eloge) （1分） 3.（15分）考虑n=3的批处理作业调度实例： t机器1 机器2 ji 作业1 1 10 作业2 3 1 作业3 2 1 i其中t是作业J需要在机器j上处理的时间。对于给定的3个作业，制定ji一个最佳作业调度方案，使其完成时间和达到最小。 要求： （1）画出该问题的解空间树； （5分） （2）写出该问题的剪枝策略(即限界条件),要求只保留第一个最优解;(2分) （3）按优先队列式分支限界法搜索解空间树，并用剪枝策略对解空间树中该剪枝的位置打

；

（5分） （4）给出最优解及最优值。 （3分） 参考解答（1）5分 9

V 0 1 3 2 11 4 3 2 3 1 3 2 1 18 10 16 9 23 23 3

2 3 1 1 2 33 30 25 36 36 26 ※

fbestf（2）若当前代价 >= 当前最优解代价，则剪枝。

2分 （3）见（1）中所画的图。5分 （4）最优解为{3，1，2}，最优值为25。3分 4.【Gray码构造问题】

（8分）—— 提示：此题可采用分治递归算法实现 n问题描述：“格雷码”是一个长度为的序列，满足： 2（a）每个元素都是长度为n比特的串 （b）序列中无相同元素 （c）连续的两个元素恰好只有1个比特不同 例如：n=2时，格雷码为{00，01，11，10}。 Gray码是一种编码，这种编码可以避免在读取时，因各数据位时序上的差异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算，请你设计一种构造方法，输入长度序列n，输出格雷码（你只要做出一种构造方案即可，格雷码并不唯一）。 参考解答：此题可用分治法解决。 当n＝1时，输出格雷码{0, 1}

nn22

当n>1时，格雷码的长度为，即共有个码序列。

此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。 评分准则： 答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当1) 仅输出1位的格雷码如何处理），本题即可得满分； 说明使用分治算法，但漏边界条件，扣2分以上； 2) 10

其它情况酌情考虑。 .（13分）给定带权有向图

5

（如下图所示）G =(V,E)，其中每条边的权是非负

实数。另外，还给定V中的一个顶点，称为源。现

在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。 S u dist[2] dist[3] dist[4] dist[5] 迭

代 {1} 初始 1 2 3 4 参考解答：

（13分） S u dist[2] dist[3] dist[4] dist[5] 迭代 {1} - 10

30 100 初始 {1，2} 2 10 60 30 100 1 {1，2，4} 4 10 50 30 90 2 {1，2，4，3} 3 10 50 30 60 3 {1，2，3，4，5} 5 10 50 30 60 4 6.（13分）有0-1背包问题如下： n=6，c=20，

P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=(15，8，6，4，3，1) W=(2，3，4，5，8，10)，单位重量物品价值（7.5，2.67，1.5,0.8,0.375,0.1） 参考解答：（13分） 可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。 1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。 2.把重量为3的物品放进背包，此时剩余载重量为14，P为23； 3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；