算法分析及设计习题集整理

《算法分析及设计习题集整理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式的上界为O(nm)。3、算法的基本特征：输入、输出、确定性、有限性。4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为：O(n3)。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、

2、盒图、PAD图。7、算法设计的基本要求：正确性和可读性。8、计算下面算法的时间复杂度记为：O(n2)。for（i＝1；i

3、ogn)，O(n2/3)，O(20n)，O(4n2)，O(3n)，O(n!)2、什么是算法？算法的特征有哪些？答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出；3)确定性；４)有穷性3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for(j=1;j<=n;j++)(1)for(i=1;i<=n;i++)(2){c[i][j]=0;(3)for(k=1;k<=n;k++)(4)c[i][j]=c[i][j]+a[i][

4、k]*b[k][j];}(5)答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。所需资源越多，表明算法的复杂性越高3）该算法的主要元操作是语句5，其执行次数是n3次。故该算法的时间复杂度记为O(n3).4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程，算法B的时间复杂性满足递归方程，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？答：分别记算法A和算法B的时间复杂性为和，解相应的递归方程得：依题意，要求最大的整数a使得〈。显然

5、，当a<=4时，〈；当a>4时，〈a<=16。所以，所求的a的最大整数值为15。5、算法分析的目的？答：1)为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；2)是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。6、算法设计常用的技术？（写５种）答：①分治法;②回溯法；③贪心法；④动态规划法⑤分治限界法；⑥蛮力法；⑦倒推法三、算法设计题　1、蛮力法：百鸡百钱问题？　　　　　　　2、倒推法：穿越沙漠问题？　　　　　第二章分治算法（1）----递归循环一、填空题：1、直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。2、递

6、归方程和约束函数（递归终止条件）是递归函数的两个要素。二、判断题：1、所有的递归函数都能找到对应的非递归定义。（√）2、定义递归函数时可以没有初始值。（X）三、简答题：1、什么是递归算法？递归算法的特点？答：1)递归算法:是一个模块（函数、过程）除了可调用其它模块（函数、过程）外，还可以直接或间接地调用自身的算法。2)递归算法特点：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）2、比较循环与递归的异同？答：1)相同：递归与循环都是解决“重复操作”的机制。2)不同：就效率而

7、言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然。递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。3、递归算法解题通常有三个步骤？答：1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。3）设计函数、确定参数：和其它算法模块一样设计函数