华南农业大学期末考试试卷（A卷）
2008学年第一学期
考试类型：（闭卷）
考试科目：算法分析与设计
考试时间：120分钟
学号
姓名
题号
一
二
得分
评阅人
年级专业
三
四
总分
一、选择题（20分，每题2分）
1下述表达不正确的是
。
A．
222
的渐进表达式上界函数是O2

B．
222
的渐进表达式下界函数是Ω2

C．log
3的渐进表达式上界函数是Olog

D．log
3的渐进表达式下界函数是Ω
3
2当输入规模为
时，算法增长率最大的是
。
A．5

B．20log2

C．2
2
D．3
log3

3T（
）表示当输入规模为
时的算法效率，以下算法效率最优的是
。
A．T（
）T（
1）1，T（1）1
B．T（
）2
2
C．T（
）T（
2）1，T（1）1
D．T（
）3
log2

4在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨
牌的个数是
。
A．（4k1）3
B．2k3
C．4k
D．2k
5在寻找
个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法
对
个元素进行划分，应如何选择划分基准？下面
答案解释最合理。
A．随机选择一个元素作为划分基准
B．取子序列的第一个元素作为划分基准
C．用中位数的中位数方法寻找划分基准
D．以上皆可行。但不同方法，算法复杂度上界可能不同
1
f6有9个村庄，其坐标位置如下表所示：
i
1
2
3
4
5
6
7
8
9
x（i）
1
2
3
4
5
6
7
8
9
y（i）
1
2
3
4
5
6
7
8
9
现在要盖一所邮局为这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．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简r