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

《南邮算法分析与设计自测题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

4、贪心选择性质/b.自顶向下求解/c.自底向上求解d.需要最优量度标准8、下列哪呜特征是“动态规划法”求解问题的特征？选择-项或多项:a.最优子结构性质/b.自底向上求解/c.子问题相互独立d.自顶向下求解e.求解过程中保存子问题的解/f.需要最优量度标准g.重叠子问题性质/h.贪心选择性质1.下面关于动态规划法的说法正确的是（选择一项：a.自底向上求解，避免重复计算重叠子问题；b.自底向上求解，会重复计算重叠子问题：c.自顶向下求解，避免重复计算重叠子问题；d.自顶向下求解，会重复计算重叠子问题。2丄C分枝限界法采用()作力活结点表。选择一项：a•图b.队列

5、c.优先权队列/d.堆栈3、备忘录方法是的一个变种。答案：动态规划法4、一般称用于确定n个元素的排列满足某些性质的状态空间树力。答案：排列树5、补充完整卜面计算最长公共子序列长度的函数，该函数只使用两行的维数组ct2j[n]，两个字符串分别存放在x[]和yD数组屮(从下标为1处开始存放)。intLCS::LCSLength(){c[1][0]=0;for(inti=1;i<=n;i++)c[O][i]=O;"初始化for(i=1;i<=m;i++)for(intj=1;j<=n;j++)if(x[i]==yffl)c[1]U]=c【0][H]+1;elsei

6、f(c[0][j]>=c[1][j-1])elsefor(intj=1;j<=n;j++)//将数组c屮第1行的元素移至第0行return四个填空答案间，用空格分隔答案:c[1]0]=c[O]0]c[1]0]=c[1][j-1]c[O]0]=c[1]0]c[1][n]