文档库

最新最全的文档下载
当前位置:文档库 > 算法设计与分析试卷(2010)

算法设计与分析试卷(2010)

1 算法设计与分析试卷(A 卷)

一、 选择题 ( 选择1-4个正确的答案, 每题2分,共20分)

(1)计算机算法的正确描述是: B 、D

A .一个算法是求特定问题的运算序列。

B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。

C .算法是一个对任一有效输入能够停机的图灵机。

D .一个算法,它是满足5 个特性的程序,这5个特性是:有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。

(2)影响程序执行时间的因素有哪些? C 、D

A .算法设计的策略

B .问题的规模

C .编译程序产生的机器代码质量

D .计算机执行指令的速度

(3)用数量级形式表示的算法执行时间称为算法的 A

A .时间复杂度

B .空间复杂度

C .处理器复杂度

D .通信复杂度

(4)时间复杂性为多项式界的算法有:

A .快速排序算法

B .n-后问题

C .计算π值

D .prim 算法

(5)对于并行算法与串行算法的关系,正确的理解是:

A .高效的串行算法不一定是能导出高效的并行算法

B .高效的串行算法不一定隐含并行性

C .串行算法经适当的改造有些可以变化成并行算法

D. 用串行方法设计和实现的并行算法未必有效

(6)衡量近似算法性能的重要标准有: A

A .算法复杂度

B .问题复杂度

C .解的最优近似度

D .算法的策略

(7)分治法的适用条件是,所解决的问题一般具有这些特征: ABCD

A .该问题的规模缩小到一定的程度就可以容易地解决;

B .该问题可以分解为若干个规模较小的相同问题;

C .利用该问题分解出的子问题的解可以合并为该问题的解

D .该问题所分解出的各个子问题是相互独立的。

(8)具有最优子结构的算法有:

A .概率算法

B .回溯法

C .分支限界法

D .动态规划法

(9)下列哪些问题是典型的NP 完全问题:

A .排序问题

B .n-后问题

C .m-着色问题

D .旅行商问题

(10)适于递归实现的算法有: C

A .并行算法

B .近似算法

C .分治法

D .回溯法

二、算法分析题(每小题5分,共10分)

(11)用展开法求解递推关系:

(12)分析当输入数据已经有序时快速排序算法的不足,提出算法的改进方案。

⎩⎨⎧>+-==1

1)1(211)(n n T n n T

免费下载Word文档免费下载: 算法设计与分析试卷(2010)

(共2页)