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

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

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

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

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

4、(ｘ1,ｘ２,……xｉ)(i

5、使用分治法，反复分治,必然要用到递归。3.为什么要分析最坏情况下的算法时间复杂性？、12　最坏情况下的时间复杂性决定算法的优劣,并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。4.简述渐进时间复杂性上界的定义。１3.T(ｎ）是某算法的时间复杂性函数,f(n)是一简单函数，存在正整数Ｎo和C，n〉No，有T(n)<ｆ（n),这种关系记作T（n)＝O(f(n))。5.二分检索算法最多的比较次数?14.二分检索算法的最多的比较次数为log　ｎ　。6.快速排序算法最坏情况下需要多少次比较运算？1５．.最坏情况下快速排序退化成

6、冒泡排序,需要比较n２次。7.贪心算法的基本思想?16.是一种依据最优化量度依次选择输入的分级处理方法。基本思路是:首先根据题意，选取一种量度标准；然后按这种量度标准对这ｎ个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件,则不把此输入加到这部分解中。8.回溯法的解(ｘ１,ｘ2,……xn）的隐约束一般指什么？17．回溯法的解(x1,ｘ2,……xn)的隐约束一般指个元素之间应满足的某种关系。9.阐述归并排序的分治思路。１8.　讲数组一分为二,分别对每个集合单独排序，然后将已排序的两个序列归并成一

7、个含n个元素的分好类的序列。如果分割后子问题还很大,则继续分治,直到一个元素。10.快速排序的基本思想是什么。　19.快速排序的基本思想是在待排序的Ｎ个记录中任意取一个记录,把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分,所有比它大的放置在后一部分,并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程,直到每一部分内只有一个记录为止。　11.什么是直接递归和间接递归?消除递归一般要用到什么数据结构？20.在定义一个过程或者函数的时候又出现了调用本过程或者函数

8、的成分，既调用它自己本身,这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。个人收集整理勿做商业用途1.什么是哈密顿环问题?21.哈密顿环是指一条沿着图Ｇ的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。2.用回溯法求解哈密