算法分析与设计样题

《算法分析与设计样题》由会员分享，可在线阅读，更多相关《算法分析与设计样题（2页珍藏版）》请在金锄头文库上搜索。

1、算法分析与设计样题算法分析与设计样题一、填空题（每空一、填空题（每空 2 2 分，共分，共 2626 分）分）(1) 算法是由若干条指令组成的有穷序列，且满足几条性质，其中有限性是指 一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。 。(2) 根据符号 定义，用它评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则 结果就越有价值 。(3) 由分治法产生的子问题往往是 原问题的较小模式 ，这就为使用 递归技术 提供了方便。(4) 动态规划算法的两个基本要是满足最优性原理和子问题重叠 。(5) 贪心选择性质是指所求问题的整体最优解可以 通过一

2、系列局部最优的选择，即贪心选择来得到 。(6) 回溯法在包含问题的所有解的解空间树中，按照 深度优先策略遍历解空间树 ，从根结点出发搜索解空间树。(7) 从活结点表中选择下一扩展结点的不同方式导致两种不同的分支限界法，它们是 。(8) 一般情况下，可将概率算法分为四类：数值概率算法、 蒙特卡罗算法、 舍伍德概率算法、拉斯维加斯概率算法 。(9) 在进行问题的计算复杂性分析时，使用的较重要的三个计算模型是随机存取机RAM、 。(10) 通常将可在 看作是易解问题，而将需要指数时间解决的问题看作是难问题。(11) 回溯法和分支限界法使用的两类典型的解空间树分别为 。(12) 在计算机上产生伪随机数

3、最常用的方法是 线性同余法 。二、对于下列各组函数 f(n)和 g(n), 确定 f(n)=O(g(n)或 f(n)=(g(n)或 f(n)= (g(n),并简述理由。(每小题 3 分，共 12 分)(1) f(n)=logn6; g(n)=8logn+5 (2) f(n)= 100n; g(n)=log2n(3) f(n)=nlogn+n; g(n)=logn (4) f(n)= 2n; g(n)=10n3三、试述分治法的基本思想并用于两个大整数的乘法, 分析其算法复杂性。(12分)四、试给出基于分治策略的二分搜索算法并分析其复杂性。(10 分)五、贪心算法的基本要素是什么？试给出基于贪心策略的活动安排问题的算法。(12 分)六、试给出用回溯法求解 4 皇后问题的部分解空间树，并简单分析其复杂性。(8 分)七、试给出用动态规划方法求解矩阵连乘问题的几个详细步骤。(10 分)八、试结合主元素问题论述蒙特卡罗算法的基本思想。(10 分)