文档网

算法 例卷2

一、填空题:

1、按照渐近阶从低到高的顺序排列下列表达式:

20n ,4n 2,logn ,3n ,2,n 2/3,n!,2n 。

____2 logn n 2/3 20n 40n 2 2n 3n n!____

2、分治法的基本思想是将一个规模为n 的问题分解为与原问题____________(相同/不相同)的k 个规模较小且____________(互相独立/相关)的子问题。

3、一个直接或间接地调用自身的算法称为___递归算法_____,它有两个条件,一个是要直接或间接地调用自身,另一个是必须有_初始条件或非递归定义的初始值_。

4、在一个n×n (n=2k )个方格组成的特殊棋盘中,需要____________个L 型骨牌完成棋盘覆盖。

5、在循环赛日程表问题中,若给定的运动员数n=2k-1,则至少需要____n_____天完成比赛;n=2k 时,则需要_____n-1____天。其中,k 为自然数。

6、动态规划算法的主要步骤包括刻画最优解的性质和结构、递归定义最优值、以自底向上的方式计算最优值、根据计算最优值的相关信息构造最优解,在分析了最优解的性质和结构之后,一个比较至关重要的步骤是给出最优值的递归定义,请给出下面几个问题的最优值的递归定义:

(1) 矩阵连乘积问题中,A[i :j]连乘所需的最少乘法次数定义为m[i ,j](1≤i≤j≤n ),

m[i ,j]的初始值定义为0(i=j ),则m[i ,j]递归定义为:

m[i ,,j]=________________________________________________ {}j i p p p

j k m k i m j k i j k i <+++-<≤1],1[],[m in

(2) 最长公共子序列问题中,c[i ,j]表示序列X i 和Y j 的最长公共子序列的长度,则c[i ,

j]可递归定义为:

j j i i y y x x j i j i j i j i c ≠==>>=⎪⎩

⎪⎨⎧=0;0,;0,,0____________________________________________________________0],[

答案1——> 1]1,1[+--j i c

答案2——> {}],1[],1,[m ax j i c j i c --

7、在使用回溯法考虑求解一个具体问题时,往往需要设计出约束条件和限界条件。装载问题的约束条件是___∑=≤k i i i C w x 1

____;限界条件是bestw>cw+r ,其中,bestw 是当前

最优值,cw=___∑=k i i i c

x 1___,r=_____∑+=n k i i w 1_______。

8、0-1背包问题的回溯法和分支限接法求界中都涉及到活结点的上界函数uProfit 的计算问题,它是由两部分组成,一是该活结点已经获得的价值之和Profit ,另一个则是剩余未考虑物品的价值上界rProfit ,这个值可通过__背包贪心方法或按单位重量价值降序排序后选择物品直到装满背包___获得

二、求解题:

1、请用快速排序法升序排序下面实例,给出每一趟排序的结果..........。

相关文档
热门文档
评论