算法设计与分析智慧树知到期末考试答案章节答案2024年山东交通学院

算法设计与分析智慧树知到期末考试答案+章节答案2024年山东交通学院堆的根总是堆的最小元素。（）

答案:错n皇后问题可以用回溯法来解决。()

答案:对广度优先查找可以检查图的无环性。()

答案:对Kruskal算法求解最小生成树的过程中得到的图不一定是连通的。()

答案:对一根直线将平面分成两个半平面，其中一个半平面中的点都满足：ax+by＞c，而另一个半平面的点都满足：ax+by＜c。()

答案:对能否利用分治法完全取决于问题的规模缩小到一定程度是否就可以容易地解决。()

答案:错分支界限找出满足条件的一个解，或某种意义下的最优解。()

答案:对算法和程序没区别。()

答案:错问题规模不能太大是问题能够用动态规划算法求解的前提。()

答案:错二叉树的前序遍历，中序遍历，后序遍历都是递归的访问二叉树的节点。()

答案:对哈夫曼树的加权路径长度是最小的。()

答案:对计数排序是一种常见的以空间换取时间的方法。()

答案:对程序可以不满足有限性。（）

答案:对解决问题的实例很小时，蛮力法也花费很大的代价。()

答案:错动态规划法实际上是研究一类最优化问题的算法，其应用非常广泛。()

答案:对算法运算效率除依赖输入规模之外，还依赖于特定的输入细节。()

答案:对堆的每一层都是满的，除了最后一层最右边元素可能有缺位。（）

答案:对在给定的数字列表中最经常出现的一个数值称为模式。（）

答案:对如果在相同的文本中查找相同的模式，Horspool算法的字符比较次数可能比蛮力算法还多。()

答案:对回溯法并不找出满足约束条件的所有解。()

答案:错

答案:相同一般不用回溯法解决的问题是（）

答案:排序问题除最后一层无任何节点外，每一层上的所有节点都有两个子节点的二叉树被称为()。

答案:满二叉树二维最近点对问题中，如果使用分治法，对于一个子集上的某一点，另一个子集上需要检查的点的个数是（）

答案:6个一棵高度为4的AVL二叉树，它具有的最少节点数是（）

答案:12在用笔计算两位n（n＞=2）位数相乘时，需要做()次一位数的加法，忽略进位导致的加法。

答案:(n-1)2当一个房间里有（）人时，其中两个人生日(月和日)相同的概率大于1/2。

答案:不大于30有一个国家只有７元和８元两种纸币，如果你是央行行长，你会设置（）为自动取款机的取款最低限额。

答案:42计数排序算法在()种情况下是卓有成效的。

答案:待排序元素的值都来自一个已知的小集合合并排序算法是利用()的算法

答案:分治法1个无环有向图必定至少具有一个源。()

答案:对我们有一份档案，其中包含学生的姓名，住址，电话等信息，假如这些学生来自美国的50个州，我们要求出来自每个州的人数，那么需不需要排序？（）

答案:不需要在2-3树中，如果叶子是3个节点，把叶子分裂成２个节点：三个键中最小的放在第一个叶子，最大的放在第二个叶子中，中间的值（）。

答案:提升到原来叶子的父母中去用Horspool算法在一个长度为n的文本中查找一个长度为m(n≥m)的模式，最差输入情况下的比较次数是（）。

答案:m(n-m+1)两个十进制n位数的积最多能有()位数。

答案:2n

答案:将规模为n的问题分解为子问题，以及合并相应的子问题的解所需时间一个严格递减的数组是快速排序的()。

答案:最差输入分治法能解决的问题应具有的关键特征是（）

答案:利用该问题分解出的子问题的解可以合并为该问题的解有２对夫妻过河，但是只有一条能容纳两人的小船，这２对夫妻中，丈夫爱吃醋，妻子不在自己身边时，不允许有其他男人在妻子身边，那么这２对夫妻能过河吗？（）

答案:能有3个野人和3个传教士来到岸边，需要过河。现在有一艘小船，最多能容两人，在渡河时，无论是在左岸还是右岸，如果野人的数目超过传教士的数目，野人就会吃掉传教士。传教士和野人能平安过河吗？（）

答案:能经常用回溯法解决的问题是（）

答案:图着色问题设有4个数的集合S={1,2,5,6,8}，取d=9，则该问题的解是()。

答案:{1,8}分支界限法不同于回溯法，不是一种在问题的解空间树中搜索问题解的算法。()

答案:错经常用分支界限法解决问题是（）

答案:分配问题分支界限法可以求解旅行商问题。()

答案:对贪婪算法在对问题求解时，总是做出当前看来最好的选择。()

答案:对Dijkstra算法和Floyd算法都是是解决完全最短路径问题的。()

答案:错哈夫曼编码总是最优前缀码。()

答案:对哈夫曼编码的压缩率通常在20%～80%之间。()

答案:对Dijkstra算法和Floyd算法采用了相同的算法设计技术。()

答案:错Dijkstra算法是解决单起点最短路径问题的。()

答案:对频率较高的字符的码长不一定小于频率较低的字符的码长。()

答案:对哈夫曼编码频率相同的所有字符都具有相同的码长。()

答案:错对于包含负权重边的图，Kruskal算法可能会无效。()

答案:错Prim算法总是通过把离树中顶点最近的顶点包含进来，从而生成一棵最小生成树。()

答案:对如果e是加权连通图中权重最小的边，它（）图的一棵最小生成树的边。

答案:必定是不属于贪婪技术的算法是（）

答案:Floyd算法如果加权连通图中每条边的权重是都是互不相同的，该图必定只有一棵最小生成树。()

答案:对对于包含负权重边的图，Prim算法()正确工作。

答案:不能对于包含负权重边的图，Dijkstra算法也是正确有效的。()

答案:错贪心算法与动态规划算法的主要区别是（）。

答案:贪心选择性质Floyd算法的时间效率是（）

答案:动态规划法不是随机化算法。（）

答案:对动态规划法分解的子问题是有重叠的，分治法分解的子问题是相互独立的。（）

答案:对动态规划算法适用于解具有某种最优性质的问题。（）

答案:对币值最大化问题的一个实例是5,1,2,10,16，则最大金额为（）

答案:23对于模式BAOBAB，A,B,O的移动距离分别为()。

答案:1,2,3用Horspool算法在一个1000个0构成的二进制文本中查找00001时，要进行（）次字符比较。

答案:996Horspool算法的最差效率Θ(mn)()

答案:对在Horspool字符串匹配算法中，输入0001是000000000000的最差输入吗？（）

答案:不是()不使用额外的存储来交换两个变量的数值，例如m和n.

答案:可以计数排序算法在一种情况下还是卓有成效的，即待排序元素的值都来自一个已知的小集合。()

答案:对双向右左旋转是在一个新的键插入到树的右子女的左子树后发生的，在插入以前，这棵树的根的平衡因子是-1。()

答案:对最大堆的根总是堆的最大元素。（）

答案:对一个具有最多节点的高度为h的2-3树是一棵全部由2节点构成的满树。（）

答案:错AVL树的旋转中，存在()种旋转.

答案:右左双转查找n个可排列数值时，折半查找通常比顺序查找快。（）

答案:对有3对夫妻过河，但是只有一条能容纳两人的小船，这3对夫妻中，丈夫爱吃醋，妻子不在自己身边时，不允许有其他男人在妻子身边。那么这3对夫妻能过河吗？（）

答案:能１、对数组中的元素先进行合并排序，再检查连续元素来检验数组中元素的唯一性，直到找到两个相等的元素或所有相邻的元素都检查一遍为止。该算法的复杂性是（）。

答案:O（nlogn）如果用合并排序做预排序，折半查找做查找，要做()次查找才能使得一个由1000000个元素组成的数组所做的预排序是有意义的。

答案:40对于相同的输入，自顶向下算法和自底向上算法产生完全相同的堆。()

答案:错2-3树要求树中的所有叶子必须位于同一层。()

答案:对对于分治法，子问题只能细分一次，不能继续细分。（）

答案:错能否利用分治法完全取决于该问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（）

答案:错一个严格递增的数组是快速排序的()。

答案:最差输入应用分治法的两个前提是问题的可分解性和解的复杂性。（）

答案:错在分治法中，将一个问题划分为同一类型的若干子问题，子问题最好规模相同。（）

答案:对快速排序是稳定的吗？()

答案:不是用分治法解决最近点对问题的时间复杂度为（）

答案:O(nlogn)Strassen矩阵乘法是利用（）实现的算法

答案:分治法两个十进制n位数的积最少能拥有()位数。

答案:2n-1以下不可以使用分治法求解的是（）

答案:0/1背包问题快速排序算法是利用()的算法。

答案:分治法对二叉搜索树进行前序遍历即可得到一个有序数列。（）

答案:错合并排序是一个稳定的排序算法。（）

答案:对插入排序和拓扑排序都属于减治法的减常量形式。()

答案:对插入排序的比较和移动次数不只依赖于输入规模，还依赖于特定输入。()

答案:对减治法的减常因子技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子，在大多数应用中，这个常数因子等于1。()

答案:错减治法的减常量形式中，每次迭代总是从实例中减去相同的常量。但是这个常量并不固定，减多少无迹可寻。()

答案:错5门必修课的一个集合{C1,C2,C3,C4,C5}，一个在职学生必须在某个阶段修完这几门课程。可以按照任何次序学习这些课程，只要满足下面的先决条件：C1和C2没有任何先决条件，修完C1和C2才能修C3，修完C3才能修C4，而修完C3和C4才能修C5，这个学生每个学期只能修一门课程，该学生不能按照()顺序学习这门课程。

答案:C2C3C4C5C1求n个数的最小值至少需要（）次比较

答案:n-1执行一次DFS遍历，并记住顶点变成死端(即退出遍历栈)的顺序。该次序就是拓扑排序一个解。()

答案:错下列()不是对数据表{26，99，20，45，15，29，65，35，20，72}用冒泡法进行排序的中间结果。

答案:20261529456520357299有9只杯口向上的杯子放在桌子上，每次将其中四只杯子同时“翻转”，使其杯口向下，经过()次“翻转”后，使9只杯口全部向下？

答案:都不对集合｛Ａ，Ｂ｝的幂集合为()。

答案:{｛Ａ，Ｂ｝，｛Ａ｝，｛Ｂ｝，Φ}以下哪种排序用的是蛮力法？()

答案:冒泡排序可以用（）求得一个图的连通分量。

答案:深度优先查找一根直线将平面分成两个半平面，其中一个半平面中的点都满足：ax+by≥c，而另一个半平面的点都满足：ax+by≥c。()

答案:错如果S是凸的，它的凸包是它本身。()

答案:对蛮力法生成整数1,2,…,n的全部排列的算法时间复杂度为O(n!)。()

答案:对对于同样的输入，选择排序和冒泡排序比较的次数是一样的。()

答案:对蛮力法是一种简单直接地解决问题的方法。()

答案:对最近对问题的输入规模为集合中点的个数n，基本操作是计算欧几里得距离，该问题的蛮力算法的时间复杂度除依赖于n外，还依赖于输入。()

答案:错蛮力字符串匹配算法将文本中的字符从右向左比较不会比从左向右比较更有优势。()

答案:错4个盘子的汉诺塔，至少要执行移动操作的次数为()。

答案:15次O表示算法效率的下界。()

答案:错

答案:Fibonacci数列的第8项为()。

答案:21并不是所有的算法，规模更大的输入需要更长的运行时间。()

答案:错当算法由两个连续执行部分组成时，该算法的整体效率等于较大增长次数＋较小增长次数。()

答案:错算法效率分析框架主要关心一个算法的基本操作次数的增长次数，并把它作为算法效率的主要指标。()

答案:对既然程序设计语言可以描述算法，所以算法就是程序。()

答案:错算法与程序没有关系。()

答案:错没有好的算法，就编不出好的程序。（）

答案:对gcd(m,n)=gcd(n,mmodn)并不是对每一对正整数(m,n)都成立。()

答案:错我将来不进行软件开发，所以学习算法没什么用。()

答案:错解决一个问题通常有多种方法。若说一个算法“有效”是指()

答案:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）求解2个数的最大公约数至少有3种方法。()

答案:错下述（）不是是算法的描述方式。

答案:E-R图可以用同样的方法证明算法的