一1. 循环赛日程表问题的相关叙述。
2. 算法运行时所需要占用的存储空间有？
3. 动态规划法的求解步骤。
4. 解空间树是排列树的问题有。
5. 分治法的步骤。
6. 就会场安排问题，贪心法的最佳贪心策略。
7. 快速排序法基准元素的选取方法。
8. 满足满m叉树的问题有？
9. 分支限界法的解题步骤。
10. 事前分析法相关的影响因素有。
11. 用分治法求解的问题一般需要具备一些特征，主要有？
二。1．给定一个有向带权图 g=(v，e)，其中每条边的权是一个非负实数，另外，给定v中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。
2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n元组。
3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。
4．一个正在生成孩子的结点称为扩展结点。
5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合s中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。
7．一个自身已生成但其孩子还没有全部生成的结点称为活结点。
8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间。
9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。
10．分支限界法采用的是宽度优先搜索。
11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法。
12．一个所有孩子已经生成的结点称做死结点。
13．在最小生成树的生成方法中，kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。
三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。
2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采用自底向上的递归，由子问题的解得到原问题的解。
3．贪心法可以理解为以逐步的局部最优，达到最终的全局最优，而且不一定能达到全局最优。
4．子集树中的所有非叶子结点均有左右两个分支，左分支为1，右分支为0。
5．回溯法是一种“能进则进，进不了则换，换不了则退”的搜索方法。
6．最长公共子序列问题具有最优子结构性质。）
7．凸多边形最优三角剖分问题具有最优子结构性质。
8．时间复杂性是对算法运行时间的长短的度量。
9．贪心法是根据贪心策略来逐步构造问题的解，该算法的好坏关键在于正确地选择贪心策略。
10．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。
11．子集树的深度等于问题的规模。
12．隐约束也叫剪枝函数，一般有两种：约束条件和限界条件。
13．加工顺序问题具有最优子结构性质。
14．包含元素最多的公共子序列即为最长公共子序列。
15．回溯法问题的解是一个n元组(x1,x2,…,xn)。
16．子集树中，从根结点到叶子结点的路径表示一个可行解。
17．针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。
18．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合s中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
19．动态规划法与分治法和贪心法类似，都是把待求解的问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。
20．快速排序法通过一趟扫描将待排序的元素分成独立的三个序列。
四。1 会场安排问题。
设有n个会议的集合c=，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi设有11个会议等待安排，如下表所示，用贪心法找出满足要求的会议集合（用箭头画出即可）。
1设g=(v，e)是无向连通带权图，v=，如下图所示，根据贪心策略写出用prim算法求解最小生成树的过程。
4. 图的m着色问题。给定无向连通图g=(v，e) 和3 种不同的颜色。
用这些颜色为图g的各顶点着色，每个顶点着一种颜色。要求有边相连的两个顶点着不同颜色，找出所有不同的着色方法。要求给出最终的搜索树。
2．用分治法求解循环赛安排问题。
设有4个运动员要进行乒乓球循环赛，现要设计一个满足以下要求的比赛日程表：
1）每个选手必须与其它3个选手各赛一次；
2）每个选手一天只能比赛一次；
3）循环赛一共需要进行7天。
要求：安排4个选手的比赛日程表。
4．有7个工件，它们在第一台机器和第二台机器上的处理时间分别为：[t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15，t21,t22,t23,t24,t25,t26,t27]=[7,2,6, 18,3, 10,4]
求7个工件的最优加工顺序。
要求：用动态规划法按照算法步骤，求出问题的解。
5．布线问题。布线问题就是在n×m的方格阵列中，指定一个方格的中点为a，另一个方格的中点为b，如图所示，问题要求找出a到b的最短布线方案（即最短路径）。布线时只能沿直线或直角，不能走斜线，黑色的单元格代表不可以通过的封锁方格。
要求给出搜索结果，并构造问题的最优解。
5．用优先队列式分支限界法求解0-1背包问题：n=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=<8，3，2，9，7，1，5，4>，采用合并排序法进行排序，画出合并排序的过程示意图。
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）画出最大团。
算法设计与分析复习
12 动态规划算法基本思想 自底向上 全局最优 讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是 适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。最优子结构性质 问题的最优解包含了其子问题的最优解 子问题重叠性质 在用递归算法自顶...
算法设计与分析复习
分治法求全排列。算法描述。分治法求解问题分为三个步骤 分解 将问题分为若干个子问题。解决 递归地求解每个子问题。合并 将每个子问题的解合并成为整个问题的解。现在我们需要求具有n个元素的数组a的全排列。例如 大小为3的数组a a,b,c 为方便起见，我把引号全都省略了，其实应该是a a b c 下同 ...
算法分析与设计复习
一 迪杰斯特拉算法。1 对下图中的有向图，应用dijkstra优化算法计算从源顶点0到其它顶点间最短路径。2 利用优化的dijkstra算法求解以节点1为源节点到其他各个节点。的的最短路径。用贪心法求解，写出具体步骤 二 多波段图问题。1 用动态规划法求下图中从源点0到终点8的最短路径，写出具体步骤...