2005.6算法设计及分析课程期末试卷.doc

华南农业大学期末考试试卷（A卷） 2004学年第学期　 考试科目：　算法设计与分析　 考试类型：（开卷）　　　考试时间：　120　分钟 学号 姓名 年级专业 题号 一 二 三 四 总分 得分 评阅人 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了 。 （A）二义性 （B）有限性 （C） 正确性 （D）可终止性 2、解决一个问题通常有多种方法。若说一个算法有效是指 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是 。 （A）5n （B）20log2n （C）2n2 （D）3nlog3n 4、渐进算法分析是指 。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销增长率上的简化分析 （C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？ （A）大O表示法 （B）大Ω表示法 （C）Θ表示法 （D）小o表示法 6、采用顺序有哪些信誉好的足球投注网站法从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序有哪些信誉好的足球投注网站法分析正确的是 。 （A）最佳情况、最差情况和平均情况下，顺序有哪些信誉好的足球投注网站法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用 来实现。 （A）有序的线性表 （B）队列 （C）栈 （D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 （A）规模相同，性质相同 （B）规模相同，性质不同 （C）规模不同，性质相同 （D）规模不同，性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面 答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面 答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或有哪些信誉好的足球投注网站算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最子结构性质，所以不能用贪心算法求解 11、关于回溯有哪些信誉好的足球投注网站法的介绍，下面 是不正确描述。 （A）回溯法有通用解题法之称，它可以系统地有哪些信誉好的足球投注网站一个问题的所有解或任意解 （B）回溯法是一种既带系统性又带有跳跃性的有哪些信誉好的足球投注网站算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的有哪些信誉好的足球投注网站，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径回溯法，又被称为通用解题法，用它可以系统地有哪些信誉好的足球投注网站问题的所有解。回溯法是一个既带有系统性又带有跳跃性的有哪些信誉好的足球投注网站算法。它在问题的解空间中按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站到解空间树的任意结点时，首先判断该结点是否包含问题的解。如果不包含则跳过对以该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则进入这棵子树继续按深度优先有哪些信誉好的足球投注网站。如收费公路重建问题。 12、关于回溯算法和分支限界法，以下 是不正确描述。 （A）回溯法中，每个活结点只有一次机会成为扩展结点 （B）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中 （C）回溯法采用深度优先的结点生成策略 （D）分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略 13、优先队列通常用以下 数据结构来实现。 （A）栈 （B）堆 （C）队列 （D）二叉查找树 14、在分支限界算法中，根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类