《北语16秋《算法与数据分析》作业4》由会员分享，可在线阅读，更多相关《北语16秋《算法与数据分析》作业4（3页珍藏版）》请在金锄头文库上搜索。
1、一、单选题（共 10 道试题，共 50 分。 ） V 1. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 . 重叠子问题 . 最优子结构性质 . 贪心选择性质 . 定义最优解标准答案： 2. 0-1 背包问题的回溯算法所需的计算时间为 . O（n2n） . O（nlogn） . O（2n） . O（n）标准答案： 3. 实现大整数的乘法是利用的算法 . 贪心法 . 动态规划法 . 分治策略 . 回溯法标准答案： 4. 背包问题的贪心算法所需的计算时间为 . O（n2n） . O（nlogn） . O（2n） . O（n）标准答案： 5. 贪心算法与动态规划算法的主要区别是 . 最优
2、子结构 . 贪心选择性质 . 构造最优解 . 定义最优解标准答案： 6. 在下列算法中得到的解未必正确的是 . 蒙特卡罗算法 . 拉斯维加斯算法 . 舍伍德算法 . 数值概率算法标准答案： 7. 广度优先是什么的一种搜索方式 . 分支界限法 . 动态规划法 . 贪心法 . 回溯法标准答案： 8. 采用最大效益优先搜索方式的算法是. 分支界限法 . 动态规划法 . 贪心法 . 回溯法标准答案： 9. 采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算 法的时间复杂度为 . O（n2n） . O（nlogn） . O（2n） . O（n）标准答案： 10. 关于分支限界法
3、的搜索策略描述错误的是 . 在扩展结点处，先生成其所有的儿子结点（分支） . 从当前的活结点表中选择上一个扩展结点。 . 为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值 （限界） . 根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间 上有最优解的分支推进，以便尽快地找出一个最优解。标准答案：二、判断题（共 10 道试题，共 50 分。 ） V 1. 设计动态规划算法的主要步骤不包括根据计算最优值时得到的信息，构造最优解 . 错误 . 正确标准答案： 2. 分支限界法与回溯法完全不同 . 错误 . 正确标准答案： 3. 分治法与动态规划
4、法的不同点是：适合于用动态规划法求解的问题，经分解得到的子问 题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的 . 错误 . 正确标准答案： 4. 队列式(FIFO)分支限界法是指按照队列先进先出（FIFO）原则选取下一个节点为扩展节 点 . 错误 . 正确标准答案： 5. 贪心算法的基本要素是贪心选择质和最优子结构性质 . 错误 . 正确标准答案： 6. 常见的分支限界法的算法框架有 3 种 . 错误 . 正确标准答案： 7. 分治法的基本思想时将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题 互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的 解 . 错误 . 正确标准答案： 8. 该问题的规模缩小到一定的程度就可以容易地解决是分治法的一个特征 . 错误 . 正确标准答案： 9. 分支限界法与回溯法都是一种在问题的解空间树 T 中搜索问题解的算法 . 错误 . 正确标准答案： 10. 回溯法中常见的两类典型的解空间树是子集树和排列树 . 错误 . 正确标准答案：
