资源描述：
《2018年6月算法设计分析(第3次)作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第3次作业—＞填空题（本大题共30分，共10小题，每小题3分）1.程序的性能一般指程序的空间复杂性和复杂性。2.计算机算法指的是解决问题的和3.最优子结构性质的含义是o4.贪心算法与动态规划算法的主要区别是5.有如下递归过程：voidprint(intw){inti;if(w!=0){print(w-1);for(i二1;i〈二w;i++)printf("%3d”,w);printf()；}}调用语句print(4)的结果是。6.Edmonds-Karp算法规定，在剩余网络中采用寻找路径作为增广路径7.问题能够应用分治算法
2、思想进行求解的前提是问题的性和解的性。在快速排序、插入排序和归并排序算法中，算法不是分治算法9.将矩阵链AdJWUV在As处断开，则m[3,7]=10.计算一个算法时间复杂度通常可以计算、或。二、简答题(本大题共30分，共5小题，每小题6分)1.下面程序段的所需要的计算时间为intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=l;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thi
3、ssum>sum){sum二thissum;besti二i;bestj=j;}returnsum;}2.请简单描述一下插入排序算法思想。3.设G=(V,E)为流网络f为流。证明对于所有XUSf(X,X)=03.Ford-Fulkerson算法的主要问题是什么？4.在三数取中划分法中，第k小的元素要成为中心数，必须与一个比它更小的元素以及一个比它大的元素一起被取出来，其概率等于多少？三、问答题(本大题共40分，共5小题，每小题8分)1.输入三个不相同的数，求出其中的最小数。用自然语言描述算法。2•请概述最小代价生成树的贪心选
4、择性质，并证明。3.简述分治法在每一层递归上的三个步骤的具体内容？4.证明0(f(n))+0(g(n))=0(max{f(n),g(n)})5.分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。答案：一、填空题(30分，共10题，每小题3分)1.参考答案：时间解题方案：评分标准：2.参考答案：方法过程解题方案：评分标准：3.参考答案：问题的最优解包含其子问题的最优解解题方案：评分标准：4.参考答案：贪心选择性质§方案:评分标准:5.参考答案:122
5、333解题方案：评分标准：6.参考答案：广度优先搜索法最短解题方案：评分标准：7.参考答案：可分可归并解题方案:评分标准:8.参考答案：插入排序解题方案：评分标准：9.参考答案：m[3,5]+m[6,7]+p2p5p7§方案:评分标准：10.参考答案：计算步循环次数基本操作的频率解题方案:评分标准:二、简答题（30分，共5题,每小题6分）1.参考答案:0（昉§方案:评分标准:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。解题方案：评分标准：3.参考答案：对所有x,yGX,f(x,y)+
6、f(y,x)二0。所以f(X,X)+f(X,X)=0解题方案：评分标准：4.参考答案：当最大流值较大时可能发生的情况是每次寻找出来的增广路径，都只能将流网络的流量增加很小的值，这样的话，会大大增加循坏的次数。尤其是
7、f*
8、=2El时,算法的时间复杂度变成流网络规模0(
9、V
10、+
11、E
12、)的指数函数0(
13、E
14、2iei)o解题方案：评分标准：5.参考答案：(k_D(n_k)n(n-l)(n—2)解题方案：评分标准：三、问答题(40分，共5题，每小题8分)先设置一个变量min,用于存放最小数。当输入a、b、c三个不相同的数后，先将a
15、与b进行比较，把小者送给变量min,再把c与min进行比较，若eVmin,贝I」min二c。解题方案：评分标准：2.参考答案：贪心选择的性质指的是局部最优选择可以得到全局最优解决方案，在最小代价牛成树中，其表现为每次选择的为当前可选情况下权值最小的边。证明：(1)一定有一个最优解包含了当前权值最小的边o假设最优解不包含该边，则将务⑷加入其中，会形成一个环，任意去掉环里比务⑷权值大的一条边，则形成了一个更优的解，与假设矛盾。(2)选择了务⑴后，子问题为去掉了务“关联的点的剩余的点为顶点集，剩余的边为边集的图的最小代价问题，规
16、模变小，性质不变。通过归纳法，其可以通过贪心性质得到最优解。解题方案：评分标准：3.参考答案：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。解题方案:评分标准:t(n)=
