《算法设计与分析试卷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分)