算法分析温习题

1、、阅读以下说明和图，填补流程图中的空缺，将解答填入答题纸的对应栏内。说明在一条农村公路的一边稀疏地散布着屋子，其散布如以下图所示。某电信公司需要在某些位置放置蜂窝基站，由于基站的覆盖范围是6千米，因此必需使得每栋屋子到某个基站的直线距离不超过6千米。为简化问题，假设所有屋子在同一直线上，而且基站沿该直线放置。现采纳贪婪策略实现用尽可能少的基站覆盖所有的屋子。实现贪婪算法的流程如以下图所示，请填充其中空白并计算该算法的时刻复杂度，其中：1. di(lWi<N)表示第i个屋子到公路A端的距离，N表示屋子的总数，屋子编号依照屋子到公路A端的距离从小到大进行编号。2. sk表示第k(k21)个基

2、站到公路A端的距离，算法终止后k的值为基站的总数。该算法的时刻复杂度为上2二、阅读以下说明，回答下列问题1至问题3,将解答填入答题纸的对应栏内。【说明】某餐厅供给各类标准的营养套餐。假设菜单上共有n项食物mi,m2,，mn,每项食物mi的营养价值为Vi,价钱为pi,其中i=l,2,n,套餐中每项食物最多显现一次。客人常需要一个算法来求解总价钱不超过M的营养价值最大的套餐。【问题1下面是用动态计划策略求解该问题的伪代码，请填充其中的空缺(1)、和处。伪代码中的要紧变量说明如下：n：总的食物项数；v：营养价值数组，下标从1到n,对应第1到第n项食物的营养价值；P：价格数组，下标从1到n,对应第1到

3、第n项食物的价格；M：总价钱标准，即套餐的价钱不超过M：x：解向量(数组)，下标从1到n,其元素值为。或1,其中元素值为0表示对应的食物不出此刻套餐中，元素值为1表示对应的食物出此刻套餐中；nv：n+l行M+1列的二维数组，其中行和列的下标均从0开始，表示由前i项食物组合且价钱不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nvnMc伪代码如下：MaxNutrientValue(n,v,p,M,x)1 fori=0ton2 nvi0=03 forj=1toM4 nv|Oj=O5 fori=1ton6 forj=1toM包问题的贪婪算法voidKnapsack(intn,floa

4、tM,floatv,floatw,floatx)(Sort(n,v,w);inti;for(i=l;i<=n;i+)xi=0;floatc=M;for(i=l;i<=n;i+)if(wi>c)break;2.最大子段和：动态计划算法intMaxSum(intn,inta)(intsum=0,b=0：心算法求装载问题template<classType>voidLoading(intx,Typew,Typec,intn)(int*t=newintn+1;for(inti=1;i<=n;i+)xi=0;for(inti=1;i<=n&&wt

5、i<=c;i+)xti=1;4.贪婪算法求活动安排问题template<classType>voidGreedySelector(intn,Types,Typef,boolA)intj=l;for(inti=2;i<=n;i+)if(si>=fj)elseAi=false;0.快速排序template<classType>voidQuicksort(Typea,intp,intr)(if(P<r)intq=Partition(a,p,r);:列问题Template<classType>voidperm(Typelist,intk,intm)治法的大体思想是什么？2.设计动态计划算法的要紧步骤是什么3分治法与动态计划法的异同有哪些4 .分支限界法与回溯法的异同有哪些5 .分支限界法的搜索策略什么6 .分治法所能解决的问题一样具有的几个特点是：7 .用分支限界法设计算法的步骤是：8 .常见的两种分支限界法的算法框架9 .回溯法中常见的两类典型的解空间树是子集树和排列树。五、算法题1 .给定已按升序排好序的n个元素现要在这n个元素中找出一特