算法设计与分析-期末考试

算法设计与分析_武汉理工大学中国大学mooc课后章节答案期末考试题库2023年

1. 在寻找 n 个元素中第 k 小元素问题中，如快速排序算法思想，运用分治算法对 n个元素进行划分，如何选择划分基准？下面（ ）答案解释最合理。

答案:

以上皆可行。但不同方法，算法复杂度上界可能不同

2. 减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（ ）值。

答案:

a

3. 使用分治法求解不需要满足的条件是（ ）。

答案:

子问题不能够重复

4. 改进分治算法的方法有（ ）。

答案:

减少子问题的个数_减少合并的时间_改进分治的均衡度

5. 阅读以下代码:int Fun(int n){ if(n <= 1) return 1; int First = Fun(n-1); int

Second = Fun(n-2); int iSum = First + Second; return iSum;}调用该函数，假设输入参数n值为5，当程序第二次执行语句 iSum = First + Second时，iSum的值为（ ）。

答案:

3

6. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。

答案:

问题规模不同，问题性质相同

7. 【图片】表示当输入规模为【图片】时的算法效率，以下算法效率最优的是（ ）

答案:

8. 以下哪些是算法的基本特点（）。

答案:

有穷性_确定性_可行性

9. 以下关于渐近记号的性质，正确的有（ ）

答案:

10. 下列关于算法的说法中正确的有（）。

答案:

算法必须在有限步操作之后停止_算法的每一步操作必须是明确的，不能有歧义或含义模糊_算法执行后一定产生确定的结果

11. 若一个算法的递归方程为【图片】，则其时间复杂度为（ ）

答案:

12. 以下关于记号【图片】的定义，正确的是（ ）

算法设计与分析

1、(1) 证明：O(f)+O(g)=O(f+g)（7分）

(2) 求下列函数的渐近表达式：（6分）

① 3n2+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nngnnf

(2);)(;log)(2nngnnf

(3);log)(;)(2nngnnf

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)(iigiif。对于给定的两个整数n和m，要求用最少的变换f和g变换次数将n变为m。（16分） 1、⑴证明：令F(n)=O(f),则存在自然数n1、c1，使得对任意的自然数n≥n1，有：F(n)≤c1f(n)……………………………..（2分）

同理可令G(n)=O(g),则存在自然数n2、c2，使得对任意的自然数n≥n2，有：G(n)≤c2g(n)……………………………..（3分）

令c3=max{c1,c2},n3=max{n1,n2},则对所有的n≥n3，有：

1 / 7 一、填空题（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所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

湖南科技学院二○年学期期末考试

信息与计算科学专业年级《算法设计与分析》试题

考试类型：开卷试卷类型：C卷考试时量：120分钟

一、填空题（每小题3分，共计30分）

1.用O、Ω和θ表示函数f与g之间的关系______________________________。

2.算法的时间复杂性为1,1()8(3/7),2nfnfnnn，则算法的时间复杂性的阶为__________________________。

3.快速排序算法的性能取决于______________________________。

4.算法是_______________________________________________________。

5.在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6.在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7.大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。

8.____________________________是问题能用动态规划算法求解的前提。

9.贪心选择性质是指____________________________________________________________________________________________________________________。

10.回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）

1.试述回溯法的基本思想及用回溯法解题的步骤。

2.有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为：