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

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

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、实现合并排序利用的算法是（）。D、冋溯法A、分治策略B、动态规划法C、贪心法4、以下不可以使用分治法求解的是（）

2、0A、棋盘覆盖问题B.选择问题C、归并排序D、0/1背包问题5、记号O的定义正确的是（）。A、O(g(n))={f(n)

3、存在正常数c和nO使得对所有有：0

4、存在正常数c和nO使得对所有有：05cg(n)

5、对于任何正常数c>0,存在正数和nQO使得对所有n>n0有:0

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

7、子问题的解可以合并D、原问题和子问题使用相同的方法解7、以下关于渐进记号的性质是正确的有：()A^f(n)=0(g(n)),g(n)=0(h(n))=>f(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))og(n)=O(f(n))8、衡量一个算法好坏的标准是()oA、运行速度快氏占用空间少C、时间复杂度低D、代码段9、背包问题的贪心算法所需的计算时间为()。A、0(n2n)B、0(nlogn)C、0(2n)D、0(n)10、实现大整数的乘法

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

9、解,然后从这些的解得到原问题的解。得分评卷人三、证明题(每题2分，共20分)1、猜测T(n)

10、解0/1背包问题。3、百钱百鸡问题。屮国古代数学家张丘建在他的《算经》屮提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？