20春《算法与数据分析》作业_1
一、单选题 ( 每题4分, 共10道小题, 总分值40分 ) 1.下列随机算法中运行时有时候成功有时候失败的是 A. 数值概率算法 B. 舍伍德算法 C. 拉斯维加斯算法 D. 蒙特卡罗算法
答：C 微 131 》 9666 》 2906
2.最长公共子序列算法利用的算法是 A. 分支界限法 B. 动态规划法 C. 贪心法 D. 回溯法 答：B
3.矩阵连乘问题的算法可由什么设计实现 A. 分支界限算法 B. 动态规划算法 C. 贪心算法 D. 回溯算法 答：B
4.下列哪一种算法不是随机化算法 A. 蒙特卡罗算法 B. .拉斯维加斯算法 C. .动态规划算法 D. .舍伍德算法 答：C
5.贪心算法与动态规划算法的共同点是 A. 重叠子问题 B. 构造最优解 C. 贪心选择性质 D. 最优子结构性质 答：D
6.下面哪种函数是回溯法中为避免无效搜索采取的策略 A. 递归函数 B. .剪枝函数 C. 。随机数函数 D. .搜索函数 答：B
7.采用最大效益优先搜索方式的算法是 A. 分支界限法 B. 动态规划法 C. 贪心法 D. 回溯法 答：A
8.下面不是分支界限法搜索方式的是 A. 广度优先 B. 最小耗费优先 C. 最大效益优先 D. 深度优先 答：D
9.动态规划算法的基本要素为
A. 最优子结构性质与贪心选择性质 B. 重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 答：C
10.衡量一个算法好坏的标准是 A. 运行速度快 B. 占用空间少 C. 时间复杂度低 D. 代码短 答：C
二、判断题 ( 每题4分, 共15道小题, 总分值60分 )
1.分支限界法解旅行售货员问题时，活结点表的组织形式是数组 答：错误
2.该问题的规模缩小到一定的程度就可以容易地解决是分治法的一个特征 答：正确
3.合并排序算法是利用分治策略实现的算法
4.拉斯维加斯算法得到的解未必正确
5.找出最优解的性质不是动态规划算法基本步骤
6.优先队列式分支限界法是指按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
7.矩阵连乘问题的算法可由动态规划设计实现
8.优先队列式分支限界法是按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
9.分支限界法能解决0/1背包问题的是
10.算法是指解决问题的一种方法或一个过程。
11.广度优先是回溯法的一搜索方式
12.回溯法搜索解空间树时，常用的剪枝函数只有结束函数
13.最大效益优先是动态规划法的一搜索方式
14.实现最长公共子序列利用的算法是回溯法
15.哈夫曼编码的贪心算法所需的计算时间为O（n）
20春《算法与数据分析》作业_2
一、单选题 ( 每题4分, 共10道小题, 总分值40分 )
1.使用分治法求解需要满足原问题和子问题使用相同的方法解 A. 对 B. 错
2.以下不可以使用分治法求解的是 A. 棋盘覆盖问题 B. 选择问题 C. 归并排序 D. 0/1背包问题
3.采用广度优先策略搜索的算法是 A. 分支界限法 B. 动态规划法 C. 贪心法 D. 回溯法
4.分支限界法解旅行售货员问题时，活结点表的组织形式是 A. 最小堆 B. 最大堆 C. 栈 D. 数组
北语 20春《算法与数据分析》作业_1234
