算法设计与分析d&k

《算法设计与分析d&k》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络学院算法试题D及答案一．填空题：（第小题每题4分，共20分）1.一个算法的优劣通常用_时间复杂度和空间复杂度来度量.2．递归函数的两大基本要素是__递归方程_和边界条件.3．对n皇后问题，将问题陈述为：将n个皇后放在n×n棋盘的不同行、不同列上，使得任意两个皇后均不能处在同一对角线上。则解空间中有n！个元素。4.实例特征是指_决定问题规模的因素，如输入数的大小及数据的数量等_____.5．在回溯法中，一个问题的解空间是指一个大的决策可由若干小的决策组成，所有可能的决策序列构成该问题的解空间.二．简答题：（第1，2，4小题每题8分，第3小题4分，共28分）1．备忘录的递归方法的基本思想是什

2、么？在使用动态规划算法求解问题时，采用备忘录的递归较一般递归方法有何好处？答：备忘录的递归方法的框架和一般的递归方法的框架相同，所不同的是每次将不同子问题的答案保存在一张表中，在以后需要时只要花很少的时间查询即可，因而在采用备忘录的递归方法时，进入函数，首先查询若所要求的子问题是否已有答案，若有只要取回即可，否则递归调用求解新的子问题。在使用动态规划算法求解问题时，采用备忘录的递归可避免子问题的重复计算，从而可大大提高算法的效率。2．简述一个程序运行所需要的空间由哪几部分构成？各部分存储的对象分别包括哪些？答：一个程序运行所需要的空间由三部分构成，分别为指令空间、数据空间和环境栈空间。指令空

3、间---用来存储经过编译之后的程序指令；数据空间用来存储所有常量和变量的值；环境栈空间保存函数调用返回时恢复运行所需要的信息。当一个函数被调用时，下面数据将被保存在环境栈中：1）返回地址；2）所有局部变量的值、递归函数的传值形式参数的值；3）所有引用参数以及常量引用参数的定义。3．算法设计通常有哪些方法？(至少列出4种)答：算法设计方法有分治算法，贪心算法，动态规划算法，归纳算法，回溯算法，分支限界算法等。4．动态规划算法的基本思想是什么？它和分治法有什么区别和联系？答：动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复子问题，为了避免

4、子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可构造出所求问题的最优解。三．分析解答题：（第1,2小题每题11分,第3,4小题每题15分，共52分）1．判断下面的算法是否正确，如果算法不正确，请说明产生错误的原因，如果算法正确，请给出算法的正确性证明。TemplateIntBinarySearch(Typea[],constType&x,intn)5{intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;If(x==a[middle])re

5、turnmiddle;If(x>a[middle])left=middle;elseright=middle;}return-1;}解答：算法不正确，因为数组左、右游标left和right的调整不正确，将导致死循环。2.考虑分数背包问题，定义如下：给出n个大小为s1,s2,…,sn,值为v1,v2,…,vn的项目，并设背包容量为C,要找到非负实数x1,x2,…,xn,使和在约束下最大。参考代码如下：floatknapsack(floatc,floats[],floatv[],floatx[]){intn=v.length;Element[]d=newElement[n];for(inti=0

6、;ic)break;x[d[i].i]=1;opt+=d[i].v;c-=d[i].s;}if(i

7、该问题91215106821895197104165参考程序如下：#defineMin(a,b)((a)<(b))?a:b#definemax104intr[max],s[max][max],t[max],dp[max][max];intmain(){intn,i,j,mx,ca,lo,cnt;scanf("%d",&ca);while(ca--){scanf("%d",&n);mx=214000000;fo