重庆大学《算法分析与设计》课程试卷 A 卷 juan 2014~2015 学年 第 1 学期 开课学院：计算机学院 课程号： 18016435 考试日期： 考试方式： 考试时间： 120 分钟 题 号 一 二 三 四 五 六 七 八 九 十 总 分 得 分 注释：此试卷为本人根据考试偷拍的照片，一个个单词手动打印，单词有错勿怪！ 一. (15 分) 算法复杂度渐进分析 (1) Sort the following items ascendingly(升序)by their asymptoticy(5 分) (log(n))0.5 1000 (2.00001)n 1.001n*(n+1) n+1/n+log(n) (2) Work out the following function by expansion method(展开法)(10 分) T(n)=2T(n/2)+n,T(1)=⊙(1) 二. (20 分) 快速排序 (1). What is the best time complexity(最好时间复杂度) to sort an array with quicksort? Describe such a situation briefly(简短叙述).(3 分) 2. What is the worst time complexity(最坏时间复杂度) to sort an array with quicksort? Describe such a situation briefly(简短叙述).(3 分) 3. During each iteration, if we assume that the initial array is split(分割) according to the ration(比例) 1:9, then A)write the recurrence of this situation;(3 分) B)draw out the corresponding recursion tree;(3 分) C)prove the tight bound(⊙)of your recurrence with substitution(替代法).(8 分) 三. (15 分) 动态规划(钢管切割问题) For rod-cutting problem,we have following prices list: Length i Price Pi 1 1 2 5 3 8 4 9 5 10 7 6 8 17 17 20 9 24 10 30 密 封 线 弊 作 绝 拒 、 纪 考 肃 严 、 信 守 实 诚 、 争 竞 平 公 名 姓 号 学 级 年 班 、 业 专 院 学 重庆大学试卷 教务处 07 版 第 1 页 共 2 页 Let r(n) be the maximum revenue( 最 大 收 入 ) by cutting up a rod of length n and selling the pieces (1) Give the recursive formula of r(n).(5 分) (2) Write the algorithm into a program in pseudo code or other programming languages.(5 分) (3) Work out r(1),r(2),...,r(8).(5 分) 四. (10 分) 贪心算法(Huffman Encoding) Give the frequencies of 6 letters to be encoded as a:40%,b:13%,c:8%,d:16%,e:9%,f:14% (1) give the corresponding Huffman tree;(5 分) (2) Write the corresponding binary codes(2 进制码) for each letter,and compute the averaged coding length(编码长度的平均值).(5 分) 五. (20 分) 动态规划(文件配置问题) Suppose we want to replicate( 复 制 )a file over a collection( 集 合 )of n servers( 服 务 器 ),labeled S1,S2,...,Sn.To place a copy of the file at server Si results in a placement cost(配置代价)of ci(ci is a positive integer).Now if a user requests the file from serve Si， and no copy of the file is present at Si,then severs Si-1,Si-2,Si-3...are searched in order until a copy of the file is finally found,say at server Sj ，where j1),Si is placed with a copy of the file.In this case,W(i)= (2)Assume server Sj,Sj+1,...Si-1,Si(j

重庆大学试卷 教务处 07 版 第 2 页 共 2 页 (5)六．(20 分)最大流 Let G=(V,E) be a flow network and |f| be the value of a flow on G,i.e.,|f|=f(s,V) with s being source of G. (1) Prove|f|=f(V,t) with t being sink of G.(5 分) (2) Work out the maximum flow of the following flow network,where the positive integers denote the capacities of each edge respectively.During each iteration,you should draw the residue network (剩余流量图) and find out an augmenting path (增广路径) (if exists).(15 分) 12 9 10 10 8 s 13 15 18 9 7 23 16 t