发布时间 : 星期六 文章算法分析与设计考试复习题及参考答案更新完毕开始阅读e2364bc56ad97f192279168884868762cbaebb4c
W[2]< CU: x[2]←1; CU←CU-W[2]=3;
W[3]>CU: x[3]←CU/ W[3]=3/8; 实例的解为：（1，1，3/8，0）
11 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。 一共要要执行四次才能找到值为82的数。
12．使用普里姆算法构造出如下图G的一棵最小生成树。
1 2 3 4 5 6
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
1 1 1 4 3 3 3 6 6 1 2 4 2 3 3 6
13.有如下函数说明 int f(int x,int y) {
f=x Mod y +1;
5 6
1 4 }
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。 }
K的值是5
14.McCathy函数定义如下： 当x>100时 m(x)=x-10;
当x<=100时 m(x)=m(m(x+11));
编写一个递归函数计算给定x的m(x)值。 int m(int x) {
int y;
if(x>100) return(x-100); else {
y=m(x+11);
return (m(y)); } }
15 设计一个算法在一个向量A中找出最大数和最小数的元素。 Void maxmin(A,n) Vector A; int n; {
int max,min,i; max=A[1];min=A[1]; for(i=2;i<=n;i++) if(A[i]>max)max=A[i];
else if(A[i] printf(“max=%d,min=%d\\n”,max,min); } 四、设计算法 1. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。 多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。 2. 设有n种面值为: d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足 d1×Xi＋……dn×XnM ，使得 Xi＋……Xn 最小 请选择贪心策略，并设计贪心算法。 3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。 4. 设计只求一个哈密顿环的回溯算法。 k 5．利用对称性设计算法，求n=2（K为正整数）的皇后问题所有解。 1. 解：对于处理机j，用S[j] 表示处理机j已有的作业数，用P[j,k]表示处理机j的第k个作业的序号 。 1）将作业按照t[1]≥t[2]≥……≥t[n]排序 2）S[1:m]清零 j←0 //从第一个处理机开始安排 3) for i←1 to n do //安排n个作业 j←j mod m +1 //选下一个处理机 S[j]←S[j]+1; P[j,S[j]]←i ； Repeat 2. 贪心原则：每次选择最大面值硬币。 CU←M;i←1;X←0 // X为解向量 While CU≠0 do X[i]←CU div d[i] // X[i]为第i中硬币数 CU←CU-d[i]*X[i] i←i+1; repeat 3、 定义结构体数组G，将物品编号、利润、重量作为一个结构体：例如G[k]={1,10,2} 求最优解，按利润/重量的递减序，有 {5,6,1,6} {1,10,2,5}{6,18,4,9/2} {3,15,5,3} {7,3,1,3}{2,5,3,5/3} {4,7,7,1} 算法 procedure KNAPSACK(P，W，M，X，n) //P(1：n)和W(1；n)分别含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小，而x(1：n)是解向量// real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n； X←0 //将解向量初始化为零// cu←M //cu是背包剩余容量// for i←1 to n do if W(i)>cu then exit endif X(i) ←1 cu←cu-W(i) repeat end GREEDY-KNAPSACK 根据算法得出的解： X=（1,1,1,1,1,0,0）获利润52， 而解 （1,1,1,1, 0, 1,0）可获利润54 因此贪心法不一定获得最优解。 4． Hamiltonian(n) {k←1; x[k] ←0; While k>0 do x[k] ← x[k]+1; while B(k)=false and x[k]≤n do x[k] ← x[k]+1; repeat If x[k]≤n then if k=n then {print x; return} else {k← k+1; x[k]←0;} endif else k← k-1 endif repeat end procedure B(k) { G[x[k-1],x[k] ]≠1 then return false; for i←1 to k-1 do if x[i]=x[k] then return false;endif repeat return true; } 5．利用对称性设计算法，求n为偶数的皇后问题所有解。 procedure NQUEENS1(n) a←0 //计数器清零 X(1)←0；k←1 //k是当前行；X(k)是当前列// While k>0 do //对所有的行执行以下语句// 1) { X(k)←X(k)+1 //移到下一列// While X(k)≤n and not PLACE(k) do 2) X(k)←X(k)十l if X(k)≤n then if k=n / then {print(X)，a←a+1 //找到一个解计数器a加1// if a=n/2 then return // 找到n/2个解算法结束 3) else {k←k+1；X(k)←0；} 4) else k←k－1 //回溯// } end NQUEENS