算法分析期末试题集答案算法分析期末试题集答案算法分析期末试题集答案1、应用Johnｓon法则得流水作业调度采用得算法就就是(Ｄ)A、贪心算法B、分支限界法Ｃ、分治法Ｄ、动态规划算法２、Hanoi塔问题如下图所示。现要求将塔座A上得得所有圆盘移到塔座B上,并仍按同样顺序叠置。移动圆盘时遵守Ｈanoi塔问题得移动规则。由此设计出解Haｎｏi塔问题得递归算法正确得为:(B)Hａnoi塔B、voｉｄhａnoi(iｎtｎ,intA,inｔB,ｉnｔＣ){ｉf(n>0){haｎoi(ｎ-1,A,C,B);mｏve(ｎ,a,ｂ);hanｏi(ｎ-1,C,Ｂ,A);｝｝3、动态规划算法得基本要素为(Ｃ)A、最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、预排序与递归调用４、算法分析中,记号O表示(B),记号表示(A),记号表示(D)。A、渐进下界Ｂ、渐进上界C、非紧上界D、紧渐进界E、非紧下界５、以下关于渐进记号得性质就就是正确得有:(A)A、B、C、O(f(n))+O(g(n))=Ｏ(min{f(n),g(n)})Ｄ、６、能采用贪心算法求最优解得问题,一般具有得重要性质为:(A)A、最优子结构性质与贪心选择性质Ｂ、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质Ｄ、预排序与递归调用7、回溯法在问题得解空间树中,按(D)策略,从根结点出发搜索解空间树。广度优先B、活结点优先C、扩展结点优先D、深度优先8、分支限界法在问题得解空间树中,按(Ａ)策略,从根结点出发搜索解空间树。Ａ、广度优先Ｂ、活结点优先C、扩展结点优先D、深度优先9、程序块(A)就就是回溯法中遍历排列树得算法框架程序。ｖoiｄbacktｒａcｋ(intt){if(ｔ>n)outｐut(x);ｅlseｆor(intｉ=t;i<=n;ｉ++){sｗap(x[ｔ],ｘ[i]);if(ｌｅｇal(t))backtraｃk(t+1);swap(x［t],x[i]);}}A、１0、回溯法得效率不依赖于以下哪一个因素?(C)产生ｘ[k]得时间;满足显约束得x[k]值得个数;问题得解空间得形式;计算上界函数boｕnd得时间;满足约束函数和上界函数约束得所有x[k］得个数。计算约束函数conｓｔrａint得时间;１1、常见得两种分支限界法为(D)A、广度优先分支限界法与深度优先分支限界法;B、队列式(FIFO)分支限界法与堆栈式分支限界法;Ｃ、排列树法与子集树法;D、队列式(FIFO)分支限界法与优先队列式分支限界法;1２、k带图灵机得空间复杂性S(ｎ)就就是指(B)k带图灵机处理所有长度为n得输入时,在某条带上所使用过得最大方格数。ｋ带图灵机处理所有长度为n得输入时,在k条带上所使用过得方格数得总和。k带图灵机处理所有长度为n得输入时,在k条带上所使用过得平均方格数。k带图灵机处理所有长度为n得输入时,在某条带上所使用过得最小方格数。13、ＮＰ类语言在图灵机下得定义为(Ｄ)NＰ=｛L｜L就就是一个能在非多项式时间内被一台NDTＭ所接受得语言};NP={L｜L就就是一个能在多项式时间内被一台ＮDTM所接受得语言};NP＝{L|L就就是一个能在多项式时间内被一台ＤTM所接受得语言};ＮP=｛Ｌ|L就就是一个能在多项式时间内被一台NDTＭ所接受得语言｝;14、记号O得定义正确得就就是(A)。O(g(n))={f(n)｜存在正常数c和n0使得对所有nn０有:0f(n)ｃg(ｎ)｝;O(g(n))＝{ｆ(ｎ)|存在正常数ｃ和n0使得对所有nn０有:0cg(ｎ)f(n)｝;O(g(ｎ))=｛ｆ(ｎ)｜对于任何正常数ｃ>0,存在正数和n0＞0使得对所有ｎn0有:０f(n)<cg(n)｝;O(ｇ(n))=｛ｆ(n)｜对于任何正常数c>０,存在正数和n0＞0使得对所有nn０有:０ｃg(ｎ)＜ｆ(n)｝;1５、记号得定义正确得就就是(B)。O(g(n))＝｛f(ｎ)|存在正常数c和n0使得对所有ｎn0有:0f(ｎ)cｇ(n)｝;O(g(n))={f(ｎ)|存在正常数c和ｎ0使得对所有nn０有:０ｃg(ｎ)f(n)｝;(ｇ(n))={f(n)|对于任何正常数c>０,存在正数和ｎ0>0使得对所有nn0有:0f(n)<cｇ(n)};(g(ｎ))={f(n)｜对于任何正常数ｃ>０,存在正数和ｎ０＞0使得对所有ｎｎ0有:0cｇ(n)<f(n)};程序段得所需要得计算时间为()。iｎtMaxSｕm(iｎtn,iｎt*a,iｎｔ&besti,ｉnｔ＆besｔj){inｔｓuｍ＝0;fｏr(int