16秋华师《算法设计与分析》在线作业

奥鹏17春16秋华师算法设计与分析在线作业一、单选题（共 20 道试题，共 60 分。）1. 下列算法中通常以深度优先方式系统搜索问题解的是（）。A. 备忘录法B. 动态规划法C. 贪心法D. 回溯法正确答案：2. 循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（）。A. front=rearB. front=0C. rear=0D. front=rear+1正确答案：3. 队列的插入操作是在（）。A. 队尾B. 队头C. 队列任意位置D. 队头元素后正确答案：4. 分支限界法解旅行售货员问题时，活结点表的组织形式是（）。A. 最小堆B. 最大堆C. 栈D. 数组正确答案：5. 最大效益优先是（）的一搜索方式。A. 分支界限法B. 动态规划法C. 贪心法D. 回溯法正确答案：6. 具有线性结构的数据结构是（）。A. 图B. 树C. 广义表D. 栈正确答案：7. 下列哪些是采用广度优先策略搜索？（）。A. 分支界限法B. 动态规划法C. 贪心法D. 回溯法正确答案：8. 下列随机算法中运行时有时候成功有时候失败的是（）A. 数值概率算法B. 舍伍德算法C. 拉斯维加斯算法D. 蒙特卡罗算法正确答案：9. 哈弗曼编码的贪心算法所需的计算时间为（）。A. O（n22）B. O（nlogn）C. O（2n）D. O（n）正确答案：10. 蒙特卡罗算法是（）的一种。A. 分支界限算法B. 概率算法C. 贪心算法D. 回溯算法正确答案：11. 实现循环赛日程表利用的算法是（）。A. 分治策略B. 动态规划法C. 贪心法D. 回溯法正确答案：12. 实现棋盘覆盖算法利用的算法是（）。A. 分治法B. 动态规划法C. 贪心法D. 回溯法正确答案：13. 最长公共子序列算法利用的算法是（）。A. 分支界限法B. 动态规划法C. 贪心法D. 回溯法正确答案：14. 设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。A. 顺序表B. 链表C. 队列D. 栈正确答案：15. 判断一个循环队列Q（最多n个元素）为满的条件是（）。A. Q-rear=Q-frontB. Q-rear=Q-front+1C. Q-front=(Q-rear+1)%nD. Q-front=(Q-rear-1)%n正确答案：16. 二分搜索算法是利用（）实现的算法。A. 分治策略B. 动态规划法C. 贪心法D. 回溯法正确答案：17. 算法分析的目的是（）A. 找出数据结构的合理B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性正确答案：18. 分支限界法解最大团问题时，活结点表的组织形式是（）。A. 最小堆B. 最大堆C. 栈D. 数组正确答案：19. 矩阵连乘问题的算法可由（）设计实现。A. 分支界限算法B. 动态规划算法C. 贪心算法D. 回溯算法正确答案：20. 快速排序方法在（）情况下最不利于发挥其长处。A. 要排序的数据量太大B. 要排序的数据中有多个相同值C. 要排序的数据已基本有序D. 要排序的数据个数为奇数正确答案： 华师算法设计与分析在线作业二、多选题（共 10 道试题，共 20 分。）1. 下列算法中哪些通常不是以自底向上的方式求解最优解？（）。A. 备忘录法B. 动态规划法C. 贪心法D. 回溯法正确答案：2. 衡量一个算法好坏的标准不包括（）。A. 运行速度快B. 占用空间少C. 时间复杂度低D. 代码短正确答案：3. 下面哪些函数不是回溯法中为避免无效搜索采取的策略（）A. 递归函数B. 剪枝函数C. 随机数函数D. 搜索函数正确答案：4. 下面关于NP问题说法不对的有（）A. NP问题都是不可能解决的问题B. P类问题包含在NP类问题中C. CNP完全问题是P类问题的子集D. DNP类问题包含在P类问题中正确答案：5. 下列哪些算法是随机化算法（）A. 蒙特卡罗算法B. 拉斯维加斯算法C. 动态规划算法D. 舍伍德算法正确答案：6. 回溯法的效率依赖于下列哪些因素（）A. 满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间正确答案：7. 下面哪些不是是贪心算法的基本要素？（）。A. 重叠子问题B. 构造最优解C. 贪心选择性质D. 定义最优解正确答案：8. 以下可以使用分治法求解的是（）。A. 棋盘覆盖问题B. 选择问题C. 归并排序D. 0/1背包问题正确答案：9. 动态规划算法的两个基本要素是（）A. 最优子结构性质B. 重叠子问题性质C. 约束条件D. 分支条件正确答案：10. 下面是分支界限法搜索方式的有（）。A. 广度优先B. 最小耗费优先C. 最大效益优先D. 深度优先正确答案： 华师算法设计与分析在线作业三、判断题（共 10 道试题，共 20 分。）1. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。A. 错误B. 正确正确答案：2. 图的深度优先搜索序列和广度优先搜索序列不是惟一的。A. 错误B. 正确正确答案：3. 快速排序是排序算法中平均性能最好的一种排序。A. 错误B. 正确正确答案：4. 二叉树是一棵无序树。A. 错误B. 正确正确答案：5. 在用单链表表示的链式队列Q中，队头指针为Q-front，队尾指针为Q-rear，则队空条件为Q-front=Q-rear。A. 错误B. 正确正确答案：6. 递归定义的数据结构通常用递归算法来实现对它的操作。A. 错误B. 正确正确答案：7. 递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。A. 错误B. 正确正确答案：8. 在一个顺序存储的循