北京语言大学计算机科学与技术专业《算法与数据分析》作业及答案3
1、用分支限界法设计算法的第二步是()。
A.针对所给问题,定义问题的解空间(对解进行编码)
B.确定易于搜索的解空间结构(按树或图组织解)
C.以广度优先或以最小耗费(最大收益)优先的方式搜索解空间
D.在搜索过程中用剪枝函数避免无效搜索
本题答案:
B
B
2、蒙特卡罗算法是以下的哪种?()
A.分支界限算法
B.概率算法
C.贪心算法
D.回溯算法
本题答案:
B
B
3、一个问题可用动态规划算法或贪心算法求解的关键特征是问题的()。
A.重叠子问题
B.最优子结构性质
C.贪心选择性质
D.定义最优解
本题答案:
B
B
4、实现合并排序利用的算法是()。
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
本题答案:
A
A
5、实现最大子段和利用的算法是()。
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
本题答案:
B
B
6、下面哪种函数是回溯法中为避免无效搜索采取的策略?()
A.递归函数
B.剪枝函数
C.随机数函数
D.搜索函数
本题答案:
B
B
7、哈弗曼编码的贪心算法所需的计算时间为()。
A.O(n2n)
B.O(nlogn)
C.O(2n)
D.O(n)
本题答案:
B
B
8、实现棋盘覆盖算法利用的算法是()。
A.分治法
B.动态规划法
C.贪心法
D.回溯法
本题答案:
A
A
9、合并排序算法是利用()。
A.分治策略
B.动态规划法
C.贪心法
D.回溯法
本题答案:
A
A
10、下面是贪心算法的基本要素的是()。
A.重叠子问题
B.构造最优解
C.贪心选择性质
D.定义最优解
本题答案:
C
C
11、矩阵连乘问题的算法可由动态规划设计实现。()
A.错误
B.正确
本题答案:
B
B
12、分支限界法是一种只带有系统性的搜索算法。()
A.错误
B.正确
本题答案:
A
A
13、矩阵连乘问题的算法可由动态规划设计实现。()
A.错误
B.正确
本题答案:
B
B
14、拉斯维加斯算法找到的解不一定是正确解。()
A.错误
B.正确
本题答案:
A
A
15、动态规划算法的基本思想是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解。()
A.错误
B.正确
本题答案:
B
B