201401批次考试算法设计分析C卷

1、201401批次考试算法设计分析 C卷题号一二四五六合计已做/题量10 / 103 / 50 / 50 / 20 / 20 / 413 / 28得分/分值0 / 300 / 200 / 100 / 100 / 100 / 200 / 100考试批次：201302批次考试课程：算法设计分析一、单项选择题（共10题、总分30分）1. 计算机算法指的是（）。（本题分数：3分。）A、计算方法厂 B、排序方法備C、解决问题的方法和过程厂 D 调度方法2. 多阶段决策问题，就是要在可以选择的那些策略中间 ，选取一个（）策略，使在预定的标准下达到最好的效果。（本题分数：3分。）A 最优B、最差C、平衡D 任

2、意）。（本题分数：3分。）3. 快速排序法的基本思想是对输入的子数组按以下三个步骤进行排序（A、分解，合并，递归求解 厂 B、合并，递归求解，分解C、递归求解，分解，合并D分解，递归求解，合并4. 与分治法不同的是，适合于用动态规划求解的问题（）（本题分数：3分。）A、经分解得到子问题往往不是互相独立的经分解得到子问题往往是互相独立的经分解得到子问题往往是互相交叉的经分解得到子问题往往是任意的3分。）回溯法分支限界法C、回溯法和分支限界法5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）（本题分数:D 回溯法求解子集树问题本题分数：3分。）6. 阶乘函数用递归

3、定义Public static int factorial(int n) if(n=O) return 1;return () ;(n*factorial(n)n*factorial(n-1)n*factorial(n-2)n*factorial(n+1)（）（本题分数：3分。）7. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比:A、效果一样动态规划效果好B、备忘录方法效果好无法判断哪个效果好（本题A、子问题的可求解性8. 能够用动态规划解决的问题还有一个显著特征（）这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不

4、具备优势。分数：3分。）B、子问题的独立性C、子问题的可合并性子问题的重叠性9. 在任何一个2k X 2k的棋盘覆盖中，用到的 L型骨牌个数恰为（）。（本题分数：3分。）kA (4 -1)/3(4 k-1)/2c、(2 k-1)/3(2 k-1)/210.动态规划的时间复杂度为（）（本题分数：3分。）O(n)0(n!)O(n2)3D O(n )Top（）。（本题分数：4分。）二、判断题 （共5题、总分20分）1. 对于难于找到从边界到解的全过程的情况，如果把问题推进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适A、正确B、错误2. 要想在电脑上扩大所处理问题的规模，有效的途径是降低

5、算法的计算复杂度（）（本题分数：4分。）A、正确B、错误3. 快速排序算法是基于贪心策略的一个算法（）。（本题分数：4分。）A、正确.B、错误4. 分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。（）（ 本题分数：4分。）A、正确B、错误5. 问题可以分解为若干个规模较小的相同问题，即称该问题具有最优子结构性质（）（ 本题分数：4分。） A、正确B、错误三、填空题（共5题、总分10分）1. 回溯法使用 1方法搜索树结构，而分支限界法一般用2 方法来搜索这些树。（本题分数：2分。）答：深度优先广度优先2. 对每一个字符规定一个 0, 1串作为其代码，并要求任一字符的代码都不是其他字

6、符代码的前缀，这种编码称为1（本题分数：2分。）答：前缀码3. 下面程序段的时间复杂度是：1 for （i=0; in; i+） for （j=0; jm; j+） Aij=0;（本题分数：2分。）答：4. 数据的基本单位称为1（本题分数：2分。）答：数据元素5. 上界函数 bound计算结点所相应价值的上界。private static double bound （int i） /计算结点所相应价值的上界double cleft = c-cw;/剩余容量double b = cp;/价值上界/以物品单位重量价值递减序装填剩余容量while （i=n & wiv=cleft）cleft -=

7、wi; b += pi;i+; /装填剩余容量装满背包if （i=n）1;return b; （本题分数：2分。）答：b += pi/wi*cleft四、改错题（共2题、总分10分）1. 在一个贪心算法中，我们所做的总是当前最佳的选择（）。（本题分数：5分。）答：对2. 拉斯维加斯算法可以得到求解问题的正确解，但可能找不到解（）（本题分数：5分。）答：对Top五、简答题 （共2题、总分10分）1. 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大？（本题分数：5分。）答：n=152. 描述Dijkstra 算法的基本思想。（本题分数：5分。）答：D

8、ijkstra算法的迭代过程迭代 S u dist1 dist2 dist3 dist4 初始0 - 10 30 100 1 0，1 1 10 60 30 100 2 0，1，3 3 10 50 30 90 3 0，1，3，2 2 10 50 30 60 4 0，1，3, 2，4 4 10Top50 30 60六、问答题 （共4题、总分20分）1. 试简述合并排序算法的基本思想？（本题分数：5分。）答：合并排序算法是用分治策略实现对n个元素进行排序的算法，其基本思想是（1）将待排序的元素分成大小大致相同的2个子集合；（2）分别对2个子集合进行排序；（3 ）最终将排好序的子集合合并成为所要求的排

9、好序的集合。2. 用贪心算法思想求解如下连续背包问题：给定一个承载量为 20的背包和3个物品，3个物品重量分别为 w1=18, w2=15, w3=10其价值分别为v1=25，v2=24，v3=15。每件物品可取数量为 xi （0xi 1），求背包装满 情况下物品的最大价值。（本题分数：5分。）解：3种物品单价分别为：25/18、24/15、 15/10即第二种物品单价最高，且w2=15 V20,应先取它完全放入背包，可取数量为x2=1;单价次高的为第三种物品，由于背包余下载重为：20- w2=20 15=5，可取第三种物品数量为 x3=5/10=0.5 ;此时背包已经装满，因此第一种物品可取数量为x仁0。得到最优解：(xl, x2, x3) = ( 0, 1, 0.5);此时，背包内物品总价值最大，为 wmax = 0X 25+1X 24+0.5 X 15=31.53. 简述分支限界法在问题的解空间树搜索策略？ ( 本题分数： 5 分。 )答： 分支限界法采用宽度优先的方式搜索解空间树，它将活结点存放在一个特殊的表中。其策略是：在扩展结点处，先生成其所有的儿子结点,将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。此后，从活结点表中按照一定的规则取出一个结点作为当前扩展结点。并