算法设计与分析试卷(A)及答案

《算法设计与分析试卷(A)及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.算法分析考试试卷（A卷）课程名称算法分析编号题号一二三四总分得分评阅人一、填空题（每小题3分，共30分）1、一个算法的优劣可以用与与来衡量。2、这种不断回头寻找目标的方法称为。3、直接或间接地调用自身的算法称为。4、q记号在算法复杂性的表示法中表示。5、由分治法产生的子问题往往是，这就为使用提供了方便。6、建立计算模型的目的是为了使。7、下列各步骤的先后顺序是。①调试程序②分析问题③设计算法④编写程序。8、最优子结构性质的含义是。9、贪心算法从初始阶段开始，每一个阶段总是作一个使的贪心选择。10、拉

2、斯维加斯算法找到的解一定是。二、选择题（每小题2分，共20分）1、哈夫曼编码可利用（）算法实现。A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是基本计算模型的是（）。A、RAMB、ROMC、RASPD、TM3、下列算法中通常以自顶向下的方式求解最优解的是（）。A、分治法B、动态规划法C、贪心法D、回溯法考试课程：班级：姓名：学号：-------------------------------------------------密--------------------------------

3、--封-----------------------------线----------------------------------------------------------------------------------------------------------密----------------------------------封-----------------------------线------------------------------------------------

4、---------word资料.4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是()A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？A、递归；B、分治；C、迭代；D、模拟。6、FIFO是（）的一搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法7、投点法是（）的一种。A、分支界限算法B、概率算法C、贪心算法D、回溯算法8、若线性规划问题存在最优解，它一定不在（）A．可行域的某个顶点上

5、B．可行域的某条边上C．可行域内部D．以上都不对9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（）对输入进行预处理。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法10、若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是().A、P类问题B、NP难问题C、NP完全问题D、P类语言三、简答题（每小题5分，共20分）1、采用高级程序设计语言表达算法，主要好处是：2、由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表

6、现出哪些特点？3、求下列函数的渐近表达式：;14+5/n+1/n2;4、简述动态规划算法的基本步骤word资料.考试课程：班级：姓名：学号：-------------------------------------------------密----------------------------------封-----------------------------线--------------------------------------------------------------------

7、--------------------------------------密----------------------------------封-----------------------------线---------------------------------------------------------四、算法设计题（每小题15分，共30分）1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树并

8、计算各个节点处的限界函数值，最后给出装载方案及背包中物品的重量和价值。物品ABCDEFG重量35306050401025价值104030503540302、用单纯形法解下列线性规划问题1）填写初始单纯型表2）写出每一步的入基变量和离基变量word资料.3）填写最终单纯型表并给出最优解目标函数的最大值为：最优解为：word资料.参考答案一、填空1、空间复杂度时间复杂度2、回溯法3、递归算法4、渐进确界或紧致界5、原问题的较小模式递归技术6、问题的计算复杂性