算法设计与分析(试题B卷).doc

《算法设计与分析(试题B卷).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》答卷说明：1、考试方式闭卷2、满分100分题号■—*四五六七总分总分人分数得分评卷人一、单项选择题（每小题2分，共20分）1、下面关于NP问题说法正确的是（）。A、NP问题都是不可能解决的问题B、P类问题包含在NP类问题中C、NP完全问题是P类问题的子集D、NP类问题包含在P类问题中2、能采用贪心算法求最优解的问题，一般具有的重要性质为：（）A、最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、预排序与递归调用3、实现合并排序利用的算法是（）。C、贪心法D、回溯法）。归并排序D、0/1背包问题A、分治策略B、

2、动态规划法4、以下不可以使用分治法求解的是（A、棋盘覆盖问题B、选择问题C、5、记号O的定义正确的是（）。A、0(g(n))={f(n)

3、存在正常数c和nO使得对所有n>n0有：0%f(n)

4、存在正常数c和nO使得对所有n2n()有:0

5、对于任何正常数c>0,存在正数和n°>0使得对所有n2n。有：0

6、对于任何正常数c〉0,存在正数和n。〉0使得对所有n>n0有：0

7、的条件是()oA、子问题必须是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题使用相同的方法解7、以下关于渐进记号的性质是正确的有：()A、f(n)=0(g(n)),g(n)=0(h(n))nf(n)=0(h(n))B、f(n)=O(g(n)),g(n)=O(h(n))=>h(n)=O(f(n))C、O(f(n))+O(g(n))=O(min{f(n),g(n)})D、f(n)=O(g(n))<=>g(n)=O(f(n))8、衡量一个算法好坏的标准是()oA、运行速度快B、占用空间少C、时间复杂度低D、代码段9、背包问题的贪心算法所需的计算时间为()。A、

8、0(n2n)B、0(nlogn)C、0(2n)D、0(n)10、实现大整数的乘法是利用的算法(A、贪心法B、动态规划法C、分治策略D、回溯法得分评卷人二、填空题(每空2分，共18分)1、算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。2、下面是一个含有多个for循环的程序段，其中有嵌套的。Sum=0For(j=l;j

9、的是组成算法的每条是清晰的，无歧义的。6、动态规划算法的基本思想是将待求解问题分解成若干，先求解，然后从这些的解得到原问题的解。得分评卷人三、证明题(每题2分，共20分)1>猜测T(n)

10、动过程当中，3个基座上的盘子都始终保持大盘子在下，小盘子在上。移动过程中可以利用C基座座辅助。2、动态规划算法解0/1背包问题。3、百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各凡何？