算法分析与设计第五组.docVIP

一、选择题（20分） 1．下列算法中通常以自底向上的方式求解最优解的是（???B????? ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 2、衡量一个算法好坏的标准是（C ）。A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短3、以下不可以使用分治法求解的是（D ）。A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题4. 实现循环赛日程表利用的算法是（????A????? ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 5、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 6．下列是动态规划算法基本要素的是（??D???? ）。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 7．下列算法中通常以自底向下的方式求解最优解的是（????B???? ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 8．采用广度优先策略有哪些信誉好的足球投注网站的算法是（?????A????? ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 9、合并排序算法是利用（???A????? ）实现的算法。 A、分治策略?? B、动态规划法?? C、贪心法??? D、回溯法 10、下列不属于影响程序执行时间的因素有哪些？ （ C ） A．算法设计的策略 B．问题的规模 C．编译程序产生的机器代码质量 D．计算机执行指令的速度 二、填空题(30分 每空2分) 1、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。 2、利用概率的性质计算近似值的随机算法是__数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法_____________________。 3、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。4、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。 5.贪心算法求活动安排问题 templateclass Type void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true; int j=1; for (int i=2;i=n;i++) { if (s[i]=f[j]) { A[i]=true; j=i; } else A[i]=false; } } 6. 二分检索算法最多的比较次数为 log n ？ 7. 快速排序算法最坏情况下需要比较 n2 次运算？ 8.贪心算法基本要素有 最优度量标准 和 最优子结构 。 9.回溯法解旅行售货员问题时的解空间树是 子集树 。 10.二分有哪些信誉好的足球投注网站算法是利用 分治策略 实现的算法。 三、 算法设计（22分） 1、试用分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试计算的所有不同排列。（10分） 解：解答如下： Templateclass Type void Perm(Type list[],int k,int m) { if(k= =m){ for(int i=0;i=m;i++) coutlist[i]; ……………………………..（3分） coutendl; } else for(int i=k;i=m;i++) if(ok(list,k,i)){ swap(list[k],list[i]); Perm(list,k+1,m); swap(list[k],list[i]); ……………………………..（7分） }; } 其中ok用于判别重复元素。 Templateclass int ok(Type list[],int k,int i) { if(ik) for(int t=k;tI;t++) if(list[t]= =list[i]) return 0; return 1; }……………………………..（10分） 2、试用贪心