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