在线网课知道智慧《算法设计与分析（山盟-山东交通学院）》单元测试考核答案

第一章单元测试1【单选题】(2分)解决一个问题通常有多种方法。若说一个算法“有效”是指()A.（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）B.这个算法比其他已知算法都更快地将问题解决C.这个算法能在人的反应时间内将问题解决D.这个算法能在一定的时间和空间资源限制内将问题解决2【单选题】(2分)农夫带着狼、羊、白菜从河的左岸到河的右岸，农夫每次只能带一样东西过河，而且，没有农夫看管，狼会吃羊，羊会吃白菜。请问农夫能不能过去？（）A.不一定B.不能过去C.能过去3【单选题】(2分)下述（）不是是算法的描述方式。A.E-R图B.自然语言C.程序设计语言D.伪代码4【单选题】(2分)有一个国家只有6元和7元两种纸币，如果你是央行行长，你会设置（）为自动取款机的取款最低限额。A.30B.42C.40D.295【判断题】算法是一系列解决问题的明确指令。（）A.对B.错6【判断题】程序=数据结构+算法（）A.对B.错7【判断题】同一个问题可以用不同的算法解决，同一个算法也可以解决不同的问题。（）A.错B.对8【判断题】算法中的每一条指令不需有确切的含义，对于相同的输入不一定得到相同的输出。()A.错B.对9【判断题】可以用同样的方法证明算法的正确性与错误性()A.错B.对10【判断题】求解2个数的最大公约数至少有3种方法。()A.对B.错11【判断题】没有好的算法，就编不出好的程序。（）A.对B.错12【判断题】算法与程序没有关系。()A.对B.错13【判断题】我将来不进行软件开发，所以学习算法没什么用。()A.错B.对14【判断题】gcd(m,n)=gcd(n,mmodn)并不是对每一对正整数(m,n)都成立。()A.错B.对15【判断题】既然程序设计语言可以描述算法，所以算法就是程序。()A.错B.对第二章单元测试1【判断题】并不是所有的算法，规模更大的输入需要更长的运行时间。()A.错B.对2【判断题】算法效率分析框架主要关心一个算法的基本操作次数的增长次数，并把它作为算法效率的主要指标。()A.错B.对3【判断题】当算法由两个连续执行部分组成时，该算法的整体效率等于较大增长次数＋较小增长次数。()A.错B.对4【判断题】O表示算法效率的下界。()A.对B.错5【单选题】(2分)4个盘子的汉诺塔，至少要执行移动操作的次数为()。A.17次B.11次C.13次D.15次6【单选题】(2分)Fibonacci数列的第8项为()。A.3B.21C.34D.137【单选题】(2分)若f(n)=+4n+2，则有f(n)∈（）A.O()B.O(n)C.O(1)D.O()第三章单元测试1【单选题】(2分)以下哪种排序用的是蛮力法？()A.合并排序B.计数排序C.拓扑排序D.冒泡排序2【单选题】(2分)集合｛Ａ，Ｂ｝的幂集合为()。A.{｛Ａ，Ｂ｝，｛Ａ｝，｛Ｂ｝，Φ}B.｛Ａ｝，｛Ｂ｝，ΦC.{｛Ａ｝，｛Ｂ｝}D.｛Ａ｝，｛Ｂ｝3【单选题】(2分)可以用（）求得一个图的连通分量。A.拓扑排序B.回溯C.分支界限D.深度优先查找4【判断题】蛮力法是一种简单直接地解决问题的方法。()A.对B.错5【判断题】对于同样的输入，选择排序和冒泡排序比较的次数是一样的。()A.对B.错6【判断题】蛮力字符串匹配算法将文本中的字符从右向左比较不会比从左向右比较更有优势。()A.错B.对7【判断题】最近对问题的输入规模为集合中点的个数n，基本操作是计算欧几里得距离，该问题的蛮力算法的时间复杂度除依赖于n外，还依赖于输入。()A.对B.错8【判断题】如果S是凸的，它的凸包是它本身。()A.错B.对9【判断题】一根直线将平面分成两个半平面，其中一个半平面中的点都满足：ax+by≥c，而另一个半平面的点都满足：ax+by≥c。()A.错B.对10【判断题】蛮力法生成整数1,2,…,n的全部排列的算法时间复杂度为O(n!)。()A.错B.对第四章单元测试1【判断题】减治法的减常量形式中，每次迭代总是从实例中减去相同的常量。但是这个常量并不固定，减多少无迹可寻。()A.错B.对2【判断题】减治法的减常因子技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子，在大多数应用中，这个常数因子等于1。()A.对B.错3【判断题】插入排序的比较和移动次数不只依赖于输入规模，还依赖于特定输入。()A.对B.错4【判断题】插入排序和拓扑排序都属于减治法的减常量形式。()A.错B.对5【判断题】执行一次DFS遍历，并记住顶点变成死端(即退出遍历栈)的顺序。该次序就是拓扑排序一个解。()A.错B.对6【单选题】(2分)求n个数的最小值至少需要（）次比较A.n-2B.n+1C.n-1D.n7【单选题】(2分)有9只杯口向上的杯子放在桌子上，每次将其中四只杯子同时“翻转”，使其杯口向下，经过()次“翻转”后，使9只杯口全部向下？A.都不对B.8C.10D.98【单选题】(2分)下列()不是对数据表{26，99，20，45，15，29，65，35，20，72}用冒泡法进行排序的中间结果。A.15202629203545657299B.20261529456520357299C.20152629352045657299D.262045152965352072999【单选题】(2分)5门必修课的一个集合{C1,C2,C3,C4,C5}，一个在职学生必须在某个阶段修完这几门课程。可以按照任何次序学习这些课程，只要满足下面的先决条件：C1和C2没有任何先决条件，修完C1和C2才能修C3，修完C3才能修C4，而修完C3和C4才能修C5，这个学生每个学期只能修一门课程，该学生不能按照()顺序学习这门课程。A.（C1C2C3C4C5）和（C2C1C3C4C5）B.C2C1C3C4C5C.C2C3C4C5C1D.C1C2C3C4C5第五章单元测试1【单选题】(2分)两个十进制n位数的积最少能拥有()位数。A.2n-1B.n-1C.2n-2D.n2【单选题】(2分)快速排序算法是利用()的算法。A.回溯法B.贪心法C.动态规划法D.分治法3【单选题】(2分)以下不可以使用分治法求解的是（）A.查找问题B.最近对问题C.0/1背包问题D.排序问题4【单选题】(2分)Strassen矩阵乘法是利用（）实现的算法A.分治法B.动态规划法C.回溯法D.贪心法5【单选题】(2分)用分治法解决最近点对问题的时间复杂度为（）A.O(logn)B.O(n)C.O()D.O(nlogn)6【单选题】(2分)快速排序是稳定的吗？()A.不是B.不一定C.是7【判断题】合并排序是一个稳定的排序算法。（）A.错B.对8【判断题】对二叉搜索树进行前序遍历即可得到一个有序数列。（）A.错B.对9【判断题】在分治法中，将一个问题划分为同一类型的若干子问题，子问题最好规模相同。（）A.对B.错10【判断题】应用分治法的两个前提是问题的可分解性和解的复杂性。（）A.对B.错11【判断题】能否利用分治法完全取决于该问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（）A.对B.错12【判断题】对于分治法，子问题只能细分一次，不能继续细分。（）A.错B.对13【单选题】(2分)一个严格递增的数组是快速排序的()。A.最优输入B.都不是C.最差输入第六章单元测试1【单选题】(2分)１、对数组中的元素先进行合并排序，再检查连续元素来检验数组中元素的唯一性，直到找到两个相等的元素或所有相邻的元素都检查一遍为止。该算法的复杂性是（）。A.O()B.O(2n)C.O（nlogn）D.O(logn)2【单选题】(2分)AVL树的旋转中，存在()种旋转.A.右左双转B.右单转C.其他选项都对D.左单转3【单选题】(2分)有3对夫妻过河，但是只有一条能容纳两人的小船，这3对夫妻中，丈夫爱吃醋，妻子不在自己身边时，不允许有其他男人在妻子身边。那么这3对夫妻能过河吗？（）A.能B.不能C.不确定4【判断题】查找n个可排列数值时，折半查找通常比顺序查找快。（）A.错B.对5【判断题】双向右左旋转是在一个新的键插入到树的右子女的左子树后发生的，在插入以前，这棵树的根的平衡因子是-1。()A.对B.错6【判断题】2-3树要求树中的所有叶子必须位于同一层。()A.错B.对7【判断题】一个具有最多节点的高度为h的2-3树是一棵全部由2节点构成的满树。（）A.错B.对8【判断题】最大堆的根总是堆的最大元素。（）A.错B.对9【判断题】对于相同的输入，自顶向下算法和自底向上算法产生完全相同的堆。()A.对B.错10【单选题】(2分)如果用合并排序做预排序，折半查找做查找，要做()次查找才能使得一个由1000000个元素组成的数组所做的预排序是有意义的。A.20B.40C.30D.10第七章单元测试1【判断题】计数排序算法在一种情况下还是卓有成效的，即待排序元素的值都来自一个已知的小集合。()A.对B.错2【判断题】Horspool算法的最差效率Θ(mn)()A.错B.对3【单选题】(2分)用Horspool算法在一个1000个0构成的二进制文本中查找00001时，要进行（）次字符比较。A.996B.995C.5*996D.5*9954【单选题】(2分)()不使用额外的存储来交换两个变量的数值，例如m和n.A.不确定B.可以C.不可以5【单选题】(2分)在Horspool字符串匹配算法中，输入0001是000000000000的最差输入吗？（）A.不是B.是C.不确定6【单选题】(2分)对于模式BAOBAB，A,B,O的移动距离分别为()。A.1,2,3B.2,1,3C.3,1,2D.2,3,1第八章单元测试1【单选题】(2分)币值最大化问题的一个实例是5,1,2,10,16，则最大金额为（）A.32B.23C.17D.202【单选题】(2分)Floyd算法的时间效率是（）A.O()B.O()C.O(n)D.O(logn)3【单选题】(2分)贪心算法与动态规划算法的主要区别是（）。A.构造最优解B.贪心选择性质C.最优子结构D.定义最优解4【判断题】动态规划法分解的子问题是有重叠的，分治法分解的子问题是相互独立的。（）A.对B.错5【判断题】动态规划法不是随机化算法。（）A.对B.错6【判断题】动态规划算法适用于解具有某种最优性质的问题。（）A.对B.错第九章单元测试1【单选题】(2分)不属于贪婪技术的算法是（）A.Dijkstra算法B.Floyd算法C.Kruskal算法D.哈夫曼编码2【单选题】(2分)如果e是加权连通图中权重最小的边，它（）图的一棵最小生成树的边。A.不一定是B.必定不是C.必定是3【单选题】(2分)对于包含负权重边的图，Prim算法()正确工作。A.不一定能B.不能C.能D.不确定4【判断题】如果加权连通图中每条边的权重是都是互不相同的，该图必定只有一棵最小生成树。()A.对B.错5【判断题】哈夫曼编码频率相同的所有字符都具有相同的码长。()A.对B.错6【判断题】频率较高的字符的码长不一定小于频率较低的字符的码长。()A.对B.错7【判断题】Prim算法总是通过把离树中顶点最近的顶点包含进来，从而生成一棵最小生成树。()A.错B.对8【判断题】对于包含负权重边的图，Kruskal算法可能会无效。()A.对B.错9【判断题】对于包含负权重边的图，Dijkstra算法也是正确有效的。()A.对B.错10【判断题】Dijkstra算法是解决单起点最短路径问题的。()A.对B.错11【判断题】Dijkstra算法和Floyd算法采用了相同的算法设计技术。()A.对B.错12【判断题】Dijkstra算法和Floyd算法都是是解决完全最短路径问题的。()A.错B.对13【判断题】贪婪算法在对问题求解时，总是做出当前看来最好的选择。()A.错B.对14【判断题】哈夫曼编码的压缩率通常在20%～80%之间。()A.错B.对15【判断题】哈夫曼编码总是最优前缀码。()A.错B.对第十章单元测试1【单选题