《算法设计与分析试卷A及答案Word版》由会员分享，可在线阅读，更多相关《算法设计与分析试卷A及答案Word版（7页珍藏版）》请在金锄头文库上搜索。
1、传播优秀Word版文档 ，希望对您有帮助，可双击去除！算法分析考试试卷（A卷）课程名称 算法分析 编号 题号一二三四总分得分评阅人一、填空题（每小题3分，共30分）1、一个算法的优劣可以用 与 与来衡量。2、这种不断回头寻找目标的方法称为 。3、直接或间接地调用自身的算法称为 。4、q 记号在算法复杂性的表示法中表示 。5、由分治法产生的子问题往往是 ，这就为使用 提供了方便。6、建立计算模型的目的是为了使 。7、下列各步骤的先后顺序是 。调试程序 分析问题 设计算法 编写程序。8、最优子结构性质的含义是 。9、贪心算法从初始阶段开始，每一个阶段总是作一个使 的贪心选择。10、拉斯维加斯算法找
2、到的解一定是 。二、选择题（每小题2分，共20分）1、哈夫曼编码可利用（ ）算法实现。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2、下列不是基本计算模型的是（ ）。A、RAM B、ROM C、RASP D、TM3、下列算法中通常以自顶向下的方式求解最优解的是（ ）。A、分治法 B、动态规划法 C、贪心法 D、回溯法考试课程： 班级： 姓名： 学号： - 密 - 封 - 线 - - 密 - 封 - 线 -4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( )A、回溯法 B、分支限界法 C、回溯法和分支限界法 D、动态规划5、秦始皇吞并六国使用的远交近攻，逐个击
3、破的连横策略采用了以下哪种算法思想？A、 递归；B、分治；C、迭代；D、模拟。6、FIFO是（ ）的一搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法7、投点法是（ ）的一种。A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法8、若线性规划问题存在最优解，它一定不在（ ）A可行域的某个顶点上 B可行域的某条边上 C可行域内部 D以上都不对9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（ ）对输入进行预处理。A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法10、若L是一个NP完全问题，L经过多项式时间变换后得到
4、问题l，则l是( ).A、P类问题 B、NP难问题 C、NP完全问题 D、P类语言三、简答题（每小题5分，共20分）1、采用高级程序设计语言表达算法，主要好处是：2、由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表现出哪些特点？3、求下列函数的渐近表达式： ; 14+5/n+1/n2; 4、简述动态规划算法的基本步骤 考试课程： 班级： 姓名： 学号： - 密 - 封 - 线 - - 密 - 封 - 线 -四、算法设计题（每小题15分，共30分）1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包问题。请写出
5、状态空间搜索树并计算各个节点处的限界函数值，最后给出装载方案及背包中物品的重量和价值。物品ABCDEFG重量35306050401025价值104030503540302、用单纯形法解下列线性规划问题1） 填写初始单纯型表2）写出每一步的入基变量和离基变量3）填写最终单纯型表并给出最优解目标函数的最大值为：最优解为：参考答案一、填空1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术6、问题的计算复杂性分析有一个共同的客观尺度 7、 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的二、选择12345678910CBCABAB
6、CBA三、简答题1、n高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。2、 不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外）策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 策略多样，结果也多样。
7、算法实现过程中，通常用到辅助算法：排序3、解： 因为：由渐近表达式的定义易知： ;的渐近表达式。 因为：由渐近表达式的定义易知： 14是14+5/n+1/ n2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】a b. c d. e. f. g. h. i.j. 在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】2、初始单纯型表如下：1）（5分）x2x3x5z0-13-2x173-12x412-240x610-4382）第一步入基变量x3、离基变量x4第二步入基变量x2、离基变量x1 3）（6分）x1x4x5z11-1/5-4/5 -12/5x245/21/104/5x351/53/102/5x6111-1/210目标函数的最大值为11最优解为：x*=(0,4,5,0,0,11)（其中表格填写占11分，目标函数的最大值2分，最优解为占2分）
