2011年安工算法设计与分析考试题

2011年安阳工学院算法设计与分析考期末试题一、填空1算法三要素：操作，控制结构，数据结构2广度优先搜索，深度优先搜索二、简答1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2回溯算法求解步骤3动态规划基本步骤三、计算题（10）用贪心算法求如下背包问题的最优解，n=7,m=15,价值P={10,5,15,7,6,18,3}，重量w={2,3,5,7,1,4,1},用列表表示货物编号1234567P1051576183W2357141P/W51.63164.53解：p/w=经过排序后排号为：5,1,6,3,7,2,4则5号先放入包，此时，W总=1，P总=6，x5=11号放入包，……………………=3，…..=16，..=16……………………………………….=7，……=34，..=17………………………………………=12，…..=49，..=12………………………………………=15，…..=55.3，..=2/3故x4=0,则得x={1,2/3,1,0,1,1,1,1},P总=55.3注：此题有错误，欢迎同学们提出正确答案（11）设有资源数目为3，分配给3个项目，g(x)为第i个项目得到资源x所得到的利润，求总利润最大的资源分配方案利润见表额项目123A0.110.130.15B0.120.160.21C0.080.120.20解：分阶段，逐步考虑每一个项目在不同资源分配情况利润，设fi(x)为将资源x分配前i个项目的最大利润，分3段决策过程：fi(x)=gi(x)0=x=3fi(x)=max{gi(z)+fi(x-z)}0=x=3,i=3分三步分析题：①第一个项目A的资金x与利润fi(x)的关系如下：Xy0123fi(x)00.110.130.15②分配前两项目的总资金x，x与利润f2(x)的关系，x2（0=x2=3）为分配给项目B的资金x2x0123f2(x)000.0010.110.120.1220.130.230.160.2330.150.250.270.210.27f1(1)=g1(1)f2(x2)=max(0=x2=2){g(x)+f(2-x)}③当资源为3时，f3(3)=max(0=x3=3){g3(x)+f2(3-x)}X30123g3(x3)0.000.080.120.20f2(3-x3)0.270.230.120.00g3(x3)+f2(3-x3)0.270.310.240.20则f1(1)=g1(1)=0.11f2(2)=g2(1)+f1(1)=0.23=0.12+0.11f3(x3)max(0=x=3){g3(x)+f2(3-x)}=g3(1)+f2(2)=0.08+0.23故当A分得1万元，B分得1万元，C分得1万元，最后利润为最大0.31万元（）（14）为马的遍历问题check函数设计Intcheck(intx,inty){if(xm&&yn&&a[x]a[y]!=1)Return1;elsereturn0;}（15）#includeiostreamUsingnamespacestd;Intack(intm,intn){If(m==0)Returnn+1;Elseif(n==0)Returnack(m-1,1);ElseReturnack(m-1,ack(m,n-1));}Intmain(){Intm,n,t;Cinmn;If(m0||n0)Cout”dataiswrong”endl;ElseIf(m4)Cout”dataistoolonger”endl;ElseIf((m==4)&&(n0))Cout”dataistoolonger”endl;ElseIf((m==3)&&(n10))Cout”dataistoolonger”endl;ElseIf((m==2)&&(n5628))Cout”dataistoolonger”endl;ElseIf((m==1)&&(n1259))Cout”dataistoolonger”endl;ElseT=ack(m,n);Couttendl;}Return0;}1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构（3）算法的基本特征P6算法的基本特征：可行性、确定性、有穷性、有一个或多个输出、有零个或多个输入（4）简述评价算法的标准P36对算法的分析和评价，一般应考虑正确性，可维护性，可读性，运算量。占用存储空间等诸多因素。其中评价算法的三条主要标准是：1算法所耗费的时间2算法实现所耗费的存储空间，其中主要考虑辅助存储空间；3算法应易于理解、易于编码。易于调试等。（5）算法的存储量包括哪些？P391、输入数据所占空间2、程序本身所占空间3、辅助变量所占空间x=2，while（x2/n）x=x*2，分析这条语句的频度由题知：x=x*2，2k+1n，，得k+1log2n-1,klog2n-2（6）for(i=1;in;i++)for(j=1;jn;j++)x=x+1;分析这条语句的频度；解：p=1+2+…….+n=n(n+1)/2（7）简述递归的方法。P58递归是一个过程活函数在定义或说明中有直接或间接调用自身的一种方法。（8）什么是数学模型P107数学模型是利用数学语言模拟现实的模型。把现实模型抽象，简化为某种数学结构是数学模型的基本特征。它或者能解释特定现状的现实状态，或者预测到对象的未来状况，或者能提供处理对象的最优决策或控制。（9）简述数学建模过程P107数学建模就是把现实问题加以提炼，构造出数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，把数学知识的这一应用过程称为数学建模。用流程框图如图1所示：建模数学处理解释实际问题数学模型实际问题的解数学模型的解释四皇后（13）4皇后问题，要求4*4的国际象棋棋盘中放4个皇后，使任意两个皇后都不被吃掉②设计问题分析（I）在第k行a[k]列放置第k个皇后，开始时k=1,a[k]=1（II）检查放置位置是否正确，如果a[i]-a[k]=|i-k|或a[i]=a[k](ik)，则不满足问题要求（III）若放置位置（k,a[k]）满足条件，重复（I）（II）放置k+1直到最后一个位置成功，否则a[k]+1,重置，直到放置位置（k,a[k]）满足