《计算机算法基础》试题及答案「完整版」

《计算机算法根底》试题及答案「完整版」1、算法是指解决问题的一种方法或一个过程，更严格地讲，算法是由假设干条指令组成的有穷序列，且满足下述4条性质：输入、输出、确定性、有限性。2、算法的时间复杂性是指需要时间的量，它依赖于求解问题的要解的问题的规模、算法的输入、算法本身的函数。4、选择算法的一个重要准那么是复杂性最低。5、一个直接或间接地调用身的算法称为递归算法，一个使用函数自身定义的函数称为递归函数，每个递归函数都必须有非递归定的的初始值。6、关于N个字符的哈夫曼算法的计算时间为O（nlogn）。7、回溯法解题时常遇到的两类典型解空间是树：a：排列、树b：子集树，假设问题有N个元素，其中树通常有a2?个叶结点，其结点总个数为n！2^(n+1)-1，遍历它的任何算法均需Ω（n！）Ω（2?）的计算时间。8、一个问题能用动态规划算法求解的两个重要特征是最优子构造和计算重要性。9、回溯法是一个既带有系统性又带有跳跃性的搜索算法。它按照深度优先用约束函数在扩展结点处剪去不满足约束的子树、用限界函数剪去不能得到最优解的子树优先的策略对空间树进展搜索，通常采用如下两种策略来防止无效搜索，提高回溯法的搜索效，其一是剪枝函数，其二是递归回溯，这两类函数统称为选代回溯。10、分支限界法最常见的两种方式分别是队列式（FIFO）分支限界法和优先队列式分支限界法。

11、概率算法的一个根本特征是对所求解问题的同一实例用同一概率算法，求解两次可能得到完全不同的效果。1、贪心算法的核心是排序（×）2、贪心算法对所有问题都能得到整体最优解（√）3、0/1背包问题和背包问题都可以用贪心法求解（×）4、概率算法在执行过程中每一计算步骤都是确定的（×）1、为什么分治法与递归像一对孪生兄弟，经常同时应用在算法设计中？答：因为分治法对原问题分小之后的子问题与原问题在特性上保持一致，只是规模缩小，这正好符合递归函数的性质。5分2、表达回溯法解题通常的三个步骤。①针对所给问题，定义问题的解空间②确定易于搜索的解空间构造③以深度优先的方式并且在搜索过程中用剪枝函数防止无效搜索3分3、表达回溯法与分支限界算法的异同之处。都是在问题的过约束条件，而分支限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，回溯法采用深度优先策略，而分支限界法状态空间树上搜索解，但求解目标不同；回溯法只通采用先广后深的策略。4、表达分支限界算法的分支和限界的涵意。分支：剪去不何能产生最优答案结点限界：包括上界函数U和下界函数C*(X所有C*(X)>U的结点被杀死5、解释什么是活结点，扩展结点，死结点？

活结点：被激活后还未完全生成其儿子结点的结点扩展结点：当前正在生成其儿子结点的结点死结点：已生成完其儿子结点的结点6、说出优先队列式分支限界法解题的详细步骤。①针对所给问题，定义问题的解空间②定义上界和下界③以先广后深的方式搜索状态空间树，并且在搜索过程中用剪枝函数防止无效搜索7、说出教材中所介绍的五种主要算法，并对每一种算法举出一个典型。求解的例子（不必写出每种详细解法过程）。分治法、动态规划、贪心法、回溯法、分支限界法（1，1，0，0，1）、（1，0，1，1）、（0，0，1，0，0，1）分别对应于：5+10+15=305+12+13=3012+18=30实际生成的状态空间树2、某公司订购4箱海