2．（10分）下面是用回溯法求解图的m着色问题的算法（求出所有解）。 图的m着色问题：给定一个无向连通图G和m种颜色，给图G的所有顶点着色，使得任何两相邻顶点的颜色不同。 算法 m-COLORING 输入：正整数m, n和含n个顶点的无向连通图G的邻接矩阵graph。 输出：图G的m着色问题的所有解, 若无解，则输出no solution。 flag=false k=1; x[1]=0 while k>=1 while (1) x[k]=x[k]+1 if color(k) then if (2) then flag=true; output x[1..n] else k= (3) (4) end if end if end while (5) end while if not flag then output “no solution” end m-COLORING 过程 color (k) //在前k-1个顶点已着色的情况下，判断第k个顶点是否可着颜色x[k], 是则 21
//返回true, 否则返回false。 ＿＿＿＿＿号学 ＿栏＿ ＿ ＿ ＿ ＿ 名 姓息 级 年线 ＿ 信＿ ＿ ＿ ＿ ＿ 业 生专订 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿
…… end color 3．（14分）设有n种不同面值的硬币，面值分别为c1, c2, ? , cn（c1=1），每种硬币的个数不限，要求用最少个数的硬币，兑换价值为m的钱（m为非负整数）。 设f[k, j]表示用面值为c1, c2, ? , cj的硬币兑换价值为k的钱所用硬币的最少个数，则 ?k , j f[k,j]???1???0?mini??k/c?f[k?i*cj, j-1]?i? , j?1 j?下面是解该最优化问题的最优值和最优解的动态规划算法。 算法 CHANGING 输入：正整数n，非负整数m，存储n种硬币面值的数组c[1..n]，其中c[1]=1。 输出：兑换价值为m的钱所用硬币的最少个数和存储最优解信息的数组s[0..m, 1..n]。 f[0..m, 1..n]= -1 min=coinchanging(m, n) return min, s end CHANGING 过程 coinchanging(k, j) //求用面值为c[1],c[2],…,c[j]的硬币兑换价值为k的钱所用硬 //币的最少个数，并返回。同时记录最优解的信息于数组s中。 if f[k, j]= (1) then if j=1 then f[k, j]=k 22
else minx=coinchanging(k, j-1); i0=0 for i=1 to ?k/c[j]? x= (2) +i if x ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级 姓名＿＿＿＿＿＿ 学号＿＿＿＿＿ 四．算法设计题（15分） 1. 写出一个随机算法，对于一个由n个整数组成的序列，求其中的第1~k小元素（即序列按升序排序后的前k个元素），并给出该算法的期望时间复杂性的阶。 考 生 信 息 栏 装 订 线 2005计本《算法设计与分析》期考试卷(B)标准答案 一. 填空题： 1. 有穷性，确定性，可行性，有>=0个输入，有>0个输出 24 2. ? 3. max{t(I)} I?Dn4. 分解出的需要求解的子问题的个数 5. 避免重复求解子问题 6. 答案 7. 相互独立的（不重叠的） 8. 不一定 9. 小 10. 插入排序算法 11. 总是或者得到正确的解或者找不到解。 12. 递归关系 13. 比较 14. 求xn的值 ?(logn) 二. 计算题和简答题： 这些函数按不同的阶分成如下4类： Θ(1): f1, f5 Θ(n): f3, f6, f7 Θ(nlogn): f2, f8 Θ(2n): f4 各类的阶按从低到高的顺序排列的结果是： Θ(1), Θ(n), Θ(nlogn), Θ(2n) 2. 解： 分别记算法A和算法B的时间复杂性为TA(n)和TB(n)，解相应的递归方程得： TA(n)?O(n) ?O(n) , a?4? TB(n)??O(nlogn) , a?4 ?log4a) , a?4?O(n2TB(n)?TA(n)； 依题意，要求最大的整数a使得TB(n)?TA(n)。显然，当a<=4时， 当a>4时，TB(n)?TA(n) ?log值为15。 3. 字符集合M的Huffman编码树是： 42a?2 ?a<4=16。所以，所求的a的最大整数 25