一、问答题?/p>
30
分)
?/p>
1
.什么是最坏情况时间复杂性?什么是平均情况时间复杂性?
答:最坏情况时间复杂性:
平均情况时间复杂性:
I*
?/p>
DN
中使
T(N, I*)
达到
Tmax(N)
的合法输入;
P(I)
是在算法的应用中出现输入
I
的概?/p>
2
.什么是递归算法?什么是递归函数?/p>
答:
?/p>
1
)递归算法
:
直接或间接地调用自身的算法;
?/p>
2
)递归函数
:
用函数自身给出定义的函数?/p>
3
.递归函数的二要素是什么?
答:
?/p>
1
)边界条件(
2
)递归方程
4
.分治法的设计思想是什么?
答:将一个规模为
n
的问题分解为
k
个规模较小的子问?/p>
,
这些子问题相互独立且与原问题
相同?/p>
5
.什么叫问题的最优子结构性质?/p>
答:一个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质?/p>
6
.动态规划基本步骤是什么?
答:
?/p>
1
)找出最优解的性质,并刻划其结构特?/p>
;
?/p>
2
)递归地定义最优?/p>
;
?/p>
3
)以自底向上的方式计算出最优?/p>
;(4)
根据计算最优值时得到的信息,构造最优解?/p>
7
.动态规划算法的基本要素是什么?举例说明一些可以用动态规划算法解决的问题?/p>
答:
?/p>
1
)最优子结构性质和子问题重叠性质是动态规划算法的基本要素
?/p>
2
)矩阵连乘问题,建立递归关系,求最优解?/p>
0-1
背包问题?/p>
8
.说明分治法与动态规划法的相同点和不同之处?
答:
同:
基本思想都是将待求解问题分解成若干个子问题先求解子问题,
然后从这些子问题
的解得到原问题的解;
异:
?/p>
1
)适合于用动态规划法求解的问题,经分解得到的子问题往往不是相互独立的?/p>
若用分治法解这类问题?/p>
则分解得到的子问题数目太多,
以至于最后解决原问题需要消耗指
数时间;
?/p>
2
?/p>
不同子问题的数目常常只有多项式量级,
在用分治法求解时?/p>
有些子问题被?/p>
复计算了许多次。动态规划法保存已解决的子问题的答案,在需要时再找到已得到的答案,
可以避免大量重复计算,从而得到多项式时间算法?/p>
9
.贪心算法的两个重要要素是什么?举例说明一些可以用贪心算法解决的问题?/p>
答:
?/p>
1
)贪心选择性质和最优子结构性质?/p>
?/p>
2
)背包问题,单源最短路径,最小生成树问题等?/p>
10
.什么叫贪心选择性质?/p>
答:
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择?/p>
即贪?/p>
选择来达到?/p>
11
.贪心算法与动态规划算法的的相同点和不同之处?
答:同:贪心算法和动态规划算法都要求问题具有最优子结构性质
异:
贪心具有贪心选择性质?/p>
这是贪心算法可行的第一个基本要素,
也是贪心算法与动
态规划算法的主要区别?/p>
12
.背包问题与
0
?/p>
1
背包问题有何区别?/p>
答:背包问题可以用贪心算法求解,?/p>
0-1
背包问题不能用贪心算法求解?/p>
13
.回溯法与分支限界法之间的相同点是什么?不同之处在哪些方面?
答:同:他们同是在问题的解空间树上搜索问题解的算法;
异:
?/p>
1
)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分
)
,
(
max
max
I
N
T
(N)
T
N
D
I
?/p>
?/p>
)
,
(
max
1
I
N
e
t
k
i
i
i
D
I
N
?/p>
?/p>
?/p>
?/p>
)
,
(
*
1
I
N
e
t
k
i
i
i
?/p>
?/p>
?/p>
)
,
(
*
I
N
T
?/p>
?/p>
?/p>
?
N
D
I
I
N
T
I
P
(N)
T
)
,
(
)
(
avg
?/p>
?/p>
?/p>
?/p>
?/p>
N
D
I
k
i
i
i
I
N
e
t
I
P
)
,
(
)
(
1