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

算法自测题 一、 1、贪心法能够保证对所有问题都得到整体最优解。 选择一项： 对 错 2、算法具有输入、输出、确定性、能行性和有穷性5个特征，其中（ ）特征的含义是算法的每一条指令必须足够基本，可以通过已经实现的基本运算执行有限次来实现。 选择一项： a. 确定性 b. 输入 c. 有穷性 d. 能行性 3、欧几里德算法（辗转相除法）用于计算两个整数m和n的 。 答案：最大公约数 4、分治法求解问题时通常得到一个递归算法，分析算法的执行时间往往得到递推关系式：T(n)=aT(n/b)+cnk，T(1)=c，求解该递推式可得到算法的渐近时间复杂度，当logbak时，T(n)=( ) 选择一项： a. nklogn b. nk c. nlogbalogn d. nlogba （ ）表示所有增长阶数不超过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/7 2、物品可分割，对应于上题中最优解值的最优解为(x0,x1,……,x3)= 。 正确答案是：( 0, 1, 3/7, 1) 3、若物品不可分割，可用 求解这一实例。（分治法？贪心法？动态规划法？） 正确答案是：动态规划法 4、物品不可分割时，最优解值f(3,9)= 8 。 5、物品不可分割时，对应于上题中最优解值的最优解为(x0,x1,……,x3)= (0,1,1,0) 。 6、下面哪些特征是属于“分治法”求解的问题特征？ 选择一项或多项： 子问题相互独立 b. 需要最优量度标准 c.最优子结构性质 d.贪心选择性质 e.保存子问题的解 f.自顶向下求解 g.自底向上求解 h.重叠子问题性质 7、下列哪些特征是“贪心法”求解问题的特征？选择一项或多项： a.保存子问题的解 b.最优子结构性质 c.重叠子问题性质 d.子问题相互独立 e.贪心选择性质 f.自顶向下求解 g.自底向上求解 h. 需要最优量度标准 8、下列哪些特征是“动态规划法”求解问题的特征？选择一项或多项： a.最优子结构性质 b.自底向上求解 c.子问题相互独立 d.自顶向下求解 e.求解过程中保存子问题的解 f. 需要最优量度标准 g.重叠子问题性质 h.贪心选择性质 三、 1.下面关于动态规划法的说法正确的是（ ） 选择一项： a.自底向上求解，避免重复计算重叠子问题； b.自底向上求解，会重复计算重叠子问题； c.自顶向下求解，避免重复计算重叠子问题； d.自顶向下求解，会重复计算重叠子问题。 LC分枝限界法采用（ ）作为活结点表。 选择一项： a. 图 b. 队列 c. 优先权队列 d.堆栈 3.备忘录方法是 的一个变种。 答案：动态规划法 4、一般称用于确定n个元素的排列满足某些性质的状态空间树为 。 答案：排列树 5、补充完整下面计算最长公共子序列长度的函数，该函数只使用两行的二维数组c[2][n]，两个字符串分别存放在x[]和y[]数组中（从下标为1处开始存放）。 int LCS::LCSLength() { c[1][0]=0; for(int i=1; i=n; i++) c[0][i]=0; //初始化 for(i=1; i=m; i++) { for(int j=1; j=n; j++) if(x[i]= =y[j]) c[1][j]=c[0][j-1]+1 ; else if(c[0][j]=c[1][j-1]) ; else ; for(int j=1; j=n; j++) //将数组c中第1行的元素移至第0行 ; }