＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿
专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 16
一．填空题（每空2分，共30分） 1．算法的五个特性是 。 2．在忽略常数因子的情况下，O，?和?三个符号中， 提供了算法运行时间的一个确切界限。 3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间，则算法的最坏情况下时间复杂性W(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： ??f(n)?d , n?n0?f(n)?af(n/c)?g(n) , n?n0 其中， a表示 。 5．动态规划算法中存储子问题的解是为了 。 6．在一个问题的状态空间树中，若从根到某结点的路径对应该问题的一个解，则称该结点为一个 结点。 7．分治法不同于动态规划，其分解出的子问题是 。 8．贪心算法通过一系列局部最优选择来求解问题，最终 能得到问题的最优解。 9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越 ，优先级越高。 10．快速排序、插入排序和归并排序算法中， 算法不是分治算法。 11．在随机算法中，Las Vegas算法的特点是 。 12．若对一个问题的求解可转化为对其性质相同的子问题的求解，则称该问题满足 。 13．下面算法的基本运算是 运算。 算法 SPLIT 输入：正整数n，数组A[1..n]。 输出：…。 i=1
17
＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年 ＿ ＿ 信＿＿ ＿ ＿ 业 专 生＿＿ ＿ ＿ ＿ ＿ 系 考＿＿＿＿＿＿院学＿＿＿＿＿＿ x=A[1] for j=2 to n if A[j]<=x then i=i+1 if i?j then A[i]?A[j] end if end for A[i]?A[1] w =i return w, A 线 end SPLIT 14．下面算法的功能是 ，其时间复杂性阶为?( )。 算法 EX1 输入：实数x和非负整数n 。 订 输出：… y=ex1(x, n) output y end EX1 装过程 ex1 (x, m) if m=0 then y=1 else y=ex1 (x, ?m/2?) y=y*y if m为奇数 then y=x*y 18
end if return y end ex1 二．计算题和简答题（每小题7分，共21分） 1．将下列各函数按阶分类，同阶的分为一类，并将各类的阶按从低到高的顺序排列： f1(n)=1000 f2(n)=6n+n?logn?-5 f3(n)=3n f4(n)=2n?n2 f5(n)=1 f6(n)=4n+n/logn-1 f7(n)=2(n?n) f8(n)=nlogn+log8n 2．算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程?T(n)?1 , n?1 ??T(n)?4T(n/2)?n , n?1，算法B的时间复杂性满足递归方程?T(n)?1 , n?1 ，若要使得算法??T(n)?aT(n/4)?n , n?1A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？ 3．对于字符集合M={A,B,C,D,E,F}，设这些字符在文本中出现的频率分别为8,1,3,10,6,5，画出字符集合M的Huffman编码树，并给出各字符的Huffman编码。 三．算法填空题（共34分） 1．（10分）下面是求解分数背包问题的贪心算法。 分数背包问题：设有一个容量为C的背包，n个物品的集合U={u1, u2, …, un}，物品ui的体积和价值分别为sj和vj，C, sj, vj都是正实数。在U中选择物品装入背包，使得装入背包的物品总价值最大。设允许取每种物品的一部分装入背包。 19
算法 GREEDY_KANPSACK ＿＿＿＿＿号学 ＿ 栏＿＿ ＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ 信 ＿ ＿ ＿ ＿ 业 专订 生 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿
输入：表示背包容量的实数C, 物品数n, 表示n个物品的体积和价值的实数数组s[1..n]和v[1..n]。 输出：装入背包的物品的最大总价值maxv和相应的最优解x[1..n]。 for i=1 to n y[i]=v[i]/s[i] end for d=sort(y, n) //对y[1..n]按降序地址排序，排序结果返回//到数组d[1..n]中, 使得//y[d[1]]>=y[d[2]]>=…>=y[d[n]]。 for i=1 to n x[i]=0 i=1; maxv=0; rc=C while (1) j=d[i] if (2) then x[j]=1; rc=rc-s[j] else x[j]= (3) (4) end if maxv= (5) i=i+1 end while return maxv, x[1..n] end GREEDY_KNAPSACK 20