- 相关推荐
《计算机算法基础》试题及答案「完整版」
《计算机算法基础》试题及答案【完整版】
一、填空题（每空1分，共35分）
1、算法是指_解决问题的一种方法或一个过程_，更严格地讲，算法是____由若干条指令组成的有穷序列__，且满足下述4条性质：_输入、
输出、 确定性、 有限性 。
2、算法的时间复杂性是指______需要时间的量_____，它依赖于求解问题的 要解的问题的规模、 算法的输入、 算法本身的函数_____。
4、选择算法的一个重要准则是____复杂性最低____。
5、一个___直接或间接地调用身____的算法称为递归算法，一个___使用函数自身定义___的函数称为递归函数，每个递归函数都必须有____非递归定的___的初始值。
6、关于N个字符的哈夫曼算法的计算时间为_____O（nlog n）___。
7、回溯法解题时常遇到的两类典型解空间树是：a：____排列树____、b：___子集树_____，若问题有N个元素，其中树通常有__a __ 2ⁿ __个叶结点，其结点总个数为____n！_2^(n +1)-1___，遍历它的任何算法均需____Ω（n！）__ Ω（2ⁿ）__的计算时间。
8、一个问题能用动态规划算法求解的两个重要特征是_____最优子结构______和_____计算重要性______。
9、回溯法是一个既带有系统性又带有_____跳跃性______的搜索算法。它按照____深度优先用约束函数在扩展结点处剪去不满足约束的子树、用限界函数剪去不能得到最优解的子树_______优先的策略对空间树进行搜索，通常采用如下两种策略来避免无效搜索，提高回溯法的搜索效，其一是_____剪枝函数______，其二是____递归回溯_______，这两类函数统称为______选代回溯_____。
10、分支限界法最常见的两种方式分别是_____ 队列式（FIFO）分支限界法______和_____优先队列式分支限界法______。
11、概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法，求解两次可能得到___完全不同的效果___。
二、判断题（下列各题，你认为正确的，请在题干的括号内打“√”、错误的打“×”，每题2分，共8分）
1、贪心算法的核心是排序（ × ）
2、贪心算法对所有问题都能得到整体最优解（ √ ）
3、0/1背包问题和背包问题都可以用贪心法求解 （ × ）
4、概率算法在执行过程中每一计算步骤都是确定的（ × ）
三、简答题（每小题5分，共35分）
1、为什么分治法与递归像一对孪生兄弟，经常同时应用在算法设计中？
答：因为分治法对原问题分小之后的子问题与原问题在特性上保持一致，只是规模缩小，这正好符合递归函数的性质。5分
2、叙述回溯法解题通常的三个步骤。
① 针对所给问题，定义问题的解空间
② 确定易于搜索的解空间结构
③ 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索3分
3、叙述回溯法与分支限界算法的异同之处。
都是在问题的状态空间树上搜索解，但求解目标不同；回溯法只通过约束条件，而分支限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，回溯法采用深度优先策略，而分支限界法采用先广后深的策略。
4、叙述分支限界算法的分支和限界的涵意。
分支：剪去不何能产生最优答案结点
限界：包括上界函数U和下界函数C*(X
所有C*(X)>U的结点被杀死
5、解释什么是活结点，扩展结点，死结点？
活结点：被激活后还未完全生成其儿子结点的结点
扩展结点：当前正在生成其儿子结点的结点
死结点：已生成完其儿子结点的结点
6、说出优先队列式分支限界法解题的具体步骤。
① 针对所给问题，定义问题的解空间
② 定义上界和下界
③ 以先广后深的方式搜索状态空间树，并且在搜索过程中用剪枝函数避免无效搜索
7、说出教材中所介绍的五种主要算法，并对每一种算法举出一个典型。求解的例子（不必写出每种具体解法过程）。
分治法、动态规划、贪心法、回溯法、分支限界法
四、计算题（每小题10分，共20分）
（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
实际生成的状态空间树
2、某公司订购4箱海鲜品，分配给下属的Ⅰ，Ⅱ，Ⅲ三个门市部，各门市部获得海鲜品后的盈利如表所示。试用动态规划求解，如何分配海鲜品，才能获得最大利润？（要写出详细的步骤）。
【《计算机算法基础》试题及答案「完整版」】相关文章：
《计算机导论》试题及答案完整版04-21
算法分析设计相关试题及答案04-02
微波技术基础试题及答案04-02
最优化理论与算法试题及参考答案04-02
程序设计基础试题及答案04-02
java基础面试题及答案04-05
《园林工程》试题及答案「完整版」04-21
大学《管理学基础》试题及答案04-02
《管理学基础》模拟试题及答案04-01