北语17春《算法与数据分析》作业1答案资料
17春《算法与数据分析》作业1北语
一、单选题：
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.下面不是分支界限法搜索方式的是 (满分:5)
A. 广度优先
B. 最小耗费优先
C. 最大效益优先
D. 深度优先
6.最大效益优先是下列哪项的一种搜索方式 (满分:5)
A. 分支界限法
B. 动态规划法
C. 贪心法
D. 回溯法
7.分治法所能解决的问题一般具有的几个特征不包括 (满分:5)
A. 该问题的规模缩小到一定的程度就可以容易地解决
B. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
C. 利用该问题分解出的子问题的解不可以合并为该问题的解
D. 原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
8.用分支限界法设计算法的第二步是 (满分:5)
A. 针对所给问题，定义问题的解空间（对解进行编码
B. 确定易于搜索的解空间结构（按树或图组织解）
C. 以广度优先或以最小耗费（最大收益）优先的方式搜索解空间
D. 在搜索过程中用剪枝函数避免无效搜索
9.以下不可以使用分治法求解的是 (满分:5)
A. 棋盘覆盖问题
B. 选择问题
C. 归并排序
D. 0/1背包问题
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.计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。 (满分:5)
A. 错误
B. 正确
本内容由易百网整理
页:
[1]