《算法设计与分析》期末考试试题（A卷）
一、选择题：
试题说明：本题包含12个小题，占24分；
请将正确答案填写在题目左侧的括号内。
（ ） 1、 分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。
A．求解目标不同，搜索方式相同 B．求解目标不同，搜索方式也不同 C．求解目标相同，搜索方式不同 D．求解目标相同，搜索方式也相同
（ ） 2、 回溯法在解空间树T上的搜索方式是（ ）。
（ ） 3、 （ ） 4、 （ ） 5、 （ ） 6、 （ ） 7、 （ ） 8、 （ ） 9、 （ ） 10、 （ ） 11、 （ ）
12、 A．深度优先 B．广度优先 C．最小耗费优先 D．活结点优先
回溯算法和分支限界法的问题的解空间树不会是（ ）。
A．有序树 B．子集树 C．排列树 D．无序树
在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点
的是（ ）。 A．回溯法 B．分支限界法
C．回溯法和分支限界法 D．回溯法求解子集树问题
从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除
（ ）之外都是最常见的方式。 A．队列式分支限界法 B．优先队列式分支限界法 C．栈式分支限界法 D．FIFO分支限界法
概率算法是一种非确定性地选择下一计算步骤的方法，力图消除问题复杂性与具
体实例间的关联，以下算法暗中适合于求解问题近似解的是（ ）。 A．数值概率算法 B．蒙特卡罗算法 C．拉斯维加斯算法 D．舍伍得算法
（ ）能够求得问题的解，但却无法有效地判定解的正确性。
A．数值概率算法 B．蒙特卡罗算法 C．拉斯维加斯算法 D．舍伍得算法
下面算法实现的是素数测试，该方法使用的数学原理是（ ）。
A．费尔马小定理 B．费尔马定理 C．Wilson定理 D．二次探测定理
以下关于判定问题难易处理的叙述中正确的是（ ）。
A．可以由多项式时间算法求解的问题是难处理的 B．需要超过多项式时间算法求解的问题是易处理的 C．可以由多项式时间算法求解的问题是易处理的
D．需要超过多项式时间算法求解的问题是不能处理的
设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数
N0，使得当N≥N0时有f（N）≤Cg（N），则称函数f（N）当N充分大时有上界g（N），记作f（N）=O（g（N）），即f（N）的阶（ ）g（N）的阶。 A．不高于 B．不低于 C．等价于 D．逼近
对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（ ）。
A．n! B．2n
nC．2
n+1
-1 D．
?n!/i!
i?1对于含有n个元素的排列树问题，最坏情况下计算时间复杂性为（ ）。
nA．2
n+1
-1 B．
?n!/i!
i?1C．n!
D．2n
二、判断题：
试题说明：本题包含8个小题，占16分；
请将正确答案填写在题目左侧的括号内。
（ ） 1、 分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，
两者的求解目标是相同的。
（ ） 2、 进行问题复杂性分析时，必须首先建立求解问题所用的数学模型，其中比较重要
的三个计算模型是随机存取机RAM、随机存取存储程序机RAPS和图灵机TM，它们的计算能力是等价的，只是计算速度不同。
（ ） 3、 判定树是RAM的一种变形和简化，运用于基于比较的排序算法的复杂性分析，
其算法时间复杂性可用判定树的高度来衡量。
（ ） 4、 已知含有n个元素的某集合X={x1，x2，…，xn}，要判定其中元素的唯一性，可
以用判别函数
?(xi?xj)是否为0进行判定。
i?j（ ）
5、 一个直接或间接地调用自身的算法称为递归算法，而一个使用函数自身给出定义
的函数称为递归函数。定义第归函数时可以没有初始值。
（ ） 6、 动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，
先求解子问题，然后从这些子问题的解得到原问题的解，二者采用的都是自底向上的计算方式。
（ ） 7、 利用贪心算法求解问题时，往往需要事先把问题集合按照一定原则进行排序，饿
活动安排问题即按活动结束时间的非减序进行排列的。
（ ） 8、 使用回溯法搜索问题的解空间树时，按照深度优先方式进行搜索，其间不受其他
条件限制。
三、填空题：
试题说明：本题包含5个小题，占20分，每空1分； 请将正确答案填写在题目要求的位置。
1、以下是对x，y，z三个数进行升序排序的一棵判定树，请在方框中填写相应的结果。
a：b ≤ ＞ a：b a：b ≤ ＞ ≤ ＞ a：b a：b ≤ ＞ ≤ ＞ 2、算法是由若干条指令组成的有序序列，并且具有（ ）、（ ）、（ ）和（ 的性质。
3、评价算法的标准包括（ ）、（ ）以及正确性简单性等。
4、下面是棋盘覆盖的分治策略算法，请按该算法将左图特殊棋盘进行L型骨牌填充。 void ChessBoard(int tr, int tc, int dr, int dc, int size)
{ if (size = = 1) return; int t = titl ++; ）
s = size / 2;
if (dr
ChessBoard(tr, tc, dr, dc, s); else {
Board[tr+s-1][tc+s-1] = t;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s); }
if (dr
ChessBoard(tr, tc+s, dr, dc, s); else {
Board[tr+s-1][tc+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 {
Board[tr+s][tc+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, dc, s); else {
Board[tr+s][tc+s] = t;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s); }
}
其中，tile为全局变量，初始值为0。
由此算法可知，覆盖一个2k×2k的特殊棋盘所需要的L型骨牌的个数为（ ），算法时间复杂性T
（k）=（ ）。
5、若一个最优化问题的最优值为c*，求解该问题的一个近似算法所求的的近似最优解相应的目标函数值
为c，则将该近似算法的性能比定义为η=（ ）。 四、算法理解题（占24分）：
1、依据优先队列式分支限界法，求下图中从s点到t点的单源最短路径，请画出求得最优解的解空间树。
要求中间被舍弃的结点用×标记，获得中间解的结点用单圆圈○框起，最优解用双圆圈◎框起。
d：7 s
a：2 b：3 c：4 u：3 e：2 f：9 g：2 h：2 i：1 j：2 k：3 q：1 l：5 m：1 n：3 o：4 r：2 p：2 t
2、已知在如下所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确
定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。
a b
3、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：
①每个选手必须与其他n-1名选手比赛各一次； ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。
（1）如果n=2k，循环赛最少需要进行（ ）天； 如果n≠2k，循环赛最少需要进行（ ）天。 （2）当n=23=8时，请画出循环赛日程表：
4、请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法在实际应用中的适用条件。
五、算法设计（占16分）：
说明：任意选择所使用的算法策略；
从下面两个题目中任意选择其中之一，有余力的同学可以全做，全做者将给予一定附加分（不超过16分）；
要求：说明所使用的算法策略；
写出算法实现的主要步骤； 分析算法的时间、空间复杂性。
1、0-1背包问题；
2、旅行售货员问题（即TSP问题）。
《算法设计与分析》试题
