算法分析和设计作业（一）与参考答案解析.doc

《算法分析和设计作业（一）与参考答案解析.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》作业（一）本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归

2、方式是：（C）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（A）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D）A、零个或多个外部输入B、至少一个输出C、指令的确

3、定性D、指令的有限性9、用分治法设计出的程序一般是：（A）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（C）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（C）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C）A、全局最优解B、0-1背包问题的解C、背包问题的解

4、D、无解14、能求解单源最短路径问题的算法是：（A）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（A）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。#include#includeusingnamespacestd;classFlowing{friendintFlow(int**,int,int[]);pri

5、vate://intBound(inti);voidBacktrack(intt);int**M;//int*x;//当前解int*bestx;//int*f2;//intf1;//intf;//intbestf;//intn;//};voidFlowing::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1

6、]:f1)+M[x[j]][2];f+=f2[i];if(f

7、n;i++)X.f2[i]=0,X.x[i]=i;X.Backtrack(1);delete[]X.x;delete[]X.f2;returnX.bestf;}voidmain(){int**M;intn;int*bestx;cout<<"请输入作业数:";cin>>n;M=newint*[n+1];cout<<"请输入各作业处理时间:"<>M[k][j];

8、bestx=newint[n+1];for(i=1;i<=n;i++)bestx[i]=0;cout<<"最优完成时间:"<