2009.1算法设计与分析课程期末试卷VIP专享VIP免费

1 华南农业大学期末考试试卷（A 卷） 2008 学年第一学期 考试科目： 算法分析与设计 考试类型：（闭卷） 考试时间： 120 分钟 学号 姓名 年级专业 题号 一 二 三 四 总分 得分 评阅人 一、选择题（20 分，每题 2 分） 1. 下述表达不正确的是 。D A．n 2/2 + 2n 的渐进表达式上界函数是O(2n) B．n 2/2 + 2n 的渐进表达式下界函数是Ω(2n) C．lo gn 3 的渐进表达式上界函数是O(lo gn ) D．lo gn 3 的渐进表达式下界函数是Ω(n 3) 改：Ω(lo gn ) 2. 当输入规模为n 时，算法增长率最大的是 。A A．5n B．20lo g2n C．2n 2 D．3n lo g3n 3. T（n ）表示当输入规模为n 时的算法效率，以下算法效率最优的是 。C A．T（n ）= T（n – 1）+1，T（1）=1 O(N) B．T（n ）= 2n 2 C．T（n ）= T（n /2）+1，T（1）=1 O(lo gn ) D．T（n ）= 3n lo g2n 4. 在棋盘覆盖问题中，对于2k×2k 的特殊棋盘（有一个特殊方块），所需的L 型骨牌的个数是 。A A．（4k – 1）/3 B．2k /3 C．4k D．2k 2 5. 在寻找n 个元素中第k 小元素问题中，若使用快速排序算法思想，运用分治算法对n 个元素进行划分，应如何选择划分基准？下面 答案解释最合理。D A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6. 有 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 个村庄的总距离和最短。C A．（4.5，0） B．（4.5，4.5） C．（5，5） D．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 说法不正确？A A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间 t 内，可以让尽可能多的人打上水 D．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形...