算法设计与分析知到智慧树章节测试课后答案2024年秋苏州大学

算法设计与分析知到智慧树章节测试课后答案2024年秋苏州大学第一章单元测试

下列对算法的理解不正确的是（）。

A:算法要求是一步步执行，每一步都能得到唯一的结果B:算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法C:算法有一个共同特点就是对一类问题都有效(而不是个别问题)D:任何问题都可以用算法来解决

答案:任何问题都可以用算法来解决算法渐近时间复杂度的分析主要关注哪一方面？（）

A:低阶项和常系数的精确计算B:最高次项的系数C:实际运行时间的精确测量D:最高次项并忽略常系数

答案:最高次项并忽略常系数渐近时间复杂度分析中，通常认为哪种情况对算法选择更重要？（）

A:最坏情况B:最好情况C:最佳和最坏情况的平均D:平均情况

答案:最坏情况使用渐近符号的函数通常刻画算法的运行时间，但是渐近符号也可以适用于刻画算法的某个其他方面的函数，甚至可以适用于和算法没有任何关系的函数。（）

A:错B:对

答案:对在算法分析中，常用大O记号限制算法的（）。

A:平均情况运行时间B:最好情况运行时间C:最坏情况运行时间

答案:最坏情况运行时间

第二章单元测试

下面关于NP问题说法正确的是（）

A:NP问题都是不可能解决的问题B:NP完全问题是P类问题的子集C:NP类问题包含在P类问题中D:P类问题包含在NP类问题中

答案:P类问题包含在NP类问题中下面关于NPC问题说法不正确的是（）

A:所有的NPC问题之间可相互归约B:非确定性多项式时间不可解决C:如果一个NPC问题在多项式时间可解，则所有NP问题在多项式时间可解D:所有的NP类问题可归约成该问题

答案:非确定性多项式时间不可解决假设存在两个问题X、Y，问题X可以在多项式时间内归约为问题Y，下面说法正确的是（）

A:如果问题X是NPC，那么问题Y是NP-hard的B:如果问题X是NP-hard，那么问题Y也是NP难的C:如果问题X是NP-hard，那么问题Y是NPCD:如果Y是易处理的（多项式时间可解），那么问题X也是易处理的

答案:如果问题X是NP-hard，那么问题Y也是NP难的；如果Y是易处理的（多项式时间可解），那么问题X也是易处理的假设集合I是图G的独立集，集合C是图G的顶点覆盖集，下面说法不正确的是（）

A:对于图G中任意一条边(u,v)，有u∈I或v∈IB:对于图G中任意一条边(u,v)，有u∈C且v∈CC:假设V为图G的顶点集合，则有I=V-CD:对于图G中任意一条边(u,v)，有u∈C或v∈C

答案:对于图G中任意一条边(u,v)，有u∈I或v∈I下列关于CNF-SAT问题的说法中，正确的是（）

A:对于任意的CNF都存在使得表达式为真的赋值B:CNF-SAT是一个P问题C:3-CNF可满足性问题可以在多项式时间内被归约到图的独立集问题D:对于一个CNF-SAT问题，可以在多项式时间内验证一个解的正确性

答案:3-CNF可满足性问题可以在多项式时间内被归约到图的独立集问题；对于一个CNF-SAT问题，可以在多项式时间内验证一个解的正确性

第三章单元测试

以下哪些算法或问题是基于分治算法设计的或者能通过分治算法解决？（）。

A:归并排序B:快速排序C:二分查找D:汉诺塔

答案:归并排序；快速排序；二分查找；汉诺塔分治法求解平面最接近点对问题的时间复杂度是（）。

A:

O(1)

B:

O(n)C:D:O(nlgn)E:F:G:O(n2)H:

答案:O(nlgn)；快速傅里叶变换求解大整数乘法利用了插值计算的思想，通过将两个大整数分别表示为多项式形式，利用FFT求解点值对，最后利用离散傅里叶变换求解出系数向量。（）

A:对B:错

答案:错在计算矩阵乘法时，Strassen算法提升性能的主要策略是什么？（）

A:使用随机化技术选择子矩阵B:应用快速傅里叶变换C:增加矩阵分解的级别D:将8个子问题减少到7个

答案:将8个子问题减少到7个在快速排序的随机化版本中，对于所有输入数据，排序的时间复杂度始终保持不变。（）

A:对B:错

答案:错

第四章单元测试

在使用动态规划求解最长公共子序列问题时，下列哪个步骤描述了问题的递推过程？（）

A:根据dp[m][n]的值，构造最长公共子序列。B:通过递推关系式dp[i][j]=max(dp[i-1][j],dp[i][j-1])，填充dp数组。C:初始化边界条件，即当i或j为0时，dp[i][j]=0。D:定义二维数组dp，其中dp[i][j]表示序列A的前i个元素和序列B的前j个元素的最长公共子序列长度。

答案:通过递推关系式dp[i][j]=max(dp[i-1][j],dp[i][j-1])，填充dp数组。在0-1背包问题中，动态规划的主要目的是什么？（）

A:找到最轻的物品组合B:最大化背包中物品的总价值C:平衡背包中物品的重量和价值D:最小化背包中物品的数量

答案:最大化背包中物品的总价值在0-1背包问题的动态规划求解方法中，递归式计算的是什么？（）

A:确定哪些物品被选中B:判断是否超过背包容量C:计算每个物品的价值D:计算达到当前容量下的最大价值

答案:计算达到当前容量下的最大价值矩阵链乘实质上是一个最优括号化问题。（）

A:错B:对

答案:对在动态规划问题中，最优子结构要素描述了问题的最优解可以通过子问题的最优解来构造。（）

A:对B:错

答案:对

第五章单元测试

多机调度问题是用贪心算法求最优解的一个例子，贪心策略是每次从剩余任务中选择一个花费时间最长的任务，安排在占用时间最少的机器上。（）

A:对B:错

答案:对下列问题中不能用贪心算法求得最优解的是（）。

A:单源最短路径问题B:0-1背包问题C:霍夫曼编码问题D:最小生成树问题

答案:0-1背包问题所有可以用贪心法求出最优解的问题都可以形式化为在一个加权拟阵中找到一个权值最大的独立子集。（）

A:对B:错

答案:错若一应用问题能被抽象为在加权拟阵中寻找最优子集，那么一定能用加权拟阵上的通用贪心算法求出其最优解。（）

A:错B:对

答案:对0-1背包问题中每个物品有固定的重量和价值，要求不能将物品部分放入，需求解放入物品使得总价值最大。对于此问题，以下哪种算法可以获得最优解？（）

A:动态规划B:两者均可C:无法确定D:贪心算法

答案:动态规划

第六章单元测试

下列不属于放宽实际问题求解中对时间性能要求的方法的是（）

A:近似算法B:引入不确定性的算法C:超多项式时间启发D:启发式概率分析

答案:引入不确定性的算法下列问题中，具有绝对近似算法的问题是（）

A:图的边着色问题B:团问题C:图的顶点着色问题D:0-1背包问题

答案:图的边着色问题；图的顶点着色问题。（）

A:对B:错

答案:错FPTAS算法的时间复杂度是（）

A:多项式时间B:指数时间C:不确定，取决于输入规模D:对数时间

答案:多项式时间FPTAS算法的第一步是对0-1背包问题中的什么进行适当的缩放，以确保算法的多项式性质？（）

A:价值B:重量C:物品数量D:容量

答案:价值

第七章单元测试

在使用数字型概率算法求解定积分的时候，为达到一定的精度，假设一维积分需要1000个采样点才能达到一定精度，那么三维积分需要的采样点数量可能为（）。

A:1000^2B:1000C:1000^3D:任意数目的点都可以

答案:1000^3在计算π值的问题中，Crude算法的方差和精度都优于HitorMiss算法，因此它总是更优的。（）

A:错B:对

答案:错在使用有回放抽样并统计第一次重复抽样所用的实验次数的方法来估计集合的势的时候，这种算法的时间复杂度和空间复杂度均为θ(√n)(n为集合的势)