1、华南农业大学期末考试试卷(A卷)2008学年第一学期考试科目：算法分析与设计考试类型：(闭卷)考试时间： 120分钟学号姓名年级专业题号一二三四总分得分评阅人一、选择题(20分，每题2分)1. 下述表达不正确的是 OA. n72 + 2 n的渐进表达式上界函数是 0(2)B. n72 + 2 n的渐进表达式下界函数是Q (2n)C. logn 3的渐进表达式上界函数是 O(logn)D. logn 3的渐进表达式下界函数是Q (n3)2. 当输入规模为n时，算法增长率最大的是 A. 5nB.20log 2nC. 2n2.3nlog 3n(n)表示当输入规模为n时的算法效率，以下算法效率最优的A
2、. T (n) = T (n1 ) +1, T (1) =1 BT (n)二 2nC. T (n) = T (n/2 ) +1, T (1) =1D . T (n)二 3nlog 2n4.在棋盘覆盖问题中,对于2kX 2k的特殊棋盘(有一个特殊方块)，所需的L型骨牌的个数是kkC . 4 D . 2kkA. (4 - 1 ) /3 B . 2 /35. 在寻找n个元素中第k小元素问题中，若使用快速排序算法思想, 运用分治算法对 n个元素进行划分，应如何选择划分基准下面 答案解释最合理。A. 随机选择一个元素作为划分基准B. 取子序列的第一个元素作为划分基准C. 用中位数的中位数方法寻找划分基准
3、D. 以上皆可行。但不同方法，算法复杂度上界可能不同6. 有9个村庄，其坐标位置如下表所示：i123456789x (i )123456789y (i)123456789现在要盖一所邮局为这 9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。A. （，0）B. （,）C.（5, 5）D.（5, 0）个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 说法不正确A.让水桶大的人先打水，可以使得每个人排队时间之和最小B. 让水桶小的人先打水，可以使得每个人排队时间之和最小C. 让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多 的人打上水
4、D. 若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都 一样8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 0A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D .问题规模不同，问题性质不同9. 对布线问题，以下是不正确描述。A. 布线问题的解空间是一个图B. 可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理， 使得算法简化对边界的判定C. 采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的D. 采
5、用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件10. 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点 数目为。nA. n!B . 2n C . 2n+1-1D .n!/i!i 1答案：DACAD CACCB二、填空题（10分，每题2分）1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存 储器资源上，因此算法的复杂性有 时间复杂性和空间复杂性之 分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同_。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为0(
6、 1 ),在最坏情况下，搜索的 时间复杂性为 0(_logn_)。4、 已知一个分治算法耗费的计算时间T(n) , T(n)满足如下递归方程：解得此递归方可得 T(n)二0 (_nlogn _)。5、 动态规划算法有一个变形方法 _备忘录方法_。这种方法不同于动 态规划算法“自底向上”的填充方向，而是“自顶向下” 的递归方向, 为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。参考解答：1、时间2、相同3、1 logn 4、n log n 5、备忘录方法三、简答题(40分，每题8分)1、(8分)写出下列复杂性函数的偏序关系(即按照渐进阶从低到高排序)：参考解答：1
7、03 log n n log n n2 2n 3n n ! nn2、(8分)现在有8位运动员要进行网球循环赛，要设计一个满足以F要求的比赛日程表:(1 )每个选手必须与其他选手各赛一次;(2) 每个选手一天只能赛一次；(3) 循环赛一共进行n - 1天。请利用分治法的思想，给这 8位运动员设计一个合理的比赛日程 参考解答：12345678214365873412785643218765567812346587214378563412876543213、( 8分)某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示幵始租用时刻，f(i
8、)表示结束租用时刻，10个客户的申请如下表所示：i12345678910s(i03153511886)f(i65498713121110)同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的 需求，并算出针对上表的 10个客户申请，最多可以安排几位客户申请。参考解答：将这10位客户的申请按照结束时间f（i）递增排序，如下表：i12345678910s(i13053568811)f(i45678910111213)1）选择申请1（ 1,4）2）依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有申请检查完毕。申
9、请4（5,7 ）、申请8（8,11 ）、申请 10（ 11,13）3）最后，可以满足：申请 1（ 1,4 ）、申请4（ 5,7 ）、申请8（ 8,11 ）、申请10（ 11,13 ）共4个客户申请。这已经是可以满足的最大客户人数4、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：其中mi，j为计算矩阵连乘 Ai -Aj所需的最少数乘次数，p“为矩阵Ai的行，pi为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：AiAAA501010404030305p 0 p 1p 1 p 2p 2 p 3p 3 p 4请根据以上的递归关系，计算出矩阵连乘积 AAAbA所需要的最少数乘 次数。参考
10、解答:5、（8分）有这样一类特殊 0-1背包问题：可选物品 重量越轻的物品 价值越高n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n为物品个数，c为背包载重量，P表示物品的价值，W表示 物品的重量。请问对于此 0-1 背包问题，应如何选择放进去的物品， 才能使到放进背包的物品总价值最大，能获得的最大总价值多少 参考解答： 因为该 01 背包问题比较特殊，恰好重量越轻的物品价 值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为 2， 3， 4， 5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 =33，为最大值。四、算法设计题
11、（ 30分，前三题每题 8 分，最后一题 6分）1、【最优服务次序问题】 （8分） 提示：此题可采用贪心算法实 现问题描述：设有 n 个顾客同时等待一项服务，顾客 i 需要的服务 时间为 ti ， 1=i1 时，格雷码的长度为 2n ，即共有 2n 个码序列。此时，将问 题一分为二，即上半部分和下半部分。上半部分最高位设为 0，下半 部分最高位设为 1。剩下 n-1 位的格雷码的构造采用递归的思路。评分准则：1）答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出 1 位的格雷码如何处理） ，本题即可得满分；2）说明使用分治算法，但漏边界条件，扣2 分以上；3）其它情况酌情考虑
12、。3、【最长上升子序列问题】 （ 8 分）提示：此题可采用动态规划算法实现对于给定的一个序列(ai,a2,|H，aN), 1 N 1000。我们可以得到一 些递增上升的子序列(ai,ai2,|,aiK)，这里1 ii i2川b N。比如， 对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如 (1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5,8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。 要求写出你设计的算法思想及递推函数的公式表达。参考解答：设f(i)表示：从左向右扫描过来直到以 ai元素结尾 的序列，获得
13、的最长上升子序列的长度，且子序列包含ai元素(1 i n ) o即, f(i)是从f (1)， f (2)到f (i 1)中找最大的一个值，再加1。或者就是1。主要是看ai这个元素能否加入到之前已经获得的 最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度 加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长 度为1o最后，所要求的整个序列的最长公共子序列长度为maxf(i):1=i 二n例如，对于序列：4 2 6 3 1 5 2i1234567array4263152f(i)1122132评分准则：1）答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界设定
14、清晰，本题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不 唯一）2）说明使用动态规划算法，但对递推函数表达错误或含糊，扣2分以上；3）其它情况酌情考虑。4、【骑士问题】（6分）一一提示：此题可采用广度优先搜索算 法实现在一个标准8X8的国际象棋棋盘上，棋盘中有些格子是可能有 障碍物的。已知骑士的初始位置和目标位置，你的任务是计算出骑士 最少需要多少步可以从初始位置到达目标位置，若无法到达目标位 置，输出“ not reachable ”。请用文字或伪代码说明你的算法。注意：骑士只能进行“日”字行对角跳，棋盘上有障碍物的格子 不能到达。图（a）:骑士能进行的“日
15、”字行对角跳，n为骑士当前位置，x为骑士下一步可以跳到的格子图（b）:骑士从初始位置n到目标位置N,最小需要7步的实例。b为棋盘障碍参考解答： 这也是一个搜索的题目，非常类似于书上的“布线问 题”，可参考书上此例。用一个二维数组 board1212 来记录棋盘的状况。为何大小是 12*12 呢棋盘大小 8*8 ，为了减少对周围边界的判断， 在上下左右四边各加上 2 行 2 列做“围墙”（障碍），因此 board 棋盘 的大小 12*12 。有如下几个步骤需要解决：1）障碍格子：将输入的障碍格子填写到 board 当中对应格上，设置为-1；2）起始格子和结束格子：将起始点start和结束点end
16、,这两个点记录下来，在 board 中这两个格子设置为 0；3）围墙：在 8*8 的棋盘外面,上下左右各加 2行2列做围墙,围墙和障碍一样,设置为 -1 ；4）除障碍围墙起始结束格子这些格子特殊对待输入之外,其余格子全部初始化为 0；5）队列初始为空。 队列是用来在骑士做 “日字型”对角跳的时候,候选位置放入队列中的一个辅助的数据结构, 以便于 “广度优 先搜索”。6）从起点开始,将这个位置所能跳的周围8 个位置都检查一下：只要未标记,就标记为前一个位置值加 1,并将该格子位置加 入队列；如果不能标记（比如障碍或围墙等） ,就跳过,继续 检查下一个位置,一共骑士所能跳的 8 个位置。7）取出队列首个位置结点, 又继续检查这个结点周围的 8 个位置,类同上一步，直到找到对终点标记位置8）最后，输出终点所标记的数值（正数） ，就是骑士所需的最少移动步数，若为0表示终点无法标记到， 输出：“not reachable 这样的信息。评分准则：1）答到使用搜索算法，并且说明采用广度优先的搜索策略，算法描述清晰准确，本题即可得满分；2）算法表达含糊或不准确，扣 2 分以上；3）其它情况酌情考虑。
