一
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,…,x n)。

16．子集树中，从根结点到叶子结点的路径表示一个可行解。

17．针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。

18．子集树是用回溯法解题时经常遇到的一种典型的解空间树。

当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。

19．动态规划法与分治法和贪心法类似，都是把待求解的问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。

20．快速排序法通过一趟扫描将待排序的元素分成独立的三个序列。

四
1 会场安排问题。

设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。

每个会议i都有要求使用该资源的起始时间b i 和结束时间e i，且b i<e i。

如果选择了会议i使用会议室，则它在半开区间[b i, e i)内占用该资源。

如果[b i, e i)与[b j, e j)不相交，则称会议i与会议j是相容的。

也就是说，当b i≥e j或b j≥e i 时，会议i与会议j相容。

会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。

设有11个会议等待安排，如下表所示，用贪心法找出满足要求的会议集合（用箭头画出即可）。

1设G=(V，E)是无向连通带权图，V={1,2,…,6}，如下图所示，根据贪心策略写出用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）画出最大团。