.以自底向上的方式计算出最优值
分治法所能解决的问题应具有的关键特征是( )。
.该问题的规模缩小到一定的程度就可以容易地解决
.该问题可以分解为若干个规模较小的相同问题
.利用该问题分解出的子问题的解可以合并为该问题的解
.该问题所分解出的各个子问题是相互独立的
下列关于回溯法的描述不正确的是( )。
.回溯法也称为试探法
.回溯法有“通用解题法”之称
.回溯法是一种能避免不必要搜索的穷举式搜索法
.用回溯法对解空间作深度优先搜索时只能用递归方法实现
常见的两种分支限界法为( )。
广度优先分支限界法与深度优先分支限界法;
队列式(!-!)分支限界法与堆栈式分支限界法;
排列树法与子集树法;
队列式(!-!)分支限界法与优先队列式分支限界法;
二、 填空题
.
' 的渐近性态 .+
,
'
的渐近性态 + +。
一个“好”的算法应具有正确性、 可读性 、 健壮性 和高效率和低存储量需求
等特性。
算法的时间复杂性函数表示为 C=F(N,I,A) ,分析算法复杂性的目的在于比较 求
解同意问题的两个不同算法的效率 的效率。
构成递归式的两个基本要素是 递归的边界条件 和 递归的定义 。
单源最短路径问题可用 分支限界法 和 贪心算法 求解。
用分治法实现快速排序算法时,最好情况下的时间复杂性为 ,最坏情况
下的时间复杂性为 ,该算法所需的时间与 运行时间 和 划分
两方面因素有关。
'* 背包问题的解空间树为 完全二叉 树; 后问题的解空间树为 排列 树;
常见的分支限界法有队列式( !-! )分支限界法 和优先队列式分支限界法。
& 回溯法搜索解空间树时常用的两种剪枝函数为 约束函数 和 剪枝函数 。
' 分支限界法解最大团问题时,活结点表的组织形式是 最大堆 ;分支限界法解单
源最短路径问题时,活结点表的组织形式是 最小堆 。
三、 算法填空题
1. 递归求解 Hanoi 塔问题/阶乘问题。
例 1 :阶乘函数 n!
阶乘的非递归方式定义:
试写出阶乖的递归式及算法。