算法与设计六套试卷

算法设计与分析试卷A卷-20080525-参考答案-第二版-by zzm （含试题预测、课堂笔记）

试题答案：

一、简答题

1. 答：如果一个算法不需要额外的存储空间（除个别存储单元以外），我们把它称为是在

位的。 2. 答：如下图，求A到C的最短距离。Dijkstra算法只需一步，就计算出A到C最短路径

为A-C，长度为3；事实上，图中因为存在负权重的边，A到C的最短路径应是A-B-C，

长度为2。

A 3 C 4 B -2

3. 答：对问题的部分或全部输入做预处理，然后对获得的额外信息进行存储，以加速后面

问题的求解。我们把这个方法称为输入增强。

二、答： 解法一：

Mindist (A[0..n-1]) dist ← ∞

for i ← 0 to n-2 do for j ← i+1 to n-1 do if │A[i]-A[j]│

Mindist (A[0..n-1])

将数组A复制到数组B；

用O(nlog n)的排序算法对Ｂ进行升序排序； dist ← B[1]-B[0];

dist ← │A[i]-A[j]│

for i ← 1 to n-2 do if B[i+1]-B[i]

Return dist

解析：解法一将基本操作│A[i]-A[j]│

三、答：

（1） 求数组A中两个元素的最大差值；

（2） 基本操作是：A[i]max； （3） 函数中循环体共循环n次，每次都执行两个基本操作，所以基本操作执行次数为2n，

其算法效率类型为O(n)。

1

解析：第（2）小题中，每次循环都要比较，但不是每次循环都要赋值，因而比较操作是基本操作。第（3）小题由于题目要求计算，最好写出基本计算过程。 四、答

kk-1k

（1） x(2) = x(2) + 2；

x(2k-1) = x(2k-2) + 2k-1；

……

x(2) = x(1) + 2；

x(1) = 1；

kk k-1k+1

则x(2) = 2+ 2+ … + 2 +1 = 2 – 1

（2） O(log n)

五、答：

解法一：

（1） 编码过程：

D B C @ A

0.4 0.2 0.15 0.15

0 0.35 1 0

0

1.0 1 0

0.6 1

0.25 0.1 1

A，B，C，D，@的编码分别为111，100，101，0，110。 （2） 100010111001010解码后为：BDC@DCD

解法二：

（1） 编码过程：

D B C @ A

0.4 0.2 0.15 0.15

1 0.35 0 1

1

1.0 0 1

0.6 0

0.25 0.1 0

A，B，C，D，@的编码分别为000，011，010，1，001， （2） 100010111001010解码后为：DADBD@C

解析：哈夫曼树不唯一，且C和@出现频率相同，所以编码还有其他可能性，以上两解法仅供参考。

六、答：

（1） h(30)=8；h(20)=9；h(56)=1；h(75)=9；h(31)=9；h(19)=8。开散列表如下：

2

0 1 56 …… 8 9 10 30 20 19 75 31

（2） 平均比较次数为：(1+1+2+1+2+3)/6 = 1.67

解析：数组里为散列值，元素存储在其散列值对应的链表中。

在（1）小题中，每次插入新的元素，是放在其散列值对应的链表的末端。例如：在以上基础上插入元素41的结果如下，请大家自己比较：

0 1 56 …… 8 9 10 30 20 19 75 41 31

七、答：

（听说堆排序不做要求，估计会换成平衡二叉树的生成过程。）

八、答：

（1） A = {1，3，4，9，13，34}和B = {2，5，16，22}合并为C的步骤如下：

a) 1 < 2，故1插入C={}，得C={1}；

b) 3 > 2，故2插入C={1}，得C={1，2}；

c) 3 < 5，故3插入C={1，2}，得C={1，2，3}；

d) 4 < 5，故4插入C={1，2，3}，得C={1，2，3，4}；

e) 9 > 5，故5插入C={1，2，3，4}，得C={1，2，3，4，5}；

f) 9 < 16，故9插入C={1，2，3，4，5}，得C={1，2，3，4，5，6}；

g) 13 < 16，故13插入C={1，2，3，4，5，6}，得C={1，2，3，4，5，6，13}； h) 34 > 16，故16插入C={1，2，3，4，5，6，13}，得C={1，2，3，4，5，6，13，

16}； i) j)

34 > 22，故22插入C={1，2，3，4，5，6，13，16}，得C={1，2，3，4，5，6，13，16，22}；

34插入C={1，2，3，4，5，6，13，16，22}，得C={1，2，3，4，5，6，13，16，22，34}；

（2） 因为合并排序就是交替遍历数组A和B，并把它们中的元素非递减地插入数组C中，

基本操作就是对A和B数组的遍历。假设A和B的规模分别为m和n，合并排序

3

算法最坏情况下的时间效率是O(m + n)。

解析：A和B自身内部已经排序

试题预测：

一、简答题

1. 简述什么是在位的算法？ 答：如果一个算法除了个别存储单元以外, 不需要额外的存储空间, 我们把它称为是在位的.

2. 简述什么是稳定的排序算法？

答：如果一个排序算法保留了等值元素在输入中的相对顺序, 它就被称为是稳定的.

3. 某某排序算法的时间复杂度，是否稳定？

4. 哪些排序算法是稳定的算法？哪些不是稳定的算法，请举出例子。 5. 哪些排序算法的时间复杂度是O(nlog n)？

排序 直接插入排序 冒泡算法 快速排序 直接选择排序 希尔排序 堆排序 归并排序 基数排序 时间复杂度 平均情况 O(n) O(n) O(nlog n) O(n2) O(nlog n) O(nlog n) O(nlog n) O(d(n+r)) 22最坏情况 O(n) O(n) O(n2) O(n2) O(nlog n) O(nlog n) O(nlog n) O(d(n+r)) 22最好情况 O(n) O(n) O(nlog n) O(n2) O(nlog n) O(nlog n) O(d(n+r)) 空间复杂度 O(1) O(1) O(nlog n) O(1) O(1) O(1) O(1) O(n+r) 稳定性 稳定 稳定 不稳定 不稳定 不稳定 不稳定 稳定 稳定 解析：冒泡排序、快速排序、直接选择排序、直接插入排序比较基础，可能会考察。

6. 请简述符号t(n)∈θ(g(n)), t(n)∈Ω(g(n)),t(n)∈Ο(g(n))的含义。 答：t(n)∈θ(g(n))成立的条件是: 对于所有足够大的n, t(n)的上界由g(n)的常数倍所确定, 也就是说, 存在大于0的常数c和非负的整数n0, 使得: 对于所有的n>=n0来说, t(n)<=cg(n)； t(n)∈Ω(g(n))成立的条件是: 对于所有足够大的n, t(n)的下界由g(n)的常数倍所确定, 也就是说, 存在大于0的常数c和非负的整数n0, 使得: 对于所有的n>=n0来说, t(n)>=cg(n)； t(n)∈Ο(g(n)) 成立的条件是: 对于所有足够大的n, t(n)的上界和下界都由g(n)的常数倍所确定, 也就是说, 存在大于0的常数c1和C2和非负的整数n0, 使得: 对于所有的n>=n0来说, c2g(n)<=t(n)<=c1g(n)

解析：只要记住，θ(g(n))是t(n)<=cg(n)，也就是有上界；t(n)∈Ω(g(n)) 是t(n)>=cg(n)，也就是有下界；t(n)∈Ο(g(n))， c2g(n)<=t(n)<=c1g(n)，也就是上下界都有。C、C1、C2为某常数。其他语言可以自己组织，不影响大局。

7. 顺序查找和折半查找的时间效率类型。 答：O(n) ，O(log n)

4

二、分析代码效率类型 1. 常见的O(n)代码： Mindist (A[0..n-1]) dist ← ∞

for i ← 0 to n-1 do

for j ← 0 to n-1 do

if i≠j and │A[i]-A[j]│

2. 常见的O(log n)代码： X（n）

if i=1 return 1

2

return X(n/2)+n

3. 常见的O(n)代码： Secret(A[0..n-1])

min ← A[0]; max ← A[0]

for i ← 1 to n do

if A[i] < min

min ← A[i] if A[i] > max

max ← A[i] Return max-min

4. 常见的O(n3)代码： Sum(A[0...n-1][0..n-1][0..n-1])

S=0

for i ← 1 to n-1 do

for j ← 1 to n-1 do

for k ← 1 to n-1 do

S+=A[i][j][k]

Return S

5. 常见的O(nlog n)代码：

解析：分析代码效率类型，主要是观察代码形态。计算循环或递归的次数，认清基本

操作，对这两个进行分析，然后得出效率类型。

三、斐波那契数列 递归算法： Fib(n)

5

iv. v. Endif EndFor

求出满足 v(uj)=max{ v(u1), v(u2),…, v(un)} 的整数j If P < v(uj) then U’={uj} vi.

Output U’

： 号学线 --- --- --- --- --- --- --- --- -- -- - 封 ： -名----姓---- -- - -- - -- - -- - -- - -- - -- - -- - -： 级密 -班---- --- --- --- --- --- --- --- --- --- --- --- ：---程---课---试--考11

、⑴ 证明：令F(N)=O(f),则存在自然数N1、C1，使得对任意的自然数N?N1，有：

F(N)?C1f(N);……………………………..（2分）

同理可令G(N)=O(g), 则存在自然数N2、C2，使得对任意的自然数N?N2，

有： G(N)?C2g(N); ……………………………..（3分）

令 C3=max{C1,C2},N3=max{N1,N2},则对所有的N?N3，有： F(N)?C1f(N)?C3f(N);

G(N)?C2g(N)?C3g(N); ……………………………..（5分） 故有：

O(f)+O(g)=F(N)+G(N)

?C3f(N)?C3g(N)?C3(f(N)?g(N))?O(f?g)

因此有：

O(f)+O(g)=O(f+g) ……………………………..（7分）

⑵ 解：① 因为：lim2(3n?10n)?3n3n?10n222n???0;由渐近表达式的定义易知：

3n是3n?10的渐近表达式。……………………………..（3分） ② 因为：lim(21?1/n)?2121?1/n?0;由渐近表达式的定义易知：

2n?? 21是21+1/n的渐近表达式。……………………………..（6分） 2、解：经分析结论为：

（1）logn??(logn?5);………………………….（5分）

2 （2）logn??(n)；………………………….（10分）

2 （3）n??(log2n)；………………………….（15分）

3、解：用分治法求解的算法代码如下： int partition(float A[],int p,int r)

12

{

int i=p,j=r+1; float x=a[p]; while (1) {

while(a[++i]x); if(i>=j) break;

a[i]?a[j]; ……………………………..（4分）

};

a[p]=a[j]; a[j]=x;

return j; ……………………………..（7分）

}

void Quicksort( float a[], int p, int r ) {

if( p

int q=partition(a,p,r); ……………………………..（10分） Quicksort(a,p,q-1); Quicksort(a,q+1,r); } };

Quicksort(a,0,n-1); ……………………………..（13分） 4、解：用动态规划算法求解的算法代码如下： int lcs_len(char *a,char *b,int c[][N]) {

int m=strlen(a),n=strlen(b),i,j; for(i=0;i<=m;i++) c[i][0]=0;

for(j=1;j<=n;j++) c[0][j]=0; ……………………………..（4分） for(i=1;i<=m;i++) for(j=1;j<=n;j++)

if(a[i-1]= =b[j-1]) c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];

else c[i][j]=c[i][j-1]; ……………………………..（7分） return c[m][n]; ……………………………..（8分） };

char *build_lcs(char s[],char *a,char *b) {

int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcs_len(a,b,c); s[k]=’\\0’; while(k>0){

if(c[i][j]= =c[i-1][j]) i--;……………………………..（11分）

13

else if(c[i][j]= =c[i][j-1]) j--; else{

s[--k]=a[i-1]; i--,j--; } }

return s; ……………………………..（15分）

}

5、解：int greedy(vecterx,int n)

{

int sum=0,k=x.size(); for(int j=0;jn){

cout<<”No solution”<

return -1; ……………………………..（6分） }

for(int i=0,s=0;i

if(s>n){ sum++;s=x[i];} ……………………………..（9分） }

return sum; ……………………………..（12分）

}

6、解：此题用动态规划算法求解：

int dist( ) {

int m=a.size( ); int n=b.size( );

vectord(n+1,0);

for(int i=1;i<=n;i++) d[i]=i; ……………………………..（5分）

for(i=1;i<=m;i++){ int y=i-1;

for(int j=1;j<=n;j++){

int x=y; y=d[j];

int z=j>1?d[j-1]:i; ……………………………..（10分） int del=a[i-1]= =b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1); ……………………………..（13分） } }

return d[n]; ……………………………..（16分） }

7、解：解答如下：

void compute() {

14

k=1;

while(!search(1,n)){ k++;

if(k>maxdep) break; init();

};……………………………..（6分）

if(found) output();……………………………..（9分）

else cout<<”No Solution!”<

}

bool search(int dep,int n)

{

if(dep>k) return false; ……………………………..（11分） for(int i=0;i<2;i++){

int n1=f(n,i);t[dep]=I; ……………………………..（13分） if(n1= =m||search(dep+1,n1)){ found=true; out();

return true;

}

return false; ……………………………..（16分）

}

第九章

福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 B 卷

15

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 16

一．填空题（每空2分，共30分） 1．算法的五个特性是 。 2．在忽略常数因子的情况下，O，?和?三个符号中， 提供了算法运行时间的一个确切界限。 3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间，则算法的最坏情况下时间复杂性W(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： ??f(n)?d , n?n0?f(n)?af(n/c)?g(n) , n?n0 其中， a表示 。 5．动态规划算法中存储子问题的解是为了 。 6．在一个问题的状态空间树中，若从根到某结点的路径对应该问题的一个解，则称该结点为一个 结点。 7．分治法不同于动态规划，其分解出的子问题是 。 8．贪心算法通过一系列局部最优选择来求解问题，最终 能得到问题的最优解。 9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越 ，优先级越高。 10．快速排序、插入排序和归并排序算法中， 算法不是分治算法。 11．在随机算法中，Las Vegas算法的特点是 。 12．若对一个问题的求解可转化为对其性质相同的子问题的求解，则称该问题满足 。 13．下面算法的基本运算是 运算。 算法 SPLIT 输入：正整数n，数组A[1..n]。 输出：…。 i=1

17

＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年 ＿ ＿ 信＿＿ ＿ ＿ 业 专 生＿＿ ＿ ＿ ＿ ＿ 系 考＿＿＿＿＿＿院学＿＿＿＿＿＿ x=A[1] for j=2 to n if A[j]<=x then i=i+1 if i?j then A[i]?A[j] end if end for A[i]?A[1] w =i return w, A 线 end SPLIT 14．下面算法的功能是 ，其时间复杂性阶为?( )。 算法 EX1 输入：实数x和非负整数n 。 订 输出：… y=ex1(x, n) output y end EX1 装过程 ex1 (x, m) if m=0 then y=1 else y=ex1 (x, ?m/2?) y=y*y if m为奇数 then y=x*y 18

end if return y end ex1 二．计算题和简答题（每小题7分，共21分） 1．将下列各函数按阶分类，同阶的分为一类，并将各类的阶按从低到高的顺序排列： f1(n)=1000 f2(n)=6n+n?logn?-5 f3(n)=3n f4(n)=2n?n2 f5(n)=1 f6(n)=4n+n/logn-1 f7(n)=2(n?n) f8(n)=nlogn+log8n 2．算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程?T(n)?1 , n?1 ??T(n)?4T(n/2)?n , n?1，算法B的时间复杂性满足递归方程?T(n)?1 , n?1 ，若要使得算法??T(n)?aT(n/4)?n , n?1A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？ 3．对于字符集合M={A,B,C,D,E,F}，设这些字符在文本中出现的频率分别为8,1,3,10,6,5，画出字符集合M的Huffman编码树，并给出各字符的Huffman编码。 三．算法填空题（共34分） 1．（10分）下面是求解分数背包问题的贪心算法。 分数背包问题：设有一个容量为C的背包，n个物品的集合U={u1, u2, …, un}，物品ui的体积和价值分别为sj和vj，C, sj, vj都是正实数。在U中选择物品装入背包，使得装入背包的物品总价值最大。设允许取每种物品的一部分装入背包。 19

算法 GREEDY_KANPSACK ＿＿＿＿＿号学 ＿ 栏＿＿ ＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ 信 ＿ ＿ ＿ ＿ 业 专订 生 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿

输入：表示背包容量的实数C, 物品数n, 表示n个物品的体积和价值的实数数组s[1..n]和v[1..n]。 输出：装入背包的物品的最大总价值maxv和相应的最优解x[1..n]。 for i=1 to n y[i]=v[i]/s[i] end for d=sort(y, n) //对y[1..n]按降序地址排序，排序结果返回//到数组d[1..n]中, 使得//y[d[1]]>=y[d[2]]>=…>=y[d[n]]。 for i=1 to n x[i]=0 i=1; maxv=0; rc=C while (1) j=d[i] if (2) then x[j]=1; rc=rc-s[j] else x[j]= (3) (4) end if maxv= (5) i=i+1 end while return maxv, x[1..n] end GREEDY_KNAPSACK 20

2．（10分）下面是用回溯法求解图的m着色问题的算法（求出所有解）。 图的m着色问题：给定一个无向连通图G和m种颜色，给图G的所有顶点着色，使得任何两相邻顶点的颜色不同。 算法 m-COLORING 输入：正整数m, n和含n个顶点的无向连通图G的邻接矩阵graph。 输出：图G的m着色问题的所有解, 若无解，则输出no solution。 flag=false k=1; x[1]=0 while k>=1 while (1) x[k]=x[k]+1 if color(k) then if (2) then flag=true; output x[1..n] else k= (3) (4) end if end if end while (5) end while if not flag then output “no solution” end m-COLORING 过程 color (k) //在前k-1个顶点已着色的情况下，判断第k个顶点是否可着颜色x[k], 是则 21

//返回true, 否则返回false。 ＿＿＿＿＿号学 ＿栏＿ ＿ ＿ ＿ ＿ 名 姓息 级 年线 ＿ 信＿ ＿ ＿ ＿ ＿ 业 生专订 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿

…… end color 3．（14分）设有n种不同面值的硬币，面值分别为c1, c2, ? , cn（c1=1），每种硬币的个数不限，要求用最少个数的硬币，兑换价值为m的钱（m为非负整数）。 设f[k, j]表示用面值为c1, c2, ? , cj的硬币兑换价值为k的钱所用硬币的最少个数，则 ?k , j f[k,j]???1???0?mini??k/c?f[k?i*cj, j-1]?i? , j?1 j?下面是解该最优化问题的最优值和最优解的动态规划算法。 算法 CHANGING 输入：正整数n，非负整数m，存储n种硬币面值的数组c[1..n]，其中c[1]=1。 输出：兑换价值为m的钱所用硬币的最少个数和存储最优解信息的数组s[0..m, 1..n]。 f[0..m, 1..n]= -1 min=coinchanging(m, n) return min, s end CHANGING 过程 coinchanging(k, j) //求用面值为c[1],c[2],…,c[j]的硬币兑换价值为k的钱所用硬 //币的最少个数，并返回。同时记录最优解的信息于数组s中。 if f[k, j]= (1) then if j=1 then f[k, j]=k 22

else minx=coinchanging(k, j-1); i0=0 for i=1 to ?k/c[j]? x= (2) +i if x

＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级 姓名＿＿＿＿＿＿ 学号＿＿＿＿＿ 四．算法设计题（15分） 1. 写出一个随机算法，对于一个由n个整数组成的序列，求其中的第1~k小元素（即序列按升序排序后的前k个元素），并给出该算法的期望时间复杂性的阶。 考 生 信 息 栏 装 订 线

2005计本《算法设计与分析》期考试卷(B)标准答案

一. 填空题：

1. 有穷性，确定性，可行性，有>=0个输入，有>0个输出

24

2. ? 3. max{t(I)}

I?Dn4. 分解出的需要求解的子问题的个数 5. 避免重复求解子问题 6. 答案

7. 相互独立的（不重叠的） 8. 不一定 9. 小

10. 插入排序算法

11. 总是或者得到正确的解或者找不到解。 12. 递归关系 13. 比较 14. 求xn的值 ?(logn)

二. 计算题和简答题：

这些函数按不同的阶分成如下4类：

Θ(1): f1, f5 Θ(n): f3, f6, f7 Θ(nlogn): f2, f8 Θ(2n): f4

各类的阶按从低到高的顺序排列的结果是：

Θ(1), Θ(n), Θ(nlogn), Θ(2n)

2. 解：

分别记算法A和算法B的时间复杂性为TA(n)和TB(n)，解相应的递归方程得： TA(n)?O(n)

?O(n) , a?4? TB(n)??O(nlogn) , a?4

?log4a) , a?4?O(n2TB(n)?TA(n)； 依题意，要求最大的整数a使得TB(n)?TA(n)。显然，当a<=4时，

当a>4时，TB(n)?TA(n) ?log值为15。

3. 字符集合M的Huffman编码树是：

42a?2 ?a<4=16。所以，所求的a的最大整数

25

各字符的Huffman编码：

A: 01 B:1000 C: 1001 D: 11 E:00 F: 101 三. 算法填空题：

1. (1) rc>0 and i<=n (2) s[j]<=rc (3) rc/s[j] (4) rc=0 (5) maxv+v[j]*x[j]

2. (1) x[k]

3. (1) –1 (2) coinchanging(k-i*c[j], j-1)

(3) i (4) minx

(5) i0 (6) s[k, i] (7) k-x[i]*c[i]

四. 算法设计题：

1. 算法 RANDOMIZEDSELECT

输入：整数n, k, 1<=k<=n, 以及n个元素的整数数组A[1..n]。 输出：A中的第1~k小元素。

rselect ( A , 1, n, k ) end RANDOMIZEDSELECT 过程 rselect ( A , low, high, k )

//求A[low..high]中的前k小元素并输出。

v=random(low, high)

mm=A[v]

将A[low..high]分成三个数组：

A1={a|amm}

if |A1|>=k then

rselect (A1,1, |A1|, k)

else if |A1|+|A2|>=k then

输出A1的所有元素以及k-|A1|个mm值

else

输出A1和A2的所有元素

rselect (A3,1, |A3|, k-|A1|-|A2| )

end if

26

end if

return end rselect

福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 A 卷

该算法的时间复杂性的阶是?(n)。 27

栏 息 信

生

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 2007 年 1 月 13 日 下 午 18 点 30 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 一．填空题（每空2分，共30分） 1．算法的时间复杂性指算法中 的执行次数。 2．在忽略常数因子的情况下，O、?和?三个符号中， 提供了的一个上界。 3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间I出现的概率，则算法的平均情况下时间复杂性A(n)= 4．分治算法的时间复杂性常常满足如下形式的递归方程： ?f(n)?d , n?n?0?f(n)?af(n/c)?g(n) , n?n 0 其中，g(n)表示 。 5. 分治算法的基本步骤包括 。 6．回溯算法的基本思想是 。 7．动态规划和分治法在分解子问题方面的不同点是 。8．贪心算法中每次做出的贪心选择都是 最优选择。 9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越越 。 10．选择排序、插入排序和归并排序算法中， 算法是分治算 11．随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到结果。 12.对于下面的确定性快速排序算法，只要在步骤3前加骤 28 ，就可得到一个随机化快速排序算步骤的功能是 。 , A[i]?A[1] w =i return w, A end SPLIT 二．计算题和简答题（每小题7分，共21分） 1．用O、?、?表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数： (1) f (n)=100 g(n)=100n (2) f(n)=6n+n?logn? g(n)=3n (3) f(n)= n/logn-1 g(n)=2n (4) f(n)=2n?n2 g(n)=3n (5) f(n)= log3n g(n)= log2n 2．下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和log2n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用?表示）。 算法 EX1 输入：正整数n，n=2k。 输出：… ex1(n) end EX1 过程 ex1(n) if n=1 then pro1(n) else 29

＿＿＿＿＿号学 ＿栏＿ ＿ ＿ ＿ ＿ 名 姓息 级 年 ＿信＿ ＿ ＿ ＿ ＿ 业 生专 ＿ ＿ ＿ ＿ ＿ ＿考系＿＿＿＿＿＿院学＿＿＿＿＿＿

pro2(n) ex1(n/2) end if return end ex1 3．用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i, j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。 线 三．算法填空题（共34分） 1．（10分）设n个不同的整数按升序存于数组A[1..n]中，求使得A[i]=i 订 的下标i 。下面是求解该问题的分治算法。 算法 SEARCH 输入：正整数n，存储n个按升序排列的不同整数的数组A[1..n]。 输出：A[1..n]中使得A[i]=i的一个下标i，若不存在，则输出 no 装solution。 i=find ( (1) ) if i>0 then output i else output “no solution” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i的一个下标并返回，若不存在， 30

//则返回0。 if (2) then return 0 else mid=?(low?high)/2? if (3) then return mid else if A[mid]

for i=1 to n C[i, i]= （1） for d=1 to n-1 for i=1 to n-d ＿＿＿＿＿号学 栏＿＿ ＿ ＿ ＿ ＿ 名 息姓 级 年线 ＿ 信 ＿ ＿ ＿ ＿ ＿ 业 生专订 ＿ ＿ ＿ ＿ ＿ 考＿ 系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿ j= (2) C[i, j]= ∞ for k=i+1 to j x= (3) if x

x=x0; y=y0 ; tag[x, y]=1 m=n*n i=1; k[i]=0 while (1) and not flag while k[i]<8 and not flag k[i]= (2) x1= x+dx[k[i]]; y1= y+dy[k[i]] if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tag[x, y]= (3) if i=m then flag=true else i= (4) (5) end if end if end while i=i-1 (6) (7) end while if flag then outputroute(k) //输出路径 else output “no solution” end HORSETRAVEL

33

＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿ 四．算法设计题（15分） 1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，0=d1?d2???dn?s，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。 福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 C 卷

34

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 35

一．填空题（每空2分，共30分） 1．计算复杂性包括 两个方面。 2．在忽略常数因子的情况下，?提供了算法运行时间的一个 界。 3．算法的平均情况下时间复杂性A(n)=?p(I)t(I)，其中Dn表示大小为n的输I?Dn入集合，t(I)表示输入为I时算法的运算时间, p(I)表示 。 4．从算法时间复杂性的角度看，时间复杂性阶为 的算法是实际可接受的。 5．用动态规划算法解题时， ，算法的效率越高。 6．分治算法的基本步骤包括 。 7．回溯算法的搜索顺序是 。 8．贪心法通常用于求解 问题。 9．PQ式的分支限界法中，活结点表的结构是 。 10．Prim算法、 Dijkstra算法、快速排序算法和Huffman算法中 不是贪心算法。 11．一个问题满足递归关系是指 。 12．随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间 。 13对于下面的确定性二分查找算法，只要将步骤3改为随机化步骤 ，就可得到一个随机化查找算法。 算法 BISEARCH 输入：正整数n，n个元素的升序数组A[1..n]和元素x。 输出：如果存在j，1<=j<=n使得x=A[j]，则输出j，否则输出0。 1. low=1; high=n ; j=0 2. while (low<=high) and (j=0) 3. mid=?(low?high)/2? 4. if x=A[mid] then j=mid 5. else if x

6. else low=mid+1 ＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年 ＿ ＿ 信＿＿ ＿ ＿ 业 专 生＿＿ ＿ ＿ ＿ ＿ 系 考＿＿＿＿＿＿院学＿＿＿＿＿＿ 7. end if 8. end if 9. end while 10. return j end BISEARCH 14．下面算法的基本运算是 运算，该算法中第4步执行了 次。 算法 COUNT 输入：正整数n（n=2k）。 线 输出：count的值。 1. count=0 2. while n>=1 订 3. for j=1 to n 4. count =count+1 5. end for 6. n=n/2 装7. end while end COUNT 二．计算题和简答题（每小题7分，共21分） 1．用?表示下列各函数的阶，并按阶从低到高的顺序排列这些函数。 n3/(n+5) , 2n+ 3n/2, 5n2log3n+n3log2n, n!+nn, log(logn)/1000 37

2．下面是一个分治算法，其中，过程pro1和pro2的运算时间分别是1和nlog2n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用?表示）。 算法 EX2 输入：正整数n，n=2k。 输出：… ex2(1, n) end EX2 过程 ex2(low, high) if low>=high then pro1( ) else m=?(low?high)/2? ex2(low, m) ex2(m+1, high) pro2(low, high) end if return end ex2 3．设矩阵M1，M2，M3，M4，M5的阶如下： M1：10?2 M2：2?5 M3：5?2 M4：2?4 M5：4?10。 下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果，

38

＿＿＿＿＿号学 ＿ 栏＿＿ ＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ 信 ＿ ＿ ＿ ＿ 业 专订 生 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿

C[1,1]=0 C[1,2]=100 C[1,3]=60 C[1,4]= C[1,5]= C[2,2]=0 C[2,3]=20 C[2,4]=36 C[2,5]= C[3,3]=0 C[3,4]=40 C[3,5]=180 C[4,4]=0 C[4,5]=80 C[5,5]=0 表1 S[1,1]=0 S[1,2]=2 S[1,3]=2 S[1,4]= S[1,5]= S[2,2]=0 S[2,3]=3 S[2,4]=4 S[2,5]= S[3,3]=0 S[3,4]=4 S[3,5]=4 S[4,4]=0 S[4,5]=5 S[5,5]=0 表2 其中，C[i, j]表示求MiMi+1…Mj所需的最少数量乘法次数，S[i, j]表示相应的最优解信息。填充表1和表2中空缺的数据，并根据数组S确定求M1M2M3M4M5的最优顺序（通过加括号表示）。 三．算法填空题（共34分） 1．（10分）下面是快速排序算法。 算法 QUICKSORT 输入：正整数n，n个元素的数组A[1..n]。 输出：按非降序排列的数组A中的元素。 quicksort(A,1,n) end QUICKSORT 过程 quicksort(A, low, high) // 将A[low..high]中的元素按非降序快速排序。 if low

quichsort( (1) ) quichsort( (2) ) end if end quicksort 过程 SPLIT ( A, low, high) //以A[low]为主元划分A[low..high], 返回主元的新位置。 i=low; x=A[low] for j=low+1 to high if A[j]<=x then i= (3) if i≠j then (4) end if end for (5) w=i return w end SPLIT 2. (10分)下面是用回溯法解n皇后问题的算法（求出所有解）。 n皇后问题：在n x n棋盘上放置n个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。） 算法 NQUEENS 输入：正整数n。 输出：n皇后问题的一个解x[1..n], 若无解，则输出No solution。 flag=false k=1 ; x[1]=0

40

while (1) while x[k]

x[k]= (2) if place(k) then if k=n then flag=true；output x[1..n] else k= (3) (4) end if end if end while (5) end while if not flag then output “No solution” end NQUEENS 过程 place (k) //判断第k行皇后是否与前k-1行皇后冲突，是则返回false, 否 //则返回true。 …… end place 3. （14分）下面是解可复选的背包问题的动态规划算法。 问题描述：有一个容量为C的背包和n种物品，每种物品的个数都是无限的。设第i种物品的体积和价值分别为si和vi，C, si, vi都是正整数，i=1,2,…,。在这n种物品中选择物品装入背包，使得 41

装入背包的物品总价值最大。设每种物品都可选择任意个装入背包。 设f[i, j]表示背包容量为j，在第1~i种物品中进行选择的可复选背包问题的最优值，则 ??0 , i?0 f[i, j]??max{f[i?1, j-k*s]?k*v} , i?0 ii??0?k??j/si?算法 KNAPSACK 输入：物品种数n, n种物品的体积数组s[1..n]和价值数组v[1..n], 背包容量C。 输出：装入背包物品的最大总价值maxv，以及存储最优解信息的数组 H[0..n, 0..C]。 f[0..n, 0..C]=-1 maxv=knapsack(n, C) return maxv , H end KNAPSACK 过程 knapsack(i, j) //从第1~i种物品中选择物品装入容量为j的背包中，求背包中物品//所能达到的最大总价值并返回，同时将最优解的相应信息存入数//组H[0..n, 0..C]。 if f[i, j]= (1) then if i=0 then f[i,j]=0 else max=knapsack(i-1,j) k0=0; j1=j; v1=0 for k=1 to ?j/s[i]? j1=j1-s[i]; v1=v1+v[i]

42

a= (2) ＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿

if a>max then max=a (3) end if end for f[i, j]= (4) (5) end if end if return f[i, j] end knapsack 算法 KNAPSACK_SOLUTION 输入：物品种数n , 背包容量C, n种物品的体积数组s[1..n], 相应的可复选的背包问题的最优解信息数组H[0..n, 0..C]。 输出：相应的可复选的背包问题的最优解x[1..n]。 y=C; x[n]=H[n, C] for i=n-1 to 1 y= (6) x[i]= (7) end for return x[1..n] end KNAPSACK_SOLUTION 43

四．算法设计题（15分） 1. 设有n种不同面值的硬币，面值分别为c1, c2, ? , cn，ci?1=sici，si为正整数，i=1, 2, …, n-1，每种硬币的个数不限，要求用最少个数的硬币，兑换价值为m的钱（m为非负整数），给出用贪心法求解该最优化问题的贪心选择策略，写出求最优值和最优解的贪心算法，并分析算法的时间复杂性。 福建师范大学数学与计算机科学学院

2006 — 2007学年第二学期考试 C 卷

44

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 45

一．填空题（每空2分，共30分） 1．计算复杂性包括 两个方面。 2．在忽略常数因子的情况下，?提供了算法运行时间的一个 界。 3．算法的平均情况下时间复杂性A(n)=?p(I)t(I)，其中Dn表示大小为n的输I?Dn入集合，t(I)表示输入为I时算法的运算时间, p(I)表示 。 4．从算法时间复杂性的角度看，时间复杂性阶为 的算法是实际可接受的。 5．用动态规划算法解题时， ，算法的效率越高。 6．分治算法的基本步骤包括 。 7．回溯算法的搜索顺序是 。 8．贪心法通常用于求解 问题。 9．PQ式的分支限界法中，活结点表的结构是 。 10．Prim算法、 Dijkstra算法、快速排序算法和Huffman算法中 不是贪心算法。 11．一个问题满足递归关系是指 。 12．随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间 。 13对于下面的确定性二分查找算法，只要将步骤3改为随机化步骤 ，就可得到一个随机化查找算法。 算法 BISEARCH 输入：正整数n，n个元素的升序数组A[1..n]和元素x。 输出：如果存在j，1<=j<=n使得x=A[j]，则输出j，否则输出0。 1. low=1; high=n ; j=0 2. while (low<=high) and (j=0) 3. mid=?(low?high)/2? 4. if x=A[mid] then j=mid 5. else if x

7. else low=mid+1 ＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年 ＿ ＿ 信＿＿ ＿ ＿ 业 专 生＿＿ ＿ ＿ ＿ ＿ 系 考＿＿＿＿＿＿院学＿＿＿＿＿＿ 7. end if 8. end if 9. end while 10. return j end BISEARCH 14．下面算法的基本运算是 运算，该算法中第4步执行了 次。 算法 COUNT 输入：正整数n（n=2k）。 线 输出：count的值。 1. count=0 2. while n>=1 订 3. for j=1 to n 4. count =count+1 5. end for 6. n=n/2 装7. end while end COUNT 二．计算题和简答题（每小题7分，共21分） 1．用?表示下列各函数的阶，并按阶从低到高的顺序排列这些函数。 n3/(n+5) , 2n+ 3n/2, 5n2log3n+n3log2n, n!+nn, log(logn)/1000 47

2．下面是一个分治算法，其中，过程pro1和pro2的运算时间分别是1和nlog2n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用?表示）。 算法 EX2 输入：正整数n，n=2k。 输出：… ex2(1, n) end EX2 过程 ex2(low, high) if low>=high then pro1( ) else m=?(low?high)/2? ex2(low, m) ex2(m+1, high) pro2(low, high) end if return end ex2 3．设矩阵M1，M2，M3，M4，M5的阶如下： M1：10?2 M2：2?5 M3：5?2 M4：2?4 M5：4?10。 下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果，

48

＿＿＿＿＿号学 ＿ 栏＿＿ ＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ 信 ＿ ＿ ＿ ＿ 业 专订 生 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿

C[1,1]=0 C[1,2]=100 C[1,3]=60 C[1,4]= C[1,5]= C[2,2]=0 C[2,3]=20 C[2,4]=36 C[2,5]= C[3,3]=0 C[3,4]=40 C[3,5]=180 C[4,4]=0 C[4,5]=80 C[5,5]=0 表1 S[1,1]=0 S[1,2]=2 S[1,3]=2 S[1,4]= S[1,5]= S[2,2]=0 S[2,3]=3 S[2,4]=4 S[2,5]= S[3,3]=0 S[3,4]=4 S[3,5]=4 S[4,4]=0 S[4,5]=5 S[5,5]=0 表2 其中，C[i, j]表示求MiMi+1…Mj所需的最少数量乘法次数，S[i, j]表示相应的最优解信息。填充表1和表2中空缺的数据，并根据数组S确定求M1M2M3M4M5的最优顺序（通过加括号表示）。 三．算法填空题（共34分） 2．（10分）下面是快速排序算法。 算法 QUICKSORT 输入：正整数n，n个元素的数组A[1..n]。 输出：按非降序排列的数组A中的元素。 quicksort(A,1,n) end QUICKSORT 过程 quicksort(A, low, high) // 将A[low..high]中的元素按非降序快速排序。 if low

quichsort( (1) ) quichsort( (2) ) end if end quicksort 过程 SPLIT ( A, low, high) //以A[low]为主元划分A[low..high], 返回主元的新位置。 i=low; x=A[low] for j=low+1 to high if A[j]<=x then i= (3) if i≠j then (4) end if end for (5) w=i return w end SPLIT 2. (10分)下面是用回溯法解n皇后问题的算法（求出所有解）。 n皇后问题：在n x n棋盘上放置n个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。） 算法 NQUEENS 输入：正整数n。 输出：n皇后问题的一个解x[1..n], 若无解，则输出No solution。 flag=false k=1 ; x[1]=0

50

本文来源：https://www.bwwdw.com/article/h6i5.html