华南农业大学期末考试试卷（A卷）
2008学年第一学期
考试类型：（闭卷）学号题号得分评阅人一姓名二三
考试科目：
考试时间：
算法分析与设计
120分钟
年级专业四总分
一、选择题（20分，每题2分）
1下述表达不正确的是。2
A．
22的渐进表达式上界函数是O2
B．
222
的渐进表达式下界函数是Ω2
C．log
3的渐进表达式上界函数是Olog
D．log
3的渐进表达式下界函数是Ω
32当输入规模为
时，算法增长率最大的是。
2
A．5B．20log2C．2
D．3
log33T（
）表示当输入规模为
时的算法效率，以下算法效率最优的是A．T（
）T（
1）1，T（1）1B．T（
）2
2C．T（
）T（
2）1，T（1）1D．T（
）3
log2
4。
在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是。kA．（41）3B．2k3C．4kD．2k5在寻找
个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对
个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准B．取子序列的第一个元素作为划分基准C．用中位数的中位数方法寻找划分基准D．以上皆可行。但不同方法，算法复杂度上界可能不同
1
f6
有9个村庄，其坐标位置如下表所示：ix（i）y（i）111222333444555666777888999
现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。A．（45，0）B．（45，45）C．（5，5）D．（5，0）7
个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下说法不正确？A．让水桶大的人先打水，可以使得每个人排队时间之和最小B．让水桶小的人先打水，可以使得每个人排队时间之和最小C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，
个人都打完水，按照什么顺序其实都一样8分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。A．问题规模相同，问题性质相同B．问题规模相同，问题性质不同C．问题规模不同，问题性质相同D．问题规模不同，问题性质不同9对布线问题，以下是不正确描述。A．布线问题的解空间是一个图B．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定C．采用广度优先的标号法找到从起点到终r