《北语19秋《算法与数据分析》作业4参考答案》由会员分享，可在线阅读，更多相关《北语19秋《算法与数据分析》作业4参考答案（3页珍藏版）》请在金锄头文库上搜索。
1、19秋算法与数据分析作业4试卷总分:100 得分:100一、单选题 (共 10 道试题,共 50 分)1.矩阵连乘问题的算法可由什么设计实现A.贪心算法B.回溯算法C.动态规划算法D.分支界限算法答案:C2.下列随机算法中运行时有时候成功有时候失败的是A.蒙特卡罗算法B.舍伍德算法C.数值概率算法D.拉斯维加斯算法答案:D3.关于分支限界法的搜索策略描述错误的是A.根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。B.在扩展结点处，先生成其所有的儿子结点（分支）C.从当前的活结点表中选择上一个扩展结点。D.为了有效地选
2、择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界）答案:C4.分治法所能解决的问题一般具有的几个特征不包括A.该问题的规模缩小到一定的程度就可以容易地解决B.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质C.原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题D.利用该问题分解出的子问题的解不可以合并为该问题的解答案:D5.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的A.重叠子问题B.贪心选择性质C.最优子结构性质D.定义最优解答案:C6.下面不是分支界限法搜索方式的是A.深度优先B.最小耗费优先C.最大效益优先D.广度
3、优先答案:A7.二分搜索算法是利用什么实现的算法A.贪心法B.回溯法C.动态规划法D.分治策略答案:D8.备忘录方法是那种算法的变形A.贪心法B.回溯法C.动态规划法D.分治法答案:C9.背包问题的贪心算法所需的计算时间为A.O（nlogn）B.O（n2n）C.O（n）D.O（2n）答案:A10.使用分治法求解不需要满足的条件是A.子问题的解可以合并B.子问题必须是一样的C.子问题不能够重复D.原问题和子问题使用相同的方法解答案:B二、判断题 (共 10 道试题,共 50 分)11.该问题的规模缩小到一定的程度就可以容易地解决是分治法的一个特征答案:正确12.矩阵连乘问题的算法可由动态规划设计实现。答案:正确13.快速排序算法不是基于分治策略的一种排序算法。答案:错误14.舍伍德算法总能求得问题的一个解。答案:正确15.贪心算法的基本要素是贪心选择质和最优子结构性质答案:正确16.分支限界法与回溯法都是一种在问题的解空间树T中搜索问题解的算法答案:正确17.问题的最优子结构性质是该问题不可用动态规划算法或贪心算法求解的关键特征。答案:错误18.从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。答案:正确19.拉斯维加斯算法找到的解不一定是正确解。答案:错误20.回溯法是一种既带有系统性又带有跳跃性的搜索算法。答案:正确
