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

算法自测题1、贪心法能够保证对所有问题都得到整体最优解。选择一项：对错/2、算法具有输入、输岀、确定性、能行性和有穷性5个特征，其中()特征的含义是算法的每条指令必须足够基本，可以通过已经实现的基本运算执行有限次来实现。选择一项：确定性输入有穷性能行性/3、欧几里德算法(辗转相除法)用于计算两个整数m和n的。答案：最大公约数4、分治法求解问题时通常得到一个递归算法，分析算法的执行时间往往得到递推关系式：T(n)=aT(n/b)+cnk,T(1)=c，求解该递推式可得到算法的渐近时间复杂度，当logbak时,T(n)=()选择一项：knlognnknlogbalognnlcV/5、()表示所有增长阶数不超过g(n)的函数的集合。选择一项:o(g(n)Q(g(n)(g(n)O(g(n)/1、背包问题实例，有4个物品，每个物品重量为(Wo,wi,”，W3)=(4,2,7,4)，物品装入背包的收益为(po,pi,P3)=(2,3,5,4)。背包载重为M=9。(1)若物品可分割，则这一实例的最优解值为。(若岀现分数，可用a/b的形式表示)答案：64/72、物品可分割，对应于上题中最优解值的最优解为(Xo,Xl,X3)=正确答案是：(0,1,3/7,1)3、若物品不可分割，可用求解这一实例。(分治法？贪心法？动态规划法？)正确答案是：动态规划法4、物品不可分割时，最优解值f(3,9)=一85、物品不可分割时，对应于上题中最优解值的最优解为(XO,X1,”，X3)=(0,1,1,0)。6、下面哪些特征是属于“分治法”求解的问题特征？选择一项或多项：子问题相互独立/需要最优量度标准最优子结构性质贪心选择性质保存子问题的解自顶向下求解/自底向上求解重叠子问题性质7、下列哪些特征是“贪心法”求解问题的特征？选择一项或多项：保存子问题的解最优子结构性质/重叠子问题性质子问题相互独立贪心选择性质/自顶向下求解/自底向上求解需要最优量度标准8、下列哪些特征是“动态规划法”求解问题的特征？选择一项或多项:最优子结构性质/自底向上求解/子问题相互独立自顶向下求解求解过程中保存子问题的解“需要最优量度标准重叠子问题性质/贪心选择性质下面关于动态规划法的说法正确的是(选择一项:a. 自底向上求解，避免重复计算重叠子问题；/自底向上求解，会重复计算重叠子问题；自顶向下求解，避免重复计算重叠子问题；自顶向下求解，会重复计算重叠子问题。LC分枝限界法采用()作为活结点表选择一项:图队列优先权队列Q堆栈3备忘录方法是的一个变种。答案：动态规划法4、一般称用于确定n个元素的排列满足某些性质的状态空间树为。答案：排列树5、补充完整下面计算最长公共子序列长度的函数，该函数只使用两行的二维数组c2n，两个字符串分别存放在x和y数组中(从下标为1处开始存放)。intLCS:LCSLength()c10=0;for(inti=1;i=n;i+)c0i=0;/初始化for(i=1;i=m;i+)for(intj=1;j=c1j-1)；else;for(intj=1;j=n;j+)将数组c中第1行的元素移至第0行return;四个填空答案间，用空格分隔答案：c1j=c0jc1j=c1j-1c0j=c1jc1n