一、选择题(15*2分)
1.算法分析是（ C）
A.将算法用某种程序设计语言恰当地表示出来
B.在抽象数据集合上执行程序,以确定是否会产生错误的结果
C.对算法需要多少计算时间和存储空间作定量分析
D.证明算法对所有可能的合法输入都能算出正确的答案
2.算法与程序的区别在于算法具有（C ）
A.能行性
B.确定性
C.有穷性
D.输入和输出
3.记号Ω的定义正确的是（B）
A.O(g(n)) = { f(n) | 存在正常数c和n0使得当n≥n0 有f(n) ≤ cg(n) }
B.O(g(n)) = { f(n) | 存在正常数c和n0使得当n≥n0有 cg(n) ≤ f(n) }
>0使得对所有n≥n0 C.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n
有f(n) D.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n >0使得对所有n≥n0 有cg(n) < f(n) } 4.衡量一个算法好坏的标准是（C ） A.运行速度快 B. 占用空间少 C.时间复杂度低 D. 代码短 5.二分搜索算法是利用（A）实现的算法。 A.分治法 B.动态规划法 C.贪心法 D.回溯法 6.下面问题（B ）不能使用贪心法解决。 A. 单源最短路径问题 B. N皇后问题 C. 最小代价生成树问题 D. 背包问题 7．用贪心法设计算法的关键是（ B ）。 A.将问题分解为多个子问题来分别处理 B.选好最优量度标准 C.获取各阶段间的递推关系式 D.满足最优性原理 8.找最小生成树的算法Kruskal的时间复杂度为（ D ）（其中n为无向图的结点数，m为边数） A．O(n2) B．O(mlogn) C．O(nlogm) D．O(mlogm) 9.回溯法搜索状态空间树是按照（C ）的顺序。 A.中序遍历 B.广度优先遍历 C.深度优先遍历 D.层次优先遍历 10. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ） A.重叠子问题 B.最优子结构性质 C.最优量度标准性质 D.定义最优解 11.程序块（A）是回溯法中遍历排列树的算法框架程序。 A.void backtrack(int t) { if(t>n)output(x); else for(int i=t;i<=n;i++){ swap(x[t],x[i]); if(legal(t))backtrack(t+1); swap(x[t],x[i]); } } B. Void backtrack (int t) { if(t>n)output(x); else for( int i=0;i<=1;i++){ x[t]=i; if(legal(t))backtrack(t+1); } } C.Void backtrack (int t) { if(t>n)output(x); else for(int i=0;i<=1;i++){ x[t]=i; if(legal(t))backtrack(t-1); } } D.Void backtrack (int t) { if(t>n)output(x); else for(int i=t;i<=n;i++){ Swap(x[t],x[i]); if(legal(t))backtrack(t+1); } } 12.0-1背包问题的回溯算法所需的计算时间为（ A ） A.O（n2n） B.O（nlogn） C.O（2n） D.O（n） 13．哈弗曼编码的贪心算法所需的计算时间为（ B ） A.O（n2n） B.O（nlogn） C.O（2n） D.O（n） 14.矩阵连乘问题的算法可由（B）设计实现。 A.分支界限算法 B.动态规划算法 C.贪心算法 D.回溯算法 15.采用广度优先策略搜索的算法是（ A ）。 A.分支界限法 B.动态规划法 C.贪心法 D.回溯法 二、填空题（15*2分） 1.算法的复杂性有______和______之分,衡量一个算法好坏的标准是_____________。 2.某一问题可用动态规划算法求解的显著特征是_________________________。 3.若序列A={xzyzzyx}，B={zxyyzxz}，请给出序列A和B的一个最长公共子序列__________________。 4.动态规划算法的基本思想是将待求解问题分解成若干___________先求解_________,然后从这些_____________的解得到原问题的解。 5.0-1背包问题的回溯算法所需的计算时间为____________,用动态规划算法所需的计算时间为________________。 6.二分法搜索算法是利用___________实现的算法。 7.所谓最优化问题是指问题给定某些约束条件，满足这些约束条件的问题解称为___________。 8.回溯法解决问题时，应明确定义问题的解空间，问题的解空间至少应包含________。 9.__________是描述问题解空间的树形结构。 10.在分枝限界法中一个活结点只可能一次成为E结点，回溯法中任何一个或结点可能____成为E结点。 答案：1.时间、空间时间复杂度空间复杂度。 2.算法效率 3.xyzz. 4.子问题子问题子问题 5.o（n*2n）o(min{nc 2n}) 6.动态规划法 7.可行解 8.2n 9.状态空间树 10.多次 三、算法设计题（每题10分、共20分） 1、设计一个回溯算法，使用可变长度状态空间树求解子集和数问题。 解、子集和数的回溯算法： void SumOfSub(float s,int k,float r,int*x,float m,float*w) { x[k]=1; if(s+w[k]==m){ for(int j=0;j<=k;j++)cout< cout< } else if(s+w[k]+w[k+1]<=m) SumOfSub(s+w[k],k+1,r-w[k],x,m,w); if((s+r-w[k]>=m)&&(s+w[k+1]<=m)){ x[k]=0; SumOfSub(s,k+1,r-w[k],x,m,w); } } void SumSub(int*x,int n,float m,float*w) { float r=0; for(int i=0;i if(r>=m&&w[0]<=m)SumOfSub(0,0,r,x,m,w); } 2、假设n=8,[w1,….,w8]=[100,200,50,90,150,50,20,80],c=400.利用贪心算 法时，所考察货箱的顺序为7,3,6,8,4,1,5,2.货箱7,3,6,8,4,1的总重量为390个单位且已被装载，剩下的装载能力为10，小于剩下的任何一个货箱。 根据贪心解决算法，得到[x1,…,x8]=[1,0,1,1,0,1,1,1],且∑Xi=6. 解、货箱装船算法实现： void ContainerLoading(int X[],T w[],T c,int n) { //货箱装船问题的贪心算法 //x[t]=1当且仅当货箱t被装载，1<=t<=n //c是船的容量，w是货箱的重量 //t是间接寻址表 int *t=new int[n+1]; IndirectSort(w,t,n); //此时，w[t[t]]<=w[t[t+1]],1<=t //初始化x for(int t=1;t<=n;t++) x[t]=0; //按重量次序选择物品 for(t=1;t<=n&&w[t[t]]<=c;t++) {//剩余容量 想x[[t]]=1; c-=w[t[t]]; } delete[]t; } （货箱装船问题。货箱可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪心准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪心策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去，直 到所有货箱均装上船，或船上不能再容纳其他任何一个货箱。） 四、应用题（30分） 1（5分）、设背包问题实例n=7，M=15,(w0,w1,w2…,w6)=(2,3,5,7,1,4,1),物品装入背包的收益为：(p0,p1,p2,…,p6)=(10,5,15,7,6,18,3)。求这一实验的最优解和最大收益。 答案：由定理：如果p0/w0>=…>=pn-1/wn-1,则用贪心法求得的背包问题的解是最优解，知按pi/wi 的非增次序选取物品可求得最优解设背包问题的解为x=(x0,x1,x2,x3,x4,x5,x6),由已知条件知(p0/w0,p1/w1,…,p6/w6)=(5,1.67,3,1,6,4.5,3),使用这一标准得到的解即最优解为，(x0,x1,…,x6)=(1,2/3,1,0,1,1,1)此时∑WiXi=(1*2+2/3*3+1*5+0*7+1*1+1*4+1)=15符合题目要求最大收益为：max ∑pixi=5*2/3+15*1+6*1+18*1+3*1=55.33 2（5）、写出对下图所示的多段图采用向后递推动态规划算法求解时的计算过程 答案： Bcost(1,0)=0 Bcost(2,1)=5 Bcost(2,2)=2 Bcost(3,3)=min{3+Bcost(2,1),6+Bcost(2,2)}=8 Bcost(3,4)=7 Bcost(3,5)=min{3+Bcost(2,1),8+Bcost(2,2)}=8 Bcost(4,6)=min{1+Bcost(3,3),6+Bcost(3,4),6+Bcost(3,5)}=9 Bcost(4,7)=min{4+Bcost(3,3),2+Bcost(3,4),3+Bcot(3,5)}=9 Bcost(5,8)=min{7+Bcost(4,6),3+Bcost(4,7)}=12 3（10分）、设有带时限的作业排序实例： n=4,(p0,d0,t0)=(5,1,1),(p1,d1,t0)=(10,3,2),(p2,d2,t2)=(6,2,1)和(p3,d3,t3)=(3,1,1),求使得总收益最大的作业子集J 。 1 2 5 6 4 7 8 t 8 5 6 3 3 2 5 4 2 6 7 1 6 3 2 1 4 3 5 11 9 10 15 c=0 2 6 7 8 12 13 14 X 0=0 U=19 u=19 c^=0 X 1=1 u=16 c^=0 X 2=2 X 2=3 X 1=2 u=13 c^=3 X 2=3 U=13 X 1=3 u=9 c^=9 U=9 X 2=3 u=15 c^=5 X 0=1 u=18 c^8 X 0=3 U=14 u=15 u=8 c^=11 c^=8 u=14 c^=14 X 1=3 u=21 c^=5 X 1=2 B (p0,d0,t0)=(5,1,1) (p1,d1,t1)=(3,1,1) (p2,d2,t2)=(b,2,1) (p3,d3,t3)=(10,3,2) c=8 u=24 高中信息技术《算法与程序设计》试题 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C 单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的 序号填在题干的括号内。) 1. f(x)在区间［x 1,x 3］上为单峰函数，x 2为区间中的一点，x 4为利用二次插值法求得的近似极值点，若x 4-x 2＜0,且f(x 4)≥f(x 2)，则新的搜索区间为( D ) A. ［x 1,x 4］ B. ［x 2,x 3］ C. ［x 1,x 2］ D.［x 4,x 3］ 2.对于平面桁架中的杆单元，每个节点在整体坐标系中的位移分量个数为（B ） A1 B2 C3 D4 3.应用四节点等参数单元时，由整体坐标系到自然坐标系单元的映射关系是（C ） A 任意四边形→任意四边形 B 正方形→任意四边形 C 任意四边形→正方形 D 正方形→正方形 4.在任何一个单元内（ D ） A 只有节点符合位移模式 B 只有边界点符合位移模式 C 只有边界点和节点符合位移模式 D 单元内任意点均符合位移模式 4.若强度r 的概率密度函数为f r (r)=λr e r r -λ,则知其分布为（ C ） A 正态分布 B 对数正态分布 C 指数分布 D 威布尔分布 6.标准正态分布的均值和标准离差为（ D ） A μ=1,σ=0 B μ=1,σ=1 C μ=0,σ=0 D μ=0,σ=1 7.若组成系统的诸零件的失效相互独立，但只有某一个零件处于工作状态，当它出现故障后，其它处于待 命状态的零件立即转入工作状态。这种系统称为（ C ） A 串联系统 B 工作冗余系统 C 非工作冗余系统 Dr/n 表决系统 8已知方程组5611327121 2x x x x +=+=??? ()()12，用高斯消元法对式(2)进行向前消元一步运算后，结果为（ C ） A. -=245652x B. x x 122373+= C.-=85252x D. -=-243343 2x 9.Powell 修正算法是一种（ D ） A 一维搜索方法 B 处理约束问题的优化方法 C 利用梯度的无约束优化方法 D 不利用梯度的无约束优化方法 10.某产品的寿命服从指数分布，若知其失效率λ=0.002，则该产品的平均寿命为（C ） A.200 B.1000 C.500 D.2000 11.下列优化方法中，不需计算迭代点一阶导数和二阶导数的是（ B ） A 可行方向法 B 复合形法 C DFP 法 D BFGS 法 11.表示机电设备的一般失效曲线(浴盆曲线)中，偶然失效期的失效密度f(t)服从（ B ） 《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。 3.用梯度法求下列无约束优化问题：MinF(X)=x12+4x22，设初始点取为X(0)={2,2}T，以梯度模为终止迭代准则，其收敛精度为5。 1)求初始点梯度▽F(X) ▽F(X)={2x1,8x2}T▽F(X(0))={4,16}T (2)第一次搜索 |▽F(X(0))|=16.5,S(0)=- ▽F(X(0))/16.5=-{0.243,0.97}T α(0)=2.157 X(1)=X(0)+α(0)S(0)={1.476,-0.923}T ▽F(x(1))={2.952,-0.738}T |▽F(x(1))|=3.043<5.0 故满足要求，停止迭代。 最优点X*={1.476,-0.0923}T 最优值F(X*)=2.21 4. 5. 6. 用外点法求解约束优化问题： ()()12211221min ..0()0 f X x x s t g X x x g X x =+=-≤=-≤ ， 收敛准则：(1) ()0.10.01k k X X εδ+-≤=，约束容限＝ 解：（1）利用外点法惩罚法构造无约束优化问题 () ( ) 12()22()212121(min ,()() k k k x x X r x x r x x r x +??Φ=?++-+-??可行域内）（可行域外） （2）此例只是为了说明外点法的思路，用微分法求解上述无约束优化问题。 用极值条件求解： 在可行域内：偏导数不可能等于0，即可行域内无极值 在可行域外，令： ()2()11211 ()2122 14()2012()0k k k r x x x r x x r x x x ?Φ =+-+=??Φ =--=? 《算法与程序设计》试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C 现代设计方法试卷1及答案 一、单项选择题 1.属于无约束优化问题求解算法中的直接法是（ C ） A. 梯度法 B.牛顿法 C.POWELL法 D.变尺度法 2.按类型划分，惩罚函数法属于（ D ） A.一维优化方法 B.无约束优化方法 C.直接法 D.约束优化方法 3.对于只含有不等式约束的优化问题，满足每一个设计约束的设计点，称为 （D） A.边界点 B.非可行点 C.外点 D.内点 4.坐标轮换法以为搜索方向。（C） A.梯度方向 B.共轭方向 C.坐标轴方向 D.负梯度方向 5.一个多元函数F（X）在点X*附近偏导数连续，则该点为极小值点的充分条件是（ B ） A.▽F（X*）=0 B. ▽F（X*）=0,H（X*）正定 C. H（X*）=0 D. ▽F（X*）=0,H（X*）负定 6.在有限元分析中，将构件分割成单元的方法称之为( C ) A.有限化 B.单元化 C.网格化 D.分割化 7.平面问题的弹性矩阵与材料的（ D） A.弹性模量有关，泊松比无关 B.弹性模量无关，泊松比有关 C.弹性模量和泊松比都无关 D.弹性模量和泊松比都有关 8.当零件材料的强度均值小于应力均值时，零件的平均安全系数为n，等效概率为F，则（A ） A.n<1，F>50% B. n>1，F>50% C. n<1，F<50% D. n>1，F<50% 9.串联系统的失效模式大多服从（ D ） A.正态分布 B.对数正态分布 C.指数分布 D.威布分布 10.抽取100只灯泡进行实验，灯泡工作到50小时有12只损坏，工作到70小 时又有20只损坏，从50小时到70小时这段时间内灯泡的平均失效密度为（ C ） A. 0.006 B. 0.004 C. 0.01 D. 0.12 二、填空题 11.单元刚度矩阵具有对称性、 分块 性和奇异性。 12.机电产品零件失效曲线分为三个区域，分别为： 早期失效区域 、正常工 作区域和功能失效区域。 13.函数()223212221+-+=x x x x x F 在点（1，0）处的梯度为 [6,-2]T 。 14.组成并联系统的零件的可靠度与该并联系统的可靠度相比较， 并联系统 的可靠度高。 15.一批产品从投入运行到发生失效的平均时间称为 平均寿命 。 16.可靠度是对产品可靠性的 概率 度量。 17.设某系统由10个零件串连组成，每个零件的可靠度均为0.95，系统的可靠度为 0.599 。 18.根据处理约束条件的方式不同，求解约束优化问题的方法分为 直接法 和间接法。 19.根据是否满足约束条件可以将设计点分为：可行点和 不可行点 。 20.利用目标函数的一阶导数或二阶导数信息构成搜索方向的方法称为 导数法 。 三、名词解释 21、（定义）可靠度：指产品在规定的条件下和规定的时间内，完成规定功能的概率，用R 表示。 22、（定义）失效率：又称故障率，产品工作t 时刻时尚未失效（或故障）的产品，在该时刻 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 高一第二学期《算法与程序设计》学分认定试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么”，然后再确定程序“如何做”请问“如何做”是属于用计算机解决问题的哪一个步骤（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、 D、 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式A+B+C 现代设计方法模拟试卷 一、单项选择题（本大题共２0小题。每小题１分。共2０分) 1.ＣＡD 一词已经成为世界通用的名词,它是指（ ） A.计算机辅助工程 B ． 计算机辅助设计 C ．计算机辅助制造? D ．计算机辅助工艺规程设计 2．实验测试了自变量为3,4,５,6，７，８时的函数值，现要用抛物线插值法计算５.８处的函数值,选择下列哪组自变量及其对应的函数值进行插值计算较为合理( ） Ａ．3，4，5 Ｂ．４，5,6 C ．5，６,7?Ｄ．6,7,８ 3．设备坐标系的维数一般为（ ） Ａ．一维 B ．二维 C 三维 Ｄ.四维 4.将平面图形沿Ｘ方向平移１０个单位,沿Y 方向平移１5个单位,其坐标变换矩阵为( ） A.??????????11510010001 B.??????? ???--11510010001 Ｃ.???? ? ?????101001500010D ．???? ??????10 10015000 1 5．在三维几何实体的实现模式中，有一种方法其基本思想是：几何实体都是由若干边界外表 面包容而成的,通过定义和全面存储这些边界外表面信息就可以建立实体几何模型,该方法是（ ) A ．ＣSG 法 ? B ．B-rep 法 ?Ｃ.光线投影法? D.扫描表示法 6．若函数Ｆ(x)在Dl 上具有连续二阶导数（Ｄ是Dl 内部的凸集),则F(ｘ)为D 上的凸函数的充分必要条件是F （x)的H ｅss ｉａn 矩阵( ) Ａ.半正定?B ．正定?C.半负定 D ．负定 7．编码裁剪法(C ｏｈe ｎ-Sutherland 法)中，某点在窗口右方,则其代码应为( ） A.００01 B ．0010 C.0１０0 D.100０ ８．在单峰搜索区间[x 1,x 3］(ｘ１ 《算法分析与设计》试题库 （一） 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上，并 D.动态规划算法 3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质 D.预排序与递归调用 4. 算法分析中，记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有：(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中，按(D)策略，从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先 《现代设计方法》课程习题集 西南科技大学成人、网络教育学院 版权所有 习题 【说明】：本课程《现代设计方法》（编号为09021）共有单选题,计算题,简答题, 填空题等多种试题类型，其中，本习题集中有[ 填空题,单选题]等试题类型未进入。 一、计算题 1. 用黄金分割法求解以下问题（缩小区间三次）。 342)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε。 2. 用黄金分割法求解以下问题（缩小区间三次） 32)(m in 2+=x x f ，给定[][],1,2a b =-，取1.0=ε 3. 用黄金分割法求解以下问题（缩小区间三次） 432+=x )x (f min ，给定[][]40,b ,a =，取10.=ε。 4. 用黄金分割法求解以下问题（缩小区间三次）。 12)(m in 3+-=x x x f ，给定初始区间[][]3,0,=b a ，取5.0=ε 5. 用黄金分割法求解以下问题（缩小区间三次）。 107)(m in 2+-=x x x f ，给定初始区间[][]3,0,=b a ，取1.0=ε 6. 用梯度法求解无约束优化问题： 168)(m in 22221+-+=x x x X f ，取初始点[]T X 1,1)0(= ，计算精度1.0=ε。 7. 用梯度法求解96)(m in 12221+-+=x x x X f ，[]T X 1,1)0(= ，1.0=ε。 8. 用梯度法求解44)(m in 22221+-+=x x x X f ，[]T X 1,1)0(=，1.0=ε 。 9. 用梯度法求解无约束优化问题：1364)(m in 222 121+-+-=x x x x X f ，取初始点[]T X 1,1)0(=，计算精度1.0=ε。 10. 用梯度法求解1212221422)(m in x x x x x X f --+=,[]T X 1,1)0(=，1.0=ε 。（请迭代两次） 11. 有三个可靠度均为0.9的子系统组成的并联系统，试比较纯并联及2/3[G]表决系统的可靠度。 12. 一个由2个子系统组成的系统，其可靠度指标为0.85，试按等同分配法分配子系统的可靠度：（1）组成串联系统，（2）组成并联系统。 13. 已知某零件的应力和强度均呈正态分布，零件强度：MPa 516=δμ（均值），MPa S 2.24=δ（标准差），应力：MPa 378=σμ（均值），Mpa S 5.41=σ（标准差），试计算零件的可靠度与失效概率。 14. 由应力分析表明，某零件所承受的应力是拉应力，可用正态分布来描述，MPa T 3500=μ，标准差MPa S T 400=。该零件在制造过程中所引起的残余应力也可用正态分布来描述，其均值MPa C 1000=μ，标准差MPa S C 150=。由强度分析表明，该零件的强度也服从正态分布，其均值MPa 5000=δμ。现要求出当保证该零件的可靠度不低0.999时，零件强度的标准差的最低值应为多少? 15. 由应力分析表明，某零件所承受的应力是拉应力，可用正态分布来描述，MPa T 3500=μ，标准差MPa S T 400=。该零件在制造过程中所引起的残余应力也可用正态分布来描述，其均值MPa C 1000=μ，标准差MPa S C 150=。由强度分析表明，该零件的强度也服从正态分布，其均值MPa 5000=δμ。现要求出当保证该零件的可靠度不低0.999时，零件强度的标准差的最低值应为多少? 2014山东省信息技术学考算法与程序设计试题答案附后讲解 山东省学考算法与程序设计试题 选择题 1、下列VB表达式中： ⑴Sqr(x) ⑵Text1.text ⑶Command1.caption ⑷"45"+"34" ⑸45+34值为字符串类型的是（） A⑴⑵⑶ B⑵⑶⑷ C ⑴⑶⑸ D⑵⑷⑸ 2、如果给出三条线段的长分别为a、b、c，且已知a≤b≤c，要问这三条线段能否构成三角形，仅需下列选项中的哪个判定条件即可？（） A 其他选项都不对 B a+c>b C a+b>c D b+c>a 3、VB程序中“Dim n As Integer”这条语句的作用是（） A 定义一个事件过程 B 定义一个数据输入方法 C 定义一个变量 D 定义一个数据处理方法 4、关于算法的描述，下列选项中正确的是（） A 算法的每一步骤必须有确切的含义 B 算法必须有输入 C 算法的步骤可以是无穷的 D 算法本身就是一种程序设计语言 5、关于算法的描述，正确的是（） A同一种算法只能用一种程序语言实现 B算法就是数值计算的方法 C描述算法的方法只有流程图 D算法是描述解决问题的方法和步骤 6、算法的描述方法有多种，下列选项中不适合描述算法的是（） A机器语言 B自然语言 C流程图 D伪代码 7、长度分别为a、b、c的三条线段，能够组成三角形的条件是（） A a+b>c Or a+c>b Or b+c>a B a+b>c or a+c>b And b+c>a C a+b>c Or a+c>b And b+c>a D a+b>c And a+c>b And b+c>a 8、已知海伦公式：()()() p p a p b p c ---p=1 2 （a+b+c），a、b、c分别为三角形的三条 边长。利用海伦公式求三角形面积的算法属于（） A 排序法 B 解析法 C 穷举法 D 查找法 9、以下程序段中循环体执行的次数是（） s=0 i=0 Do While s<10 i=i+1 s=s+i*i Loop A 1 B 3 C 2 D 4 10、下列VB表达式中，能正确表达不等式方程|x|>1的解的是（） A x>-1 and x<1 B x>-1 or x<1 C x<-1 and x>1 D x<-1 or x>1 11、一元二次方程ax2+bx+c=0(a≠0)的两个实数根分别为： x 1 24 b b ac -+- 2 24 b b ac ---下列表达式正确的是（） A x 2=-b-sqr(b^2-4*a*c)/(2*a) B x 1 =(-b+sqr(b^2-4ac))/(2*a) 环境变量 一．用牛顿法求函数 2214121)2()2(),(x x x x x f -+-= 的极小值点坐标（迭代二次）。 解 初始点T x ]2,3[0 = 则初始点处的函数梯度、海森矩阵及其逆矩阵为 ?? ????=??????---+-=?42)2(4)2(2)2(4)(21213 1 0x x x x x x f ????? ?--=??????--+-=?844148442)2(12)(21 02x x f ???? ??? ???=?=487241241121 )]([1 02x f 代入牛顿法迭代公式，得 T x f x f x x ? ? ? ???=??-=34,38)()]([0 1 2 1 - ??? ?????=??????---+-=?02732)2(4)2(2)2(4)(212 1311x x x x x x f 代入牛顿法迭代公式，得 ?? ? ???=??-=26.152.2)()]([1 1 12 1 2 x f x f x x - 二、分析比较牛顿法、阻尼牛顿法、共轭梯度法、变尺度法和鲍威尔法的特点，找出前四种方法的相互联系。 比较牛顿法：牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。 阻尼牛顿法：可以看出原始牛顿法就相当于阻尼牛顿法的步长因子取成固定值1的情况。阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。 这类方法的主要缺点计算复杂，工作量大，要求计算机存储量大 共轭梯度法：共轭方向主要是针对二次函数的，但也可以用于一般非二次函数。共轭方向法是二次收敛的，计算程序简单，存储量相对较少 变尺度法：只需用到函数的一阶梯度；下降算法，故收敛全局；计算量小（不需要求矩阵逆）；一般可以达到超线性收敛（速度快） 鲍威尔法：多维无约束优化算法是在无约束优化算法之一，首先选取一组共轭方向，从某个初始点出发，求目标函数在这些方向上的极小值点，然后以该点为新的出发点，重复这一过程直到获得满意解，其优点是不必计算目标函数的梯度就可以在有限步内找到极值点。 三、已知约束优化问题minf(x)=(x 1-2)2+(x 2-x 1)2 2020年高中信息技术《算法与程序设计》 试题精品版 新课标高中信息技术《算法与程序设计》试题一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（ ） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C 算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do 课程名称： 现代设计方法 一、 单选题 ( 每题1分，共10题，共10分，下列各小题备选答案中，只有一个符合题意的答案。多选、错选、不选均不得分 ) 1. 参数化绘图在定义图形时关键是利用了图形的（ ） A ．相似性 B ．多样性 C ．个别性 D ．特殊性 2. 下列设备不属于CAD 作业输入设备的，有（ ） A ．绘图仪 B ．键盘 C ．数字化仪 D ．光笔 3. 二维图形比例变换矩阵中?? ????=d a T 00，可有（ ） A.a=0,d=1 B. a=1,d=0 C. a=d=1 D. a=d=0 4. 内点罚函数法的特点是（ ） A.能处理等式约束问题 B.初始点必须在可行域内 C. 初始点可以在可行域外 D.后面产生的迭代点序列可以在可行域外 5. 对于极小化F(x)，而受限于约束g μ(x)≤0(μ= 0,1,2,…,m)的优化问题，其内点罚函数表达式为（ ） A.∑=-=Φm k k X g r X F r X 1)()()(/1)(),(μμ B.∑=+=Φm k k X g r X F r X 1)()()(/1)(),(μμ C.∑=-=Φm k k X g r X F r X 1)()()](,0m ax[)(),(μμ D.∑=-=Φm k k X g r X F r X 1)()()](,0m in[)(),(μμ 6. 设F (X )为区间(0,3)上的单峰函数，且F (1)=2、F (2)=1.5，则可将搜索区间(0,3)缩小为（ ） A ．(0,2) B ．(1,2) C ．(2,3) D ．(1,3) 7. 标准正态分布是定义为（ ） A.μ＝1，σ＝0.5的正态分布 B.μ＝1，σ＝1的正态分布 C.μ＝0，σ＝1的正态分布 D.μ＝0.5，σ＝1的正态分布 8. 抽取100只灯泡进行实验，灯泡工作到50小时有12只损坏，工作到70小时有20只损坏，从50小时到70小时这段时间内灯泡的平均失效密度是（ ） A.0.006 B.0.004 C.0.01 D.0.12 9. 当转换开关的可靠度为1时，非工作冗余系统的可靠度为R1, 工作冗余系统的可靠度为R2，则R1与R2之间的关系为（ ） A. R1＜R2 B. R1＞R 2 C. R1= R2 D. R1≤R2 10. 设试验数为N 0，累积失效数为N f (t)，仍正常工作数N s (t)，则存活频率是指（ ） A ．0) (N t N f B ．0)(N t N s C ．)()(t N t N f s D ．) ()(t N t N s f 算法与程序设计试题 一、选择题（每题两分，共１４分每题2分） １、要进行元旦晚会比赛，学校请你设计一个能够对元旦晚会节目分数自动排序的软件，你接到任务后，准备开始设计此软件，比较好的方法和步骤是（） Ａ、设计算法，编写程序，提出问题，调试程序 Ｂ、分析问题，编写程序，设计算法，调试程序 Ｃ、分析问题，设计算法，编写程序，调试程序 Ｄ、设计算法，提出问题，编写程序，调试程序 2、数值型数据包括两种。 A、整型和长整型 B、整型和浮点型 C、单精度型和双精度型 D、整型、实型和货币型 3、具有输出数据功能的控件是：（） Ａ、窗体控件和标签控件 Ｂ、复选框控件和文本框控件 Ｃ、标签控件和文本框控件 Ｄ、选项框按钮控件和复选框控件 4、要使循环体至少执行一次，应使用循环。 ５、下列程序段是计算公式的： s=0;t=1 for I =1 to 10 t:=t*I s:=s+t Next I A、s=1+2+3＋......１０Ｂ、s=1*2*3* (10) C、s=1!+2!+3! ......10! D、s=1+2*3+3*4+4*5+......９*10 6、在窗体（Name属性为Formal）上画两个文本框（其Name属性分别为Text1和Text2）和一个命令按钮（Name属性为Command1），然后编写如下两个事件过程： Private Sub Command1_Click() A = Text１Text + Text2.Text Print a End Sub Private Sub Formal_Load() Text1.Text = " " Text2.Text = " " End Sub 程序运行后，在第一个文本框（Text1）和第二个文本框（Text2）中分别输入123和321，然后单击命令按钮，则输出结果为（）。 A、444 B、321123 C、123321 D、132231 ７、使用函数与过程是为了。 A、使程序模块化Ｂ、使程序易于阅读高中信息技术《算法与程序设计》试题
现代设计方法复习题1
算法分析与设计试卷
现代设计方法习题答案
《算法与程序设计》试题带答案
现代设计方法试卷1及答案
算法设计与分析试卷A及答案
算法与程序设计试题带答案
现代设计方法模拟试题
5.《算法设计与分析》试题库
现代设计方法-习题集(含答案)
2014山东省信息技术学考算法与程序设计试题答案附后讲解
现代设计方法答案
最新高中信息技术《算法与程序设计》试题精品版
算法分析与设计复习题及答案
现代设计方法试卷及答案
算法与程序设计试题
相关主题
文本预览