算法分析与设计第一组(最新版).doc

一、 选择题（20分）1下面不是分支界限法搜索方式的是（D ）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先2下列算法中通常以深度优先方式系统搜索问题解的是（D ）。A、备忘录法B、动态规划法C、贪心法D、回溯法3.备忘录方法是那种算法的变形。（ B ）A、分治法B、动态规划法C、贪心法D、回溯法4哈弗曼编码的贪心算法所需的计算时间为（B ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）5分支限界法解最大团问题时，活结点表的组织形式是（B ）。A、最小堆B、最大堆 C、栈D、数组6、在下列算法中得到的解未必正确的是（B ）。A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法7、背包问题的贪心算法所需的计算时间为（B ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）8实现大整数的乘法是利用的算法（C ）。A、贪心法B、动态规划法C、分治策略D、回溯法90-1背包问题的回溯算法所需的计算时间为（A ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）10.下列关于贪心算法，说法错误的是 （C）A贪心法不一定产生最优解，但最终结果可能是最优解的很好的近似解B贪心算法是通过分步布决策的方法来求解问题的C贪心算法是从整体上进行考虑的D贪心法求解的典型问题包括有背包问题、最佳合并模式及带时限的作业排序问题 二、填空题（32分 每空2分）1、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。2、矩阵连乘问题的算法可由 动态规划 设计实现。3、拉斯维加斯算法找到的解一定是 正确解。4.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。5. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。6.贪心算法求装载问题templatevoid Loading(int x, Type w, Type c, int n) int *t = new int n+1; ; for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; ; 5. 有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当使用二分查找值为82的结点时，经过 82 多少次比较后查找成功并给出过程。 6.算法的五大特性包括 有零个或多个外部输入量 、 算法至少产生一个输出量 、 算命法的每条指令没有二义性 、能行性 、 有穷性 。 7. 图的着色问题的算法可由 回溯法 设计实现。8.Strassen矩阵乘法是利用 分治策略 实现的算法。三、 算法设计与分析（20分）1.用欧几里德迭代算法求两个数的最小公倍数（10分）#includeusing namespace std;int Gcd(int m,int n)if(m=0)return n;if(n=0)return m;int t=mn?n:m;while(m%t|n%t)t-;return t;int main()int a,b;coutInput a & b (0=aab;int m=a*b/Gcd(a,b);coutThe Least Common Multiple is:mendl;return 0;3、试用分治法对一个有序表实现二分搜索算法。（12分）解：解答如下： Template int BinarySearch(Type a,const Type& x,int n)/假定数组a已按非递减有序排列，本算法找到x后返回其在数组a中的位置，/否则返回-1 int left=0,right=n-1; while(leftamiddle) left=middle+1; .（8分） else right=middle-1;return -1;.（12分）三、简答题（36分）1. 假设有5个物品，它们的重量和价值如下所示。若这些物品均可以被分割，且背包容量m100，使用贪心算法求解此背包问题，使收益最大，请写出求解过程。（10分） P=(28,120,33,72,256)，W=(7,60,11,48,64)解：（P0/W0,P1/W1.P4/W4）=(4,2,3,3/2,4)(X0,X1.X6) = (1,0,1,3/8,1)总收益为3442、识别下图的关节点，画出他们的连通分图。（13分） 6 0 7 5 1 3 4 2 答案： 0 6 7 1 3 2 7 7 5 3 3、已知 6个矩阵连成：A1A2A3A4A5A6，设他们的维数分别为A1：510，A2：103，A3：312， A4,125， A5,550，：A6：506。求矩阵链积A1A2A3A4A5A6的最佳求积顺序。（要求：给出计算步骤）（13分）答安：使用动态规划算法进行求解。求解矩阵为：123456101503304051655201020360330243019