号 位 座 别 性 名 姓 号 学 师 教 课 任 级 年 业 专 院 学 湖南师范大学 2006 —2007 学年 04 级期末课程 计算机算法基础 考核试题参考答案及评分细则 课程代码： 考核方式: 闭卷 考试时量：120 分钟 试卷类型：C 一、填空题（每题 1 分，共 40 分） 1、 解决问题的一种方法或一个过程、 由若干条指令组成的有穷序列、 输入、 输出、 确定性、 有限性。 2、需要时间的量、 要解的问题的规模、 算法的输入、 算法本身的函数。 3、上界、 O( gCN ）、 下界、  (gCN ) 4、复杂性最低 5、直接或间接地调用身、 使用函数自身定义、 非递归定的 6、 ( nO log n ) 7、a、排列树、 子集树、 a、n！、 )!(n b、 n2 、 2 1 n 1 、 )2( n 8、最优子结构、 计算重要性 9、系统性、 跳跃性、 深度优先用约束函数在扩展结点处剪去不满足约束的子树、 用限界函数剪去不能得到最优解的子树、 剪枝函数、 递归回溯、 选代回溯 10、队列式（FIFO）分支限界法，优先队列式分支限界法。 11、完全不同的效果。 二、判断题 1、（√）、 2、（√）、 3、（×） 4、（×） 三、简答题 1、因为分治法对原问题分小之后的子问题与原问题在特性上保持一致，只是规模 缩小，这正好符合递归函数的性质。……………………………………………………… 5 分 2、 ① 针对所给问题，定义问题的解空间……………………………………………………1 分 ② 确定易于搜索的解空间结构……………………………………………………………1 分 ③ 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索……3 分 3、都是在问题的状态空间树上搜索解，但求解目标不同；回溯法只通过约束条件，而分支限界 法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索………………………2 分 回溯法采用深度优先策略，而分支限界法采用先广后深的策略…………………………2 分 4、分支：剪去不何能产生最优答案结点………………………………………………………2 分 限界：包括上界函数 U 和下界函数 )(* xC ………………………………………………2 分 所有 UxC )(* 的结点被杀死 第 1 页共 2 页 5、活结点：被激活后还未完全生成其儿子结点的结点……………………2 分 扩展结点：当前正在生成其儿子结点的结点……………………………2 分 死结点：已生成完其儿子结点的结点……………………………………1 分 6、① 针对所给问题，定义问题的解空间………………………………… 1 分 ② 定义上界和下界……………………………………………………… 2 分 ③ 以先广后深的方式搜索状态空间树，并且在搜索过程中用剪枝函数避免 无效搜索……………………………………………………………… 2 分 7、分治法、动态规划、贪心法、回溯法、分支限界法…………… 每答 1 分 四、计算题 1、（1，1，0，0，1）、（1，0，1，1）、（0，0，1，0，0，1） 分别对应于：5+10+15=30 5+12+13=30 12+18=30……………3 分 实际生成的状态空间树………………………………………………… 7 分 2、最优方案是每年均投资于 A 项目………………………………………5 分 三年末的最大利润为 440 万元…………………………………………5 分 第 2 页共 2 页