《算法分析与设计》期末试题及参考答案

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

1、《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。3.3.算法的时间复杂性与问题的什么因素相关？3.算法的时间复杂性与问题的规模相关，是问题大小n的函数。4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶

2、)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5.最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n)=max{T(n，I)},I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=∑P(I)T(n，I)I∈Dn6.简述二分检索（折半查找）算法的基本过程。6.设输入是一个按非降次序排列的元素表A[i：j]和x，选

3、取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]

4、完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i

5、调用？11.子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。3.为什么要分析最坏情况下的算法时间复杂性？、12最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。4.简述渐进时间复杂性上界的定义。13.T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)

6、坏情况下需要多少次比较运算？15．.最坏情况下快速排序退化成冒泡排序，需要比较n2次。7.贪心算法的基本思想？16.是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。8.回溯法的解（x1,x2,……xn）的隐约束一般指什么？17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。9.阐述归并排序的分治

7、思路。18.讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。10.快速排序的基本思想是什么。19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。11.什么是直接递归和

8、间接递归？消除递归一般要用到什么数据结构？20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。1.什么是哈密顿环问题？21.哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。2.用回溯法求解哈密顿环，如何定义判定函数？22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i]