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

奥鹏作业答案

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

一、单选题：
1.实现最长公共子序列利用的算法是          (满分:5)
    A. 分治策略
    B. 动态规划法
    C. 贪心法
    D. 回溯法
2.下面问题哪个不能使用贪心法解决          (满分:5)
    A. 单源最短路径问题
    B. N皇后问题
    C. 最小花费生成树问题
    D. 背包问题
3.下列算法中通常以自底向下的方式求解最优解的是          (满分:5)
    A. 分治法
    B. 动态规划法
    C. 贪心法
    D. 回溯法
4.合并排序算法是利用          (满分:5)
    A. 分治策略
    B. 动态规划法
    C. 贪心法
    D. 回溯法
5.Strassen矩阵乘法是利用什么实现的算法          (满分:5)
    A. 分治策略
    B. 动态规划法
    C. 贪心法
    D. 回溯法
6.下列算法中不能解决0/1背包问题的是          (满分: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.分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。          (满分:5)
    A. 错误
    B. 正确
7.分支限界法与回溯法的求解目标相同          (满分:5)
    A. 错误
    B. 正确
8.设计动态规划算法的主要步骤有5步          (满分:5)
    A. 错误
    B. 正确
9.任何可用计算机求解的问题所需的时间都与其规模无关。          (满分:5)
    A. 错误
    B. 正确
10.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。          (满分:5)
    A. 错误
    B. 正确
本内容由易百网整理