算法设计与分析算法考试2011年答案段

VIP免费

2025-01-13 0 0 36.5KB 1 页 5.9玖币

侵权投诉

一、判断题

1.T

2.F

3.T

4.F

5.F

6.F

7.F

8.T

9.T

10.F

11.F

12.F

13.T

14.T

二、问答题

1.二叉查找树属于减治策略中的减去的规模是可变的。当二叉查找树是严格歪斜的时候，效

率最差，此时的查找和插入效率为。

2.伪多项式时间算法是一种算法，它在 L值的多项式时间内运行，其中 L是输入实例中的

最大数值。这是 PPT 里的定义（维基百科：伪多项式算法：若算法的时间复杂度可以表示

成输入数值 N的多项式，则称其为伪多项式算法。）

当Monte Carlo 算法得出一个解时，并不直接返回该解，而是对该解进行验证是否是正确的

解，如果是正确的解才返回。这样就把 Monte Carlo 算法转化为了 Las Vegas 算法。

3.为了避免二叉查找树出现严重歪斜的现象，改善了最差时间复杂度。AVL 树和 2-3 树在平

均情况和最差情况下，查找和插入的时间效率都是。

4.背包判定问题：在背包重量不超过 W的前提下，是否存在一个物品组合使得背包的物品

价值大于等于 K？

证明：1.背包优化问题可以多项式转化为背包判定问题。我可以利用背包优化问题的最优解

K*去判断 K*是否大于等于 K。2.背包判定问题可以多项式转化为背包优化问题。我们可以对

可能的背包物品价值进行二分查找。搜索区间的下限是（其中是所有物品中

的最小值），上限是（其中是所有物品中的最小值）。在各搜索点

上解其背包判定问题以确定背包优化问题的最优解 K*。

5.属于 NP 问题。因为给定一个肯定的实例（存在一条由 p到q的路径经过顶点

p,v1,v2,...vn,q，该路径的长度大于 C，遍历时间小于 t）。我们可以在多项式时间内验证该

实例是否正确，只需要求出这条路径上的每条边的长度之和 S和遍历时间 T，判断 S>C,T<t

是否成立即可。以上验证算法是可以在多项式时间内完成的。

三、提示：和合并排序的思路一样，只是在合并排序的时候，判断如果在后半段的数大于

在前半段的数，就更新逆对数的数目。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

已全部加载

摘要：

一、判断题1.T2.F3.T4.F5.F6.F7.F8.T9.T10.F11.F12.F13.T14.T二、问答题1.二叉查找树属于减治策略中的减去的规模是可变的。当二叉查找树是严格歪斜的时候，效率最差，此时的查找和插入效率为。2.伪多项式时间算法是一种算法，它在L值的多项式时间内运行，其中L是输入实例中的最大数值。这是PPT里的定义（维基百科：伪多项式算法：若算法的时间复杂度可以表示成输入数值N的多项式，则称其为伪多项式算法。）当MonteCarlo算法得出一个解时，并不直接返回该解，而是对该解进行验证是否是正确的解，如果是正确的解才返回。这样就把MonteCarlo算法转化为了LasVeg...

展开>> 收起<<

算法设计与分析算法考试2011年答案段.doc

共1页,预览1页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析算法考试2011年答案段

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: