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

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.贪心法C.分治法D.回溯法参考答案：C 第 2 题：设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n 0)及 T(0)=1，则该算法的时间复杂度为 _。A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)参考答案：D 第 3 题：一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有_特性。A.有穷性B.可行性C.确定性D.健壮性参考答案：B 2 斐波那契(Fibonacci)数列可以递归地定义为：用递归算法求解 F(5)时需要执行(4)次“+”运算，该方法采用的算法策略是(5)。第 4 题：A.5 B.6 C.7 D.8 参考答案：C 第 5 题：A.动态规划B.分治C.回溯D.分支限界参考答案：B 第 6 题：若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为 _。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)参考答案：C 第 7 题：3 某算法的时间复杂度可用递归式表示，若用表示该算法的渐进时间复杂度的紧致界，则正确的是 _。A.B.C.D.参考答案：B 第 8 题：用动态规划策略求解矩阵连乘问题M1*M2*M3*M4，其中M1(20*5)、M2(5*35)、M3(35*4)和M4(4*25)，则最优的计算次序为 _。A.(M1*M2)*M3)*M4 B.(M1*M2)*(M3*M4)C.(M1*(M2*M3)*M4 D.M1*(M2*(M33*M4)参考答案：C 第 9 题：4 下面 C程序段中 count+语句执行的次数为 _。for(int i=1;i=11;i*=2)for(int j=1；j =i；j+)count+;A.15 B.16 C.31 D.32 参考答案：A 第 10 题：_不能保证求得 0-1 背包问题的最优解。A.分支限界法B.贪心算法C.回溯法D.动态规划策略参考答案：B 第 11 题：若某算法在问题规模为n 时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为 _。A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)参考答案：B 第 12 题：若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结点)时，_。A.插入和删除操作的时间复杂度都为O(1)5 B.插入和删除操作的时间复杂度都为O(n)C.插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)D.插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)参考答案：C 第 13 题：某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d，其中，n 为问题的规模，a、b、c 和 d 为常数，用 O表示其渐近时间复杂度为 _。A.O(n2)B.O(n)C.O(nlgn)D.O(1)参考答案：A 第 14 题：现有 16 枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若采用分治法找出这枚假币，至少比较_次才能够找出该假币。A.3 B.4 C.5 D.6 参考答案：B 第 15 题：以下的算法设计方法中，_以获取问题最优解为目标。A.回溯方法B.分治法C.动态规划D.递推参考答案：C 第 16 题：6 归并排序采用的算法设计方法属于_。A.归纳法B.分治法C.贪心法D.回溯方法参考答案：B