算法分析与设计样题.doc

算法分析与设计样题

一、填空题（每空2分，共26分）
(1)算法是由若干条指令组成的有穷序列，且满足几条性质，其中有限性是指一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。。
(2)根据符号Ω定义，用它评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则结果就越有价值。
(3)由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
(4)动态规划算法的两个基本要是满足最优性原理和子问题重叠。
(5)贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。
(6)回溯法在包含问题的所有解的解空间树中，按照深度优先策略遍历解空间树，
从根结点出发搜索解空间树。
(7)从活结点表中选择下一扩展结点的不同方式导致两种不同的分支限界法，它们是。
(8)一般情况下，可将概率算法分为四类：数值概率算法、蒙特卡罗算法、舍伍德概率算法、拉斯维加斯概率算法。
(9)在进行问题的计算复杂性分析时，使用的较重要的三个计算模型是随机存取机RAM、。
(10)通常将可在看作是易解问题，而将需要指数时间解决的问题看作是难问题。
(11)回溯法和分支限界法使用的两类典型的解空间树分别为。
(12)在计算机上产生伪随机数最常用的方法是线性同余法。
二、对于下列各组函数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分)