计算机算法设计与分析第2~4章算法复习题
需积分: 9 166 浏览量
2021-01-02
13:47:50
上传
评论
收藏 304KB DOCX 举报
第 2 章 分治算法
1.分治法解决问题分为三步走，即分、治、合。下面列出了几种操作， 请按分、治、合
顺序选择正确的表述。（1）将子问题的解合并为大问题的解，（2）将问题分解为子问题，
（3）将子问题合并为大问题。（4）求子问题的解，（5）将问题分解为可重复的子问题。
A.(2)(4)(1) B.(5)(4)(1) C.(2)(1)(3) D.(5)(1)(3)
2 分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性 T(n)的一个递归方
程， 然后解此方程可得 T(n)的结果。T(n)的递归定义如下：
关于该定义中 k，n/m, f(n)的解释准确的是
A.k 是子问题个数，n/m 是子问题的规模，f(n)是规模为 n 的问题分解为子问题
的时间复杂性
B.k 是子问题个数，n/m 是子问题的规模，f(n)是分解为子问题的时间复杂性与
合并子问题的解的时间复杂性之和
C.k 是常系数，n/m 是规模为 n 的问题分为 m 个子问题，f(n)是将子问题的解合
并为问题的解的时间复杂性。
D.k 是常系数，n/m 是规模为 n 的问题分为 m 个子问题，f(n)是分解为子问题的
时间复杂性与合并子问题的解的时间复杂性之和。
3 已知斐波那契数列中第 n 个斐波那契数 F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第 n
个斐波那契数，从下面选项中选取答案。
A.不能，因为它不可以用分、治、合三个步骤完成计算
B.能，因为它可以用分、治、合三个步骤完成计算
C.不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就
是没有重复子问题）
D.能，因为它满足分治法的四个适应条件
评论0