29.1算法设计与分析课程期末试卷-a卷(自测 ) (2)(1).docx

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