算法设计与分析大作业答案

算法设计技术与方法

大作业

学院电子工程学院

专业电路与系统

姓名

学号

导师姓名

作业 1.分别实现多项式求值的四种运算，若针对不同规模的输入值a ，各算法的运行时间，问题 规模n 分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。

2.分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为2222?，

3322?，4422?，5522?，6622?，7722?，8822?，9922?，101022?，111122?，121222?时的运行时间与MATLAB 自带的矩阵相乘的运行时间，绘制时间对比图。

3.利用遗传算法求解下面的问题：

)20sin()4sin(5.21),(max 221121x x x x x x f ππ?+?+=

?

??≤≤≤≤-8.51.41.120.3..21x x t s

1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归：

① n n n n x a x P x P +=-)()(1；

② 0a P =,1=Q ,Q a P P Qx Q i +==,；

③ i n i i a x x P x P --+'=')()(1。

本文对上述四种方法进行了编程，具体代码如下：

程序1.1

文件名poly.m

% 主程序：实现不同规模下多项式求值的四种运算

clc;

close all ;

clear all ;

n=[10 50 100 150 200 300 400 500 10000 20000 50000 100000];

x=2;

for i=1:12

a=rand(1,(n(i)+1)); % 产生多项式,最高次幂为n(i)+1

tic;

p1(i)=polyval(a,x); % 直接代入法

t1(i)=toc;

tic;

p2(i)=0;

for j=1:(n(i)+1)

p2(i)=p2(i)+a(j)*x^(j-1); % 递归法1

end

t2(i)=toc;

tic;

p3(i)=0;

q=1;

for j=2:(n(i)+1)

q=q*x;

p3(i)=p3(i)+a(j)*q; % 递归法2

end

t3(i)=toc;

tic;

p4(i)=0;

for j=1:n(i);

p4(i)=x*p4(i)+a(n(i)+1-j); % 递归法3

end

t4(i)=toc;

end

figure(1);

subplot(2,2,1);

h=semilogx(n,t1); % 这里不能用plot，横轴需要取对数，下同

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','g','marke rsize',6);

xlabel('The scale of the problem:n');

ylabel('time for first method(s)');

title('the relationship between time and scale');

grid on;

subplot(2,2,2);

h=semilogx(n,t2);

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','b','marke rsize',6);

xlabel('The scale of the problem:n');

ylabel('time for second method(s)');

title('the relationship between time and scale');

grid on;

subplot(2,2,3);

h=semilogx(n,t2);

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','k','marke rsize',6);

xlabel('The scale of the problem:n');

ylabel('time for third method(s)');

title('the relationship between time and scale');

grid on;

subplot(2,2,4);

h=semilogx(n,t2);

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','r','marke rsize',6);

xlabel('The scale of the problem:n');

ylabel('time for forth method(s)');

title('the relationship between time and scale');

grid on;

figure(2);

g=semilogx(n,t1,'g+',n,t2,'bx',n,t3,'k*',n,t4,'ro');

legend('the first method','the second method','the third method','the forth method');

set(g,'linestyle','-','linewidth',2.0,'markersize',8);

xlabel('n=10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000');

ylabel('time');

title('The comparison chart of four different methods for polyval'); grid on;

运行结果如下：

图 1.1 四种方法所用时间随规模不同而变化的结果图

图 2.2 四种方法所用时间随规模不同而变化的对比图

由理论分析可知，四种算法的时间复杂度分别为)(2n O 、)(2

n O 、)(n O 、)(n O ，由图1.2分析可知，直接带入计算和递归法所用时间相差无几，这与理论分析一直。而第三种方法与第四种方法的差异可能是由于每次加法所用时间与每次乘法所用时间不同所导致。 另外，在问题规模较小(n<1000)时，在图上几乎看不出区别，更精细的分析需要更深入地讨论，本文不做讨论。

2、分析题意可知，要利用四种方法计算矩阵相乘，每种方法取矩阵大小从2222?~ 121222?不同的规模。本文采用了以下方法进行求值：矩阵计算法、定义法、分治法和Strassen 方法。 详细程序如下：

程序2.1

文件名matrix.m

% 比较三种算法的运行时间与MATLAB 自带的矩阵相乘的运行时间

clc;

close all ;

clear all ;

n=[2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10 2^11 2^12];

for m=1:11

A=round(rand(n(m))); % 随机生成矩阵

B=round(rand(n(m)));

tic;

C1=A*B; % MATLAB自带的矩阵相乘

t1(m)=toc;

tic;

C2=zeros(n(m));

for i=1:n(m)

for k=1:n(m)

for j=1:n(m)

C2(i,j)=C2(i,j)+A(i,k)*B(k,j); % 按照定义进行计算end

end

end

t2(m)=toc;

A11=A(1:n(m)/2,1:n(m)/2);

A12=A(1:n(m)/2,n(m)/2+1:n(m));

A21=A(n(m)/2+1:n(m),1:n(m)/2);

A22=A(n(m)/2+1:n(m),n(m)/2+1:n(m));

B11=B(1:n(m)/2,1:n(m)/2);

B12=B(1:n(m)/2,n(m)/2+1:n(m));

B21=B(n(m)/2+1:n(m),1:n(m)/2);

B22=B(n(m)/2+1:n(m),n(m)/2+1:n(m));

tic;

C3=zeros(n(m));

C11=A11*B11+A12*B21; % 分治法

C12=A11*B12+A12*B22;

C21=A21*B11+A22*B21;

C22=A21*B12+A22*B22;

C3=[C11 C12;C21 C22];

t3(m)=toc;

tic;

C4=zeros(n(m));

M1=A11*(B12-B22);

M2=(A11+A12)*B22;

M3=(A21+A22)*B11;

M4=A22*(B21-B11);

M5=(A11+A22)*(B11+B22);

M6=(A12-A22)*(B21+B22);

M7=(A11-A21)*(B11+B12);

C11=M5+M4-M2+M6; % Strassen方法

C12=M1+M2;

C21=M3+M4;

C22=M5+M1-M3-M7;

C4=[C11 C12;C21 C22];

t4(m)=toc;

end

figure(1);

subplot(2,2,1);

h=semilogx(n,t1); % 这里不能用plot，横轴需要取对数，下同

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','g','marke rsize',6);

xlabel('The scale of the matrix:n');

ylabel('time for first method(s)');

title('the relationship between time and scale');

grid on;

subplot(2,2,2);

h=semilogx(n,t2);

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','b','marke rsize',6);

xlabel('The scale of the matrix:n');

ylabel('time for second method(s)');

title('the relationship between time and scale');

grid on;

subplot(2,2,3);

h=semilogx(n,t2);

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','k','marke rsize',6);

xlabel('The scale of the matrix:n');

ylabel('time for third method(s)');

title('the relationship between time and scale');

grid on;

subplot(2,2,4);

h=semilogx(n,t2);

set(h,'linestyle','-','linewidth',1.8,'marker','*','color','r','marke rsize',6);

xlabel('The scale of the matrix:n');

ylabel('time for forth method(s)');

title('the relationship between time and scale');

grid on;

figure(2);

g=semilogx(n,t1,'g+',n,t2,'bx',n,t3,'k*',n,t4,'ro');

legend('the MATLAB method','the definition method','分治法','the Strassen method');

set(g,'linestyle','-','linewidth',2.0,'markersize',8);

xlabel('n=2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10 2^11 2^12'); ylabel('time');

title('The comparison chart of four different methods for matrix multiplication');

grid on ;

实验结果如下：

图 2.1 四种方法所用时间随规模不同而变化的结果图

3、

方法1：将原函数取负，求),(21x x f 的最小值即得原函数的最大值。

程序采用MATLAB 自带的工具箱实现，程序如下： 程序3.1

文件名main_function.m

% 主程序：用遗传算法求解带约束二元函数的最大值

clc;

close all ;

clear all ;

G=100; % 进化的代数

optionsOrigin=gaoptimset('Generation',G/2);

[x,fval,reason,output,final_pop]=ga(@fun,2,optionsOrigin);

options1=gaoptimset('Generation',G/2,'InitialPopulation',final_pop,'P lotFcns',@gaplotbestf);

[x,fval,reason,output,final_pop]=ga(@fun,2,options1);

Bestx=x

BestFval=fval

% 子程序：带约束的目标函数

function f=fun(x)

if (x(1)>12.1|(x(2)>5.8))

f=inf;

elseif (x(1)<-3.0|x(2)<4.1)

f=inf;

else

f=-(21.5+x(1)*sin(4*pi*x(1))+x(2)*sin(20*pi*x(2)));

end

运行后的结果：

Bestx =

11.6184 5.7273

BestFval =

-38.7478

从而可知原函数在(11.6184,5.7273)取得最大值38.7478。

方法2：按照遗传算法的思路编程，程序如下：

程序3.2文件名main_function.m % 主程序：用遗传算法求解带约束二元函数的最大值

clc;

clear all;

close all;

G=100; % 进化代数

N=80; % 群体规模

pm=0.05; % 变异概率

pc=0.8; % 交叉概率

u1max=12.1;u1min=-3.0; % 参数取值范围

u2max=5.8;u2min=4.1; % 参数取值范围

L=10; % 单个参数字串长度，总编码长度2L

bval=round(rand(N,2*L)); % 随机产生初始种群

bestv=-inf; % 最优适应度初值

for k=1:G

for i=1:N

y1=0;y2=0;

for j=1:1:L

y1=y1+bval(i,L-j+1)*2^(j-1);

end

x1=(u1max-u1min)*y1/(2^L-1)+u1min;

for j=1:1:L

y2=y2+bval(i,2*L-j+1)*2^(j-1);

end

x2=(u2max-u2min)*y2/(2^L-1)+u2min;

fun(i)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2); % 目标函数 xx(i,:)=[x1,x2];

end

fitfun=fun; % 目标函数转换为适应度函数

p=fitfun./sum(fitfun); % 轮盘赌选择函数

q=cumsum(p);

[fmax,indmax]=max(fitfun);% 记录每一代最佳个体

if fmax>=bestv

bestv=fmax; % 到目前为止最优适应度值

bvalxx=bval(indmax,:); % 到目前为止最佳位串

optxx=xx(indmax,:); % 到目前为止最优参数

end

Bestfit(k)=bestv; % 记录每代的最优适应度

for i=1:(N-1)

r=rand;

tmp=find(r<=q);

newbval(i,:)=bval(tmp(1),:);

end

newbval(N,:)=bvalxx; % 最优保留

bval=newbval;

for i=1:2:(N-1)

cc=rand;

if cc

point=ceil(rand*(2*L-1));

ch=bval(i,:);

bval(i,point+1:2*L)=bval(i+1,point+1:2*L);

bval(i+1,point+1:2*L)=ch(1,point+1:2*L);

end

end

bval(N,:)=bvalxx; % 最优保留

mm=rand(N,2*L)

bval(mm)=1-bval(mm);

end

plot(Bestfit); % 绘制最优适应度进化曲线

xlabel('Generation');

ylabel('FitnessValue');

title('The relationship between FitnessValue and Generation'); Optxx

bestv

运行结果如下：

optxx =

11.627663734115348 5.525806451612903

bestv =

38.639864218199662

从而可知原函数在(11.627663734115348,5.525806451612903)取得最大值

38.639864218199662。

《ACM算法与数据结构设计》大作业

《ACM算法与数据结构设计》课程大作业报告 题目：五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24

注意事项 （1）课程大作业从《ACM算法与数据结构设计》课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 （3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 （4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚19:00~20:00，地点：计算中心A机房。

一、课题名称： 五位以内的对称素数 二、课题内容和要求： 题目：判断一个数是否为对称且不大于五位数的素数。 要求：判断输入的一组数据（正整数）是否是五位以内的对称素数，逐个判断并输出“yes”或“no” 三、课题分析： 定义两个函数分别判断数据是否为素数（bool isprime(int n)），是否是对称数（bool issym(int n)）；在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件，才能判断一个数据是五位以内的对称素数，输出“yes”；否则输出“no”。 输入输出方案： 输入: 输入数据含有不多于50个的正整数(0

《计算机算法设计与分析》习题及答案

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法

11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。

算法设计与分析复习题目及答案19874

一。选择题 1、二分搜索算法就是利用( A )实现的算法。 Ａ、分治策略B、动态规划法C、贪心法 D、回溯法 2、下列不就是动态规划算法基本步骤的就是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 ３、最大效益优先就是( A )的一搜索方式。 Ａ、分支界限法Ｂ、动态规划法Ｃ、贪心法Ｄ、回溯法 4、在下列算法中有时找不到问题解的就是( B )。 Ａ、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5、回溯法解旅行售货员问题时的解空间树就是( B )。 A、子集树???Ｂ、排列树C、深度优先生成树?D、广度优先生成树 6.下列算法中通常以自底向上的方式求解最优解的就是( Ｂ)。 Ａ、备忘录法?B、动态规划法?C、贪心法????D、回溯法 7、衡量一个算法好坏的标准就是(C )。?A 运行速度快Ｂ占用空间少 C 时间复杂度低 D 代码短?８、以下不可以使用分治法求解的就是(D )。?Ａ棋盘覆盖问题Ｂ选择问题 C 归并排序 D 0/1背包问题?9、实现循环赛日程表利用的算法就是( A )。 A、分治策略?? B、动态规划法 C、贪心法??Ｄ、回溯法 10、下列随机算法中运行时有时候成功有时候失败的就是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不就是分支界限法搜索方式的就是( D )。 Ａ、广度优先?B、最小耗费优先C、最大效益优先D、深度优先 12、下列算法中通常以深度优先方式系统搜索问题解的就是( D )。 Ａ、备忘录法B、动态规划法??C、贪心法???D、回溯法

13、备忘录方法就是那种算法的变形。( B ) A、分治法? B、动态规划法? C、贪心法?? D、回溯法 1４、哈弗曼编码的贪心算法所需的计算时间为( B )。 A、Ｏ(n2n)?? B、O(nｌogｎ)? C、O(2ｎ) ??? D、Ｏ(n) 15.分支限界法解最大团问题时,活结点表的组织形式就是( B )。 A、最小堆???? B、最大堆?? C、栈???Ｄ、数组 １6.最长公共子序列算法利用的算法就是( B )。 A、分支界限法? B、动态规划法? C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法就是( A )。 Ａ、分治法??Ｂ、动态规划法C、贪心法??D、回溯法 18、下面就是贪心算法的基本要素的就是( C )。 A、重叠子问题?Ｂ、构造最优解??C、贪心选择性质??D、定义最优解 1９.回溯法的效率不依赖于下列哪些因素( D ) A、满足显约束的值的个数????Ｂ、计算约束函数的时间 C、计算限界函数的时间?? D、确定解空间的时间 ２０、下面哪种函数就是回溯法中为避免无效搜索采取的策略( B ) A.递归函数?B、剪枝函数? C。随机数函数???Ｄ、搜索函数 21、下面关于NＰ问题说法正确的就是(B )?A NＰ问题都就是不可能解决的问题?B P类问题包含在ＮＰ类问题中?C NP完全问题就是P类问题的子集 D ＮP类问题包含在P类问题中 22、蒙特卡罗算法就是( B )的一种。 Ａ、分支界限算法 B、概率算法C、贪心算法D、回溯算法 2３、下列哪一种算法不就是随机化算法( C ) A、蒙特卡罗算法 B、拉斯维加斯算法 C、动态规划算法 D、舍伍德算法 24、 ( D )就是贪心算法与动态规划算法的共同点。Ａ、重叠子问题B、构造最优解?C、贪心选择性质D、最优子结构性质２5、矩阵连乘问题的算法可由( B)设计实现。

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

算法设计与分析课后部分习题答案

算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中

for(i=0;i=0;row--)//从上往下递归计算 for(int col=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; else triangle[row][col]+=triangle[row+1][col+1]; out=fopen("output.txt","w"); fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 } 算法实现题4-9 汽车加油问题 问题描述： 一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产出一个最优解。编程任务： 对于给定的n和k个加油站位置，编程计算最少加油次数。数据输入： 由文件input.txt给出输入数据。第1行有2个正整数n和k ，表示汽车加满油后可行驶nkm，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第

算法设计与分析考试题及答案

算法设计与分析考试题及 答案 It was last revised on January 2, 2021

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算， 此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造 最优解； 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i }；②将N 1 中作业按a i 的非减序排序得到N 1 ’，将N 2 中作业按b i 的非增序排序得到N 2’；③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i 和b i ，且 (a 1,a 2 ,a 3 ,a 4 )=(4,5,12,10)，(b 1 ,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案，并计算最优 值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0）

算法设计与分析试卷

算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案,每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列. B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列. C ．算法是一个对任一有效输入能够停机的图灵机. D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出. （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的. （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案. ???>+-==1 1)1(211)(n n T n n T

《程序设计与算法综合实践》期末大作业题目及评分标准

2017级《程序设计与算法综合实践》 期末大作业题目及评分标准 有如下情况之一者，为不及格。 （1）未能完成所选题目评分标准的最低要求。 （2）抄袭他人成果。 （3）大作业检查时不带电脑，或电脑没有C语言开发环境。 （4）出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。 备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 -

OpenJudge算法设计与分析习题解答

1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。

源代码： #include #include int main(){ int t=1; int i,j,k; int n; scanf("%d",&n); int A=n,B=n/2,C=n/5; for(i=0;i<=C;i++){ for(j=0;j<=B;j++){ for(k=0;k<=A;k++){ if(i*5+j*2+k*1==n){ printf("%03d%12d%12d%12d\n",t,k,j,i); t++; } } } } getchar(); return 0; } 2、比赛排名 描述 5名运动员参加100米赛跑，各自对比赛结果进行了预测：A说：E是第1名。 B说：我是第2名。 C说：A肯定垫底。 D说：C肯定拿不了第1名。

E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include int main() { printf("5\n"); printf("2\n"); printf("1\n"); printf("3\n"); printf("4\n"); return 0; } 3、鸡兔同笼 描述 一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

软件系统分析与设计大作业

《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1

目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················

一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。

二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。

《算法设计与分析》复习题(汇编)

填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进

算法设计与分析课后习题

第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n ; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答：

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.

算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

《算法设计与分析实用教程》习题参考解答

《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include void main() {long a,b,d,n,x,y; printf(" 请输入整数a,b: "); scanf("%ld,%ld",&a,&b); if(a%2==0 && b%2==0) { printf(" -1\n");return;} n=0; while(1) { n++; for(x=1;x<=n;x++) { y=n+1-x;d=x*a-y*b; if(d==1 || d==-1) // 满足加减结果为1 { printf(" n=%ld\n",n);return;} } } } 请输入整数a,b: 2012,19 961 请输入整数a,b: 101,2013 606

算法设计与分析课程期末试卷-A卷(自测 )

华南农业大学期末考试试卷（A卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同

6. 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2n+1-1 D ． ∑=n i i n 1 !/! 答案：DACAD CACCB