文档介绍：一、 要回答下列 ：
算法重要特性是什么？
算法分析的目的是什么？
算法的 复 性与 的什么因素相关？
算法的 复 性的含 ？
最坏情况下的 复 性和平均 复 性有什么不同？
述二分
C(1,2)=3
， C(1,3)=5
，C(1,4)=2
C(2,6)=8
， C(2,7)=4
，C(3,5)=5
， C(3,6)=4 ， C(4,5)=2
， C(4,6)=1
C(5,8)=4
， C(6,8)=5
，C(7,8)=6
2、 写出 maxmin 算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7)
3、 给出 5 个数 (3,6,9,1,7),M=13 ，用递归树描述 sumofsub 算法求和数 =M 的一个子集
的过程。
4、 快速排序算法对下列实例排序， 算法执行过程中， 写出数组 A 第一次被分割的过程。
A=(65,70,75,80,85,55,50,2)
5、 归并排序算法对下列实例排序，写出算法执行过程。
A=(48,12,61,3,5,19,32,7)
6、 写出图着色问题的回溯算法的判断 X[k] 是否合理的过程。
7、 对于下图，写出图着色算法得出一种着色方案的过程。
2
3
1
4
8、 写出第 7 题的状态空间树。
9、 写出归并排序算法对下列实例排序的过程。
(6,2,9,3,5,1,8,7)
10、 写出用背包问题贪心算法解决下列实例的过程。
P=(18,12,4,1)
W=(12,10,8,3)
M=25
11 、有一个有序表 {1 ， 3， 9， 12，32，41，45， 62，75，77，82， 95，100} ，当使用二分 找 82 的 点 ， 多少次比 后 找成功并 出 程。
12、使用 prim 算法构造出如下 G的一棵最小生成 。
1
2 4
3
6
5
dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;
dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6
13、有如下函数 明
int f(int x,int y)
{
f=x Mod y +1;
}
已知 a=10,b=4,c=5
行
k=f(f(a+c,b),f(b,c))
后， k 的 是多少并写出 程。
14、 McCathy 函数定 如下：
当 x>100 m(x)=x-10;
当 x<=100 m(x)=m(m(x+11));
写一个 函数 算 定 x 的
15、 一个算法在一个向量
m(x) 。
A 中找出最大数和最小数的元素。
四、 算法
1. 有 n 独立的作 {1,2, ⋯, n}, 由 m台相同的机器加工 理。作 i 所需要的
理 t i 。 定：任何一 作 可在任何一台机器上 理，但未完工前不准中断 理； 任
何作 不能拆分更小的子作 。
多机 度 要求 出一种 度方案， 使所 的 n 个作 在尽可能短的 内由 m台机
器 理完。 算法，并 是否可 最 解。
有 n 种面 :
d1≥ d2≥⋯⋯≥ dn 的 ，需要找零 M，如何 dk，的数目 Xk ， 足
d1× Xi ＋⋯⋯ dn× Xn M ，使得
Xi ＋⋯⋯ Xn 最小
心策略，并 心算法。
3. 有 n 个物品，已知 n=7, 利 P=(10,5,15,7,6,18,3) ，重量 W=(2,3,5,7,1,4,1) ，
背包容 M=15,物品只能 全部装入背包或不装入背包， 心算法，并 是否可
最 解。
只求一个哈密 的回溯算法。
5．利用 称性 算法，求 n 偶数的皇后 所有解。
参考答案
一、 要回答下列 ：
确定性、可 性、 入、 出、有 性
分析算法占用 算