2009.1算法设计与分析课程期末试卷-A卷(自测 ).docx

华南农业大学期末考试试卷(A卷)2008学年第一学期考试科目：算法分析与设计考试类型：(闭卷)考试时间：120分钟学号姓名年级专业题号三四总分得分评阅人一、选择题(20分，每题2分)1. 下述表达不正确的是A. n2/2+2n的渐进表达式上界函数是O(2n)B. n2/2+2n的渐进表达式下界函数是Q(2n)C. logn3的渐进表达式上界函数是O(logn)D.logn3的渐进表达式下界函数是Q(n3)2. 当输入规模为n时，算法增长率最大的。A.5nB.20log2nC.2n2D.3nlog3n3. T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是。B.T(n)=2n2A.T(n)=T(n-1)+1,T(1)=1CT（n）=T（n/2）+1，T（1）=1DT(n)=3nlog2n4. 在棋盘覆盖问题中，对于2kX2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是。A.（4k-1）/3B.2k/3