算法设计试题（2019A答）

第1页（共3页）考试科目：算法设计与分析试题（A）参考答案选择题（每题2分，共10分）1-5CCCBD二、填空题（每空2分，共16分）1、X=7321568，X删除4位数字后的最大值为___768_，7/16的埃及分数表达式为__1/3+1/10+1/240。2、算法描述方式有（至少3个）_流程图_、__盒图__、__伪代码_。3、设计递归算法的步骤__找出大规模问题与小规模问题的关系，找出停止条件，_设计函数、确定参数_。得分三、简答题（每题8分，共24分）1、算法的五个基本特征。1)有穷性2)确定性3)可行性4)算法有零个或多个的输入5)算法有一个或多个的输出2、简述什么是算法的时间复杂度及“O”的含义。一个特定算法的“运行工作量”的大小,依赖于问题的规模(通常用整数量n表示),或者说,算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和函数f(n)的增长率相同,则可记作:T(n)=O(f(n))称T(n)为算法的渐近时间复杂度(asymptotictimecomplexity),简称时间复杂度。O是数量级的符号,标准数量级通常有Ο(1)称为常数级；Ο(logn)称为对数级；Ο(n)称为线性级；Ο(nc)称为多项式级；Ο(cn)称为指数级；Ο(n！)称为阶乘级。3、比较用循环和递归实现求n!算法的优劣。用递归计算n!比循环更加消耗资源,前者空间上时间上都有消耗，每次调用过程都使得调用链条不断加长，系统不得不使用栈进行数据保存和恢复。而循环就不需要这样的消耗。四、综合题（共20分）：1.（10分）现有四个矩阵，其中各矩阵维数分别为：A1A2A3A440´3030´2020´1010´5p0´p1p1´p2p2´p3p3´p4计算出矩阵连乘积A2A3A4所需要的最少乘法次数及组合方案。1）所有连续2个矩阵乘法次数T（A1A2）=40*30*20=24000T（A2A3）=30*20*10=6000T（A3A4）=20*10*5=10002）所有连续3个矩阵最少乘法次数T（A1A2A3）=min{A1（A2A3）,（A1A2）A3}=min{24000+40*20*10,6000+40*30*10}=18000T（A2A3A4）=min{A2（A3A4）,（A2A3）A4}=min{1000+30*20*5,6000+30*10*5}=40003）T（A1A2A3A4）=min{A1（A2A3A4）,（A1A2）(A3A4）,（A1A2A3）A4}=min{4000+40*30*5,24000+1000+40*20*5.18000+40*10*5}=10000组合方案A1（A2（A3A4））2（10分）资源分配问题：现有n=7万元投资到A，B，C，D四个项目，利润见下表1234567A0.130.160.180.200.250.290.35B0.110.140.200.230.250.280.32C0.100.130.200.230.260.320.33D0.120.150.180.210.230.260.30求总利润最大的资源分配方案。1）只考虑A项目各种投资利润表A01234567利润00.130.160.180.200.250.290.352）考虑A，B两项目各种投资利润表BA+B012345670010.13*0.1120.160.24*0.1430.180.27*0.27*0.2040.200.290.300.33*0.2350.250.310.320.36*0.36*0.2560.290.360.340.380.39*0.380.2870.350.400.390.400.41*0.41*0.41*0.323）考虑A，B,C三个项目各种投资利润表CA+B+C012345670010.13*0.1020.24*0.230.1330.270.34*0.260.2040.330.37*0.37*0.330.2350.360.430.400.44*0.360.2660.390.460.460.47*0.47*0.390.3270.410.490.490.53*0.500.500.450.334）四个项目总投资7万，第四个项目各种投资利润表D01234567D利润00.120.150.180.210.230.260.30A+B+C利润0.530.470.440.370.340.240.130总利润0．530.590.590.550.550.470.390.30最大利润为0.59，投资方案如下：1）A1万B1万C3万D2万2）A2万B1万C3万D1万3）A1万B2万C3万D1万4）A1万B1万C4万D1万五、算法设计题（每题15分，共30分）1、一个数如果恰好等于它的因子之和(包括1,但不包括这个数本身),这个数就称为“完数”，设计算法求所有四位数中的“完数”。main(){inti,k,j,s,a［20］;for(i=1000;i<10000;i=i+1){s=1;k=0;for(j=2;ji;j=j+1)if(imodj)=0){s=s+j;a［k］=j;k=k+1;}if(i==s){print(s,"it'sfactorsare:",1);for(j=0;jk;j=j+1)print(",",a［j］);}}}2、设计算法输出(a+b)n二项式系数。coeff(inta［］,intn){if(n==1){a［1］=1;a［2］=1;}else{coeff(a,n-1)a［n+1］=1for