西安邮电大学算法考试.doc

《西安邮电大学算法考试.doc》由会员分享，可在线阅读，更多相关《西安邮电大学算法考试.doc（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流西安邮电大学算法考试【精品文档】第 6 页第 1 章 算法概述（1）算法的性质包括输入、输出、确定性 、有限性。（2）算法复杂性 ：算法所运行所需要的计算机资源的量，所需资源多，算法的复杂性高；反之则复杂性低。 时间复杂性 ：需要时间资源的量(指令数) 空间复杂性：需要空间资源的量(存储器的大小)（3） 计算题第 2 章 递归与分治策略（1）分治法主要思想：将一个规模为n 的问题分解为k个规模较小子问题，这些子问题互相独立且与原问题相同，递归解决这些子问题，然后将各子问题的解合并得到原问题解。（2）使用分治算法找一组数的最大最小数。采用如下设计思想：将数

2、据集 S 均分为 S1 和 S2；求解 S1 和 S2 中的最大和最小值；最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；采用同样的处理方法递归处理 S1 和 S2。可以得到该算法复杂性的递推公式如下根据递推公式推导出该复杂性表达式:3） 分治法所能解决的问题具有的特征.（1）该问题规模缩小到一定的程度就可以容易地解决；因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。（2）该问题可分解为若干个规模较小相同问题，即该问题具有“最优子结构性质”。这条特征是应用分治法前提，它也是大多数问题可满足的，反映了递归思想的应用。（3）

3、利用该问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。4）数组 A 含有 9 个元素，这些元素恰好是第 2 至第 10 个 Fibonacci 数，写出在数组 A 中查找 x = 17 的二分查找过程（写出过程即可，不需要写代码）。（5）下面给出了非递归形式的

4、二分搜索方法代码，请补充下划线处的代码。template int BinarySearch( Type a, const Type& x, int n ) / 在 a 0 = a 1 = . = a n 1 中搜索 x，找到 x 时返回其在数组中的位置，否则返回 -1 int left = 0; int right = n - 1; while ( left a middle ) left = middle + 1; else right = middle - 1; return -1; / 未找到 x（6）判断下列递归算法（计算n！）是否正确，如果不正确，请说明原因，并改正。int fact

5、oral(int i) if ( n 0 ) return( n * factoral( n - 1 ) ); 【分析】不正确，因为递归函数没有边界值的判断，无法得出正确的值。另外入口参数与下面的使用不一致。修改如下：int factoral( int n ) if ( n = = 0 ) return 1; return( n * factoral( n 1 ) ); 第 3 章 动态规划（1）备忘录法是那种算法的变形（ B ）。A、分治算法 B、动态规划算法 C、贪心算法 D、回溯法（2）分治法与动态规划算法的相同点和不同点是什么？（3）利用动态规划法设计如下的矩阵连乘最小次数问题，写出动

6、态规划法求解过程。A1：4025 A2：2525 A3：2515解：m00=m11 =m22 =m33=0 r=2 i=1 j=2 m12=40*25*10=10000 i=2 j=3 m23= 25*10*15=3750 r=3 i=1 j=3 m13= m11+ m23+ 40*25*15=18750 k=2 t= m12+ m33+ 40*10*15=16000 m13=t=16000（4）具有最优子结构的算法有（ D ）。A概率算法 B回溯法 C分支限界法 D动态规划法（5）证明题。（6） 计算题（7）有一个箱子容量为 V（正整数），同时有 n 个物品，每个物品有一个体积（正整数）。要

7、求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。编写程序实现，自定义输入和输出。【提示】使用二维数组 f i j , 表示前 i 个物品装入容量为 j 的箱子能获得的最大体积，则状态转移方程：f i j = max( f i - 1 j , f i -1 j - a i + a i );（8）已知字符串 A 的值是 sot，字符串 B 的值是 stop，将字符串 A 转换为字符串 B 的编辑距离值为（ ）。A1 B2 C3 D4【分析】根据“编辑距离”的定义，可知答案为 B。sot 通过一个“增加”操作变为 stot，然后通过一个“编辑”操作就可以变为 stop。注意答案 C 是

8、错误的。（9）有一辆货车，货车有载重为 D，有 n 件货物，每个货物有重量 wi，价值 pi。问怎么装能够使装上货车的物品的总价值最大（使用动态规划算法）【分析】“0-1”背包问题。第 4 章 贪心算法（1） 简述贪心法的基本思想：设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时，S 中仅含有源。设 u 是 G 的某一个顶点，把从源到 u 且中间只经过 S 中顶点的路称为从源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S（顶点集合 V“减去”集合 S）

9、 中取出具有最短特殊路长度的顶点 u，将 u 添加到 S 中，同时对数组dist 作必要的修改。一旦 S 包含了所有 V 中顶点，dist 就记录了从源到所有其它顶点之间的最短路径长度。贪心算法的两个重要性质：贪心选择性质和最优子结构性质贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。 （1）对于具有最优子结构的问题应该选用贪心算法？（2）是否能用动态规划算法求解的问题也能用贪心算法求解 ?（2）证明上述问题具有“贪心选择性质”和“最优子结构性质”。（3）设 7 个独立作业 1，2，3，4，5，6，7 由 3 台相同机器 M1，M2，M3 加工处理。各作业所需的处

10、理时间分别 2，14，4，16，6，5，3 。任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。按贪心算法产生作业调度，所需加工时间为多少？（4）某体育馆有一篮球球场出租，共有 10 位客户申请租用。每个客户申请租用的时间单元如下表所示，其中 i 表示客户编号，s(i) 表示开始租用时刻，f(i) 表示结束租用时刻。同一时刻该篮球球场只能租借给一位客户。请使用贪心算法设计一个租用安排方案，在这 10 位客户里面，使得体育馆能尽可能满足多位客户的需求。并计算出针对上表的 10 个客户申请，最多可以安排几位客户申请。【分析】这是一个活动安排问题。将这

11、10 位客户的申请按照结束时间 f(i)递增排序，如下表：（1）选择申请 1（1,4）。（2）依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有申请检查完毕。申请 4（5,7）、申请 8（8,11）、申请 10（11,13）。（3）最后可以满足：申请 1（1,4）、申请 4（5,7）、申请 8（8,11）、申请 10（11,13）共4 个客户申请。这是可以满足的最大客户人数。（5）下列哪个问题不能用贪心法求解？（ ）A最优装载问题 B活动安排问题 C0-1背包问题 D多机调度问题【分析】答案为 C。（6）设有 n 个程序 1,2,.,n 要存放在长度为 L 的磁带上，程

12、序 i 存放在磁带上的长度为 li, 1=i n ) output( x ); else for ( int i = t; i = n; i+ ) swap( x t , x i ); if ( Constraint( t ) & Bound( t ) ) Backtrack( t + 1 ); swap( x t , x i ); 在调用Backtrack(1)执行回溯搜索之前，先将变量数组x初始化为单位排列(1,2,n)（4）对批处理作业调度问题：作业需要机器处理时间的表如下，如果调度方案为：1，2，3，计算完成时间和。作业调度方案：1，2，3（必须考虑机器的空闲时间）：作业 1 在机器

13、1 上完成的时间为 2，在机器 2 上完成的时间为 3（2 + 1）作业 2 在机器 1 上完成的时间为 5（2 + 3），在机器 2 上完成的时间为 6（5 + 1）作业 3 在机器 1 上完成的时间为 7（2 + 3 + 2），在机器 2 上完成的时间为 10（7 + 3）完成时间和：3 + 6 + 10 = 19（5）写出用回溯法求解如下 0-1 背包 的求解过程（使用约束函数和限界函数进行剪枝），并画出状态空间搜索树：有 3 个物品，它们的重量和价值如下表所示，背包容量 C 60。（6）设有 n 件工作分配给 n 个人。将工作 i 分配给第 j 个人所需的费用为 cij。采用回溯法设计

14、一个算法，为每一个人都分配 1 件不同的工作，并使总费用达到最小。【分析】根据问题描述，可得解题思路如下：由于每个人都必须分配到工作，可以建一个二维数组 c i j ，用以表示 i 号工人完成 j 号工作所需的费用。给定一个循环，从第 1 个工人开始循环分配工作，直到所有工人都分配到。为第 i 个工人分配工作时，再循环检查每个工作是否已被分配，没有则分配给 i 号工人，否则检查下一个工作。可以用一个一维数组x j 来表示第j号工作是否被分配，未分配则x j = 0，否则x j = 1。利用回溯法在工人循环结束后回到上一工人，取消此次分配的工作，而去分配下一工作直到可以分配为止。这样，一直回溯到

15、第1个工人后，就能得到所有的可行解。在检查工作分配时，其实就是判断取得可行解时的二维数组的下标一都不相同，下标二同样不相同。第 6 章 分支限界法（1）简述回溯法和分支限界法的异同点。 分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。二者的不同之处在于：（1）回溯法的求解目标往往是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解；（2）回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费（最大效益）优先的方式搜索解空间树。（2） 给定 0/1 背包问题，参数为：n = 3,

16、 w = 16, 15, 15 , p = 45, 25, 25 , c = 30。用队列式分支限界法求解此问题。给出求解过程（包括在求解过程中队列内容的变化情况）。（3）布线问题的解空间是图.1:程序与算法的区别:算法是给人来读的，直接给计算机是不能执行的;程序可以不满足算法的有限性2:简述分治法的主要思想。将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。因此分治法可以分为两个重要步骤：（1）自顶向下：将问题不断分割成小的问题。（2）自底而上：将小问题解决来构建大问题的解。3：分治法能解决问题所具有的性质（1）该问题规模缩小到一定的程度就可以容易地解决；因为问题的计

17、算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有“最优子结构性质”。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。（3）利用该问题分解出的子问题的解可以合并为该问题的解。4：动态规划与分治法的相同点和不同点1共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。2.不同点：1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重

18、新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低5：简述贪心算法的基本思想所谓贪心算法指的是为了解决在不回溯的前提之下，找出整体最优或者接近最优解的这样一种类型的问题而设计出来的算法。贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活

19、动安排问题和背包问题。6：简述回溯法与分支限界打的异同相同点：二者都是一种在问题的解空间树T上搜索问题解的算法。不同点：1.在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。2.回溯法与分支-限界法对解空间的搜索方式不同，回溯法通常采用尝试优先搜索，而分支限界法则通常采用广度优先搜索。3.对节点存储的常用数据结构以及节点存储特性也各不相同，除由搜索方式决定的不同的存储结构外，分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索。7：贪心算法与动态规划的异同贪心选择（整体最优解可以通过局部），贪心从上到下，动态规划送下到上8:二分搜索方法的思想缩小到一定程度可以解决；可以分解为若干规摸较小的相同的子问题；子问题的解可以合并为该问题的解；子问题之间相互独立9动态规划的基本思想及要素将要求解的较大规模的问题分割为k个较小规模的子问题，这些子问题之间是相互独立的。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。要素：最有子结构，重叠子问题