算法分析与设计习题集答案

《算法分析与设计习题集答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计习题集基础篇1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算（书上定义）特征：输入、输出、有穷性、明确性、有效性区别：算法是完成特定任务的有限指令集。程序是用计算机语言编写的写成特定任务的指令序列。2、算法的时间复杂度指的是什么？如何表示？算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。（百度百科）3、算法的空间复杂度指的是什么？如何表示？一个程序的空间复杂度是指运行完一个程序所需内

2、存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))

3、其中n为问题的规模，S(n)表示空间复杂度。4、什么是最坏时间复杂性？什么是最好时间复杂性？答：最坏情况时间复杂性：最好情况时间复杂性：：I*是DN中使T(N,I*)达到Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率1、什么是递归算法？什么是递归函数？递归算法（包括直接递归和间接递归子程序）都是通过自己调用自己，将求解问题转化成性质相同的子问题，最终达到求解的的。递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对相关且必要的信息的保存与恢复，从而省略了求解过程中的许多细节的描述。【课本】直接递归子程序在运行完成前调用它们自己。间接递归子程序在运行过程中调用其它子

4、程序，其他子程序反过来调用这个调用子程序。递归函数，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。网上：答：（1）递归算法:直接或间接地调用自身的算法；（2）递归函数:用函数自身给出递归定义的函数。2、分治法的设计思想是什么？将整个问题分成若干个小问题后分而治之给定一个有n个输入的函数，分治策略建议将输入分为k个不同的子集，1

5、子问题仍然较大，可以再次使用分治策略。更精确地说，分治策略将输入划分为与原问题同类型的k个子问题。许多时候，k=2。3、动态规划基本步骤是什么？答：（1）找出最优解的性质，并刻划其结构特征;（2）递归地定义最优值;（3）以自底向上的方式计算出最优值;(4)根据计算最优值时得到的信息，构造最优解。4、回溯法与分枝限界法之间的相同点是什么？不同之处在哪些方面？答：同：他们同是在问题的解空间树上搜索问题解的算法；异：（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解；（2）搜索方

6、式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。5、分枝限界法的基本思想是什么？答：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。6、限界函数的功能是什么？答：用限界函数剪去得不到最优解的子树1、设某一函数定义如下：编写一个递归函数计算给定x的M（x）的值。本函数是一个递归函数，其递归出口是：M（x）=x-10x>100递归体是：M（M（x+11））x≤100实现本题功能的递归函数如下：intm(intx){inty;if(x>100)return(x-10);else{y=m(x+11);return(

7、m(y));}}procedureM(x)ifx>100thenreturn(x-10)elsereturnM(M(x+11))endifendM2、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。