重庆大学2013算法考卷B(共1页).docx

《重庆大学2013算法考卷B(共1页).docx》由会员分享，可在线阅读，更多相关《重庆大学2013算法考卷B(共1页).docx（1页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上命题人：罗辛 组题人： 陈波 审题人： 李佳 命题时间： 2013-07-02 教务处制学院 专业、班 年级 学号 姓名 公平竞争、诚实守信、严肃考纪、拒绝作弊封线密重庆大学算法分析与设计课程试卷juan 20122013 学年 第二学期开课学院：计算机学院 课程号： 考试日期： 考试时间： 120 分钟题 号ABCDEFGHIJ总 分得 分注：答案填写在试题页后的答案纸上，用中文解答。一些重要的关键词句后附有中文解释。A. (15 points) Use mathematical induction(数学归纳法) to show that when n = 2k w

2、ith k0 the solution of the recurrence equation (递归等式) T (n) = T(n/2) + n, where T(1)=3is T(n)= 2n+1. B. (15 points) Quicksort(快速排序) is a very interesting algorithm. Given an disordered array with n elements, 1. What is the best time complexity(最好时间复杂度) to sort this array with quicksort? 2. What is t

3、he worst time complexity(最坏时间复杂度) to sort this array with quicksort? 3. During each iteration, if we assume that the initial array is split(分割) according to the ration(比例) 1:9, then write the recurrence of this situation, and prove that the asymptotic time complexity will remain (n log n) with subst

4、itution .C. (25 points) Suppose that in a 0-1 knapsack problem(0-1 背包问题) , the order of the items when sorted by increasing weight(按重量升序排序) is the same as their order when sorted by decreasing value(按价值降序排序). Give an efficient algorithm to find an optimal solution to this variant of the knapsack pro

5、blem, and argue that your algorithm is correct. 1. Describe the greedy choice. 2. Prove the greedy choice property （贪心选择性质） of this problem. 3.Write a program in pseudo code （伪代码） or other popular programming language to solve this problem based on your algorithm. D. (25 points) For input sequence X

6、1.m and Y1.n, we define ci,j = length(长度) of Longest Common Sequence(最长公共子序列) of X1.i and Y1.j; By using methodology of dynamic programming(动态规划), we got ci,js recursive formula:1. Fill out(填空) the above formula and indicate the time complexity for computing cm,n.2. Assume X = and Y = . Then fill ou

7、t the following table of c0.6,0.6.j0123456iCCGGAC001A2G3C4C5G6GE. (20 points) Run either the matrix multiplication(矩阵乘法) or the Folyd-Warshall algorithm for the all-pairs shortest paths(全部顶点对最短路径) on the following weighted, directed graph. Indicate(指出) clearly which algorithm is used(用了何种算法) and show the matrix D(k) at each iteration(迭代) until the shortest distances(最短距离) between all pairs of vertices are computed.21231-24-243-126453专心-专注-专业