《算法设计与分析》试题

1、()()()()()()()()()()算法设计与分析期末考试试题( A 卷、选择题：试题说明：本题包含 12 个小题，占24 分；请将正确答案填写在题目左侧的括号内。1、 分支限界法与回溯法都是在问题的解空间树 T 上搜索问题的解，二者(。A.求解目标不同，搜索方式相同B.求解目标不同，搜索方式也不同C.求解目标相同，搜索方式不同D.求解目标相同，搜索方式也相同2、 回溯法在解空间树 T 上的搜索方式是( 。A.深度优先B,广度优先C.最小耗费优先D,活结点优先3、 回溯算法和分支限界法的问题的解空间树不会是( 。A.有序树B.子集树C.排列树D.无序树4、 在对问题的解空间树进行搜索的方法

2、中， 一个活结点最多有一次机会成为活结点的是(。A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集树问题)5、从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除( 之外都是最常见的方式。A.队列式分支限界法B .优先队列式分支限界法C.栈式分支限界法D. FIFO分支限界法6、 概率算法是一种非确定性地选择下一计算步骤的方法， 力图消除问题复杂性与具体实例间的关联，以下算法暗中适合于求解问题近似解的是( 。A.数值概率算法B.蒙特卡罗算法C.拉斯维加斯算法D.舍伍得算法7、 ( 能够求得问题的解，但却无法有效地判定解的正确性。A.数值概率算法B.蒙特卡罗算法C

3、.拉斯维加斯算法D.舍伍得算法8、 下面算法实现的是素数测试，该方法使用的数学原理是( 。A.费尔马小定理B.费尔马定理C. Wilson定理D.二次探测定理9、 以下关于判定问题难易处理的叙述中正确的是( 。A.可以由多项式时间算法求解的问题是难处理的B.需要超过多项式时间算法求解的问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的10、 设f (N)、g (N)是定义在正数集上的正函数，如果存在正的常数 C和自然数N。， 使得当NRN。时有f(N) < Cg (N),则称函数f(N)当N充分大时有上界g (N),记彳f (N)

4、=O (g (N),即 f (N)的阶()g (N)的阶。A.不高于B.不低于C.等价于D.逼近11、 对于含有 n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为( 。A n!B 2nnC 2n+1-1dn!/ i!i112 、对于含有 n 个元素的排列树问题，最坏情况下计算时间复杂性为(nA 2n+1-1B n! /i!i1C n!D 2n二、判断题：试题说明：本题包含 8 个小题，占16 分；请将正确答案填写在题目左侧的括号内。1、2、分支限界法类似于回溯法, 的求解目标是相同的。进行问题复杂性分析时， 个计算模型是随机存取机也是一种在问题的解空间树T上搜索问题解的算法，两者必须首

5、先建立求解问题所用的数学模型，其中比较重要的三RAM、随机存取存储程序机 RAPS和图灵机TM,它们的计3、4、5、6、算能力是等价的，只是计算速度不同。判定树是RAM的一种变形和简化，运用于基于比较的排序算法的复杂性分析，其算 法时间复杂性可用判定树的高度来衡量。已知含有n个元素的某集合 X=X1, X2,，Xn,要判定其中元素的唯一性，可以用判别函数（Xi xj）是否为0进行判定。一个直接或间接地调用自身的算法称为递归算法，而一个使用函数自身给出定义的函数称为递归函数。定义第归函数时可以没有初始值。动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这

6、些子问题的解得到原问题的解，二者采用的都是自底向上的计算方式。7、利用贪心算法求解问题时，往往需要事先把问题集合按照一定原则进行排序, 安排问题即按活动结束时间的非减序进行排列的。饿活动8、使用回溯法搜索问题的解空间树时，按照深度优先方式进行搜索，其间不受其他条件限制。三、填空题:试题说明：本题包含5个小题，占20分，每空1分;并且具有(）、请将正确答案填写在题目要求的位置。1、以下是对x, v, z三个数进行升序排序的一棵判定树，请在方框中填写相应的结果。2、算法是由若干条指令组成的有序序列, 的性质。）以及正确性简单性等。3、评价算法的标准包括（L型骨牌填充。4、下面是棋盘覆盖的分治策略算

7、法，请按该算法将左图特殊棋盘进行 void ChessBoard(int tr, int tc, int dr, int dc, int size) if (size = = 1) return;int t = titl +;s = size / 2;if (dr <tr + s && dc < tc + s) ChessBoard(tr, tc, dr, dc, s); else Boardtr+s-1tc+s-1 = t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s); if (dr <tr + s && dc

8、>= tc + s) ChessBoard(tr, tc+s, dr, dc, s); else Boardtr+s-1tc+s = t;ChessBoard(tr, tc+s, tr+s-1, tc+s, s); if (dr >= tr + s && dc < tc + s) ChessBoard(tr+s, tc, dr, dc, s); else Boardtr+stc+s-1 = t;ChessBoard(tr+s, tc, tr+s, tc+s-1, s); if (dr >= tr + s && dc >= tc +

9、s) ChessBoard(tr+s, tc+s, dr, dc, s); else Boardtr+stc+s = t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s); 其中，tile为全局变量，初始值为0。由此算法可知，覆盖一个2kx 2k的特殊棋盘所需要的L型骨牌的个数为()，算法时间复杂性T (k)=()。5、若一个最优化问题的最优值为c*,求解该问题的一个近似算法所求的的近似最优解相应的目标函数值为c,则将该近似算法的性能比定义为4=()。四、算法理解题(占24分)：1、依据优先队列式分支限界法，求下图中从 s点到t点的单源最短路径，请画出求得最优解的解空

10、间树。要 求中间被舍弃的结点用X标记，获得中间解的结点用单圆圈。框起，最优解用双圆圈框起。2、已知在如下所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。ba3、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表:每个选手必须与其他n-1名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。（1）如果n=2k,循环赛最少需要进行（）天；如果nw2k,循环赛最少需要进行（）天。（2）当n=23=8时，请画出循环赛日程表：4、请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法