华南农业大学期末考试试卷（A卷） 2008学年第一学期 考试科目： 算法分析与设计
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号 得分 评阅人 一 二 三 四 总分 一、选择题（20分，每题2分）
1. 下述表达不正确的是 。D
A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3)
2. 当输入规模为n时，算法增长率最大的是 。A A．5n B．20log2n C．2n2 D．3nlog3n
3. T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是 。C A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n
4. 在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨
牌的个数是 。A A．（4k – 1）/3 B．2k /3 C．4k D．2k
5. 在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法
对n个元素进行划分，应如何选择划分基准？下面 答案解释最合理。D A．随机选择一个元素作为划分基准
B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准
D．以上皆可行。但不同方法，算法复杂度上界可能不同
6. 有9个村庄，其坐标位置如下表所示： i x（i） y（i） 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。C A．（4.5，0） B．（4.5，4.5） C．（5，5） D．（5，0）
7. n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，
水流恒定。如下 说法不正确？A
A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小
C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水 D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样
8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分
别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。C
A．问题规模相同，问题性质相同 B．问题规模相同，问题性质不同 C．问题规模不同，问题性质相同 D．问题规模不同，问题性质不同
9. 对布线问题，以下 是不正确描述。C A．布线问题的解空间是一个图
B．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定
C．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的
D．采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件
10. 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。B
nA．n!
B．2 C．2
nn+1
-1 D．
?n!/i!
i?1二、填空题（10分，每题2分）
1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 复杂性和空间复杂性之分。
参考解答：时间
2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 。 参考解答：相同
3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ ），在最坏情况下，搜索的时间复杂性为O（ ）。 参考解答：1 logn
4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：
n?2?O(1) T(n)??2T(n/2)?O(n)n?2?解得此递归方可得T(n)= O（ ）。 参考解答：nlogn
5、动态规划算法有一个变形方法 。这种方法不同于动态规划算法“自底向
上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。 参考解答：备忘录方法
三、简答题（40分，每题8分）
1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：
2n参考解答：10
33nlognnlognn!nlognn22nn23nnnn!103 nn
logn
2、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表：
（1） 每个选手必须与其他选手各赛一次； （2） 每个选手一天只能赛一次； （3） 循环赛一共进行n – 1天。
请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。 参考解答：
1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 3、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i)表示结束租用时刻，10个客户的申请如下表所示：
i s(i) f(i) 1 0 6 2 3 5 3 1 4 4 5 9 5 3 8 6 5 7 7 11 13 8 8 12 9 8 11 10 6 10 同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。
参考解答：将这10位客户的申请按照结束时间f(i)递增排序，如下表：
i s(i) f(i) 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 11 13 1） 选择申请1（1,4）
2） 依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到
所有申请检查完毕。申请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分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：
0i?j??m[i,j]??
min{m[i,k]?m[k?1,j]?pi?1pkpj}i?j??i?k?j其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi-1为矩阵Ai的行，pi为矩阵Ai的列。现有四个矩阵，其中各矩阵维数分别为：
A1 50?10 p 0? p 1 A2 10?40 p 1? p 2 A3 40?30 p 2? p 3 A4 30?5 p 3? p 4 请根据以上的递归关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。
参考解答：
?m[1][1]?m[2][4]?p0p1p4?0?8000?50?10?5?10500?m[1][4]?min?m[1][2]?m[3][4]?p0p2p4?20000?6000?50?40?5?36000?m[1][3]?m[4][4]?ppp?27000?0?50?30?5?34500
034??10500
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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？
参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。
四、算法设计题（30分，前三题每题8分，最后一题6分）
1、【最优服务次序问题】（8分）—— 提示：此题可采用贪心算法实现
问题描述：设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti，1<=i<=n。
应该如何安排n个顾客的服务次序才能使平均等待时间达到最小？（平均等待时间是n个顾客等待服务时间的总和除以n）。
参考解答：贪心策略：最短服务时间优先。
1算法设计与分析课程期末试卷A卷（含答案）
