算法设计与分析试题(C)
- 格式：doc
- 大小：61.16 KB
- 文档页数：2
曲阜师范大学计算机科学学院试题
1 2006级计算机专业2006—2007学年第二学期
《算法设计与分析》期末试题 (C卷)
一、 填空题(10题×2分=20分)
1、()()OfOg等于（ ）。
2、按照渐近阶从低到高的顺序排列下列表达式：
32,,,4,lognnnnn，结果为（ ）。
3、动态规划算法中，通常不同子问题的个数随问题规模呈（ ）级增长。
4、（ ）和（ ）是采用动态规划算法的两个基本要素。
5、（ ）和（ ）是贪心算法的基本要素。
6、（ ）是设计贪心算法的核心问题。
7、装载问题的贪心算法求解中，贪心策略是（ ）。
8、贪心选择性质是指所求问题的整体最优解可以通过一系列（ ）的选择，即贪心选择达到。
9、按照活结点表的组织方式的不同，分支限界法包括（ ）和（ ）两种形式。
10、优化问题主要由两个部分组成（ ）和（ ）。
二、判断题(10题×2分=20分)
1、f=O(f)。
2、递归的两个基本要素是递归方程和约束函数。
3、最优子结构性质是指原问题的最优解包含了其子问题的最优解。
4、直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
5、动态规划算法采用与递归定义一致的自上而下的方式求解子问题。
6、贪心算法并不总能求得问题的整体最优解。
7、满足最优子结构性质必满足贪心选择性质。
8、子集树通常有n！个叶子节点。
9、回溯法的含义是指加剪枝的深度优先展开方法。
10、回溯法中限界函数的目的是剪去得不到最优解的子树。
三、简答题(6题×5分=30分)
1、简述什么是渐近复杂性。
2、简述状态空间树的广度优先展开方法。
3、简述动态规划算法求解问题的一般步骤。
4、简述什么是备忘录方法。 曲阜师范大学计算机科学学院试题
2 5、简述什么是P类判断问题。
6、给出0－1背包问题的数学描述，若m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，给出计算m(i，j)的递归公式。
四、计算题(2题×7分=14分)
1、对于下图所示的有向图，用Dijkstra算法计算从源顶点1到其它顶点间的最短路径，请列表描述出Dijkstra算法的迭代过程。
2、对于下图所示的带权图，给出按照Prim算法构造其最小生成树的过程。
五、算法分析题(2题×8分=16分)
1、设a[0:n-1]是已排序的数组，请改写二分搜索算法，使要搜索的元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。
2、工作分配问题：设有n件工作分配给n个人。将工作i分配给第j个人所需费用为ijc。试设计一个算法，为每一个人分配一件不同的工作，并使总费用达到最小。 1 6
2
3 4
5 6 3 1 5 5
5
6 6 4 2 5 1
2
3 4 10
50
20 10 30 100
60
