算法设计与分析期末答案2023秋

1.以深度优先方式系统搜索问题解的算法称为（ ）。
A:概率算法 B:回溯算法 C:分支界限算法 D:贪心算法
答案:回溯算法
2.关于回溯法以下叙述中不正确的是( )。
A:回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解 B:回溯法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 C:回溯法是一种既带系统性又带跳跃性的搜索算法 D:回溯法在生成解空间的任一结点时先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
答案:回溯法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
3.分治法能解决的问题应具有的关键特征是（ ）
A:利用该问题分解出的子问题的解可以合并为该问题的解 B:该问题可以分解为若干个规模较小的子问题 C:该问题的规模缩小到一定程度就可以容易地解决 D:该问题所分解出的各子问题是相互独立的
答案:利用该问题分解出的子问题的解可以合并为该问题的解
4.求n个数的最大值至少需要（ ）次比较。
A:n+1 B:n-1 C:n-2 D:n
答案:n-1
5.AVL树的旋转中，不存在（ ）种旋转。
A:左右双转 B:上下双转 C:左单转 D:右单转
答案:上下双转
6.可以用( ) 求得一个图的连通分量。
A:Prim算法 B:贪婪技术 C:广度优先查找 D:哈夫曼编码
答案:广度优先查找
7.程序执行的效率只取决于程序的控制结构。（ ）
A:错 B:对
答案:AI参考:答案是B：对。程序执行的效率只取决于程序的控制结构。程序的执行效率与程序的控制结构（如顺序结构、选择结构、循环结构）密切相关。控制结构的合理设计可以有效地减少程序的执行时间，提高程序的执行效率。因此，这个说法是正确的。'
8.算法的渐近分析中，,, 则的渐近上界函数都可以表示为 （ ）
A:错 B:对
答案:AI参考:根据所给的三张图片，我们无法确定第四张图片的渐近上界函数是否可以表示为给定的渐近上界函数。因此，无法得出结论。所以，正确答案是“错”。'
9.， 则h(. ( )
A:对 B:错
答案:AI参考:答案是B:错。\n\n根据给出的代码片段，标签是HTML中的图像标签，用于在网页中插入图像。然而，代码中的""这部分代码不完整，缺少了标签的结束部分">"。因此，这段代码无法正确执行，无法判断h()函数是否正确。因此，答案是B:错。正确的代码应该是""，完整的标签格式确保了HTML代码的正确性。'
10.考虑快速排序算法在划分执行过程中总选择A[3]作为支点元素，其中A[1, …, n]是待划分的数组，则该快速排序算法最坏执行时间为. ( )
A:错 B:对
答案:AI参考:答案：B\n\n快速排序算法在划分执行过程中，选择A[i]作为支点元素时，其最坏情况是每次递归都会得到一个逆序对，此时递归深度为n-1，所以最坏执行时间复杂度为O(n^2)。而题目中提到快速排序算法在划分执行过程中总选择A[3]作为支点元素，这只是算法的一个特性，并不能影响其最坏执行时间复杂度。因此，本题答案是B。'
11.对，若, 则. ( )
A:对 B:错

12.若背包承重，则使用动态规划方法是解决0/1背包问题的所有方法中时间复杂度最低的方法。（ ）
A:对 B:错 13.假定一个算法对于规模为n的输入的运行时间为, 那么仍旧存在一组可能的输入使得运行时间为. ( )
A:错 B:对 14.问题Q可以通过复杂性为的算法调用复杂性为的算法来求解，那么正确的论述有（ ）
A:若,,则Q不可能为P类问题。 B:若和的复杂性均为指数级，则Q为NP类问题。 C:若和的复杂性均为多项式界，则Q为P类问题。 D:若,,则Q也可能为P类问题。 15.算法的渐近分析中，下列说法正确的是（ ）.
A:记号表示算法的渐近上界 B:记号表示算法的渐近下界 C:记号表示算法的紧渐近界 D:记号表示算法的紧渐近界 16.利用合并排序，对数的序列[49] [38] [65] [97] [76] [13] [27]，进行一次排序，结果为（ ）：
A:[38 49] [65 97] [13 76] [27] B:[38 97] [49 65] [13 76] [27] C:[38 76] [65 49] [13 97] [27] D:[49 38] [97 65] [76 13] [27] 17.下面哪些内容不是算法设计之前要完成的内容? ( )
A:是求精确解还是近似解 B:确定合适的数据结构 C:使用何种计算机语言设计程序 D:确定合适的算法策略 18.使用分治法求解不需要满足的条件是（ ）。
A:原问题和子问题使用相同的方法解 B:子问题的解可以合并 C:子问题必须是一样的 D:子问题不能重复 19.Prim算法的算法思想为（ ）
A:在保证连通的前提下依次选出权重较小的n – 1条边； B:逐步求得整体最优解； C:将原问题分解为若干子问题，再递归求解； D:在保证无回路的前提下依次选出权重较小的n – 1条边。 20.下面关于动态规划解题的步骤内容描述不正确的是哪个？（ ）
A:计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。 B:构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造。 C:分析最优解的结构：将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质。 D:建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。 21.下列排序算法中，占用辅助空间最多的是：( )
A:堆排序 B:快速排序 C:归并排序 D:插入排序 22.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用哪种方法最快。（ ）
A:堆排序 B:起泡排序 C:快速排列 D:归并排序 23.设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm≠yn且zk≠xm则（ ）。
A:则Zk-1是Xm-1和Y的最长公共子序列。 B:则Z是Xm-1和Yn-1的最长公共子序列。 C:则Z是X和Yn-1的最长公共子序列。 D:则Z是Xm-1和Y的最长公共子序列。 24.函数10logn3的渐近表达式为（ ）：
A:O(nlogn) B:O(logn) C:O(n) D:O（1） 25.利用快速排序，对n个数，选择基准，进行一次划分，所用时间为（ ）：
A:O（n） B:O(nlogn) C:O(logn) D:O(2n) 26.归并排序中，归并的趟数是( )。
A:O(logn) B:O（n） C:O(nlogn) D:O(n*n) 27.对n个物品的0-1背包问题用回溯法求解，其解空间树有个多少个叶子结点（ ）
A:n2 B:n！ C:2n D:nlogn 28.下列哪一个是问题能用动态规划算法求解的前提？( )
A:贪心选择性质 B:复杂度高 C:最优子结构性质 D:复杂度低. 29.当(a1,a2, a3, a4, a5,a6)=(-2,11,-3,14,-5,-2)时，最大子段和为( ).
A:20 B:11 C:18 D:22 30.设有四个矩阵A,B,C,D,它们的维数分别是A=5*10, B=10*20, C=20*30, D=30*5, 则计算其乘积至少需要（ ）次乘法运算。
A:8750 B:3600, C:4250, D:1600, 31.动态规划方法的递归方式是（ ）
A:自小到大 B:不能确定. C:自顶向下 D:自底向上 32.二分搜索过程的算法行为可以用一棵（ ）来描述。
A:二叉排序树 B:二叉判定树 C:子集树 D:排列树 33.对0-1背包问题，n=5，c=10，w={2,2,6,5,4}，v={6,3,5,4,6}，则其最优解为（ ）
A:（0，1，1，1，1） B:（1，1，1，1，1） C:（0，1，0，1，1） D:（1，1，0，0，1） 34.回溯搜索解空间树的结束条件是（ ）
A:计算完成限界函数; B:计算完成剪枝函数; C:计算得到当前最优解; D:完成解空间树搜索 35.递归函数包括的两个基本要素是（ ）。
A:边界条件 B:输入 C:迭代 D:递归方程 36.关于使用回溯法求解0-1背包问题，以下说法正确的是( )。
A:使用约束函数剪去不满足约束条件的右子树。 B:使用约束函数剪去不满足约束条件的左子树。 C:使用限界函数剪去得不到最优解的右子树。 D:使用限界函数剪去得不到最优解的左子树。 37.算法分析是对一个算法（ ）等方面进行估算。
A:代码的长度 B:变量的耗费 C:空间的耗费 D:时间的耗费 38.利用动态规划法解决问题的基本基本步骤 ( )
A:递归地定义最优值。 B:找出最优解的性质，并刻画其结构特征。 C:根据计算最优值时得到的信息，构造最优解 D:以自底向上的方式计算出最优值。 39.下列哪一项是分治法所能解决的问题一般具有的特征（ ）？
A:该问题可以分解为若干个规模较小的相同问题; B:分解出的各个子问题相互不是独立的。 C:分解出的子问题的解可以合并为原问题的解； D:该问题的规模缩小到一定的程度就可以容易地解决； 40.关于P问题、NP问题、NPC问题，下列哪些解释不正确：( )
A:P=NP B:到目前为止，还未发现任何NPC问题有确定时间算法 C:P问题是可以在多项式时间解决的判定问题 D:NP问题是不能在多项式时间复杂性解决的可判定问题 41.当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成的任务有（ ）。
A:将控制转移到被调用函数的入口。 B:保存被调函数的计算结果； C:为被调用函数的局部变量分配存储区； D:将所有的实在参数、返回地址等信息传递给被调用函数保存； 42.算法效率的衡量方法通常有（ ）
A:事后统计法 B:手工计算方法 C:时空的精确计算法 D:事前分析估算法 43.对线性时间选择问题找第i小的元素的算法，下列叙述中正确的是？（ ）
A:算法第一步中不能按每三个元素一组找中位数； B:算法第一步中可以按每五个元素一组找中位数； C:算法第一步中可以按每七个元素一组找中位数； D:如果要求的n个元素的中位数，则中位数一定是第一步中找到的中位数中的某一个。 44.算法必须具备的重要特性有（ ）
A:递归性 B:确定性 C:有限性 D:简洁性 45.双向左右旋转是在一个新的键插入到树的左子女的右子树后发生的，在插入以前，这棵树的根的平衡因子是+1。( )
A:对 B:错 46.快速排序是一个稳定的排序算法。 ( )
A:错误 B:正确 47.一颗2-3树中，对于每个叶子来说，从树的根到叶子的路径长度都是相同的。（ ）
A:错误 B:正确 48.速排序算法在最坏情况下的时间复杂度为O()。（ ）
A:正确 B:错误 49.分治法通常以自顶向下的方式求解最优解。( )
A:正确 B:错误 50.n皇后问题可以用回溯法来解决。 ( )
A:正确 B:错误 51.快速排序要先进行元素划分。（ ）
A:错误 B:正确 52.能否利用分治法完全取决于该问题是否可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。( )
A:正确 B:错误 53.对于相同的数组元素，自顶向下构造和自底向上构造产生的堆不一定完全相同。( )
A:对 B:错 54.折半查找的效率不只依赖于输入规模，也依赖于特定输入。( )
A:对 B:错 55.O表示算法效率的上界。( )
A:正确 B:错误 56.描述一个算法只能用一种方式。（ ）
A:正确 B:错误 57.如果在相同的文本中查找相同的模式，Horspool算法的字符比较次数可能比蛮力算法还多。( )
A:正确 B:错误 58.当需要找出它的解集或者要求回答什么解是满足某些条件的最佳解时，往往要使用分治法。( )
A:错误 B:正确 59.对二叉搜索树进行中序遍历即可得到一个有序数列。（ ）
A:对 B:错 60.查找n个可排列数值时，折半查找一定比顺序查找快。（ ）
A:对 B:错 61.蛮力法生成整数1,2,…,n的全部组合的算法时间复杂度为O(n!)。( )
A:对 B:错 62.对规模同样为n的列表来说，顺序查找算法的运行时间会有很大差异。( )
A:错误 B:正确 63.快速排序、合并排序、二叉树遍历等算法均采用了分治法。（ ）
A:正确 B:错误 64.对于同样的输入，选择排序和冒泡排序交换的次数是一样的。 ( )
A:对 B:错 65.有关旅行商问题的分支限界法说明正确的是（ ）
A:旅行商问题的限界条件可以是当前已走过的路径长度小于当前找到的最优路径长度 B:旅行商问题的优先队列式分支限界法中，优先级可以设置为当前已走过的路径长度加上未走过的城市最小出边权之和 C:旅行商问题的约束条件是当前城市和要去的城市之间有路相连 D:旅行商问题可以用FIFO队列式分支限界法，也可以用优先队列式分支限界法 66.下面的问题中，属于难解的问题有 ( )
A:停机问题 B:矩阵乘法链问题 C:汉诺塔问题 D:在整个互联网里，查找含有”NP 问题” 的网页 67.下列问题不可使用贪心算法求得最优解的是（ ）.
A:最大无关集问题 B:0/1背包问题 C:偶图覆盖问题 D:货箱装载问题 68.下列算法中能解决 0/1 背包问题的是（ ）。
A:分支限界法 B:动态规划 C:回溯法 D:贪心法 69.动态规划方法适合解决（ ）等问题。
A:最短路径问题 B:N皇后问题 C:旅行商问题 D:背包问题 70.请依次指出选择排序、快速排序的时间复杂度（ ）。
A:n^2 B:logn C:n D:nlogn 71.有关0/1背包问题说法正确的是（ ）
A:该问题的解空间的组织结构是二叉树 B:该问题需要设置约束条件，也可以设置限界条件 C:该问题只需要设置约束条件，不需要设置限界条件 D:该问题用分支限界法求解时，只能用优先级队列的分支限界法 72.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去。 （ ）
A:错 B:对 73.与回溯法一样，分支限界也是搜索一个解空间，而这个解空间通常组织成一棵树。（ ）
A:错误 B:正确 74.停机问题属于NP难问题。 （ ）
A:错 B:对 75.偶图覆盖问题是NP-hard问题，对于任何输入，使用贪心算法只能求得近似解。 （ ）
A:正确 B:错误 76.算法的复杂性分析研究问题的实例编码长度与复杂性的关系。（ ）
A:错误 B:正确 77.求解最短路径问题的Dijkstra算法采用了贪心法的设计思想，使用Dijkstra算法求解最短路径问题，得到的路径不能保证最短。 ( )
A:错误 B:正确 78.在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。（ ）
A:错误 B:正确 79.最优子结构性质是指问题的最优解包含了其子问题的最优解。（ ）
A:错误 B:正确 80.在使用动态规划方法求解三个字符串的最长公共子序列时，可以看作某两个字符串的最长公共子序列与第三个字符串的最长公共子序列。（ ）
A:错误 B:正确 81.假定图中所有边的权值都非负，那么两点之间的最短路径一定被包含在图的最小生成树中。 （ ）
A:错误 B:正确 82.NPC问题可能是NP问题，也可能是NP难问题。 （ ）
A:正确 B:错误 83.FIFO队列式分支限界法以最小耗费优先的方式搜索解空间树。 （ ）
A:错 B:对 84.快速排序的最坏时间复杂度与平均时间复杂度都是O(nlogn).（ ）
A:错 B:对 85.设有m个城市，当第1个城市确定时，旅行售货员问题解的数量是m!。（ ）
A:对 B:错 86.背包问题能用贪心算法求得最优解（ ）
A:对 B:错 87.递归算法简洁明了，容易证明正确性，但效率往往很低，时空效率较差。（ ）
A:对 B:错 88.任何递归函数都应有边界条件。（ ）
A:对 B:错 89.对0-1背包问题，贪心法之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满（ ）
A:对 B:错 90.函数21+1/n的渐近表达式为1/n。（ ）
A:对 B:错 91.子问题之间不存在公共的子问题，这个条件影响到分治法的效率。（ ）
A:对 B:错 92.合并排序的最坏时间复杂度与平均时间复杂度都是O(nlogn).（ ）
A:对 B:错 93.贪心算法总是作出在当前及今后看来最好的选择。（ ）
A:错 B:对 94.使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重星价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。（ ）
A:对 B:错 95.对算法的时间复杂性分析，平均情况下的时间复杂性可操作性最好（ ） 。
A:对 B:错 96.程序和算法实质上是一回事（ ）。
A:错 B:对 97.快速排序总比其它排序速度快。（ ）
A:错 B:对 98.用贪心算法解背包问题时重量最低的物品最先装入（ ）
A:对 B:错 99.分治法所能解决的问题应具有的关键特征是该问题的规模缩小到一定的程度就可以容易地解决。（ ）
A:错 B:对 100.算法分析是对一个算法所消耗时间、空间资源进行估算。（ ）
A:对 B:错 101.动态规划算法可以有效地解0-1背包问题（ ）
A:对 B:错 102.一般来说，动态规划法的效率高于贪心算法（ ）
A:对 B:错 103.分治法的基本思想是将一个规模较大的问题分解成若干个规模较小的子问题，这些子问题之间并不一定相互独立。（ ）
A:对 B:错 104.分治算法可用于求解残缺棋盘覆盖问题，假定棋盘共有n个格子，其中，每次采用分治算法将棋盘分成小棋盘进行覆盖，最后得到整个残缺棋盘覆盖问题的解，则分治算法的算法复杂度函数为（ ）
A: B: C: D: 105.函数 则函数的渐近上限可表示为( ).
A: B: C: D: 106.若可由一个常数限界，则可渐近表示为 ( ).
A: B: C: D: 107.无论是有向图还是无向图，用邻接矩阵来表示时所需要的存储空间都是（ ）.
A: B: C: D: 108.

下面给出的四种排序方法中，所需要的比较次数与待排数据的输入无关的是（ ）.

A:插入排序 B:选择排序 C:堆排序 D:快速排序 109.无论是有向图还是无向图，用邻接表来表示时所需要的存储空间都是（ ）.
A: B: C: D: 110.问题X可以多项式地规约到问题Y，那么（ ）
A:X比Y“难” B:X至多与Y一样“难” C:Y比X“难” D:Y至多与X一样“难” 111.下述关于分支限界法的说法中，错误的是（ ）
A:分支限界法分为FIFO队列式分支限界法和优先队列式分支限界法 B:分支限界法一般更适合求解最优化问题 C:分支限界法一般比回溯法使用更多内存空间 D:分支限界法不能求解n皇后问题 112.问题Q是NP难问题，则（ ）
A:Q不可能属于NP类问题 B:Q至少与NP类问题一样“难” C:Q比所有的NP类问题都要“难” D:Q至多与NP类问题一样“难” 113.关于NP类问题，下面叙述正确的是（ ）
A:NP类问题指的是不存在多项式界求解算法的问题。 B:求解NP类问题算法的复杂性包括产生和验证一个证书的复杂性。 C:NP类问题中的非确定性指的是验证过程的非确定性。 D:NP类问题一定包含P类问题。 114.以下哪个选项是正确的（ ）
A: B: C: D: 115.下面的问题中，已知为易解的问题为（ ）
A:素数检验问题 B:最大集团问题 C:4-皇后问题 D:货箱装船问题 116.下面的问题中，属于难解的问题有 ( )
A:停机问题 B:汉诺塔问题 C:两个序列的最长公共子序列问题 D:矩阵乘法链问题 117.计算一个整数的完全平方根问题不属于（ ）
A:易解问题 B:决策问题 C:NP类问题 D:P类问题 118.集合A的幂集是( )。
A:A的子集合 B:的所有子集合的集合 C:空集 D:中所有元素的集合 119.对于二叉查找树的每个节点来说，所有左子树的元素都（ ）右子树的元素。
A:小于 B:大于 C:不确定 D:等于 120.

下列( )不是对数据表{26，99，30，45，10，29，65，35，30，91}用冒泡法进行排序的中间结果。

A:10 30 26 29 30 35 45 65 91 99 B:30 26 10 29 45 35 30 65 91 99 C:26 30 45 10 29 65 35 30 91 99 D:30 10 26 30 29 35 45 65 91 99 121.若f(n)=3n+2，因此有f(n)∈ （ ）
A:O() B:O(n) C:O() D:O(1) 122.合并排序是稳定的吗？( )
A:是 B:不是 C:不一定 123.蛮力法可以解决以下哪种类型的题目？（ ）
A:都不可以 B:大规模的问题 C:都可以 D:小规模的问题 124.在2-3树中，如果叶子是3个节点，把叶子分裂成２个节点：三个键中最小的放在第一个叶子，最大的放在第二个叶子中，中间的值（ ）。
A:提升到原来叶子的父母中去 B:放到第二个叶子中 C:放到第一个叶子中 125.以下对动态规划法描述不正确的是（ ）
A:适合用动态规划求解的问题，经分解得到的子问题往往不是互相独立的 B:动态规划求解问题时和分治法一样，对子问题重复计算多次 C:具体的动态规划法多种多样，但是它们具有相同的填表格式 D:动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题 126.计数排序算法在( )种情况下是卓有成效的。
A:待排序元素的值无要求 B:待排序元素的值都来自一个已知的小集合 C:待排序元素的值各不相同 D:待排序元素的值是随机产生的 127.以下关于渐进记号的性质是正确的有：（ ）
A:O(f(n))+O(g(n)) = O(min{f(n),g(n)}) B:若f（n）=Ο(g(n)), g（n）=Ο(h(n)),则 h(n)= Ο(f(n)) C:f（n）=Ο(g(n)) g（n）=Ο(f(n)) D:若f（n）=Θ(g(n)), g（n）=Θ(h(n)),则 f(n)= Θ(g(n))