雨课堂学堂在线学堂云《算法设计与分析( 华北电力大)》单元测试考核答案

注：不含主观题第1题填空题(2分)图灵机模型的基本结构包括纸带，____,____。正确答案：:["读写头"]正确答案：:["有限状态自动机"]第2题单选题(1分)下面有关P问题，NP问题和NPC问题，说法错误的是（）A所有的P类问题都是NP问题BNP问题是指可以在多项式的时间里验证一个解的问题C若一个问题可以找到一个能在多项式的时间里解决它的算法，该问题就属于P问题DNPC问题不一定是个NP问题，只要保证所有的NP问题都可以约化到它即可第3题单选题(1分)T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是AT(n)=T(n-1)+1，T(1)=1BA.

T(n)=2n2C

T(n)=T(n/2)+1，T(1)=1DT(n)=3nlog2n第4题单选题(1分)下述算法时间复杂度为（）x=0；y=0；for(k=1；k<=n；k++)x++；for(i=1；i<=n；i++)for(j=1；j<=n；j++)y++；AnBn^2Cn^3D2^n第5题单选题(1分)衡量一个算法好坏的标准是A运行速度快B占用空间少C代码短D时间复杂度空间复杂度低第6题单选题(1分)下列关于算法的说法中正确的有（）。Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A1个B2个C3个D4个第7题填空题(1分)用主方法求解递推方程T(n)=3T(n/4)+nlognT(n)=Q(____)正确答案：:["nlogn"]第8题填空题(1分)用主方法求解递推方程T(n)=T(2n/3)+1T(n)=Q(____)正确答案：:["logn"]第9题填空题(2分)描述算法时间增长率上限用____符号，增长率下限用____符号表示。注：本课程中后续填空题中出现

幂用^表示；Q用Theta表示；Ω用Omega表示

；正确答案：:["O"]正确答案：:["Theta"]第2章习题第1题填空题(1分)在分治法处理中，实践证明，采用____思想划分子问题总是有较好的结果。正确答案：:["平衡"]第2题填空题(2分)改进分治算法的途径有____,____等正确答案：:["增加预处理"]正确答案：:["减少子问题的个数"]第3题填空题(1分)一个基于BSP模型的并行算法，假设有p台处理器，用于计算整数数组a[0..n-1]的所有元素之和，算法的时间复杂度为____。正确答案：:["O(n/p+p)"]第4题单选题(1分)以下不可以使用分治法求解的是（）。A求最大最小元素B棋盘覆盖问题C归并排序D0/1背包问题第5题单选题(1分)在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。A随机选择一个元素作为划分基准B取子序列的第一个元素作为划分基准C用中位数的中位数方法寻找划分基准D以上皆可行。但不同方法，算法复杂度上界可能不同第6题单选题(1分)分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。A问题规模相同，问题性质相同B问题规模相同，问题性质不同C问题规模不同，问题性质相同D问题规模不同，问题性质不同第3章习题第1题单选题(1分)最长公共子序列可以用（

）求解A分支界限法B动态规划法C贪心法D回溯法第2题填空题(2分)0/1背包问题中设：V(i,j)：前i个物品中能够装入承重量j的背包中的最大总价值。请将如下递推式填写完整：V(0,j)=0；V(i,0)=0；V(i,j)=V(i-1,j)//j<wiV(i,j)=max{____,____}//j>wi正确答案：:["V(i-1,j)"]正确答案：:["V(i-1,-wi)+vi"]第3题单选题(1分)备忘录/填表方法是（）算法的变形A分治法B动态规划法C贪心法D回溯法第4题单选题(1分)下列是动态规划算法基本要素的是（）A定义最优解B构造最优解C算出最优解D子问题重叠第5题单选题(1分)能采用动态规划求解的问题必须要满足的性质是A无后效性B贪心选择性质C子问题重叠D最优子结构第4章习题第1题填空题(2分)用贪心法求解下列0-1背包问题：给定M=10,(p1,…,p4)=(10,10,12,18)和(w1,…,w4)=(2,4,6,10),贪心策略为优先选取单位重量价值大的物品，找出其最佳解向量及取得的最大效益为____,____正确答案：:["1,1,0,0"]正确答案：:["20"]第2题单选题(1分)采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（）AO(n)BO(n2)CO(n3)DO(nlog2n)第3题单选题(1分)下面是贪心算法的基本要素的是（）A重叠子问题B贪心选择性质C定义最优解D构造最优解第4题单选题(1分)下面问题（）不能使用贪心法解决A单源最短路径问题n皇后问题Bn皇后问题C最小生成树问题D背包问题第5章习题第1题单选题(1分)关于回溯法以下叙述中不正确的是（）A回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B回溯法是一种既带系统性又带有跳跃性的搜索算法C回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径D回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯第2题填空题(3分)回溯法的解空间树有____,____和____正确答案：:["子集树"]正确答案：:["排列树"]正确答案：:["n叉树"]第3题填空题(3分)回溯法是一种____的穷举法，它采用了____搜索方式，求得问题的____或所有解正确答案：:["带剪枝"]正确答案：:["深度优先"]正确答案：:["最优解"]第4题单选题(1分)回溯法中用到的两种约束条件是()两种。A限界和限期Bx[k]和BiC显约束和隐约束D目标函数和约束函数第5题单选题(1分)回溯法的效率不依赖于下列哪些因素（）A确定解空间的时间后问题B满足显约束的值的个数C计算约束函数的时间D计算限界函数的时间第6题单选题(1分)下面（）函数是回溯法中为避免无效搜索采取的策略A递归函数B剪枝函数C随机数函数D搜索函数第6章习题第1题单选题(1分)优先队列式分枝限界法选取扩展结点的原则是（）A先进先出B后进先出C结点的优先级D随机第2题单选题(1分)采用最大效益优先搜索方式的算法是（）A分支限界法B动态规划法C贪心法D回溯法第3题单选题(1分)分支限界法求解0/1背包问题时，活结点表的组织形式是（）A小根堆B大根堆C栈D数组第4题单选题(1分)常见的两种分支限界法