算法设计与分析试卷及答案
湖南科技学院二○年学期期末考试
信息与计算科学专业年级《算法设计与分析》试题
考试类型：开卷试卷类型：C 卷考试时量：120分钟
性的阶为
结点的是 指1.试述回溯法的基本思想及用回溯法解题的步骤。
2.有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1给出一个最优调度方案，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少，并计算所需的最少时间。 答：
最优调度方案为
所需的最少时间为：_______________________
3.根据优先队列式分支限界法，求下图中从v1点到v9点的单源最短路径，请画出求得最优解的解空间树。要求中间被舍弃的结点用×标记，获得中间解的结点用单圆圈○框起（如），最优解用双圆圈◎框起。
三、算法填空（每空2分，共计10分）
设R={r1,r2,...,r n}是要进行排列的n个元素，其中元素r1,r2,...,r n可能相同，试设计一个算法，列出R的所有不同排列，并给出不同排列的总数。算法如下，填写缺失的语句。
template
Swap(R[k],R[i]);
}
}
}
四、算法设计（共计15分）
设有n个程序{1,2,3...,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序，在保证存储最多程序的前提下还要求磁带的利用率达到最大。
（1）给出求解存储最多程序的算法，并证明算法的正确性；
（2）给出求解使磁带的利用率达到最大的方案的算法思路。。
五、算法设计（共计15分）
通过键盘输入一个高精度的正整数n （n 的有效位数≤240），去掉其中任意s 个数字后，剩下的数字按原左右次序将组成一个新的正整数。对给定的n 和s ，寻找一种方案，使得剩下的数字组成的新最小。 如输入n 为178543，s 为4，结果为13 ⑴简述你的算法思路； ⑵给出算法（用C++描述）。
注：正整数n 存于字符串中，例：
stringn="178543";
n.at(0)//返回字符串n 的第1个字符
n.erase(2,3)//删除n 中索引为2开始的3个字符 解：
⑴算法思路
1.f(n)=
2.73
log 8
n
4.5.9.10.1.
2.
所需的最少时间为：73（4分在前一问正确的前提下方可得分）
3.
错一处扣1分
三、算法填空（每空2分，共计10分） 1.b=a
2.R[t]==R[i]
3.sum++
4.R[i]
5.R,k+1,n,sum
四、算法设计（共计15分）
贪心策略：最短程序优先。将程序从小到大排序，依次选取尽可能多的程序，但总长度不超过磁盘容量，则可求得最多可以存储的程序个数m。
采用回溯法，从n个程序中选取总长度最大的m个，算法同装载问题。
五、算法设计（共计15分）
1.7分
为了尽可能地逼近目标，选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字母。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是总是的解。
2.8分
{
{
i++;
s--;
}
}
《算法设计与分析》考试题目及答案
《算法分析与设计》期末复习题 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则。由此设计出解Hanoi 塔问题的递归算法正确的为：（B ） Hanoi 塔 A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); }
3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f(n)O(g(n))g(n)O(f(n)) =?= 6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质
算法设计与分析考试题及答案
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 5.设S=｛X1，X2，···，X n｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i，其概率为b i。（2）在二叉搜索树的叶结点中确定X∈（X i，X i+1），其概率为a i。在表示S的二叉搜索树T中，设存储元素X i的结点深度为C i；叶结点（X i，X i+1）的结点深度为d i，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]=｛X i，X i+1，···，X j｝最优值为m[i][j]，W[i][j]= a i-1+b i+···+b j+a j，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？ 6.描述0-1背包问题。 三、简答题（30分） 1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为a i和b i，请写出流水作业调度问题的johnson法则中对a i和b i的排序算法。（函数名可写为sort(s,n)）
算法设计与分析考试题目及答案
算法设计与分析考试题目及答案 Revised at 16:25 am on June 10, 2021 I hope tomorrow will definitely be better
算法分析与设计期末复习题 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是D A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 塔问题如下图所示;现要求将塔座A 上的的所有圆盘移到塔座B 上,并仍按同样顺序叠置;移动圆盘时遵守Hanoi 塔问题的移动规则;由此设计出解Hanoi 塔问题的递归算法正确的为：B 3. 动态规划算法的基本要素为C A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中,记号O 表示B , 记号Ω表示A , 记号Θ表示D ; A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：A A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ⇒=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==⇒= C. Ofn+Ogn = Omin{fn,gn} D. f (n)O(g(n))g(n)O(f (n))=⇔= Hanoi 塔 A. void hanoiint n, int A, int C, int B { if n > 0 { hanoin-1,A,C, B; moven,a,b; hanoin-1, C, B, A; } B. void hanoiint n, int A, int B, int C { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } C. void hanoiint n, int C, int B, int A { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; } D. void hanoiint n, int C, int A, int B { if n > 0 { hanoin-1, A, C, B; moven,a,b; hanoin-1, C, B, A; }
《算法设计与分析》考试题目及答案
《算法分析与设计》期末复习题 一、选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解 Hanoi塔问题的递归算法正确的为：（B） Hanoi塔
3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f(n)O(g(n))g(n)O(f(n)) =?= 6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。 A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先 8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。 A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先 9. 程序块（A）是回溯法中遍历排列树的算法框架程序。 A. B. C.
《算法设计与分析》试卷及答案
《算法设计与分析》试卷及答案 算法设计与分析考试复习试卷 《算法设计与分析》试卷1 一、多项选择题（每空2分，共20分）： 1、以下关于算法设计问题的叙述中正确的是__________。 A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关 B、利用计算机无法解决非数值问题 C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算 D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题 2、算法的特征包括_________。 A、有穷性 B、确定性 C、输入和输出 D、能行性或可行性 3、以下描述是有关算法设计的基本步骤： ①问题的陈述②算法分析③模型的拟制④算法的实现 ⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起 其中正确的顺序是__________。
A、①②③④⑤⑥ B、①③⑤②④⑥ C、②④①③⑤⑥ D、⑥①③⑤②④ 4、以下说法正确的是__________。 A、数学归纳法可以证明算法终止性 B、良序原则是证明算法的正确性的有力工具 C、x = 小于或等于x的最大整数（x的低限） D、x = 小于或等于x的最大整数（x的高限） 5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C 上所用的次数，则递归方程 为__________，其初始条件为__________，将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数，则有递归方程为__________，其中F1=F2=__________。 A、Fn=Fn-1+Fn-2 B、h（n）= 2h（n-1）+1 C、1 D、h（1）= 1 E、h（n）=2n-1 F、0 6、在一个有向连通图中（如下图所示），找出点A到点B的一条最短路为____ ______。 A、最短路：1→3→5→8→10，耗费：20 B、最短路：1→4→6→9→10，耗费： 16
算法设计与分析试题及答案
1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L 型骨 牌；并在棋盘上填写L 型骨牌的覆盖情况。 2． 假设有7个物品，给出重量和价值。若这些物品均不能被分割，且背包容量M ＝140，使用回 溯方法求解此0-1背包问题。请画出状态空间搜索树。 3． 假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M ＝140，使用贪心算法求解此背包问题。请写出求解策略和求解过程。 W （35,30,50,60,40,10,25）p （10,40,30,50,35,40,30） 4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定 a 到 b 的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。 5． 画出字符表的哈夫曼编码对应的二叉树。 6． 已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=8，r 5=5，r 6=20，r 7=6，求 矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。 7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树， 描述出用优先队列式分支限界法求解时的搜索情况。表示出优先队列、当前扩展结点等的变化情况。 8． 依据优先队列式分支限界法，求从s 点到t 点的单源最短路径，画出求得最优解的解空间树。 一、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M ＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。 答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】
计算机算法设计和分析习题及答案解析
计算机算法设计与分析习题及答案 一．选择题 1、二分搜索算法是利用 A 实现的算法; A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是 A ; A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是A 的一搜索方式; A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是 A ; A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是B ; A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是 C ; A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是 D ; A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是A ; A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是D ; A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是D ; A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形; B A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为B ; A、On2n B、Onlogn C、O2n D、On 13．分支限界法解最大团问题时,活结点表的组织形式是B ; A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是B; A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是A ; A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是C ; A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素 D A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略B A．递归函数 B.剪枝函数 C;随机数函数 D.搜索函数 19. D是贪心算法与动态规划算法的共同点; A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由 B 设计实现; A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
算法设计与分析(第二版)王红梅试题及解析
算法设计与分析（第二版）王红梅试题及解析 本文主要介绍了《算法设计与分析（第二版）》一书中的王红梅试题及解析，旨在帮助读者更好地掌握算法的基础知识，提高算法设计与分析的能力。 一、算法设计与分析 算法是计算机科学的重要组成部分，是解决计算问题的一种方法。算法设计与分析是计算机科学的一项核心技术，也是计算机科学专业必修的一门课程。算法的好坏将直接影响计算机程序的运行效率。
王红梅编写的《算法设计与分析（第二版）》是一本通俗易懂的教材，作者通过详细解析 算法设计和分析的基本概念和方法，给出了 很多数学原理和实例，帮助读者深刻理解算 法设计和分析的基本原则和方法。 二、王红梅试题及解析 1. 下面哪个算法的时间复杂度最小？ A. 插入排序 B. 选择排序 C. 冒泡排序 D. 快速排序
答案：D 解析：快速排序是一种分治算法，基于递归 的思想进行排序，每次划分找到一个基准点，将比基准点小的数放到左边，比基准点大的 数放到右边，递归进行排序，因此它的时间 复杂度为O(nlogn)，是四种算法中最小的。 2. 下列哪些数据结构可以用来实现递归算法？ A. 数组 B. 栈 C. 队列 D. 链表
答案：B、D 解析：递归算法通常使用栈和链表来实现， 因为它们具有后进先出或者先进先出的特点，符合递归算法的调用过程。 3. 下列哪个算法不是稳定排序？ A. 插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 答案：D
解析：稳定排序表示排序后，具有相同值得 元素，排序前后其相对位置不变。插入排序、冒泡排序和归并排序都是稳定排序算法，只 有堆排序不是稳定排序算法。 4. 设有n个元素的数组，采用冒泡排序，平均比较次数和平均移动次数分别是多少？ 答案：平均比较次数为n(n-1)/2，平均移动次数为3 n(n-1)/4。 解析：冒泡排序的平均时间复杂度为O(n²)。在n个元素的数组中，每个元素最多需要比 较n-1次，所以平均比较次数为(n-1 + n-2
算法设计与分析试卷(A)及答案
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 二、选择 1 2 3 4 5 6 7 8 9 10 C B C A B A B C B A 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 a a a b a a c Q 1 11 x =21 x =31x =41=50x =60x =70x =d e e 40x =30 x =41x =e 51x =f 60 x =g 50x =h 40 x =i 20x =j 10x =
算法设计与分析试题及答案
一、填空题〔20分〕 1.一个算法就是一个有穷规那么的集合，其中之规那么规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度上下。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子构造性质。 4.假设序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个〔最优〕解。 6.动态规划算法的根本思想是将待求解问题分解成假设干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n),用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个根本要素是最优子构造和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题〔50分〕 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子构造性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai
计算机算法设计与分析考试复习题及答案
计算机算法设计与分析考试复习题 一.选择题 1、二分搜索算法是利用（）实现的算法。［单选题］* A、分治策略。 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（1 ［单选题］* A、找出最优解的性质。 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（）的一搜索方式。［单选题］* A、分支界限法V B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（\ ［单选题］* A、分支界限法
B、动态规划法V空1答案：规模 11、计算一个算法时间复杂度通常可以计算循环次数、或计算步。［填空题］*空1答案：基本操作的频 率 12、回溯法搜索解空间树时，常用的两种剪枝函数为和限界函数［填空题］*空1答案：约束函数 14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是,需要排序的是［填空题］*空1答案：动态规划法空2答案：回溯法空3答案：分支限界法 15、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界，N［单选题］* 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进， 行裁剪的是｛0/1背包问题｝,只使用约束条件进行裁剪的是｛N皇后问题｝。 17、回溯法是一种既带有又带有的搜索算法。［填空题］*空1答案：系统性空2答案：跳跃性 18.动态规划算法的两个基本要素是.最优子结构性质和性质［填空题］*空1答案：重叠子问题 19.贪心算法的基本要素是性质和性质。［填空题］*空1答案：贪心选择空2答案：最优子结构 21.动态规划算法的基本思想是将待求解问题分解成若干 ,先求解 ,然后从这些的解得到原问题的解。［填空题］*空1答案：子问题空2答案：子问题空3答案：子问题 22.算法是由若干条指令组成的有穷序列，且要满足和四条性质。［填空题］*
算法设计与分析试卷及答案
算法设计与分析试卷及答案 LT
算法设计与分析 1、(1) 证明：O(f)+O(g)=O(f+g)（7分） (2) 求下列函数的渐近表达式：（6分） ① 3n 2+10n; ② 21+1/n; 2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。（15分） (1) ;5log )(;log )(2+==n n g n n f (2) ;)(;log )(2n n g n n f == (3) ;log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分） 5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分） 6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： (1)删除一个字符。 (2)插入一个字符。 (3)将一个字符改为另一个字符。 将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。
（16分） 7、试用回溯法解决下列整数变换问题：关于整数i 的变换f 和g 定义如下：⎣⎦2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。（16分）
计算机算法设计与分析考试复习题及答案
计算机算法设计与分析考试复习题 一、选择题 1、二分搜索算法是利用（）实现的算法。[单选题] * A、分治策略√ B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（）。[单选题] * A、找出最优解的性质√ B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（）的一搜索方式。[单选题] * A、分支界限法√ B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（）。[单选题] * A、分支界限法 B、动态规划法√
C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（）。[单选题] * A、子集树√ B、排列树 C、深度优先生成树 D、广度优先生成树 6．下列算法中通常以自底向上的方式求解最优解的是（）。[单选题] * A、备忘录法 B、动态规划法√ C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（）。[单选题] * A 运行速度快 B 占用空间少 C 时间复杂度低√ D 代码短 8、以下不可以使用分治法求解的是（）。[单选题] * A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题√
9. 实现循环赛日程表利用的算法是（）。[单选题] * A、分治策略√ B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（）。[单选题] * A、分治策略 B、动态规划法√ C、贪心法 D、回溯法 11．下面不是分支界限法搜索方式的是（）。[单选题] * A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先√ 12．下列算法中通常以深度优先方式系统搜索问题解的是（）。[单选题] * A、备忘录法 B、动态规划法 C、贪心法 D、回溯法√ 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的[单选题] * （B ）。√
算法设计与分析试卷及答案
算法设计与分析 1、(1) 证明：O(f)+O(g)=O(f+g)（7分） (2) 求下列函数的渐近表达式：（6分） ① 3n 2+10n; ② 21+1/n; 2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。（15分） (1);5log )(;log )(2+==n n g n n f (2) ;)(;log )(2n n g n n f == (3) ;log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分） 5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分） 6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： (1)删除一个字符。 (2)插入一个字符。 (3)将一个字符改为另一个字符。 将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符
串A 和B ，计算出它们的编辑距离d(A,B)。 （16分） 7、试用回溯法解决下列整数变换问题：关于整数i 的变换f 和g 定义如下：⎣⎦2/)(;3)(i i g i i f ==。对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。（16分）
算法设计与分析试卷及答案
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 一、填空题（每小题3 分，共计30 分） 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =⎧=⎨ +≥⎩，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。 二、简答题（每小题10分，共计30分） 1. 试述回溯法的基本思想及用回溯法解题的步骤。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 复查人
- 算法设计与分析-习题参考答案
- 算法设计与分析考试题及答案
- 算法设计与分析实验报告
- 算法设计与分析考试题目及答案
- (完整版)算法设计与分析考试题及答案
- 算法设计与分析实验报告
- 《计算机算法设计与分析》习题及答案
- 算法设计与分析试卷及答案
- 《算法设计与分析》试卷及答案
- 算法设计与分析实验报告
- 算法设计与分析试卷及答案
- 算法设计与分析试卷及答案
- 算法设计与分析试卷(2010)
- 算法设计与分析试卷
- 算法设计与分析试卷(A)及答案
- 2015武汉大学《算法设计与分析》期中试卷课案
- 《算法设计与分析》历年期末试题整理_含答案_
- (完整版)算法设计与分析期末试题_考试版
- 算法设计与分析考试题(自测)
- 算法设计与分析课程期末试卷-A卷(自测 )