【答案】《算法设计与分析》(武汉理工大学)章节作业中国大学慕课答案

第一章算法设计基础“算法设计基础”单元测验1.多选题：下列关于算法的说法中正确的有（）。

选项：

A、求解某一类问题的算法是唯一的

B、算法必须在有限步操作之后停止

C、算法的每一步操作必须是明确的，不能有歧义或含义模糊

D、算法执行后一定产生确定的结果

答案：【算法必须在有限步操作之后停止;算法的每一步操作必须是明确的，不能有歧义或含义模糊;算法执行后一定产生确定的结果】2.多选题：以下哪些是算法的基本特点（）。

选项：

A、至少有1个输入和1个输出

B、有穷性

C、确定性

D、可行性

答案：【有穷性;确定性;可行性】“算法设计基础”算法实现题1.Smith数问题

答案：【题目内容：若一个正整数的质因数分解式逐位相加之和等于其本身逐位相加之和，则称这个数为Smith数。如4937775=3*5*5*65837，而3+5+5+6+5+8+3+7=42，4+9+3+7+7+7+5=42，所以4937775是Smith数。给定一个正整数N，求大于N的最小Smith数。输入格式:若干个正整数，一行代表一个正整数N，以输入0表示结束输出格式：按行输出大于正整数N的最小Smith数输入样例：49377742000输出样例：4937775202】2.最接近数问题

答案：【题目内容：设计算法找出整数数组a[n]（n＜=50）中相差最小的两个元素（称为最接近数）的差。输入格式:第一行为数组大小n，第二行为n个数组元素，元素之间用空格分开输出格式：最接近数的差输入样例：56538267540输出样例：2】第二章算法分析基础“算法分析基础”测试题1.单选题：以下关于渐近记号的性质，正确的有（）

选项：

A、

B、

C、

D、

答案：【】2.单选题：以下关于记号的定义，正确的是（）

选项：

A、存在正常数和使得对所有有：

B、存在正常数和使得对所有有：

C、对于任何正常数，存在正数和使得对所有有：

D、对于任何正常数，存在正数和使得对所有有：

答案：【存在正常数和使得对所有有：】3.单选题：若一个算法的递归方程为，则其时间复杂度为（）

选项：

A、

B、

C、

D、

答案：【】4.单选题：表示当输入规模为时的算法效率，以下算法效率最优的是（）

选项：

A、

B、

C、

D、

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

选项：

A、随机选择一个元素作为划分基准

B、取子序列的第一个元素作为划分基准

C、用中位数的中位数方法寻找划分基准

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

答案：【以上皆可行。但不同方法，算法复杂度上界可能不同】2.单选题：减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n)中的（）值。

选项：

A、n

B、a

C、b

D、f(n)

答案：【a】3.单选题：使用分治法求解不需要满足的条件是（）。

选项：

A、子问题不能够重复

B、子问题必须具有相同的性质

C、子问题的解可以合并

D、原问题和子问题使用相同的方法求解

答案：【子问题不能够重复】4.单选题：分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。

选项：

A、问题规模相同，问题性质相同

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

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

D、问题规模不同，问题性质不同

答案：【问题规模不同，问题性质相同】5.多选题：改进分治算法的方法有（）。

选项：

A、减少子问题的个数

B、减少合并的时间

C、减少问题的规模

D、改进分治的均衡度

答案：【减少子问题的个数;减少合并的时间;改进分治的均衡度】“分治法”算法实现题1.循环左移问题

答案：【题目内容：设计分治算法实现将字符数组A[n]中所有元素循环左移k个位置,例如，对abcdefgh循环左移3位得到defghabc。输入格式:第一行为数组长度n第二行为循环左移数k第三行为数组中元素输出格式：循环左移k个位置后的结果输入样例：83abcdefgh输出样例：defghabc】2.逆序数问题

答案：【题目内容：设a1,a2,…,an是集合{1,2,…,n}的一个排列，如果iaj，则序偶(ai,aj)称为该排列的一个逆序。例如，2,3,1有两个逆序：(3,1)和(2,1)。设计算法统计给定排列中含有逆序的个数。输入格式:第一行输入集合中元素个数n，第二行输入n个集合元素输出格式：含有逆序的个数输入样例：3231输出样例：2】第四章动态规划法“动态规划法”算法实现题1.拦截导弹问题

答案：【题目内容：某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。输入格式：第一行，输入雷达捕捉到的敌国导弹的数量k（k＜=25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。输出格式：输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。输入样例：830020715530029917015865输出样例：6】2.新水果取名

答案：【题目内容：两种水果杂交出一种新水果，现在给新水果取名，要求这个名字中包含以前两种水果的字母，且名字尽量短，即：以前的水果名字arr1、arr2是新水果名arr的子序列，使用动态规划的思想设计算法得到新水果名arr。输入格式:以空格分开两个水果的名字输出格式：新水果的名字输入样例：pearpeach输出样例：pearch输入样例：peachpear输出样例：peachr】3.机器人路径规划

答案：【题目内容：一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求机器人从（1,1）到（m，n）有多少条路径。输入格式:以空格分开m，n输出格式：路径条数输入样例：45输出样例：35】第五章回溯法“回溯法”算法实现题1.求解最小机器重量设计问题

答案：【题目内容：设某一机器由n个部件组成,部件编号为1~n，每一种部件都可以从m个不同的供应商处购得，供应商编号为1~m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。（注意：输出结果中第一行最后没有空格。比如下面的输出样例中131后面没有空格。）输入格式:第1行输入3个正整数n,m和d。接下来n行输入wij（每行m个整数），最后n行输入cij（每行m个整数）,这里1≤n、m≤100。输出格式：输出的第1行包括n个整数，表示每个对应的供应商编号，第2行为对应的最小重量。输入样例：337123321232123542212输出样例：1314】2.求解部分和问题

答案：【题目内容：给出N个正整数组成的数组A，求能否从中选出若干个，使他们的和为K。如果可以，输出："YES"，否则输出"NO"。输入格式:第1行：2个数N、K,N为数组的长度,K为需要判断的和(2≤N≤20，1≤K≤10^9)第2到第N+1行：每行1个数，对应数组的元素A[i](1≤A[i]≤10^6)输出格式：如果可以，输出："YES"，否则输出"NO"。样例输入4131247样例输出YES输入样例：5912345输出样例：YES】第六章分枝限界法“分枝限界法”算法实现题1.迷宫问题

答案：【题目内容：定义一个二维数组，例如：intmaze[5][5]={0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。输入格式:一个5×5的二维数组，表示一个迷宫。数据保证有唯一最短路径。输出格式：左上角到右下角的最短路径，格式如样例所示。输入样例：0100001010000000111000010输出样例：(0,0)(1,0)(2,0)(2,1)(2,2)(2,3)(2,4)(3,4)(4,4)】第七章贪心法“贪心法”算法实现题1.求解畜栏问题

答案：【题目内容：有n头牛（1＜=n＜=50,000)要挤奶。给定每头牛挤奶的时间区间[A,B](1＜=A＜=B＜=1,000,000，A,B为整数)。牛需要呆在畜栏里才能挤奶。一个畜栏同一时间只能容纳一头牛。问至少需要多少个畜栏，才能完成全部挤奶工作，以及每头牛都放哪个畜栏里？注意：在同一个畜栏的两头牛，它们挤奶时间区间不能在端点重合。输入格式:第1行：一个正整数N；第2..N+1行：第i+1行的两个整数给出第i头奶牛的挤奶时间。输出格式：需要畜栏的最小数输入样例：511024365847输出样例：4】2.求解区间覆盖问题

答案：【题目内容：设x1,x2,...,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计求解此问题的有效算法。对于给定的实直线上的n个点和闭区间的长度k，编程计算覆盖点集的最少区间数。输入格式:输入数据的第一行有2个正整数n和k，表示有n个点，且固定长度闭区间的长度为k。接下来的1行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。输出格式：将编程计算出的最少区间数输出。输入样例：7312345-26输出样例：3】算法考试题算法设计与分析考试题1.单选题：采用最大效益优先搜索方式的算法是（）。

选项：

A、分支限界法

B、动态规划法

C、贪心法

D、回溯法

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

选项：

A、随机选择一个元素作为划分基准

B、取子序列的第一个元素作为划分基准

C、用中位数作为划分基准

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

答案：【以上皆可行。但不同方法，算法复杂度上界可能不同】3.单选题：回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

选项：

A、广度优先

B、活结点优先

C、扩展结点优先

D、深度优先

答案：【深度优先】4.单选题：优先队列式分支限界法选取扩展结点的原则是（）。

选项：

A、先进先出

B、后进先出

C、结点的优先级

D、随机

答案：【结点的优先级】5.单选题：对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

选项：

A、0－1背包问题和背包问题都可用贪心算法求得最优解

B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解

C、0－1背包问题不能用贪心算法求最优解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解

D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

答案：【0－1背包问题不能用贪心算法求最优解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解】6.单选题：常见的两种分支限界法为（）。

选项：

A、广度优先分支限界法与深度优先分支限界法

B、队列式（FIFO）分支限界法与堆栈式分支限界法

C、排列树法与子集树法

D、队列式（FIFO）分支限界法与优先队列式分支限界法

答案：【队列式（FIFO）分支限界法与优先队列式分支限界法】7.单选题：T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。

选项：

A、

B、

C、

D、

答案：【】8.单选题：算法分析中，记号Θ表示（）。

选项：

A、渐近下界

B、渐近上界

C、非紧上界

D、渐近紧界

答案：【渐近紧界】9.单选题：矩阵连乘问题的算法可由（）设计实现

选项：

A、贪心算法

B、回溯算法

C、动态规划算法

D、分支界限算法

答案：【动态规划算法】10.单选题：归并排序算法是利用（）实现的算法

选项：

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

答案：【分治策略】11.单选题：（）是回溯法中为避免无效搜索采取的策略。

选项：

A、递归函数

B、剪枝函数

C、随机数函数

D、限界函数

答案：【剪枝函数】12.单选题：找n个元素的中位数的分治算法的时间复杂度为()。

选项：

A、

B、

C、

D、

答案：【】13.单选题：回溯法的算法框架按照问题的解空间一般分为子集树算法框架与（）算法框架。

选项：

A、深度优先生成树

B、二叉树

C、广度优先生成树

D、排列树

答案：【排列树】14.单选题：分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。

选项：

A、问题规模相同，问题性质相同

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

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

D、问题规模不同，问题性质不同

答案：【问题规模不同，问题性质相同】15.单选题：下面问题（）不能使用贪心法解决。

选项：

A、单源最短路径问题

B、n皇后问题

C、最小生成树问题

D、背包问题

答案：【n皇后问题】16.多选题：分治法所能解决的问题一般具有（）特征。

选项：

A、问题可以分解为规模较小的子问题

B、子问题可合并为原问题的解

C、小规模子问题可解

D、子问题不相互独立

答案：【问题可以分解为规模较小的子问题;子问题可合并为原问题的解;小规模子问题可解】17.多选题：回溯法的效率依赖于下列哪些因素（）。

选项：

A、满足显式约束的值的个数

B、计算限界函数的时间

C、确定解空间的时间

D、计算约束函数的时间

答案：【满足显式约束的值的个数;计算限界函数的时间;计算约束函数的时间】18.多选题：改进分治算法的方法有（）。

选项：

A、改进分治的均衡度

B、减少合并的时间

C、减少子问题的个数

D、减少问题的规模

答案：【改进分治的均衡度;减少合并的时间;减少子问题的个数】19.多选题：算法是由若干条指令组成的有穷序列，而且满足以下性质（）。

选项：

A、输入：有0个或多个输入

B、输出：至少有一个输出

C、确定性：指令清晰，无歧义

D、有限性：指令执行次数有限，而且执行时间有限

答案：【输入：有0个或多个输入;输出：至少有一个输出;确定性：指令清晰，无歧义;有限性：指令执行次数有限，而且执行时间有限】20.多选题：求解递归方程使用的方法有（）。

选项：

A、迭代法

B、代入法

C、主定理

D、递归树

答案：【迭代法;代入法;主定理;递归树】21.单选题：同一个问题，其动态规划算法的效率一定比分治法设计的算法高。

选项：

A、正确

B、错误

答案：【错误】22.单选题：如果问题的最优解中也包含着其子问题的最优解，则该问题具有最优子结构性质。

选项：

A、正确

B、错误

答案：【正确】23.单选题：无论在何种情况下，分治法总能产生效率最高的算法。

选项：

A、正确

B、错误

答案：【错误】24.单选题：一个算法是正确的，那么它就是有效的。

选项：

A、正确

B、错误

答案：【错误】25.单选题：重叠子问题保证了动态规划算法的正确性。

选项：

A、正确

B、错误

答案：【错误】实验实验报告1.请完成实验后，按要求撰写《实验报告》，并在此提交。（注：附件命名为“专业班级姓名.DOCX”）

答案：【20】实验二动态规划法的应用1.最大K乘积问题

答案：【题目内容：问题描述设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。例如十进制整数1234划分为3段可有如下情形：1×2×34=681×23×4=9212×3×4=144编程任务对于给定的I和k，编程计算I的最大k乘积。输入格式：输入的第1行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的段数。接下来的一行中是一个n位十进制整数。（n＜=10）输出格式：计算出的最大k乘积。输入样例：32312输出样例：62】2.游艇租用问题

答案：【题目内容：问题描述长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i编程任务对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i输入格式：第1行中有1个正整数n（n＜=200），表示有n个游艇出租站。接下来的n-1行是r(i,j),1£i例如：35157第一行：表示一共有3个出租站点第二行：第1个站点到第2个的租金为5，第1个站点到第3个的租金为15第三行：第2个站点到第3个的租金为7输出格式：程序运行结束时，输出从游艇出租站1到游艇出租站n所需的最少租金。输入样例：35157输出样例：12】实验一分治法的应用1.中位数问题

答案：【题目内容：问题描述设X[0:n-1]和Y[0:n–1]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。编程任务利用分治策略试