《算法设计与分析》试习题

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栈式分支限界法 DFIFO分支限界法（ ） 6、概率算法是一种非确定性地选择下一计算步骤的方法，力图消除问题复杂性与具体实例间的关联，以下算法暗中适合于求解问题近似解的是（ ）。A数值概率算法 B蒙特卡罗算法C拉斯维加斯算法D舍伍得算法（ ） 7、（ ）能够求得问题的解，但却无法有效地判定解的正确性。A数值概率算法 B蒙特卡罗算法C拉斯维加斯算法D舍伍得算法（ ） 8、

3、下面算法实现的是素数测试，该方法使用的数学原理是（ ）。A费尔马小定理 B费尔马定理CWilson定理D二次探测定理（ ） 9、以下关于判定问题难易处理的叙述中正确的是（ ）。A可以由多项式时间算法求解的问题是难处理的B需要超过多项式时间算法求解的问题是易处理的C可以由多项式时间算法求解的问题是易处理的D需要超过多项式时间算法求解的问题是不能处理的（ ）10、设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时有上界g（N），记作f（N）=O（g（N），即f（N）的阶（ ）g（N）的阶。A不高于B不低于C

4、等价于D逼近（ ）11、对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（ ）。An!B2nC2n+1-1D（ ）12、对于含有n个元素的排列树问题，最坏情况下计算时间复杂性为（ ）。A2n+1-1BCn!D2n二、判断题：试题说明：本题包含8个小题，占16分； 请将正确答案填写在题目左侧的括号内。（ ） 1、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的求解目标是相同的。（ ） 2、进行问题复杂性分析时，必须首先建立求解问题所用的数学模型，其中比较重要的三个计算模型是随机存取机RAM、随机存取存储程序机RAPS和图灵机TM，它们的计算能力是等价的，

5、只是计算速度不同。（ ） 3、判定树是RAM的一种变形和简化，运用于基于比较的排序算法的复杂性分析，其算法时间复杂性可用判定树的高度来衡量。（ ） 4、已知含有n个元素的某集合X=x1，x2，xn，要判定其中元素的唯一性，可以用判别函数是否为0进行判定。（ ） 5、一个直接或间接地调用自身的算法称为递归算法，而一个使用函数自身给出定义的函数称为递归函数。定义第归函数时可以没有初始值。（ ） 6、动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，二者采用的都是自底向上的计算方式。（ ） 7、利用贪心算法求解问题时，往往需要事先

6、把问题集合按照一定原则进行排序，饿活动安排问题即按活动结束时间的非减序进行排列的。（ ） 8、使用回溯法搜索问题的解空间树时，按照深度优先方式进行搜索，其间不受其他条件限制。三、填空题：试题说明：本题包含5个小题，占20分，每空1分； 请将正确答案填写在题目要求的位置。a：ba：ba：ba：ba：b 1、以下是对x，y，z三个数进行升序排序的一棵判定树，请在方框中填写相应的结果。 2、算法是由若干条指令组成的有序序列，并且具有（ ）、（ ）、（ ）和（ ）的性质。 3、评价算法的标准包括（ ）、（ ）以及正确性简单性等。 4、下面是棋盘覆盖的分治策略算法，请按该算法将左图特殊棋盘进行L型骨牌填

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);elseBoardtr+s-1tc+s-1 = t;ChessBoard(tr, tc, tr+s-1, tc+s-1, s);if (dr <tr + s && dc >= tc + s)ChessBo

8、ard(tr, tc+s, dr, dc, s);elseBoardtr+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);elseBoardtr+stc+s-1 = t;ChessBoard(tr+s, tc, tr+s, tc+s-1, s);if (dr >= tr + s && dc >= tc + s)ChessBoard(tr+s, tc+s, dr,

9、 dc, s);elseBoardtr+stc+s = t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s);其中，tile为全局变量，初始值为0。由此算法可知，覆盖一个2k×2k的特殊棋盘所需要的L型骨牌的个数为（ ），算法时间复杂性T（k）=（ ）。 5、若一个最优化问题的最优值为c*，求解该问题的一个近似算法所求的的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为=（ ）。四、算法理解题（占24分）：sta：2b：3c：4u：3d：7e：2f：9g：2h：2q：1k：3i：1j：2l：5m：1r：2p：2o：4n：3 1、依据优先队列式分支

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