算法设计与分析课后部分习题答案
算法实现题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 for(j=0;j<=i;j++) fscanf(in,"%d",&triangle[i][j]); for(int row=n-2;row>=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个加油站之间的距离。第 0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。结果输出： 将编程计算出的最少加油次数输出到文件output.txt。如果无法到达目的地，则输出"No Solution“。 输入文件示例输出文件示例 input.txt output.txt 7 7 4 1 2 3 4 5 1 6 6 源程序： #include"stdio.h" void main() { FILE *in,*out; inti,s,n,k,x[100],sum=0;//x数组用来存储距离，sum表示加油次数，s 表示加油后行驶的距离 in=fopen("input.txt","r"); //读入n，k以及距 离 fscanf(in,"%d",&n); fscanf(in,"%d",&k); for(i=0;i<=k;i++) fscanf(in,"%d",&x[i]); for(i=0;i<=k;i++){ if(x[i]>n) printf("No Solution!");} for(i=0,s=0;i<=k;i++){ s+=x[i]; if(s>n) {sum++; s=x[i];} } out=fopen("output.txt","w");//输出结果sum到output.txt中 fprintf(out,"%d",sum); } 算法实现题 5-15最佳调度问题 问题描述： 假设有n个任务由k个可并行工作的机器来完成。完成任务i需要 的时间为ti。试设计一个算法找到出完成这个n个任务的最佳调度，使得完成全部任务的时间最早。编程任务： 对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1-n。编程计算完成这n个任务的最佳调度。数据输入： 由文件input.txt给出输入数据。第1 行有2个正整数n 和k。第2行的n个正整数是完成n 根任务需要的时间。结果输出： 将计算出的完成全部任务的最早时间输出到文件output.txt。 输入文件示例输出文件示例 input.txt output.txt 7 3 17 2 14 4 16 6 5 3 源程序： #include"stdio.h" intlen[100],t[100],best=1000,n,k; int comp()//comp函数用来计算完成时间 { inttmp=0; for(inti=0;i if(len[i]>tmp) tmp=len[i]; returntmp; } void search(intdep)//search函数用来回溯搜索 { if(dep==n){ inttmp=comp(); if(tmp for(inti=0;i if(len[i] len[i]-=t[dep];} } void main() { FILE *in,*out; in=fopen("input.txt","r");//读入n，k以及每个任务需要时间t[i] fscanf(in,"%d",&n); fscanf(in,"%d",&k); for(inti=0;i { fscanf(in,"%d",&t[i]); len[i]=0;} search(0);//第一个任务开始搜索 out=fopen("output.txt","w"); fprintf(out,"%d",best); } 第一章 1.计算机系统是由计算机硬件系统和软件系统这两个密不可分的部分组成的。 2.计算机软件系统通过运行程序来实现各种不同应用，包括用户为自己的特定目的编写的程序、检查和诊断机器系统的程序、支持用户应用程序运行的系统程序、管理和控制机器系统资源的程序等。 3.在软件工程学中，软件开发技术包括软件开发方法学、软件工具和软件工程环境。 4.在软件工程层次结构中，包括工具层、方法层、过程、技术层和质量保证层。 5.在面向对象概念中，消息传递是其与外部世界相互关联的唯一途径。 第三章 1.软件需求分析，可以把软件功能和性能的总体概念描述为具体的软件需求规格说明，进而建立软件开发的基础。 2.软件需求工作基本上包括收集用户、市场等方面对项目的需要，经过分析建立解题模型，细化模型，抽取需求。 3.结构化分析方法的基本步骤是采用由顶向下对系统进行功能分解，画出分层数据流图；由后向前定义系统的数据和加工，绘制数据词典和加工说明；最终写出软件需求和规格说明书。 4.面向对象分析方法总是从理解系统的“使用实例”开始，基本步骤是：定义系统的用例，在领域分析的基础上建立问题域的类（对象模型），然后开始建立对象——关系和对象——行为模型。 5.需求分析评审过程由以下5个步骤组成：规划、准备、召开审查大会、修改缺陷、重审。 第四章 1.与软件需求分析一样，软件设计也有两种主要设计方法：以结构化设计为基础的结构化软件设计和面向对象方法指导的面向对象软件设计。 2.传统的软件设计任务通常分两个阶段完成。第一个阶段是概要设计，包括体系结构设计 和接口设计，并编写概要设计文档；第二阶段是详细设计，其任务是确定各个软件的数据结构和操作，产生描述各软件组件的详细设计文档。 3.结构化的软件设计方法是一种面向数据流的设计方法，在面向数据流的方法中，数据流是考虑一切问题的出发点。 4.在数据流图中所代表的结构化设计模型中，所有系统均可纳入两种典型的形式，因此系统结构图也有两种类型：变换型系统结构图，事务型系统结构图。 5.Jackson表示法包括图形描述（Jackson图）和文本描述（Jackson伪代码）两种形式。 第五章 1.与结构化设计一样，面向对象设计也是将分析阶段所建立的分析模型转变为软件设计模型，应用数据设计（对象属性设计）、接口设计（消息模型开发）以及过程设计（子系统级设计）。 2.当两个子系统相互通信时，可以建立客户机/服务器连接或端对端连接。 3.系统设计不仅包括主要的业务需求子系统设计，还包括用户界面子系统设计、任务管理子系统设计、数据管理子系统设计。 4.对象设计强调从问题域的概念转换成计算机领域的概念，通过对象的描述、算法和数据结构设计、程序构件和接口，实现相关的类、关联、属性和操作。 5.在面向对象设计中系统设计的主要目标是表示软件体系结构。对象设计着重于对象及其交互的描述 第八章 1.软件程序测试的目的是发现程序中的错误，其主要任务是通过在计算机上执行程序，暴露 《计算机算法设计与分析》习题及答案 一．选择题 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 ）。 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 机械设计习题 第3章疲劳强度 问答题 1.问：试述零件的静应力与变应力是在何种载荷作用下产生的？ 答：静应力只能在静载荷作用下产生，变应力可能由变载荷产生，也可能由静载荷产生。 2、稳定循环变应力的种类有哪些？画出其应力变化曲线，并分别写出最大应力σmax、最小应力σmin、平均应力σm、应力幅σa与应力循环特性γ的表达式。 答：对称循环变应力、脉动循环变应力、非对称循环变应力 3、机械零件疲劳破坏的特征有哪些？机械零件疲劳强度与哪些因素有关？ 特征：（1）疲劳失效过程：裂纹萌生、裂纹扩展和突然发生脆性断裂三个阶段（2）断裂面：疲劳源、光滑的疲劳区、粗糙的断裂区（3）无明显塑性变形的脆性突然断裂（4）破坏时的应力（疲劳极限）远小于材料的屈服极限 影响因素：不仅与材料性能有关，变应力的循环特性，应力循环次数，应力幅都对疲劳极限有很大影响。 4、如何由σ-1、σ0和σs三个试验数据作出材料的简化极限应力图？ 5、相对于材料，影响机械零件疲劳强度的主要因素有哪些？综合影响因素（Kσ）D的表达式为何？如何作零件的简化极限应力图？ 应力集中、零件尺寸、表面状态 6、应力集中、零件尺寸和表面状态是否对零件的平均应力σm和应力幅均有影响？ 只对应力幅有影响，对平均应力没有明显影响 7、按Hertz公式，两球体和圆柱体接触时的接触强度与哪些因素有关？ 外载荷F、ρΣ、弹性模量E、泊松比u以及b 8.问：零件的等寿命疲劳曲线与材料试件的等寿命疲劳曲线是否相同？ 答：两者不同，零件的等寿命疲劳曲线需考虑零件上应力集中对材料疲劳极限的影响。 9.问：疲劳损伤线性累积假说的含义是什么？ 答：该假说是：在每一次应力作用下，零件寿命就要受到一定损伤率，当损伤率累积达到100%时（即达到疲劳寿命极限）便发生疲劳破坏。通过该假说可将非稳定变应力下零件的疲劳强度计算折算成等效的稳定变应力疲劳强度。 10.问：机械零件上的哪些位置易产生应力集中？举例说明。如果零件一个截面有多种产生应力集中的结构，有效应力集中系数如何求取？ 算法实现题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 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 1.冷原子吸收法和冷原子荧光法测定水样中的汞，在原理和仪器方面有何主要相同和不同之处？ 答：水样中的汞化合物经酸性高锰酸钾热消解，转化为无机的二价汞离子，再经亚锡离子还原为单质汞，用载气或振荡使之挥发成汞蒸气。冷原子吸收法利用汞蒸气对波长为253.7nm 的紫外光有选择性吸，测定吸收光强并通过标准曲线确定汞的浓度。冷原子荧光法是在原子吸收法的基础上发展起来发射光谱法。汞蒸气经过汞灯发射的光束时，汞原子吸收特定共振波的能量，由基态激发到不稳定的高能态，当被激发的原子回到基态时，发出特征荧光，测定荧光强度通过标准曲线确定汞的浓度。两种方法的仪器均主要由光源、吸收管、试样系统、光电检测系统、指示系统等组成，检测吸收光强的检测器与汞灯发射光束在一条直线上，但检测荧光强度的检测器应与汞灯发射光束垂直。 2.高锰酸盐指数和化学需氧量在应用上有何区别？二者在数量上有何关系？为什么？ 答：高锰酸盐指数（I Mn）和化学需氧量（COD Cr）均为表示水体中有机物相对含量的指标，是指在一定条件下，分别以重铬酸钾（K2Cr2O7）和高锰酸钾（KMnO4）氧化水中的亚硝酸盐、亚铁盐、硫化物和有机物所消耗的氧化剂的量，以氧的mg/L表示，二者均是条件性指标。I Mn指数仅用表征地表水的水质，COD Cr既可用于地表水也可用于废水。由于所用的氧化剂氧化强度不同、氧化反应条件也不同，I Mn能表征水中50~70%的有机物，而COD Cr能表征水中除吡啶、芳香族、苯类等以外的绝大部分有机物，故对于同一个水质I Mn < COD Cr。 3.如何提高溶液吸收法的富集效率？ 答：溶液吸收法的富集效率取决于溶液吸收效率和气体与溶液的接触面积。提高溶液吸收效率应选择适宜的吸收液及吸收管。吸收液应……，吸收管应……。 4.测定烟气中颗粒物的采样方法和测定气态或蒸气态组分的采样方法有何不同？ 答：由于颗粒物与其他组分惯性大小不同，采集颗粒物时必须等速采样，根据需要进行移动采样或定点采样后测定其浓度，气态或蒸气态惯性较小，不必等速采样，其在烟道中分布较均匀，一般进行定点采样即可。 《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题 答：算法如下： （1） 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 华侨大学金融市场学课件习题答案—科目老师：刘卫红（希望以后修这门的同学计算方面会轻松点儿） 来源： 金融市场习题答案 1、某公司发行面额为100万元的商业票据融资，发行折扣为5720元，期限为60天，则该票据投资者的实际收益率为多少？ 2、假设某投资者以994280元的价格购买了上例中面额为100万的商业票据，在持有30天后将其出售，此时市场利率为5%，则该商业票据的市场价格为多少？该投资者的实际收益为多少？ ?元 实际收益=995850.62-994280=1570.62元 3、某银行发行大额可转让存单，面值50万元，存单利率5%，期限270天，某投资者持有该存单4个月后出售，出售时市场利率为4%，计算存单的转让价格。 4、某证券的回购价格为100万元，回购利率为5.5%,回购期限7天,则该证券的售出价格是多少? 回购利息=回购价格×回购利率×回购天数/360=100万×5.5%×7/360=1069.44元，售价=100万 -1069.44=998930.56元 5、假定某投资者以6.75%的利率投资于5天期限的再购回协议,协议金额为2500万元,该投资者的收益为多少?如果该投资者与借款人签订的是连续再购回协议,5天后终止该合同,假定5天中每天的再购回利率分别为6.75%,7%,6.5%,6.25%,6.45%,这一连续协议的总利息收入为多少? 投资收益=2500万×6.75%×5/360=2.344万 总利息收入=2500万×（6.75%+7%+6.5%+6.25%+6.45%）×1/360=2.29万 1、息票债券的票面利率为8%，面值1000元，距到期日还有5年，到期收益率为7%，在下列情况下分别求债券的现值。（1）每年付息一次；（2）半年付息一次；（3）每季度付息一次 （1） 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include （2）什么是过程控制系统？试用方框图表示其一般组成。 答：过程控制系统：一般是指工业生产过程中自动控制系统的变量是温度、 压力、流量、液位、成份等这样一些变量的系统。 过程控制系统的一般性框图如图１-1所示: 图１－1 过程控制系统的一般性框图 （3)单元组合式仪表的统一信号是如何规定的？ 答：各个单元模块之间用统一的标准信号进行联络。 １）模拟仪表的信号:气动0．０2 ~0.1MPa；电动Ⅲ型：4~20mAＤC或1~5V DＣ。 2）数字式仪表的信号:无统一标准。 (4)试将图1-2加热炉控制系统流程图用方框图表示。 答：加热炉控制系统流程图的方框图如图1-3所示: 图1-2 加热炉过程控制系统流程 （5)过程控制系统的单项性能指标有哪些?各自是如何定义的? 控制器 r(t) 执行器被控过程 检测变送装置 y(t) _ f(t) e(t)u(t)q(t) z(t) TC PC 给定值 阀管道加热炉 热油出口温 度 PT 燃油压力 _ TT _ 干扰2干扰1 AC AT 燃油 PT PC TC TT 引风机 烟气 冷油入口 热油出口 火嘴 送风机 空气 1 100%() y y σ= ?∞答:1）单项性能指标主要有:衰减比、超调量与最大动态偏差、静差、调节时间、振荡频率、上升时间和峰值时间等。 2)各自定义为：衰减比：等于两个相邻的同向波峰值之比n ； 超调量σ:第一个波峰值 1 y 与最终稳态值y(∞）之比的百分数： 最大动态偏差A ：在设定值阶跃响应中,系统过渡过程的第一个峰值超出稳态值的幅度; 静差,也称残余偏差C ： 过渡过程结束后，被控参数所达到的新稳态值y(∞）与设定值之间的偏差C 称为残余偏差，简称残差; 调节时间s t :系统从受干扰开始到被控量进入新的稳态值的5%±（2%±）范围内所需要的时间； 振荡频率 n ω:过渡过程中相邻两同向波峰（或波谷)之间的时间间隔叫振荡周期或工作周期，其倒数称为振荡频率； 上升时间p t :系统从干扰开始到被控量达到最大值时所需时间; 峰值时间 p t ：过渡过程开始至被控参数到达第一个波峰所需要的时间。 （9)两个流量控制系统如图１-4所示。试分别说明它们是属于什么系统?并画出各自的系统框图。 图１-4 两个流量控制回路示意图 答：系统1是前馈控制系统,系统2是反馈控制系统。系统框图如图１-５如下： 系统1 系统2 图１-5 两个流量控制回路方框图 (１0)只要是防爆仪表就可以用于有爆炸危险的场所吗？为什么？ 答:1）不是这样。 2）比如对安全火花型防爆仪表，还有安全等级方面的考虑等。 (11）构成安全火花型防爆控制系统的仪表都是安全火花型的吗？为什么？ 答：1)是的。 2)因为安全火花型防爆系统必备条件之一为:现场仪表必须设计成安全火花型。 2.综合练习题 （3）某化学反应过程规定操作温度为80±５℃,最大超调量小于或等于5％,要求设计的定值控制系统,在设定值作最大阶跃干扰时的过渡过程曲线如图1-８所示。要求:１）计算该系统的稳态误差、衰减比、最大超调量和过渡过程时间； 测量变送 被控过程 执行器测量变送 被控过程 执行器 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算法的思想。 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 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）是贪心算法与动态规划算法的共同点。 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 Linux基础教程部分参考答案 1.2 什么是软件？软件分为哪几大类？Linux、Flash、Oracle、抓图软件、Skype各属于哪几类软件？ 详见课本P3-4 软件是与数据处理系统操作有关的计算机程序和相关数据等的总称。 程序是计算机完成一项任务的指令的集合。 数据是由程序使用或生成的不同类型的信息。 系统软件 这些软件对计算机系统的资源进行控制、管理，并为用户使用和其他程序的运行提供服务。 Linux Oracle 是系统软件。 支撑软件 是辅助软件技术人员从事软件开发工作的软件。 应用软件 是为解决某一类应用需要或某个特定问题而设计的程序。 Flash、抓图软件、Skype 是应用软件。 1.5下列哪些软件是开源软件：Windows XP、Red Hat、IE、UNIX？ Red Hat、UNIX。 1.7 Linux迅速发展的优势是什么？ Linux的迅速发展具有一系列优势，主要包括： (1)开放源码系统从本质上就具有其它系统无法比拟的发优势。 (2)Linux受到各国政府的大力支持。 (3)得到全球各大软、硬件公司的支持。 (4)格优势和安全性。 1.8 Linux核心版本与发行版本有何区别？ 详见课本P15 2.7请说明下列命令的含义：/dev/hda3,/dev/sdb6。 /dev/hda3指IDE接口的第一个硬盘的3号分区 /dev/sdb6指SATA接口的第二个硬盘的6号分区 4.6 命令cp与mv有何异同？你能够用copy作为文件复制的命令吗？为什么？ 详见课本P81 copy不能做为文件复制的命令，因为系统没有copy命令。 4.7 将文件file1的前20行、文件file2的最后15行合并成一个文件AB。 head -n 20 file1 > A tail -n 15 file2 > B cat A B > AB 5.5 说出下列每一项信息各对应哪一类文件： (1)drwxr-xr-x 目录文件 (2)/bin 二进制文件目录 (3)/etc/passwd账户文件 (4)brw-rw-rw-块设备文件 (5)/dev/fd0 标识设备的特殊文件 (6)/usr/lib 库文件 (7)-rwx--x--x 普通文件 5.6 假设利用ls -l长列表格式显示某个目录的内容时，看到如下一行文件说明： -rwxr-xr-- 2 menggc users 5699 12月28 11:36 prog1 问： (1)该文件的名称是什么？他是什么类型的文件？ 文件名：prog1 文件类型：普通文件 (2)想要取消其他用户对文件的执行权限，应使用什么命令？ chmod o-x prog1 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 第一章 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)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题软件工程部分课后练习题答案
《计算机算法设计与分析》习题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
机械零件部分课后习题答案
算法设计与分析课后部分习题答案
算法设计与分析试卷(2010)
课后部分习题答案
算法设计与分析习题
计算机算法设计与分析期末考试复习题
金融学部分课后习题答案
算法设计与分析第2版 王红梅 胡明 习题答案
过程与控制部分课后题标准答案
算法设计与分析考试题及答案
计算机算法设计与分析习题及答案
算法设计与分析期末试题答案解析
linux部分课后习题答案
算法设计与分析试卷及答案
算法设计与分析课后习题
相关文档
- 算法设计与分析习题
- 算法设计与分析基础课后习题答案solu3
- 计算机算法设计与分析第四版课后答案
- 计算机算法设计与分析期末考试复习题
- (精品)算法设计与分析基础课后习题答案(中文版)
- 算法设计与分析习题
- 算法设计与分析.习题课
- OpenJudge算法设计与分析习题解答
- 算法设计与分析习题与实验题(12.18)
- 算法设计与分析基础习题参考答案
- 计算机算法设计与分析习题及答案
- 算法设计与分析习题
- 算法设计与分析 习题2-5
- 算法设计与分析C++语言描述(陈慧南版)课后答案
- 计算机算法设计与分析期末考试复习题
- 算法设计与分析习题课
- 计算机算法设计与分析习题及答案
- 算法设计与分析课后习题
- 《算法设计与分析》复习题参考答案
- 算法设计与分析习题