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

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

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

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

3、2+1：j]找x。上述过程被反复递归调用。7.背包问题的目标函数和贪心算法最优化量度相同吗？7.不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。8.采用回溯法求解的问题，其解如何表示？有什么规定？8.问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si,Si为有穷集合，xi∈Si,（x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i

4、有的值，便回溯到x[k-1]。1.n皇后问题回溯算法的判别函数place的基本流程是什么？10.将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。2.为什么用分治法设计的算法一般有递归调用？11.子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。3.为什么要分析最坏情况下的算法时间复杂性？、12最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。4.简述渐进时间复杂性上界的定义。13.T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉N

5、o，有T(n)

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

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