1. 当设定的问题有多种算法去解决时，其选择算法的主要原则是选择其中复杂性最低者。 2. 用函数自身给出定义的函数是一种递归函数。 3. 动态规划算法适用于解最优化问题。
4. 贪心算法的两个基本要素是最优子结构性质、贪心选择性质。
5. 回溯法在搜索解空间树的时候，为了避免无效搜索，通常使用深度优先手段来提高搜索效率。 6. 依据求解目标的不同，分支界限法和回溯法分别用广度优先遍历或者最小耗费优先、深度优先的方式搜索解空间树。
7. 分支界限法和回溯法主要区别在于求解目标和搜索方式不同。
8. 在分支界限法实现的时候，通常采用 方式来实现最大优先队列。
9. 依据求解所花费的时间和所得到的结果不同，随机化算法大致分为数值随机化算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法四类。 10. 产生伪随机数最常用的方法是线性同余法。
11. 线性规划算法中转轴变化的目的是将入基变量与离基变量互调位置。 12. 最大网络流问题中可增广路是残留网络中一条容量大于0的路。 13. 待解决问题适用于动态规划法的两个基本要素是 。 14. 算法必须满足的四个特征是输入、输出、确定性、有限性。
15. 算法复杂性依赖于 、 、 三个方面的复杂因素。 16. 实现递归调用的关键是
17. 动态规划算法求解问题的重要线索是问题的 性质。 18. 最优子结构性质是贪心算法求解问题的关键特征。
19. 分支界限法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
20. 问题的解空间树常见的有子集树、排列树两种类型。
21. 分支界限算法依据其从和节点表中选择获得下一扩展节点的不同方式被分为
22. 对于任何约束标准型线性规划问题，只要将所用分基本变量都设置为0，就可以获得一个 解。
三 概念题（6x2=12分）
1. 算法复杂性：是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资
源的量称为空间复杂性。
2. 递归算法：直接或间接地调用自身的算法称为递归算法。
3. 贪心算法：在对问题求解时，总是做出当前看来是最好的选择。也就是说，贪心算法并不从整体最优
考虑，他所做出的选择只是在某种意义上的局部最优选择。贪心算法不能对所有问题都得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
4. 子集树：当所给问题是从n个元素的集合s中找出满足某种性质的子集时，相应的解空间树称为子集
树。
5. 队列式（FIFO）分支限界法：将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点
为当前扩展结点。
6. 分治法：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 7. 算法：由若干条指令组成的有穷序列。
8. 最优子结构：当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 9. 回溯法：以深度优先方式系统搜索问题解的算法称为回溯法。
10. 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。 11. 网络流：是定义在网络的边集合E上的一个非负函数flow = {flow(v,w)}，并称flow(v,w)为边（v,w）上的
流量。
四 简答题（3x4=12分）
1. 在一个算法中调用另一个算法时，系统需在运行被调用算法之前完成哪些工作？同时从被调用算法返
回调用算法需完成哪些工作？
答：在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事：
（1） 将所有实参指针、返回地址等信息传递给被调用算法； （2） 为被调用算法的局部变量分配存储区； （3） 将控制转移到被调用算法的入口。 在从被调用算法返回调用算法时需完成三件事： （1） 保存被调用算法的计算结果； （2） 释放分配给被调用算法的数据区；
（3） 依照被调用算法保存的返回地址将控制转移到调用算法。
2. 动态规划算法求解问题的步骤？
答：动态规划法适用于解最优化问题。通常可以按以下4个步骤设计： （1） 找出最优解的性质，并刻画其结构特征； （2） 递归地定义最优值；
（3） 以自底向上的方式计算最优值；
（4） 根据计算最优值时得到的信息构造最优解。 3. 线性规划法中单纯形算法的基本步骤？
答：步骤一 选入基变量。
步骤二 选离基变量。 步骤三 做转轴变换。 步骤四 转步骤一。
4. 分治法的基本思想和原理是什么？
答：分治法的基本思想是将一个规模为ｎ的问题分解为ｋ个规模较小的子问题，这些子问题互相独立
且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
5. 利用回溯法解决问题包含哪些步骤？
答：利用回溯法解题常包含以下3步骤： （1） 针对所给问题，定义问题的解空间； （2） 确定易于搜索的解空间结构；
（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 五 分析题（36分）
1．求下列函数的渐进表达式：
3n+10n; n/10+2; 21+1/n; logn; 10log3分析与解答： 3n+10n=O(n); n/10+2=O(2); 21+1/n=O(1); logn=O(logn); 10log3=O(n)
2．讨论O(1)和O(2)的区别。 分析与解答：
根据符号O的定义易知O(1)=O(2)。用O(1)或O(2)表示同一个函数时，差别仅在于其中的常数因子。
3．按渐近阶排列表达式
按照渐近阶从低到高的顺序排列以下表达式：4n，logn，3，20n，2，n。又n!应该排在哪一位？ 分析与解答：
2
n
2/3
n32
n
n
2
2
2
2
n
3
n
按渐近阶从低到高，函数排列顺序如下：2，logn，n，20n，4n，3，n！。 4.算法效率
(1)假设某算法在输入规模为n时计算时间为T(n)=3*2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？
(2)若上述算法的计算时间改进为T(n)=n，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？
(3)若上述算法的计算时间进一步改进为T(n)=8，其余条件不变，那么在新机器上用t秒时间能解输入规模为多大的问题？ 分析解答：
(1)设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有：t=3*2=3*2/64，解得你n1=n+6。(2)n1=64nn1=8n。
(3)由于T(n)=常数，因此算法可解任意规模的问题。
5．阶乘函数
阶乘函数可递归地定义为：
int factorial(int n) {
if(n = = 0) return 1; return n * factorial(n-1); }
6．Fibonacci数列
无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：
请对这个无穷数列设计一个算法，并进行描述（自然语言描述和VC++描述）.
第n个Fibonacci数可递归地计算如下：
int fibonacci(int n) {
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2); }
2
2
2
n1
2
n
2/32n
1n0n!n(n1)!n01n0F(n)1n1F(n1)F(n2)n1
7．循环赛日程表
设有n=2个运动员要进行兵乓球循环赛。现在要设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。
请设计一个算法解决以上问题，并进行描述（自然语言和C++语言）
按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。
8．有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载
体积不受限制的情况下，将尽可能多的集装箱装上轮船。 分析回答以下两个问题：
(1)分析以上最优装载问题具有贪心选择性质 (2)用C++程序进行正确的算法描述 分析与解答： (1)
设集装箱已依其重量从小到大排序，(x1,x2,…,xn)是最有装载问题的一个最优解。又设k=min{i|xi=1}。易知，如果给定的最有装载问题有解，则1≤k≤n。 ② 当k=1时，(x1,x2,…,xn)是满足贪心选择性质的最优解。 ②当k>1时，取y1=1;yk=0;yi=xi,1 另一方面，由知，()是满足贪心选择性质的最优解。所以，最优装载问题具有贪心选择性质。 (2)最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下。 template void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} } k 因篇幅问题不能全部显示，请点此查看更多更全内容