南邮算法分析与设计自测题

1、算法自测题一、1、贪心法能够保证对所有问题都得到整体最优解。选择一项：对错 2、算法具有输入、输出、确定性、能行性和有穷性5个特征，其中（ ）特征的含义是算法的每一条指令必须足够基本，可以通过已经实现的基本运算执行有限次来实现。选择一项：a. 确定性b. 输入c. 有穷性 d. 能行性3、欧几里德算法（辗转相除法）用于计算两个整数m和n的 。答案：最大公约数4、分治法求解问题时通常得到一个递归算法，分析算法的执行时间往往得到递推关系式：T(n)=aT(n/b)+cnk，T(1)=c，求解该递推式可得到算法的渐近时间复杂度，当logbak时，T(n)=( )选择一项：a. nklognb. nk

2、c. nlogbalognd. nlogba 5、 （ ）表示所有增长阶数不超过g(n)的函数的集合。选择一项：a. o(g(n)b. (g(n)c. (g(n)d. O(g(n) 二1、背包问题实例，有4个物品，每个物品重量为(w0,w1,w3)=(4, 2, 7, 4)，物品装入背包的收益为(p0,p1,p3)=(2, 3, 5, 4)。背包载重为M=9。（1）若物品可分割，则这一实例的最优解值为 。（若出现分数，可用a/b的形式表示）答案：64/72、物品可分割，对应于上题中最优解值的最优解为(x0,x1,x3)= 。正确答案是：( 0, 1, 3/7, 1)3、若物品不可分割，可用 求

3、解这一实例。（分治法？贪心法？动态规划法？）正确答案是：动态规划法4、物品不可分割时，最优解值f(3,9)= 8 。5、物品不可分割时，对应于上题中最优解值的最优解为(x0,x1,x3)= (0,1,1,0) 。6、下面哪些特征是属于“分治法”求解的问题特征？选择一项或多项：a. 子问题相互独立b. 需要最优量度标准c.最优子结构性质d.贪心选择性质e.保存子问题的解f.自顶向下求解g.自底向上求解h.重叠子问题性质7、下列哪些特征是“贪心法”求解问题的特征？选择一项或多项：a.保存子问题的解b.最优子结构性质c.重叠子问题性质d.子问题相互独立e.贪心选择性质f.自顶向下求解g.自底向上求解

4、h. 需要最优量度标准8、下列哪些特征是“动态规划法”求解问题的特征？选择一项或多项：a.最优子结构性质b.自底向上求解c.子问题相互独立d.自顶向下求解e.求解过程中保存子问题的解f. 需要最优量度标准g.重叠子问题性质h.贪心选择性质三、1.下面关于动态规划法的说法正确的是（ ）选择一项：a.自底向上求解，避免重复计算重叠子问题； b.自底向上求解，会重复计算重叠子问题；c.自顶向下求解，避免重复计算重叠子问题；d.自顶向下求解，会重复计算重叠子问题。2. LC分枝限界法采用（ ）作为活结点表。选择一项：a. 图b. 队列c. 优先权队列 d.堆栈3.备忘录方法是 的一个变种。答案：动态规划法4、一般称用于确定n个元素的排列满足某些性质的状态空间树为 。答案：排列树5、补充完整下面计算最长公共子序列长度的函数，该函数只使用两行的二维数组c2n，两个字符串分别存放在x和y数组中（从下标为1处开始存放）。int LCS:LCSLength() c10=0; for(int i=1; i=n; i+) c0i=0; /初始化 for(i=1; i=m; i+) for(int j=1; j=c1j-1) ; else ; for(int j=1; j=n; j+)