算法分析与设计 第一次课外作业
文章目录
- 算法分析与设计 第一次课外作业
- 一. 单选题（共8题，80分）
- 二. 判断题（共2题，20分）
一. 单选题（共8题，80分）
-
(单选题)以下叙述中错误的是（ ）。
A. 算法不能采用自然语言描述，必须使用程序设计语言进行描述。
B. 算法中每条指令的执行次数有限，执行每条指令的时间也有限。
C. 组成算法的每条指令是清晰的，无歧义的。
D. 有零个或多个外部量作为算法的输入并产生至少一个量作为输出。正确答案: A :算法不能采用自然语言描述，必须使用程序设计语言进行描述。;10分
答案解析：
算法除了可以使用自然语言描述，还可以使用伪代码，流程图等来描述。 -
(单选题)
算法复杂性与（ ）无关。
A. 算法要解决的问题的规模
B. 算法本身
C. 算法的输入
D. 运行该算法的硬件正确答案: D :运行该算法的硬件;10分
-
(单选题)
当输入规模为n时，算法增长率最小的是（ ）。A. 5 n 5n 5n
B. 20 l o g 2 n 20log_2{n} 20log2n
C. 2 n 2 2n^2 2n2
D. 3 n l o g 3 n 3nlog_3{n} 3nlog3n正确答案: B :;
10分 -
(单选题)渐近算法分析是指（ ）。
A. 在最坏情况下的复杂性分析。
B. 在平均情况下的复杂性分析。
C. 在最好情况下的复杂性分析。
D. 当规模N -> ∞时，对算法资源开销“增长率”上的简化分析。正确答案: D :当规模N -> ∞时，对算法资源开销“增长率”上的简化分析。;
10分 -
(单选题)下述表达不正确的是（ ）。
A.
B.
C.
D.
正确答案: D :;
10分 -
(单选题)当上下界表达式相等时，使用（ ）来描述算法代价。
A.
B.
C.
D.
正确答案: C :;
10分 -
(单选题)
关于f(n)=O(g(n)),下列说法正确的是 ( ) 。A.
B.
C.
D.
正确答案: A :;
10分 -
(单选题)
下列表述错误的是（ ）。A. 2 N 2 + 11 N − 10 = O ( N 2 ) 2N^2 + 11N - 10 = O(N^2) 2N2+11N−10=O(N2)
B. 2 N 2 + 11 N − 10 = o ( N 2 ) 2N^2 + 11N - 10 = o(N^2) 2N2+11N−10=o(N2)
C. 2 N 2 + 11 N − 10 = θ ( N 2 ) 2N^2 + 11N - 10 = \theta(N^2) 2N2+11N−10=θ(N2)
D. 2 N 2 + 11 N − 10 = Ω ( N 2 ) 2N^2 + 11N - 10 = \Omega(N^2) 2N2+11N−10=Ω(N2)正确答案: B :;
10分
二. 判断题（共2题，20分）
-
(判断题)
算法分析的两个主要方面是时间复杂度和空间复杂度的分析。A. 对
B. 错正确答案: 对
10分 -
(判断题)
如果一个算法的时间复杂性越高，则它的空间复杂性越低。A. 对
B. 错正确答案: 错
