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

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