1/4
文档分类:中学教育

算法11年期末考试卷答案.docx


下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
算法11年期末考试卷答案.docx
文档介绍:
北京航空航天大学






2010-2011 学年 第二学期期末










《算法设计与分析》


考 试 卷


















班 级 学 号 _________







姓 名 成 绩 _________















2011 年 6 月 9 日







班号 学号 姓名 成绩




《算法设计与分析》期末考试卷



注意事项: 1、关闭手机、将考试用文具以外的物品放于讲台上


、严格遵守学校的考场纪律,违纪者请出考场







题目:

一、 判断题( 21 分,每小题 3 分)

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


1. (

的下界是



√ )基于比较的寻找数组 A[1...

n/2 。



n] 中最大值元素和最小值元素问题

( √ )合并排序使用了分治策略。

3. ( × )快速排序算法的平均时间复杂度是 O(nlogn), 使用随机化快速排序算法可以将平均时间复杂度降得更低。
4. ( × )如果一个问题是 NP 问题,则它一定不是 P 问题。

5. ( √ ) 2n 1
O( 2n ) 且 2n
O (22 n )

6. (
×
)下列问题是一个判定问题: 给定一个合取范式
,对 中的所有逻
辑变量求一组真值赋值,使得
在该组真值赋值下为真。

7. (
×
) NP完备( NP-Complete)问题是所有 NP 问题中最难的,目前还
没有找到用于解决 NP完备问题的多项式算法。






二、 简答题( 28 分,每小题 7 分):

1.请给出基于比较的对数组 A[1 ⋯ n] 进行排序问题的最紧的下界,并写出两个平均时间复杂度为该下界的排序算法的名称。

nlogn ;快速排序、随机化的快速排序。


2.按照增长率上升的顺序排列以下函数,即,若在你的排序结果中,函数 f(n)

跟在 g(n) 的后面,则说明应该满足
g(n) 是 O(f(n)
):

f1 (n)
n3 / 4
f2 (n)
2n
f3 (n) log n f 4 (n) n! f5 (n) 2n 2
f6 (n) n log n
f3 (n) ,
f1 (n) ,
f 6 ( n) ,
f 2 ( n) , f 4 ( n) ,
f 5 (n)



3.推导以下递推式的解:
n
当 n
= 1


T( )=2








T( n)=4T( n/2)+2n 当 n ≥ 2时


T(n)=4T(n/2)+2n

=4(4T(n/4)+2n/2)+2n

=⋯
logn k k-1 =4 T(1)+2n(1+2+4+ ⋯ +n/2) 或设 n=2^k, 4 T(1)+2n(1+2+4+⋯ +2 )

2 2
内容来自淘豆网www.taodocs.com转载请标明出处.