软件设计师算法设计和分析

1、 模拟 软件设计师算法设计和分析选择题第 1 题：给定一组长度为 n 的无序序列，将其存储在一维数组 a0.n-1 中。现采用如 下方法找出其中的最大元素和最小元素：比较 a0 和 an-1 ，若 a0 较大， 则将二者的值进行交换；再比较 a1 和 an-2 ，若 a1 较大，则交换二者的 值；然后依次比较 a2 和 an-3 、 a3 和 an-4 、. ，使得每一对元素中的 较小者被交换到低下标端。重复上述方法，在数组的前 n/2 个元素中查找最小 元素，在后 n/2 个元素查找最大元素，从而得到整个序列的最小元素和最大元 素。上述方法采用的算法设计策略是 。A. 动态规划法B. 贪心法

2、C. 分治法D. 回溯法参考答案： CT(n)=T(n-1)+n(n 0)及 T(0)=1 ，则该第 2 题： 设某算法的计算时间表示为递推关系式 算法的时间复杂度为 。A. O(lgn)B. O(nlgn)C. O(n)D. O(n²)参考答案： D第 3 题：一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有 特性。A. 有穷性B. 可行性C. 确定性D. 健壮性参考答案： B斐波那契 (Fibonacci) 数列可以递归地定义为：用递归算法求解 F(5) 时需要执行

3、(4) 次“+”运算， 该方法采用的算法 策略是 (5) 。第 4 题：A. 5B. 6C. 7D. 8参考答案： C第 5 题：A. 动态规划B. 分治C. 回溯D. 分支限界参考答案： B第 6 题： 若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下 的时间复杂度为 。A. O(log₂n)B. O(n)C. O(nlog₂n)D. O(n²)参考答案： C第 7 题：某算法的时间复杂度可用递归式 表示，若用表示该算法的渐进时间复杂度

4、的紧致界， 则正确的是A.B.C.D.参考答案： B第 8 题： 用动态规划策略求解矩阵连乘问题 M₁*M₂*M₃*M₄，其中 M₁(20*5) 、M₂(5*35) 、M₃(35*4) 和 M₄(4*25) ，则最优的计算次序为 。

5、A. (M₁*M₂)*M₃)*M₄B. (M₁*M₂)*(M₃*M₄)C. (M₁*(M₂*M₃

6、;)*M₄D. M₁*(M₂*(M₃3*M₄)参考答案： C第 9 题：下面 C 程序段中 count+ 语句执行的次数为 for (int i=1; i =11; i*=2) for(int j=1 ；j =i ； j+) count+;A. 15B. 16C. 31D. 32参考答案： A第 10 题：不能保证求得 0-1 背包问题的最优解A. 分支限界法B. 贪

7、心算法C. 回溯法D. 动态规划策略参考答案： B第 11 题：若某算法在问题规模为 n 时，其基本操作的重复次数可由下式表示，则该算法 的时间复杂度为 。A. O(n)B. O(n²)C. O(log₂n)D. O(nlog₂n)参考答案： B第 12 题：若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指 针的单向循环链表 (不含头结点 ) 时， 。A. 插入和删除操作的时间复杂度都为 O(1)B. 插入和删除操作的时间复杂度都为 O(

8、n)C. 插入操作的时间复杂度为 O(1) ，删除操作的时间复杂度为 O(n)D. 插入操作的时间复杂度为 O(n) ，删除操作的时间复杂度为 O(1) 参考答案： C第 13 题：某算法的时间复杂度表达式为 T(n)=an²+bnlgn+cn+d ，其中， n 为 问题的规模， a、b、c和 d为常数，用 O表示其渐近时间复杂度为 。A. O(n²)B. O(n)C. O(nlgn)D. O(1)参考答案： A第 14 题：现有 16 枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若采用分治法 找出这枚假币，至少比较 次才能够找出该假币。A. 3B. 4C. 5D