雨课堂学堂在线学堂云《算法设计与分析（北京交通）》单元测试考核答案

第1题对于一个算法而言，（）是第一位的。A有效性B最优性C健壮性D正确性第2题要求算法必须可以终止指的是算法的（）。A有效性B有限性C健壮性D正确性第3题要求算法每一步都必须严格明确、不能含混指的是算法的（

）。A有效性B有限性C明确性D正确性第4题以下时间复杂度里，（）在计算复杂性理论中被称为是“慢”的？An100BnlognC2nDO(1)第5题可以使用数组或链表方式实现线性表，其中（

）方式适合进行直接访问/随机访问。A数组B链表第6题度量算法的时间复杂度一般考察算法在（

）情况下的运行时间和在（

）情况下的运行时间。A最差；平均B最佳；平均C最差；最佳第7题假设f(n)和g(n)是定义在非负实数集合上的取值为正数的增函数。如果要表达f(n)的增长不比g(n)快，那么可以写为（

）。Af(n)ÎO(g(n))Bf(n)ÎW(g(n))Cf(n)ÎQ(g(n))第8题若，则（）。Af(n)ÎO(g(n))Bf(n)ÎW(g(n))Cf(n)ÎQ(g(n))第9题设f(n)=1.01n，g(n)=n1000，则有（

）。Af(n)ÎO(g(n))Bf(n)ÎW(g(n))Cf(n)ÎQ(g(n))第10题如果一个算法的运行时间是（

）的，则可以称该算法是有效的。A多项式B指数C对数D阶乘正确答案：AC第1题在计算机程序设计中，若一个函数在其函数体内又直接调用了自身，则称之为（

）。A递归B迭代第2题一个递归算法（

）是不断地调用自身。A必然B有可能C不可能第3题递归算法一般都是（

）的。A自顶而下B自底而上第4题以下算法中，（

）不是基于分治策略的。A归并排序B快速排序CPrim算法D二分查找第5题分支策略的基本框架分为三个主要步骤，依次是（

）。A分；治；合B分；合；治C治；合；分D合；分；治第6题若T(n)=9T(n/3)+n,T(1)=1，则T(n)Î（

）。AT(n)ÎQ(n)BT(n)ÎQ(n2)CT(n)ÎQ(n2logn)第7题二分查找在最差情况下时间复杂度和平均情况下时间复杂度都是O（

）。Alog2nBnCn2第8题猜数问题在最差情况下时间复杂度是O（

）。AnBlog2nCn2第9题归并排序算法的执行过程中（

）使用临时数组。A不需要B需要第10题归并排序的时间复杂度是O（

）。AnlognBnClogn第11题两个长度为n的大数相加的算法的时间复杂度是W（

）。AlognBnCnlogn第12题基本的快速排序算法在最差情况下的时间复杂度是O（

）。AnlognBnClognDn2第13题基本的快速排序算法在平均情况下的时间复杂度是O（

）。AnBlognCnlognDn2第14题快速排序算法的执行过程中（

）使用临时数组。A需要B不需要第15题选择问题的随机化算法的期望时间复杂度是O（

）。AnlognBnClogn第3章作业第1题如果现在有面额分别为1元、3元、4元的三种硬币，收银员算法（

）确保获得最优解。A能够B不能够第2题对于计件的装载问题，采用的贪婪策略是在（

）的条件下（

）优先。A船上还有容量；轻的集装箱B船上还有容量；重的集装箱C无需任何；轻的集装箱D无需任何；重的集装箱第3题对于活动选择问题，采用的贪婪策略是（

）。A最早开始时刻优先B最早结束时刻优先C最短持续时间优先D最少冲突数量优先第4题对于活动安排问题，采用的贪婪策略是（

）。A最早开始时刻优先B最早结束时刻优先C最短持续时间优先D最短持续时间优先第5题在0-1背包问题中，有若干物品，每件物品有各自的重量和价值，而且背包有一个容量限制。希望在不超过背包容量限制的前提下，使得选取的物品的总价值达到最大。如果使用贪婪策略设计解决0-1背包问题的算法，以下论述中（

）是正确的。A优先选择重量小的物品装入背包（如果可以装下的话），可以确保得到最优解。B优先选择价值高的物品装入背包（如果可以装下的话），可以确保得到最优解。C优先选择比值[价值/重量]大的物品装入背包（如果可以装下的话），可以确保得到最优解。DA、B和C的三种策略都不能确保得到最优解。第6题对于最小延迟调度问题，采用的贪婪策略是（

）。A最短任务优先B紧急任务优先C最小松弛时间优先第7题Pirm算法采用的贪婪策略是选择（

）的条件下（

）的边。A恰有一端属于已选择的子树；权值最小B恰有一端属于已选择的子树；权值最大C和已选择的边不能构成回路；权值最小D和已选择的边不能构成回路；权值最大第8题Kruskal算法采用的贪婪策略是选择（

）的条件下（

）的边。A恰有一端属于已选择的子树；权值最大B恰有一端属于已选择的子树；权值最小C和已选择的边不能构成回路；权值最大D和已选择的边不能构成回路；权值最小第9题10个顶点的连通图的支撑树有9条边。第10题在Dijkstra算法中，顶点的标签值在（

相邻顶点被加入“已探索顶点集合”中

）时可能发生变化。第11题Dijkstra算法（

）应用在边存在负数权值的图。A能够B不能够第12题一般而言，Huffman编码是（

）。A定长编码B变长编码第13题当使用堆实现优先级队列时，Huffman编码算法的时间复杂度是O（

）。AnlognBnClognDn2第14题当使用堆实现优先级队列时，求最优二路归并模式算法的时间复杂度是O（

）。An2BlognCnDnlogn第15题最大价值-重量比优先的贪婪策略对于（

）背包问题可以确保得到最优解。A分数B0-1第4章作业第1题递归实现的求斐波那契数列算法效率极低的根本原因在计算过程中存在（

大量重复计算

）。第2题给定面值分别为1元、5元、7元、10元的硬币（每种都有足够多枚），用Find[n]表示找零n元所需的最少硬币数，则关于它的递推式是Find[n]¬（

min{Find[i-1]+1,Find[i-5]+1,Find[i-7]+1,Find[i-10]+1}

）。第3题动态规划和分治策略都是将一个问题分解为多个子问题，并将子问题的解结合起来形成原问题的解。但是，动态规划面对的可能是（

存在重叠

）的子问题。第4题5，6，7，1，2，8的最长单调增子序列的长度为（

）。A3B4C5D6第5题在关于最长单调增子序列的动态规划算法的递推式中，“XXX”应为（

）。AL(j)-1BL(j)CL(j)+1第6题-2,11,-4,13,-5,-2的最大子段和为（

）。A18B19C20D21第7题-2,-11,-4,-13,-5,-2的最大子段和为（

）。A0B-2C-7D-4第8题令C(j)表示必须以元素aj结尾的最大子段和（允许为负数值），在关于最大子段和的动态规划算法的递推式中，“XXX”应为（

），“YYY”应为（

）。AC(j-1)+aj；ajBC(j-1)+aj；aj+1CC(j-1)；ajDC(j-1)；aj+1第9题在投资问题的动态规划算法中，用Fk(x)表示对前k个理财产品进行共计x元的投资所能取得的最大收益，xk(x)表示在Fk(x)中投资给理财产品k的钱数，则递推式中，“XXX”应为（

）。第10题abcd和dabc的最长公共子序列的长度为（

）。A1B2C3D4第11题abcd和cdab的最长公共子序列的长度为（

）。A1B2C3D4第12题令len(i,j)表示X[1...i]和Y[1...j]的LCS的长度，若X[i]=Y[j]，则len(i,j)=（

）。Alen(i,j-1)+1Blen(i-1,j)+1Clen(i-1,j-1)Dlen(i-1,j-1)+1第13题在矩阵链乘积问题的动态规划算法中，假定给定了矩阵的序列A1,A2,…,An，其中Ai为Pi-1´Pi阶矩阵，将Ai×Ai+1×…×Aj的乘积记做Ai..j，令m(i,j)表示计算Ai..j的最优方式的元素乘法总次数。当i<j时，递推式m(i,j)=min{m(i,k)+m(k+1,j)+■■■}中，“■■■”应为（

Pi´Pk´Pj

）。第14题在最优二叉查找树问题的动态规划算法中，假定给定了n个不同的键值k1,k2,…,kn，每个键值ki被访问的概率为pi，记T(i,j)表示对应于键值ki,…,kj（及其相应的查找概率）的最优二叉查找树，并令C(i,j)表示此时成功查找的（最优）期望开销（比较次数）。当i≤j时，递推式C(i,j)=C(i,s-1)+C(s+1,j)+(■■■)中，“■■■”应为（

pi+…+pj

）。第15题在求解“跳棋棋盘”问题的动态规划算法中，假设n´n的方格棋盘中第i行第j列的方格的开销为c(i,j)，定义函数q(i,j)为到达方格(i,j)的最小总开销。当2≤i≤n-1时，递推式定给定了n个不同的键值k1,k2,…,kn，每个键值ki被访问的概率为pi，记T(i,j)表示对应于键值ki,…,kj（及其相应的查找概率）的最优二叉查找树，并令C(i,j)表示此时成功查找的（最优）期望开销（比较次数）。q(i,j)=min(q(i-1,j-1),q(i-1,j),▲▲▲)+■■■中，“▲▲▲”应为（

），“■■■”应为（

）。Aq(i-1,j+1)；c(i,j)Bq(i-1,j)；c(i,j)Cq(i,j+1)；c(i,j)Dq(i,j)；c(i,j)第5章作业第1题在回溯法中，“剪枝”表示（

）。A分支语句不再执行B进行一个称作“剪枝”的程序动作第2题在n-皇后问题的回溯算法中，当对第i+1行的皇后位置进行尝试后，如满足第i+1行的皇后（

与之前某行的皇后处于同一列

）或者第i+1行的皇后与之前某行的皇后处于同一斜线的条件时，则进行回溯。第3题在子集和问题的回溯算法中，如果要求的总和是75，目前已经选了值分别是20和13的两个元素，则余下的元素总值之和满足（

大于42

）的条件时，进行回溯。第4题在顶点着色问题的回溯算法中，当对第i+1个顶点进行着色尝试后，如满足（

对第i+1个顶点进行的尝试着色是否与之前某个顶点同色且相邻（之间存在边）

）的条件时，则进行回溯。第5题在哈密顿回路问题的回溯算法中，当尝试第i+1个顶点后（i<n时），如满足（

第i+1个顶点与之前已确定的第i个顶点之间存在边

）或第i+1个顶点与之前的顶点有相同者的条件时，则进行回溯。第6题第i+1个顶点与之前已确定的第i个顶点之间不存在边A求合法解的B求最优解的第7题当使用分支限界法求最小值时，应估计（

）。A上界B下界第8题在最短道路问题的分支限界算法中，以（

）的权值作为估界函数。A最短边B最长边第9题在装载问题中，如果车的总容量是80，目前已经取了两个物品，重量分别是25和17，当前的最优解为78,则余下的物品总重量之和满足（

小于或等于36

）条件时，进行回溯。第10题在0-1背包问题中，如果背包总容量是100，目前已经取了两个物品，重量分别是25和17，余下的物品中价值-重量比的最大值为3；那么，按照估值方法一，至多还能获得（

）的价值。A171B172C173D174第6章作业第1题以下关于NP问题的说法中，（）目前确定是正确的。ANP问题都是不可能解决的问题BP类问题包含在NP问题中CNP完全问题是P类问题的子集DNP类问题包含在P类问题中第2题假定X,Y,Z都是判定性问题且X£PY，Y£PZ，则以下说法中（）是不正确的。（X£PY意为X可多项式时间归约到Y）A若Y可以在多项式时间内求解，则X也可以在多项式时间内求解B若X可以在多项式时间内求解，则Y也可以在多项式时间内求解C若X不能在多项式时间内求解，则Y也不能在多项式时间内求解DX£PZ第3题对于下列NP完全性的表述中，（）目前确定是正确的。A若存在一个NP类的问题可以被一个多项式时间复杂度的算法解决，则P=NP。B所有NP-hard（NP困难）问题