北航算法设计与分析（5套卷）.doc

算法设计与分析--jzp整理

PAGE14

北京航空航天大学研究生课程试卷1

——算法设计与分析

判断题（本题共7分，每小题0.5分）

请在正确的陈述前面括号中打√，在错误的陈述前面括号中打×。

（ 对）回溯法用深度优先法来搜索状态空间树

（ 错）一个完全多项式近似方案是一个近似方案{A$}，其中每一个算法A$在输入实例I的规模的多项式时间内运行。

（ 对）基于比较的寻找数组A[1…n]中最大值元素问题的下界是Ω（n/3）

（ 错）NP完全问题比其他NP问题都要难

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

（ 错）在动态规划中，各阶段的所确定的策