华南农业大学期末考试试卷（A卷）
2007学年第二学期
考试类型：（闭卷）
学号
姓名
考试科目：算法分析与设计
考试时间：120分钟年级专业
题号
一
二
三
总分
得分
评阅人
一、选择题（30分，每题2分）
1、下面的算法段针对不同的自然数
作不同的处理，其中函数odd
当
是奇数
时返回true，否则返回false，
while
1
ifodd

3
1
else

2
请问该算法所需计算时间的下界是
D。
A．Ω（2
）B．Ω（
log
）C．Ω（
！）D．Ω（log
）
2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s（i）表示开始租用时刻，f（i）表示结束租用时刻，
i
1
2
3
4
5
6
7
8
9
10
s（i）0
3
1
5
3
5
2
8
8
6
f（i）6
5
4
9
8
7
13121110
同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多
能满足B位客户的需求。P104
A．3B．4C．5D．6
3、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有
1
f较大差别时，可以使用
B来消除或减少问题的好坏实例间的这种差别。
A．数值概率算法B．舍伍德算法
C．拉斯维加斯算法D．蒙特卡罗算法
4、将一个正整数
表示成一系列正整数之和，

1
2…
k（其中，
1≥
2≥…≥
k≥1，k≥1）
正整数
的一个这种表示称为正整数
的一个划分。正整数
的不同的划分个数总
和称为正整数
的划分数，记作p（
）；另外，在正整数
的所有不同划分中，将
最大加数
1不大于m的划分个数记作q（
，m）。则当
10时，p（
）C。
A．q（8，8）
B．1q（9，9）P12
C．2q（10，8）D．A，B，C都正确
5、对于含有
个元素的子集树问题，最坏情况下其解空间的叶结点数目为B。
A．
B．2


C．2
11D．
iP140i1
6、在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是A。A．（4k1）3B．2k3C．4kD．2k
7、T（
）表示当输入规模为
时的算法效率，以下算法效率最优的是
A．T（
）T（
1）1，T（1）＝1B．T（
）2
2
C．T（
）T（
2）1，T（1）1
D．T（
）3
log2

C。
8、给出一个由
个数组成的序列A1…
，要求找出它的最长单调上升子序列，设mi（1≤i≤
），表示以Ai结尾的最长单调上升子序列的长度，则m11，mi（1i≤
）为A。A．mi1max0，mk（AkAi，1≤ki）B．mi1mk（ki1i1）C．mi1max0，mk（Ak≤Ai，1≤ki）D．mimax0，mk（AkAr