算法分析设计历年题目

算法分析设计历年题目判断题一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。NP完全问题比其他所有NP问题都要难。回溯法用深度优先法或广度优先法搜索状态空间树。在动态规划中，

算法分析设计历年题目 1. 判断题 1. 一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。 2. NPNP 完全问题比其他所有问题都要难。 3. 回溯法用深度优先法或广度优先法搜索状态空间树。 4. 在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。 5. 类和类问题的关系用来表示是错误的。 6. A 若近似算法求解某极小化问题一实例的解为，且已知该问题的最优解为，则该近似算 3 法的性能比为。 7. 通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。 8. P2(polynomialtransformsto)P1P2P1 若多项式时间转化为，则至少与一样难。 9. 快速排序算法的平均时间复杂度是，使用随机化快速排序算法可以将平均时间复杂度降 得更低。 10. 基于比较的寻找数组中最大元素的问题下届是。 11. 12. 若，，则 13. 若，则 14. 贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。 15. LasVegas 算法只要给出解就是正确的。 16. 一个完全多项式近似方案是一个近似方案，其中每一个算法在输入实例的规模的多项式 时间内运行。 2. 问答题 1. 二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出 最差的效率？此时的查找和插入算法的复杂性如何？ 2. MonteCarloLasVegas 何谓为多项式算法？如何将一算法转化为算法？ 3. AVL2-3 构造树和数的主要目的是什么？它们各自有什么样的查找和插入的效率？ 4. 0/1(PolynomialEquivalent) 写出背包问题的一个多项式等价的判定问题，并说明为什 么它们是多项式等价的。 5. NP 下面问题是否属于问题？为什么？ 问题表述：给定图中的两个点、，整数和，图中每条边的长度及便利这条边的时间，问 图中是否存在一条由到的路径，使得其长度大于，且遍历时间小于？