算法设计与分析复习资料1

《算法设计与分析复习资料1》由会员分享，可在线阅读，更多相关《算法设计与分析复习资料1（4页珍藏版）》请在装配图网上搜索。

1、1. 循环赛日程表问题的相关叙述。2. 算法运行时所需要占用的存储空间有？3. 动态规划法的求解步骤4. 解空间树是排列树的问题有。5. 分治法的步骤6. 就会场安排问题，贪心法的最佳贪心策略7. 快速排序法基准元素的选取方法8. 满足满 m 叉树的问题有？9. 分支限界法的解题步骤10. 事前分析法相关的影响因素有11. 用分治法求解的问题一般需要具备一些特征，主要有？1给定一个有向带权图G=(V, E),其中每条边的权是一个非负实数，另外，给定 V 中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最 短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题 通常称

2、为单源最短路径问题。2采用回溯法可以求解0-1背包问题，其解空间的形式为：(xl,x2,x)或n 元组。3当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应 的解空间树称为排列树。4一个正在生成孩子的结点称为扩展结点。5. 子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是 从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称 为子集树。6. 当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对 这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素 取值的一种组合，这类问题的解空间树称为满m叉树。7一

3、个自身已生成但其孩子还没有全部生成的结点称为活结点8回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间9. 分支限界法有两种：队列式分支限界法和优先队列式分支限界法。10分支限界法采用的是宽度优先搜索。11. 时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法12. 个所有孩子已经生成的结点称做死结点13. 在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小 的边取出来，在不构成环的情况下，将该边加入最小生成树。1. 分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子 问题，子问题相互独立，如果子问题

4、还是不容易解决， 再把子问题分成更小的子问题， 直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行 合并即得原问题的解。2. 动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是 相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采 用自底向上的递归，由子问题的解得到原问题的解。3贪心法可以理解为以逐步的局部最优，达到最终的全局最优，而且不一定能达到全局最 优。4子集树中的所有非叶子结点均有左右两个分支，左分支为1，右分支为 0。 5回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。6最长公共子序列问题具有

5、最优子结构性质。） 7凸多边形最优三角剖分问题具有最优子结构性质。8时间复杂性是对算法运行时间的长短的度量。9贪心法是根据贪心策略来逐步构造问题的解，该算法的好坏关键在于正确地选择贪心策 略。10. 当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树 称为排列树。11. 子集树的深度等于问题的规模12. 隐约束也叫剪枝函数，一般有两种：约束条件和限界条件。13. 加工顺序问题具有最优子结构性质。14. 包含元素最多的公共子序列即为最长公共子序列。15. 回溯法问题的解是一个n元组仪/?,/。16. 子集树中，从根结点到叶子结点的路径表示一个可行解。17. 针对问题的可

6、能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。18. 子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素 组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。19. 动态规划法与分治法和贪心法类似，都是把待求解的问题分解为更小的、相同的子问题， 然后对子问题进行求解，最终产生一个整体最优解。20. 快速排序法通过一趟扫描将待排序的元素分成独立的三个序列。 四1 会场安排问题。设有n个会议的集合C=l,2,.,n,其中每个会议都要求使用同一个资源（如会议室） 而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始

7、时间b.i 和结束时间e.,且b.ve.。如果选择了会议i使用会议室，则它在半开区间b., e.）内占用该资 源。如果b., e.）与叫,引不相交，则称会议i与会议j是相容的。也就是说，当b.之e.或b. e. 时，会议i与会议j相容。会场安排问题要求在所给的会议集合中选出最大的相容活动子集, 也即尽可能地选择更多的会议来使用资源。设有 11 个会议等待安排，如下表所示，用贪心法找出满足要求的会议集合（用箭头画 出即可）。会议i1234567891011开始时间b.i130535688212结束时间e.i45678910111213141设G=（V, E）是无向连通带权图，V=1,2,.,6,

8、如下图所示，根据贪心策略写出用Prim 算法求解最小生成树的过程。4.图的m着色问题。给定无向连通图G=（V, E）和3种不同的颜色。用这些颜色为图G的 各顶点着色，每个顶点着一种颜色。要求有边相连的两个顶点着不同颜色，找出所有不同的 着色方法。要求给出最终的搜索树。2用分治法求解循环赛安排问题。 设有4个运动员要进行乒乓球循环赛,现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它 3 个选手各赛一次；（2）每个选手一天只能比赛一次；（3）循环赛一共需要进行7 天。要求：安排4个选手的比赛日程表。4有7 个工件,它们在第一台机器和第二台机器上的处理时间分别为：t ,t ,t ,t

9、,t ,t ,t =3,8,10,12,6,9,15,11 12 13 14 15 16 17t ,t ,t ,t ,t ,t ,t =7,2,6, 18,3, 10,421 22 23 24 25 26 27求7 个工件的最优加工顺序。 要求：用动态规划法按照算法步骤,求出问题的解。5布线问题。布线问题就是在NxM的方格阵列中，指定一个方格的中点为a,另一个方格 的中点为b,如图所示，问题要求找出a到b的最短布线方案（即最短路径）。布线时只能 沿直线或直角，不能走斜线，黑色的单元格代表不可以通过的封锁方格。要求给出搜索结果，并构造问题的最优解。5.用优先队列式分支限界法求解0-1背包问题：n

10、=4, W=3, 5, 2, 1,v=9, 10, 7, 4,C=7。要求给出最终的搜索结果。3 用二分查找算法在有序序列（6， 12， 15， 18， 22， 25， 28， 35， 46， 58， 60）中查找元 素 12,画出每次划分的示意图。3. 已知待排序序列 A=,采用合并排序法进行排序,画出合并排 序的过程示意图。6.用分支限界法求解旅行商问题。如图所示，n=4,城市1为售货员所在的住地城市，画出最终的搜索树。2.已知某系统在通信联络中只可能出现8种字符，分别为a, b, c, d, e, f, g, h,其使 用频率分别为 0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，用贪心法求解哈夫曼 编码。要求：给出构造哈夫曼树的过程，并给出各个字符的编码。6. 已知如图所示的无向图，用回溯法求解最大团。要求：（1）画出搜索树；（2）画出最大 团。