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

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