资源描述:
《南邮算法分析与设计自测题资料》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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]