北语17春《算法与数据分析》作业2答案资料

网院作业

17春《算法与数据分析》作业2
北语

一、单选题：
1.分支限界法解最大团问题时，活结点表的组织形式是          (满分:5)
    A. 最小堆
    B. 最大堆
    C. 栈
    D. 数组
2.贪心算法与动态规划算法的共同点是          (满分:5)
    A. 重叠子问题
    B. 构造最优解
    C. 贪心选择性质
    D. 最优子结构性质
3.蒙特卡罗算法是以下的哪种          (满分:5)
    A. 分支界限算法
    B. 概率算法
    C. 贪心算法
    D. 回溯算法
4.下面是贪心算法的基本要素的是          (满分:5)
    A. 重叠子问题
    B. 构造最优解
    C. 贪心选择性质
    D. 定义最优解
5.下面关于NP问题说法正确的是          (满分:5)
    A. NP问题都是不可能解决的问题
    B. P类问题包含在NP类问题中
    C. NP完全问题是P类问题的子集
    D. NP类问题包含在P类问题中
6.下列哪一种算法不是随机化算法          (满分:5)
    A. 蒙特卡罗算法
    B. .拉斯维加斯算法
    C. .动态规划算法
    D. .舍伍德算法
7.矩阵连乘问题的算法可由什么设计实现          (满分:5)
    A. 分支界限算法
    B. 动态规划算法
    C. 贪心算法
    D. 回溯算法
8.舍伍德算法是以下的哪一种          (满分:5)
    A. 分支界限算法
    B. 概率算法
    C. 贪心算法
    D. 回溯算法
9.下面哪种函数是回溯法中为避免无效搜索采取的策略          (满分:5)
    A. 递归函数
    B. .剪枝函数
    C. 。随机数函数
    D. .搜索函数
10.最长公共子序列算法利用的算法是          (满分:5)
    A. 分支界限法
    B. 动态规划法
    C. 贪心法
    D. 回溯法
三、判断题：
1.大整数乘积算法是用分治法来设计的。          (满分:5)
    A. 错误
    B. 正确
2.拉斯维加斯算法找到的解不一定是正确解          (满分:5)
    A. 错误
    B. 正确
3.矩阵连乘问题的算法可由动态规划设计实现          (满分:5)
    A. 错误
    B. 正确
4.以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。          (满分:5)
    A. 错误
    B. 正确
5.贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。          (满分:5)
    A. 错误
    B. 正确
6.快速排序算法不是基于分治策略的一种排序算法。          (满分:5)
    A. 错误
    B. 正确
7.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。          (满分:5)
    A. 错误
    B. 正确
8.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。          (满分:5)
    A. 错误
    B. 正确
9.贪心选择性质是贪心算法可行的第一个基本要素，但不是贪心算法与动态规划算法的主要区别          (满分:5)
    A. 错误
    B. 正确
10.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法          (满分:5)
    A. 错误
    B. 正确
本内容由易百网整理