suanfafenxixxA.doc

院系：_ 专业：_ 班级：_ 学号：_ 姓名：_山 西 师 范 大 学 20072008 学 年 第 一 学 期 期 末 考 试 试 题 （卷）密 封 线 密 封 线 以 内 不 准 作 任 何 标 记 密 封 线山西师范大学期末考试试题（卷）20072008学年第一学期院系：_数计学院_ 专业：_信息_ 考试科目：_算法分析与设计_ 试卷号： A 卷题 号一二三四五六七八总分分 数评卷人复查人一. 选择题（每空2分，共20分）。1. 分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（ ）。A求解目标不同，搜索方式相同B求解目标不同，搜索方式也不同C求解目标相同，搜索方式不同D求解目标相同，搜索方式也相同2. 回溯法在解空间树T上的搜索方式是（ ）。A深度优先 B广度优先C最小耗费优先 D活结点优先3. 回溯算法和分支限界法的问题的解空间树不会是（ ）。A有序树B子集树C排列树D无序树4. （ ）能够求得问题的解，但却无法有效地判定解的正确性。A数值概率算法 B蒙特卡罗算法C拉斯维加斯算法D舍伍得算法5. 下面算法实现的是素数测试，该方法使用的数学原理是（ ）。A费尔马小定理 B费尔马定理CWilson定理D二次探测定理6. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（ ）之外都是最常见的方式。A队列式分支限界法 B优先队列式分支限界法C栈式分支限界法 DFIFO分支限界法7. 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（ ）。 An!B2nC2n+1-1D8. 对于含有n个元素的排列树问题，最坏情况下计算时间复杂性为（ ）。A2n+1-1BCn!D2n9. 设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时有上界g（N），记作f（N）=O（g（N），即f（N）的阶（ ）g（N）的阶。A不高于B不低于C等价于D逼近10. 以下关于判定问题难易处理的叙述中正确的是（ ）。A可以由多项式时间算法求解的问题是难处理的B需要超过多项式时间算法求解的问题是易处理的C可以由多项式时间算法求解的问题是易处理的D需要超过多项式时间算法求解的问题是不能处理的二. 填空题（每空2分，共20分）11. 算法应满足的性质有 、 、 和 四个性质。12. 一个直接或间接调用自身的算法称为 。13. 设有一段程序A时间代价为T1(n)O(f1(n)，但它的时间单位不是最基本的，而以某子程序的执行代价为单位来考虑，这个子程序每次调用的时间代价为T2(n)O(f2(n)，则这段程序A的实际时间代价是 。14. 贪心算法求解的问题一般具有 和贪心选择两个重要性质。15. 设n为自变量，a,m为常数，按照O渐近阶从低到高对a，n2，nm，n ，nn排序为 。16. 回溯法对解空间树的搜索方式是 。17. 分治法的基本思想是将一个规模为n的问题分解为与原问题相同的k个规模较小且_的子问题。三. 简答题（共20分，每题5分）。18. 算法的定义，并比较算法和程序的异同。19. 比较动态规划算法和分支算法的异同。20. 简述动态规划算法的基本要素。21. 简述分支限界法的基本思想。四. 算法应用题（共20分，每题10分）22. 证明：哈夫曼算法的正确性。23. Dijkstra算法应用（如下图）（1） 算法的基本思路； （2） 用Djikstra算法计算从源顶点1到其他顶点的最短路径的迭代过程。12543101005030102060五. 算法设计题（共30分，每题15分）。24. 使用分治策略是先快速排序算法（要求写出算法思想）。25. 实现基于的回溯算法的0/1背包问题（要求写出算法思想）。山 西 师 范 大 学 20072008 学 年 第 二 学 期 期 末 考 试 试 题 （卷）密 封 线 密 封 线 以 内 不 准 作 任 何 标 记 密 封 线山西师范大学期末考试答案纸20072008学年第一学期院系：_数计学院 _ 专业：_ 信息 _ 考试科目：_算法分析与设计_ 试卷号： A 卷一. 选择题（每空1分，共20分）。1、B 2、A 3、D 4、B 5、C 6、C 7、B 8、A 9、A 10、C二. 填空题（每空2分，共20分）11、输入、输出、确定性、有限性12、递归13、T(n)=O(f1(n)f2(n)14、最优子结构15、 a ， n，nn，n2，nm 16、深度优先方式17、相互独立三. 略四. 算法应用题（共20分，每题10分）23、用S表示贪心选择不断扩充的顶点集合，u代表每次选择的顶点，数组disti代表当前从源到顶点i最短特殊路径长度。（写出思路评分标准：5分，说明变量评分标准：5分）迭代S udist2dist3dist4dist5初始1-