雨课堂学堂在线学堂云《算法分析与设计(西北工业)》单元测试考核答案

第1题一个算法产生____量作为输出。正确答案：:至少一个第2题算法是解决问题的一种方法或过程，它是由若干条指令组成的____序列。正确答案：:有穷第3题算法中可以存在某些被无限次执行的指令。第4题算法中每条指令的执行次数有限。第5题一个算法可以有0个量作为输入。第6题一个算法可以有0个量作为输出。第7题算法的正确性证明方法主要有：归纳法和____正确答案：:反证法第8题算法设计的描述有:自然语言，流程图，____正确答案：:伪代码第9题一个算法应该具有以下5个方面的特征：输入、输出、确定性、有限性、____。正确答案：:可行性第10题算法是解决问题的一种方法或过程，它是由若干条____组成的有穷序列。正确答案：:指令第11题科技殿堂里陈列着两颗熠熠生辉的宝石，一颗是微积分，另一颗就是____。正确答案：:算法第1题O(f(n))*O(g(n))=O(f(n)*g(n)).第2题O(f(n))+O(g(n))=O(f(n)+g(n)).第3题O(f(n))+O(g(n))=O(max{f(n),g(n)}).第4题如果f=Θ(g)和g=Θ(h)，那么f=Θ(h).第5题如果f=Ω(g)且g=Ω(h)，那么f=Ω(h).第6题如果f=O(g)且g=O(h)，那么f=O(h).第7题渐近意义下的记号ω表示____。正确答案：:下界第8题渐近意义下的记号o表示____。正确答案：:上界第9题渐近意义下的记号Θ表示____。正确答案：:渐近紧界第10题渐近意义下的记号O表示____。正确答案：:渐近上界第11题算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为____，需要的空间资源的量称为空间复杂性。正确答案：:时间复杂性迭代法作业第1题倒推法：是对某些特殊问题所采用的违反通常习惯的，从____推解问题的方法。正确答案：:后向前第2题迭代法有两种：____和倒推法。正确答案：:递推法第3题利用迭代算法策略求解问题，设计工作主要有三步：确定迭代模型、____、对迭代过程进行控制。正确答案：:建立迭代关系第4题迭代法也称“辗转法”，是一种不断用变量的旧值递推出____的解决问题的方法。正确答案：:新值蛮力法作业第1题枚举法解决问题，可从两个方面进行算法设计：找出枚举范围、____。正确答案：:找出约束条件第2题常用的蛮力策略主要是____、穷举搜索算法。正确答案：:枚举法第3题顺序查找采用的是蛮力法的思想。第4题插入排序采用的是蛮力法的思想。第5题冒泡排序采用的是蛮力法的思想。第6题选择排序采用的是蛮力法的思想。分治法基础知识作业第1题____是分治法中最常用的技术。正确答案：:递归第2题分治法的求解过程由以下三个阶段组成：____、求解子问题、合并正确答案：:划分第3题分治法分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。第4题递归是分治法中最常用的技术。分治法案例分析作业第1题通过预排序不可以降低最近点问题的复杂度第2题二分搜索的时间复杂度为O(log(n))。第3题二分搜索采用的是迭代的思想。第4题快速排序的时间复杂度为O(n*n)。第5题快速排序采用的是迭代法的思想。第6题二分搜索的时间复杂度为O(n)。第7题二分搜索采用的是分治法的思想。第8题快速排序的时间复杂度为O(nlog(n))。第9题快速排序采用的是分治法的思想。动态规划基础知识作业第1题动态规划算法的三个要素是：最优子结构、____、备忘录（表格）正确答案：:重叠子问题第2题动态规划的基本步骤主要有四步：找出____、建立递推方程，计算最优值，构造最优解正确答案：:最优子结构第3题动态规划中分解得到的子问题往往不是互相独立的。第4题动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。第5题动态规划基本思想是____已解决的子问题的解，在需要时再查找已求得的解，就可以避免大量重复计算，进而提升算法效率。正确答案：:保留动态规划案例分析作业第1题矩阵连乘问题不可以用动态规划求出最优解。第2题最长公共子序列问题可以用动态规划求出最优解。第3题01背包问题不可以用动态规划求出最优解。第4题电路布线问题可以用动态规划求出最优解。第5题动态规划法求解矩阵连乘问题采取的是至顶向下的方式。第6题备忘录法求解矩阵连乘问题采取的是至顶向下的方式。贪心法基本知识练习第1题贪心法每一步选择采取的是一种____的做法正确答案：:只顾眼前第2题贪心选择的性质通常可以通过归纳法证明，一般通过对算法步数归纳或通过对____归纳来证明正确答案：:问题规模第3题动态规划通常采用自底向上的方式求解各个子问题，而贪心算法通常采用____进行正确答案：:自顶向下第4题贪心法对于满足____和最优子结构性质的问题能够保障最优解正确答案：:贪心选择第5题贪心法对于所有的问题都能保障最优解活动安排问题练习第1题活动安排问题可以通过早完成的先开始贪心的方式得到问题最优解第2题活动安排问题可以通过占用时间少先开始贪心的方式得到问题最优解第3题活动安排问题可以通过早到早开始贪心的方式得到问题最优解第4题活动安排问题可以通过贪心法得到问题最优解最小生成树问题练习第1题Kruskal算法的最坏复杂度是O(elog(e))第2题Prim算法的最坏复杂度是O(n^2)第3题Prim算法一定比Kruskal算法效率低第4题Prim算法一定比Kruskal算法效率高第5题权值最小的边一定在某个最小生成树当中第6题与某个节点相关的权值最小的边一定在某个最小生成树当中第7题最小生成树问题可以用prim和____求解正确答案：:Prim第8题最小生成树问题可以用____和____求解正确答案：:Prim正确答案：:Kruskal回溯法基础知识练习第1题使用回溯法时，如果变量不满足多米诺性质，可以通过____和变量替换解决。正确答案：:调整变量顺序第2题回溯法搜索解空间树主要以深度优先搜索方式为主。第3题回溯法避免无效的搜索策略有____和约束函数正确答案：:界限函数第4题回溯法总能找到问题的最优解第5题回溯法的基本思想是，当一条路走到尽头时，____一步或若干步，从另外一个状态出发正确答案：:后退第6题回溯法也叫____正确答案：:试探法第7题回溯法是问题的通用解法第8题解向量需要满足____和____才能称为解正确答案：:显示约束正确答案：:隐式约束第9题两类典型的解空间树分别为____,____正确答案：:子集树正确答案：:排列树第10题只有满足____性质，才能用回溯法求解正确答案：:多米诺第11题回溯法结点的状态有3种分别是白结点____,____正确答案：:灰结点正确答案：:黑结点回溯法案例分析练习第1题n皇后问题迭代求解回退到上一行时需要从上次探索的下一个位置开始第2题n皇后问题迭代求解向下探索时需要从下一行的首个位置开始第3题n皇后问题的解向量（x1,x2,…,xn）需要满足的显示约有xi=1,2,…n第4题n皇后问题的解向量（x1,x2,…,xn）需要满足以下的隐式约束有Axi不等于xkB|i-j|不等于|xi-xj|Cxi到xi+1有边正确答案：AB第5题判断一个高精度数是否能够被整除可以通过计算高精度的数值保存到大整数变量中然后取余第6题高精度数可以通过数组保存第7题n个城市的货郎担问题的解向量（x1,x2,…,xn）需要满足以下的隐式约束有Axi到xi+1有边Bxn到x1有边Cxi不等于xkDxi到xi+2有边正确答案：ABC第8题n个城市的货郎担问题的解空间规模是n^(n-1)第9题n个城市的货郎担问题的解空间规模是A（n-1）!Bn^2Cn^nDn^(n-1)第10题01背包问题的解空间属于子集树第11题货郎担问题的解空间属于子集树第12题货郎担问题的解空间属于A子集树B排列树第13题01背包问题的解空间属于A子集树B排列树分支限界法基础知识练习第1题对于求最大值的优化问题，如果节点v的上界UB(v)小于等于当前最好界cBest，则节点v可以加入黑名单，不再对其搜索第2题对于求最大值的优化问题，如果根节点的上界等于下界，则直接结束，输出对应于下界的解即可第3题对于求最小值的优化问题，如果根节点的上界等于下界，则直接结束，输出对应于上界的解即可第4题对于求最小值的优化问题，如果节点v的下界LB(v)大于等于当前最好界cBest，则节点v可以加入黑名单，不再对其搜索第5题如果所有叶子节点的最小效益值____LB(v)，则LB(v)为节点v的下确界正确答案：:等于第6题如果所有叶子节点的最小效益值等于LB(v)，则LB(v)为节点v的____正确答案：:下确界第7题下界越大越好第8题上界越大越好第9题如果所有叶子节点的最大效益值____UB(v)，则UB(v)为节点v的上确界正确答案：:等于第10题最大优先队列采用____实现，最小优先队列采用____实现正确答案：:最大堆正确答案：:最小堆第11题分支限界算法中常见的两种分支搜索法或选择节点方式为（）。AFIFOB优先队列式CFIFOD随机选择正确答案：AB第12题分支限界算法的结束条件是找到所需的解或活节点列表为____。正确答案：:空第13题在分支限界法中，每个活结点只有____次机会成为扩展结点（填阿拉伯数字）正确答案：:1第14题分支限界法主要以深度优先的方式搜索解空间树装载问题练习第1题批作业调度问题的结点需要包含的信息有A下界B层C作业调度方案正确答案：ABC第2题作业调度问题的上界可以用贪心法求得第3题货郎担问题的上界可以用贪心法求得第4题用优先队列实现装载问题，每个活节点必需要记录哪些信息A上界B层C父节点D是否为左儿子正确答案：ABCD第5题用FIFO实现不需要给出装载方案的装载问题，每个活节点必需要记录哪些信息A当前载重B当前层数C物品选择情况遗传算法练习第1题遗传算法中解的好坏用____来评价正确答案：:适应度函数第2题遗传算法要实现全局收敛，必须要有____操作来防止最优解遗失正确答案：:保优第3题轮盘赌算子的思想是个体被选中的概率与其适应度值大小成____正确答案：:正比第4题轮盘赌算子又称为____算子，它的思想是个体被选中的概率与其适应度值大小成正比正确答案：:比例选择第5题适应度函数的设计标准是：适应度函数值____，解的质量越好正确答案：:越大第6题适应度函数的设计标准是：适应度函数值越小，解的质量越好第7题把基因型变成表现型的过程叫____，把表现成变成基因型的过程叫____正确答案：:解码正确答案：:编码第8题0到4的闭区间，求解结果精确到6位小