算法分析与设计期末考试试卷b卷

算法设计与分析试卷B 与解答一．填空题：（每题4分，共20分）1. 算法的特性有 _0至多个输入， 至少一个输出， 指令无歧义性，指令条数有限且每条指令执行时间有限 .2．直接或间接地调用自身的算法称为 递归 算法。

用函数自身给出定义的函数称为 递归 函数。

3．在回溯法中，为了避免无效的搜索，通常采用两种剪枝策略，分别为和 。

（约束剪枝，限界剪枝）4． 算法的时间复杂性T (n ) 是指算法其中n 是问题的规模。

5．动态规划算法的两大基本要素分别为 和 。

（最优子结构性质和子问题的重叠性质。

）二．简答题：（每小题5分，共20分）1. 给定2个序列12{,,,}m X x x x =L 和12{,,,}n Y y y y =L ，说明X 和Y 的最长公共子序列问题具有最优子结构性质。

设序列X m ={x 1,x 2,…,x m }和Y n ={y 1,y 2,…,y n }的最长公共子序列为Z k ={z 1,z 2,…,z k} ，则 (1)若x m =y n ，那么z k =x m =y n ，且Z k-1是X m-1和Y n-1的最长公共子序列。

(2)若x m ≠y n 且z k ≠x m ，那么Z k 是X m-1和Y n的最长公共子序列。

(3)若x m ≠y n 且z k ≠y n ，那么Z k 是X m 和Y n-1的最长公共子序列。

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。

因此，最长公共子序列问题具有最优子结构性质。

2. 简述常见的两种分支限界法。

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

3. 假设以加法和乘法为关键操作，估算下述n 次多项式求值函数的时间复杂度（取T 为整型）template<class T>T PolyEval(T coeff[], int n, const T& x){ // 计算 n 次多项式的值， coeff[0:n] 为多项式的系数T y=1, value=coeff[0];for(i=1;i<=n;i++) {y*=x;value+=y*coeff[i];}return value;}解答：T PolyEval(T coeff[], int n, const T& x){ // 计算n 次多项式的值，coeff[0:n]为多项式的系数T y=1, value=coeff[0];for(i=1;i<=n;i++) //n 循环{ // 累加下一项y*=x; //一次乘法value+=y*coeff[i]; //一次加法和一次乘法}return value;} // 3n 次基本操作4.动态规划算法的基本思想是什么？它和分治法有什么区别和联系？答：动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复子问题，为了避免子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可构造出所求问题的最优解。

西南交通大学2015 — 2016学年第(一)学期考试试卷课程代码 3244152课程名称 算法分析与设计考试时间 120分钟阅卷教师签字： __________________________________填空题(每空1分，共15分)1、 程序是 (1)用某种程序设计语言的具体实现。

2、 矩阵连乘问题的算法可由(2)设计实现。

3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是(3)4、 大整数乘积算法是用 (4) 来设计的。

5、 贪心算法总是做出在当前看来(5) 的选择。

也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的(6) o6、 回溯法是一种既带有(7)又带有 (8)的搜索算法。

7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9)类型8、 在忽略常数因子的情况下，0、门和0三个符号中，(10)提供了算法运行时间的一个上界。

9、 算法的“确定性”指的是组成算法的每条(11)是清晰的，无歧义的。

10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。

11、 算法就是一组有穷(13)，它们规定了解决某一特定类型问题的(14) o12、 变治思想有三种主要的类型：实例化简，改变表现，(15) o、___________________________________________________________________________________ L线订装封密线订装封密、__________________ 二 线订装封密级班选择题(每题2分，共20 分)1、二分搜索算法是利用（）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2、衡量一个算法好坏的标准是（）。

A、运行速度快B、占用空间少C、时间复杂度低D、代码短3、能采用贪心算法求最优解的问题，一般具有的重要性质为：（）A.最优子结构性质与贪心选择性质 B •重叠子问题性质与贪心选择性质C •最优子结构性质与重叠子问题性质 D.预排序与递归调用4、常见的两种分支限界法为（）A、广度优先分支限界法与深度优先分支限界法；B、队列式（FIFO ）分支限界法与堆栈式分支限界法；C 、排列树法与子集树法；D、队列式（FIFO ）分支限界法与优先队列式分支限界法;5、实现循环赛日程表利用的算法是（）A、分治策略B、动态规划法C、贪心法D、回溯法6、回溯法的效率不依赖于下列哪些因素（）A. 满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间7、A、子问题必须是一样的C、子问题的解可以合并8、实现合并排序利用的算法是（A、分治策略B、动态规划法B、子问题不能够重复D、原问题和子问题使用相同的方法解）。

（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。

不存在二义性。

只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

大学期末考试试卷B 卷（算法设计与分析）一、选择题（30分，每题2分）1、下面的算法段针对不同的自然数n 作不同的处理，其中函数odd (n) 当n 是奇数时返回true ，否则返回false ，while ( n > 1) if ( odd (n) ) n = 3 * n + 1;else n = n / 2;请问该算法所需计算时间的下界是 。

A ．Ω（2n ） B ．Ω（nlog n ） C ．Ω（n ！） D ．Ω（logn ）2、某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下同一时刻，该羽毛球场只能租借给一位客户，请问在这10位客户里面，体育馆最多能满足 位客户的需求。

P104 A ．3 B ．4 C ．5 D ．63、当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用 来消除或减少问题的好坏实例间的这种差别。

A ．数值概率算法 B ．舍伍德算法 C ．拉斯维加斯算法 D ．蒙特卡罗算法4、将一个正整数n 表示成一系列正整数之和， n = n 1 + n 2 + … +n k （其中，n 1≥n 2≥ … ≥n k ≥1，k ≥1）正整数n 的一个这种表示称为正整数n 的一个划分。

正整数n 的不同的划分个数总和称为正整数n 的划分数，记作p （n ）；另外，在正整数n 的所有不同划分中，将最大加数n1不大于m 的划分个数记作q （n ，m ）。

则当n=10时，p （n ）= 。

A ．q （8，8） B ．1 + q （9，9） P12 C ．2 + q （10，8） D ．A ，B ，C 都正确5、对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。

A ．n!B ．2nC ．2n+1-1D ．∑=ni i n 1!/! P1406、在棋盘覆盖问题中，对于2k ×2k 的特殊棋盘（有一个特殊方块），所需的L 型骨牌的个数是 A 。

西南交通大学2015－2016学年第(一)学期考试试卷课程代码 3244152 课程名称 算法分析与设计 考试时间 120 分钟阅卷教师签字：一、 填空题（每空1分，共15分）1、 程序是 （1） 用某种程序设计语言的具体实现。

2、 矩阵连乘问题的算法可由 （2） 设计实现。

3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 （3） 。

4、 大整数乘积算法是用 （4） 来设计的。

5、贪心算法总是做出在当前看来 （5） 的选择。

也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 （6） 。

6、 回溯法是一种既带有 （7） 又带有 （8） 的搜索算法。

7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 （9） 类型。

8、在忽略常数因子的情况下，O 、Ω和Θ三个符号中， （10） 提供了算法运行时间的一个上界。

9、算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。

10、 问题的 (12) 是该问题可用动态规划算法或贪心算法求解的关键特征。

11、 算法就是一组有穷 (13) ，它们规定了解决某一特定类型问题的 (14) 。

12、 变治思想有三种主要的类型：实例化简，改变表现， (15) 。

二、 选择题（每题2分，共20分）1、二分搜索算法是利用（ ）实现的算法。

A 、分治策略B 、动态规划法C 、贪心法D 、回溯法 2、衡量一个算法好坏的标准是（ ）。

A 、运行速度快B 、占用空间少C 、 时间复杂度低D 、代码短 3、能采用贪心算法求最优解的问题，一般具有的重要性质为：（ ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质班 级 学 号 姓 名密封装订线 密封装订线 密封装订线C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用4、常见的两种分支限界法为（）A、广度优先分支限界法与深度优先分支限界法；B、队列式（FIFO）分支限界法与堆栈式分支限界法；C、排列树法与子集树法；D、队列式（FIFO）分支限界法与优先队列式分支限界法；5、实现循环赛日程表利用的算法是（）。

《算法分析与设计》期末测验复习题纲(完整版)————————————————————————————————作者：————————————————————————————————日期：《算法分析与设计》期末复习题一、选择题1.算法必须具备输入、输出和（ D ）等4个特性。

A．可行性和安全性 B．确定性和易读性C．有穷性和安全性 D．有穷性和确定性2.算法分析中，记号O表示（ B ），记号Ω表示（ A ）A.渐进下界B.渐进上界C.非紧上界D.紧渐进界3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成概算法的时间为t秒。

现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2^n*64=3*2^xA．n+8 B．n+6C．n+7 D．n+54.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。

A．O(logN) B．O(N)C．O(NlogN) D．O(N²logN)5.直接或间接调用自身的算法称为（ B ）。

A．贪心算法 B．递归算法C．迭代算法 D．回溯法6.Fibonacci数列中，第4个和第11个数分别是（ D ）。

A．5，89 B．3，89C．5，144 D．3，1447.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。

A．6条弦和7个三角形 B．5条弦和6个三角形C．6条弦和6个三角形 D．5条弦和5个三角形8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。

A．重叠子问题 B．最优子结构性质C．贪心选择性质 D．定义最优解9.下列哪个问题不用贪心法求解（ C ）。

A．哈夫曼编码问题 B．单源最短路径问题C．最大团问题 D．最小生成树问题10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。

计算机算法设计与分析期末试题4套（含答案）（1）用计算机求解问题的步骤: 1问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。

不存在二义性。

只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

1、二分搜索算法是利用（ A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是( B )。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是( A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。

A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是(C ）。

A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D )。

A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9。

实现循环赛日程表利用的算法是（ A ）。

A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D )。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先(回溯法）12．下列算法中通常以深度优先方式系统搜索问题解的是( D ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。

( B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B )。

A、O（n2n)B、O（nlogn）C、O(2n）D、O(n）15．分支限界法解最大团问题时，活结点表的组织形式是( B ）。

A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）.A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A )。