算法设计与分析算法考试算法分析设计历年题目和答案2

VIP免费

2025-01-13 2 0 23.14KB 3 页 5.9玖币

侵权投诉

算法分析设计历年题目

1. 判断题

1. 一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。

2. NP 完全问题比其他所有 NP 问题都要难。

3. 回溯法用深度优先法或广度优先法搜索状态空间树。

4. 在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。

类和

类问题的关系用

P⊂NP

来表示是错误的。

6. 若近似算法 A求解某极小化问题一实例的解为

，且已知该问题的最优解为

sa/3

，则该

近似算法的性能比为 3。

7. 通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。

8. 若P2 多项式时间转化为(polynomial transforms to) P1，则 P2 至少与 P1 一样难。

9. 快速排序算法的平均时间复杂度是

O(nlogn)

，使用随机化快速排序算法可以将平均时

间复杂度降得更低。

10. 基于比较的寻找数组

A[1, …, n]

中最大元素的问题下届是

Ω(n/3)

。

11.

(

)

(

)

=O¿

12. 若

(

)

=Ω

(

)

，

(

)

=Ω

(

)

，则

(

)

=Ω

(

)

13. 若

(

)

(

)

，则

(

)

=Ω(f

(

)

14. 贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。

15. Las Vegas 算法只要给出解就是正确的。

16. 一个完全多项式近似方案是一个近似方案

{Aε}

，其中每一个算法

Aε

在输入实例

的规

模的多项式时间内运行。

2. 问答题

1. 二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现

出最差的效率？此时的查找和插入算法的复杂性如何？

2. 何谓为多项式算法？如何将一 Monte Carlo 算法转化为 Las Vegas 算法？

3. 构造 AVL 树和 2-3 数的主要目的是什么？它们各自有什么样的查找和插入的效率？

4. 写出 0/1 背包问题的一个多项式等价(Polynomial Equivalent)的判定问题，并说明为什么

它们是多项式等价的。

5. 下面问题是否属于 NP 问题？为什么？

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

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

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

算法分析设计历年题目1.判断题1.一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。2.NP完全问题比其他所有NP问题都要难。3.回溯法用深度优先法或广度优先法搜索状态空间树。4.在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。5.P类和NP类问题的关系用P⊂NP来表示是错误的。6.若近似算法A求解某极小化问题一实例的解为sa，且已知该问题的最优解为sa/3，则该近似算法的性能比为3。7.通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。8.若P2多项式时间转化为(polynomialtransformsto)P1，则P2至少...

展开>> 收起<<

算法设计与分析算法考试算法分析设计历年题目和答案2.docx

共3页,预览1页

还剩页未读，继续阅读

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

算法设计与分析算法考试算法分析设计历年题目和答案2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: