2023年8月1日发(作者：)
《算法设计与分析》考试题⽬及答案解析《算法分析与设计》期末复习题⼀、选择题1.应⽤Johnson法则的流⽔作业调度采⽤的算法是（D）A. 贪⼼算法B. 分⽀限界法C.分治法D. 动态规划算法塔问题如下图所⽰。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔3. 动态规划算法的基本要素为（C）A. 最优⼦结构性质与贪⼼选择性质B．重叠⼦问题性质与贪⼼选择性质C．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤4. 算法分析中，记号O表⽰（B），记号Ω表⽰（A），记号Θ表⽰（D）。A.渐进下界B.渐进上界C.⾮紧上界D.紧渐进界E.⾮紧下界5. 以下关于渐进记号的性质是正确的有：（A）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ?=ΘB. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==?=C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})D. f(n)O(g(n))g(n)O(f(n))=?=6.能采⽤贪⼼算法求最优解的问题，⼀般具有的重要性质为：（A）A. 最优⼦结构性质与贪⼼选择性质B．重叠⼦问题性质与贪⼼选择性质C．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分⽀限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。A.B.C.D.10. 回溯法的效率不依赖于以下哪⼀个因素？（C ）A.产⽣x[k]的时间；B.满⾜显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满⾜约束函数和上界函数约束的所有x[k]的个数。F.计算约束函数constraint的时间；11. 常见的两种分⽀限界法为（D）A. ⼴度优先分⽀限界法与深度优先分⽀限界法；B. 队列式（FIFO）分⽀限界法与堆栈式分⽀限界法；C. 排列树法与⼦集树法；D. 队列式（FIFO）分⽀限界法与优先队列式分⽀限界法；12. k带图灵机的空间复杂性S(n)是指（B）A.k带图灵机处理所有长度为n的输⼊时，在某条带上所使⽤过的最⼤⽅格数。B.k带图灵机处理所有长度为n的输⼊时，在k条带上所使⽤过的⽅格数的总和。C.k带图灵机处理所有长度为n的输⼊时，在k条带上所使⽤过的平均⽅格数。D.k带图灵机处理所有长度为n的输⼊时，在某条带上所使⽤过的最⼩⽅格数。13. N P类语⾔在图灵机下的定义为（D）={L|L是⼀个能在⾮多项式时间内被⼀台NDTM所接受的语⾔}；={L|L是⼀个能在多项式时间内被⼀台NDTM所接受的语⾔}；={L|L是⼀个能在多项式时间内被⼀台DTM所接受的语⾔}；={L|L是⼀个能在多项式时间内被⼀台NDTM所接受的语⾔}；14. 记号O的定义正确的是（A）。A.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤cg(n) }；B.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；>0使得对所有n≥n0 C.O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n有：0 ≤f(n)>0使得对所有D.O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和nn≥n0有：0 ≤cg(n) < f(n) }；15. 记号Ω的定义正确的是（B）。A.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤cg(n) }；B.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；C.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n>0使得对所有n≥n0有：0 ≤f(n)D.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0>0使得对所有n≥n0有：0 ≤cg(n) < f(n) }；⼆、填空题1.下⾯程序段的所需要的计算时间为（2O(n)）。Array2.有11个待安排的活动，它们具有下表所⽰的开始时间与结束时间，如果以贪⼼算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最⼤的相容活动⼦集合），得到的最⼤相容活动⼦集合为活动（ {1，4，8，11} ）。3. 所谓贪⼼选择性质是指（所求问题的整体最优解可以通过⼀系列局部最优的选择，即贪⼼选择来达到）。4. 所谓最优⼦结构性质是指（问题的最优解包含了其⼦问题的最优解）。5. 回溯法是指（具有限界函数的深度优先⽣成法）。6. ⽤回溯法解题的⼀个显著特征是在搜索过程中动态产⽣问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。7. 回溯法的算法框架按照问题的解空间⼀般分为（⼦集树）算法框架与（排列树）算法框架。8. ⽤回溯法解0/1背包问题时，该问题的解空间结构为（⼦集树）结构。 9.⽤回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。10.⽤回溯法解0/1背包问题时，计算结点的上界的函数如下所⽰，请在空格中填⼊合适的内容：87654f[i]12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i11. ⽤回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为n m 的⽅格阵列，扩展每个结点需O(1)的时间，L 为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。 12. ⽤回溯法解图的m 着⾊问题时，使⽤下⾯的函数OK 检查当前扩展结点的每⼀个⼉⼦所相应的颜⾊的可⽤性，则需耗时（渐进时间上限）（O （mn ））。13. 旅⾏售货员问题的解空间树是（排列树）。三、证明题1. ⼀个分治法将规模为n的问题分成k个规模为n／m的⼦问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个⼦问题以及⽤merge将k个⼦问题的解合并为原问题的解需⽤f(n)个单位时间。⽤T(n)表⽰该分治法解规模为|P|=n的问题所需的计算时间，则有：(1)1 ()(/)()1O nT nkT n m f n n==?+>通过迭代法求得T（n）的显式表达式为：log1log()(/)nmk j jmjT n n k f n m-==+∑试证明T（n）的显式表达式的正确性。2. 举反例证明0/1背包问题若使⽤的算法是按照p i/w i的⾮递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装⼊背包，则此⽅法不⼀定能得到最优解（此题说明0/1背包问题与背包问题的不同）。证明：举例如：p={7,4,4},w={3,2,2},c=4时，由于7/3最⼤，若按题⽬要求的⽅法，只能取第⼀个，收益是7。⽽此实例的最⼤的收益应该是8，取第2，3 个。3. 求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。证明：对于任意f1(n)∈O(f(n)) ，存在正常数c1和⾃然数n1，使得对所有n≥n1，有f1(n)≤c1f(n) 。类似地，对于任意g1(n) ∈O(g(n)) ，存在正常数c2和⾃然数n2，使得对所有n≥n2，有g1(n) ≤c2g(n) 。令c3=max{c1, c2}，n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。则对所有的n ≥n3，有f1(n) +g1(n) ≤c1f(n) + c2g(n)≤c3f(n) + c3g(n)= c3(f(n) + g(n))≤c32 max{f(n),g(n)}= 2c3h(n) = O(max{f(n),g(n)}) .4. 求证最优装载问题具有贪⼼选择性质。（最优装载问题：有⼀批集装箱要装上⼀艘载重量为c 的轮船。其中集装箱i 的重量为Wi 。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 设集装箱已依其重量从⼩到⼤排序，(x 1,x 2,…,x n )是最优装载问题的⼀个最优解。⼜设1min{|1}i i nk i x ≤≤== 。如果给定的最优装载问题有解，则有1k n ≤≤。）证明： 四、解答题1. 机器调度问题。问题描述：现在有n 件任务和⽆限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为s i ，完成时间为f i ，s i问题实例：若任务占⽤的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要⼏台机器？（提⽰：使⽤贪⼼算法）画出⼯作在对应的机器上的分配情况。2. 已知⾮齐次递归⽅程：f (n)bf (n 1)g(n)f (0)c =-+??=? ，其中，b 、c 是常数，g(n)是n 的某⼀个函数。则f(n)的⾮递归表达式为：nnn i i 1f (n)cb b g(i)-==+∑。现有Hanoi 塔问题的递归⽅程为：h(n)2h(n 1)1h(1)1=-+??=? ，求h(n)的⾮递归表达式。解：利⽤给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：n 1n 1n 1i i 1n 1n 22n h(n)cbb g(i)22 (22121)----=--=+=+++++=-∑3. 单源最短路径的求解。问题的描述：给定带权有向图（如下图所⽰）G =(V,E)，其中每条边的权是⾮负实数。另外，还给定V 中的⼀个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这⾥路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法：现采⽤Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填⼊下表中。43 2 1 100 30 maxint10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代4. 请写出⽤回溯法解装载问题的函数。装载问题：有⼀批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且121niiw c c=≤+∑。装载问题要求确定是否有⼀个合理的装载⽅案可将这n个集装箱装上这2艘轮船。如果有，找出⼀种装载⽅案。解：void backtrack (int i){// 搜索第i层结点if (i > n) // 到达叶结点更新最优解bestx,bestw;return;r -= w[i];if (cw + w[i] <= c) {// 搜索左⼦树x[i] = 1;cw += w[i];backtrack(i + 1);cw -= w[i]; }if (cw + r > bestw) {x[i] = 0; // 搜索右⼦树backtrack(i + 1); }r += w[i];}5. ⽤分⽀限界法解装载问题时，对算法进⾏了⼀些改进，下⾯的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采⽤这样的⽅式，算法在执⾏上有什么不同。解答：斜线标识的部分完成的功能为：提前更新bestw值；这样做可以尽早的进⾏对右⼦树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第⼀个叶结点时才更新bestw。因此在算法搜索到第⼀个叶⼦结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成⽴。也就是说，此时右⼦树测试不起作⽤。为了使上述右⼦树测试尽早⽣效，应提早更新bestw。⼜知算法最终找到的最优值是所求问题的⼦集树中所有可⾏结点相应重量的最⼤值。⽽结点所相应得重量仅在搜索进⼊左⼦树是增加，因此，可以在算法每⼀次进⼊左⼦树时更新bestw的值。7. 最长公共⼦序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共⼦序列。由最长公共⼦序列问题的最优⼦结构性质建⽴⼦问题最优值的递归关系。⽤c[i][j]记录序列Xi和Yj的最长公共⼦序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共⼦序列。故此时C[i][j]=0。其它情况下，由最优⼦结构性质可建⽴递归关系如下：00,0 [][][1][1]1,0;max{[][1],[1][]},0;i ji ji jc i j c i j i j x yc i j c i j i j x y===--+>=-->≠在程序中，b[i][j]记录C[i][j]的值是由哪⼀个⼦问题的解得到的。（2） 函数LCS 实现根据b 的内容打印出Xi 和Yj 的最长公共⼦序列。请填写程序中的空格，以使函数LCS 完成构造最长公共⼦序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。8.对下⾯的递归算法，写出调⽤f(4)的执⾏结果。⼀、填空题1.的⼀系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。2.算法的复杂性有_____________和___________之分，衡量⼀个算法好坏的标准是______________________。3.某⼀问题可⽤动态规划算法求解的显著特征是____________________________________。4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的⼀个最长公共⼦序列_____________________________。5.⽤回溯法解问题时，应明确定义问题的解空间，问题的解空间⾄少应包含___________。6.动态规划算法的基本思想是将待求解问题分解成若⼲____________，先求解___________，然后从这些____________的解得到原问题的解。7.以深度优先⽅式系统搜索问题解的算法称为_____________。8.0-1背包问题的回溯算法所需的计算时间为_____________,⽤动态规划算法所需的计算时间为____________。9.动态规划算法的两个基本要素是___________和___________。10.⼆分搜索算法是利⽤_______________实现的算法。⼆、综合题（50分）1.写出设计动态规划算法的主要步骤。2.流⽔作业调度问题的johnson算法的思想。3.若n=4，在机器M1和M2上加⼯作业i所需的时间分别为ai 和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度⽅案，并计算最优值。4.使⽤回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求⽤⼀棵完全⼆叉树表⽰其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。5.设S=｛X1，X2，···，Xn｝是严格递增的有序集，利⽤⼆叉树的结点来存储S中的元素，在表⽰S的⼆叉搜索树中搜索⼀个元素X，返回的结果有两种情形，（在⼆叉搜索树的内结点中找到X=Xi ，其概率为bi。（2）在⼆叉搜索树的叶结点中确定X∈（Xi ，Xi+1），其概率为ai。在表⽰S的⼆叉搜索树T中，设存储元素Xi的结点深度为Ci ；叶结点（Xi，Xi+1）的结点深度为di，则⼆叉搜索树T的平均路长p为多少？假设⼆叉搜索树T[i][j]=｛Xi ，Xi+1，···，Xj｝最优值为m[i][j]，1）W[i][j]= ai-1+bi+···+bj+aj，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？6.描述0-1背包问题。三、简答题（30分）1.流⽔作业调度中，已知有n个作业，机器M1和M2上加⼯作业i所需的时间分别为ai 和bi，请写出流⽔作业调度问题的johnson法则中对ai和bi的排序算法。（函数名可写为sort(s,n)）2.最优⼆叉搜索树问题的动态规划算法（设函数名binarysearchtree)）答案：⼀、填空1．确定性有穷性可⾏性 0个或多个输⼊⼀个或多个输出2.时间复杂性空间复杂性时间复杂度⾼低3. 该问题具有最优⼦结构性质4.{BABCD}或{CABCD}或{CADCD｝5.⼀个（最优）解6.⼦问题⼦问题⼦问题7.回溯法8. o(n*2n) o(min{nc,2n})9.最优⼦结构重叠⼦问题10.动态规划法 ⼆、综合题1.①问题具有最优⼦结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解；2. ①令N 1={i|a i =b i }；②将N 1中作业按a i 的⾮减序排序得到N 1’，将N 2中作业按b i 的⾮增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满⾜Johnson 法则的最优调度。3.步骤为：N1={1，3}，N2={2，4}；N 1’={1，3}， N 2’={4，2}； 最优值为：384.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为：该问题的最优值为：16 最优解为：（1，1，0） 5.⼆叉树T 的平均路长P=∑=+n i 1Ci)(1*bi +∑=nj 0dj *aj{m[i][j]=0 (i>j)6.已知⼀个背包的容量为C ，有n 件物品，物品i 的重量为W i ，价值为V i ，求应如何选择装⼊背包中的物品，使得装⼊背包中物品的总价值最⼤。 三、简答题 sort(flowjope s[],int n) {int i,k,j,l;for(i=1;i<=n-1;i++)//-----选择排序m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0){k=i;while(k<=n&&s[k].tag!=0) k++;，跳出if(k>n) break;//-----没有aielse{for(j=k+1;j<=n;j++)if(s[j].tag==0)if(s[k].a>s[j].a) k=j;swap(s[i].index,s[k].index);swap(s[i].tag,s[k].tag);}}的下标l=i;//-----记下当前第⼀个bifor(i=l;i<=n-1;i++){k=i;for(j=k+1;j<=n;j++)if(s[k].bswap(s[i].index,s[k].index); //-----只移动index和tagswap(s[i].tag,s[k].tag);}} binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) {int i,j,k,t,l;for(i=1;i<=n+1;i++){w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w[i][j];if(t{m[i][j]=t;s[i][j]=k;}}}}⼀、填空题（本题15分，每⼩题1分）1、算法就是⼀组有穷的，它们规定了解决某⼀特定类型问题的。2、在进⾏问题的计算复杂性分析之前，⾸先必须建⽴求解问题所⽤的计算模型。3个基本计算模型是、、。3、算法的复杂性是的度量，是评价算法优劣的重要依据。4、计算机的资源最重要的是和资源。因⽽，算法的复杂性有和之分。5、f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O( )6、贪⼼算法总是做出在当前看来的选择。也就是说贪⼼算法并不从整体最优考虑，它所做出的选择只是在某种意义上的。7、许多可以⽤贪⼼算法求解的问题⼀般具有2个重要的性质：性质和性质。⼆、简答题（本题25分，每⼩题5分）1、简单描述分治法的基本思想。2、简述动态规划⽅法所运⽤的最优化原理。3、何谓最优⼦结构性质？4、简单描述回溯法基本思想。5、何谓P、NP、NPC问题三、算法填空（本题20分，每⼩题5分）1、n后问题回溯算法(1)⽤⼆维数组A[N][N]存储皇后位置,若第i⾏第j列放有皇后,则A[i][j]为⾮0值,否则值为0。(2)分别⽤⼀维数组M[N]、L[2*N-1]、R[2*N-1]表⽰竖列、左斜线、右斜线是否放有棋⼦，有则值为1,否则值为0。for(j=0;jif( 1 ) /*安全检查*/{ A[i][j]=i+1; /*放皇后*/2 ；if(i==N-1) 输出结果；else 3 ；; /*试探下⼀⾏*/4 ； /*去皇后*/5 ；;}2、数塔问题。有形如下图所⽰的数塔，从顶部出发，在每⼀结点可以选择向左⾛或是向右⾛，⼀起⾛到底层，要求找出⼀条路径，使路径上的值最⼤。for(r=n-2;r>=0;r--) //⾃底向上递归计算for(c=0; 1 ;c++)if( t[r+1][c]>t[r+1][c+1]) 2 ；else 3 ；3、Hanoi算法Hanoi(n,a,b,c)if （n==1） 1 ；else{ 2 ；3 ；Hanoi(n-1,b, a, c);}4、Dijkstra算法求单源最短路径d[u]:s到u的距离 p[u]:记录前⼀节点信息Init-single-source(G,s)for each vertex v∈V[G]do { d[v]=∞; 1 }d[s]=0Relax(u,v,w)if d[v]>d[u]+w(u,v)then { d[v]=d[u]+w[u,v];2}dijkstra(G,w,s)1. Init-single-source(G,s)2. S=Φ3. Q=V[G]
2023年8月1日发(作者：)
《算法设计与分析》考试题⽬及答案解析《算法分析与设计》期末复习题⼀、选择题1.应⽤Johnson法则的流⽔作业调度采⽤的算法是（D）A. 贪⼼算法B. 分⽀限界法C.分治法D. 动态规划算法塔问题如下图所⽰。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔3. 动态规划算法的基本要素为（C）A. 最优⼦结构性质与贪⼼选择性质B．重叠⼦问题性质与贪⼼选择性质C．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤4. 算法分析中，记号O表⽰（B），记号Ω表⽰（A），记号Θ表⽰（D）。A.渐进下界B.渐进上界C.⾮紧上界D.紧渐进界E.⾮紧下界5. 以下关于渐进记号的性质是正确的有：（A）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ?=ΘB. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==?=C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})D. f(n)O(g(n))g(n)O(f(n))=?=6.能采⽤贪⼼算法求最优解的问题，⼀般具有的重要性质为：（A）A. 最优⼦结构性质与贪⼼选择性质B．重叠⼦问题性质与贪⼼选择性质C．最优⼦结构性质与重叠⼦问题性质D. 预排序与递归调⽤7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分⽀限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。A．⼴度优先B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。A.B.C.D.10. 回溯法的效率不依赖于以下哪⼀个因素？（C ）A.产⽣x[k]的时间；B.满⾜显约束的x[k]值的个数；C.问题的解空间的形式；D.计算上界函数bound的时间；E.满⾜约束函数和上界函数约束的所有x[k]的个数。F.计算约束函数constraint的时间；11. 常见的两种分⽀限界法为（D）A. ⼴度优先分⽀限界法与深度优先分⽀限界法；B. 队列式（FIFO）分⽀限界法与堆栈式分⽀限界法；C. 排列树法与⼦集树法；D. 队列式（FIFO）分⽀限界法与优先队列式分⽀限界法；12. k带图灵机的空间复杂性S(n)是指（B）A.k带图灵机处理所有长度为n的输⼊时，在某条带上所使⽤过的最⼤⽅格数。B.k带图灵机处理所有长度为n的输⼊时，在k条带上所使⽤过的⽅格数的总和。C.k带图灵机处理所有长度为n的输⼊时，在k条带上所使⽤过的平均⽅格数。D.k带图灵机处理所有长度为n的输⼊时，在某条带上所使⽤过的最⼩⽅格数。13. N P类语⾔在图灵机下的定义为（D）={L|L是⼀个能在⾮多项式时间内被⼀台NDTM所接受的语⾔}；={L|L是⼀个能在多项式时间内被⼀台NDTM所接受的语⾔}；={L|L是⼀个能在多项式时间内被⼀台DTM所接受的语⾔}；={L|L是⼀个能在多项式时间内被⼀台NDTM所接受的语⾔}；14. 记号O的定义正确的是（A）。A.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤cg(n) }；B.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；>0使得对所有n≥n0 C.O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n有：0 ≤f(n)>0使得对所有D.O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和nn≥n0有：0 ≤cg(n) < f(n) }；15. 记号Ω的定义正确的是（B）。A.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤cg(n) }；B.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；C.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n>0使得对所有n≥n0有：0 ≤f(n)D.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0>0使得对所有n≥n0有：0 ≤cg(n) < f(n) }；⼆、填空题1.下⾯程序段的所需要的计算时间为（2O(n)）。Array2.有11个待安排的活动，它们具有下表所⽰的开始时间与结束时间，如果以贪⼼算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最⼤的相容活动⼦集合），得到的最⼤相容活动⼦集合为活动（ {1，4，8，11} ）。3. 所谓贪⼼选择性质是指（所求问题的整体最优解可以通过⼀系列局部最优的选择，即贪⼼选择来达到）。4. 所谓最优⼦结构性质是指（问题的最优解包含了其⼦问题的最优解）。5. 回溯法是指（具有限界函数的深度优先⽣成法）。6. ⽤回溯法解题的⼀个显著特征是在搜索过程中动态产⽣问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。7. 回溯法的算法框架按照问题的解空间⼀般分为（⼦集树）算法框架与（排列树）算法框架。8. ⽤回溯法解0/1背包问题时，该问题的解空间结构为（⼦集树）结构。 9.⽤回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。10.⽤回溯法解0/1背包问题时，计算结点的上界的函数如下所⽰，请在空格中填⼊合适的内容：87654f[i]12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i11. ⽤回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为n m 的⽅格阵列，扩展每个结点需O(1)的时间，L 为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。 12. ⽤回溯法解图的m 着⾊问题时，使⽤下⾯的函数OK 检查当前扩展结点的每⼀个⼉⼦所相应的颜⾊的可⽤性，则需耗时（渐进时间上限）（O （mn ））。13. 旅⾏售货员问题的解空间树是（排列树）。三、证明题1. ⼀个分治法将规模为n的问题分成k个规模为n／m的⼦问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个⼦问题以及⽤merge将k个⼦问题的解合并为原问题的解需⽤f(n)个单位时间。⽤T(n)表⽰该分治法解规模为|P|=n的问题所需的计算时间，则有：(1)1 ()(/)()1O nT nkT n m f n n==?+>通过迭代法求得T（n）的显式表达式为：log1log()(/)nmk j jmjT n n k f n m-==+∑试证明T（n）的显式表达式的正确性。2. 举反例证明0/1背包问题若使⽤的算法是按照p i/w i的⾮递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装⼊背包，则此⽅法不⼀定能得到最优解（此题说明0/1背包问题与背包问题的不同）。证明：举例如：p={7,4,4},w={3,2,2},c=4时，由于7/3最⼤，若按题⽬要求的⽅法，只能取第⼀个，收益是7。⽽此实例的最⼤的收益应该是8，取第2，3 个。3. 求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。证明：对于任意f1(n)∈O(f(n)) ，存在正常数c1和⾃然数n1，使得对所有n≥n1，有f1(n)≤c1f(n) 。类似地，对于任意g1(n) ∈O(g(n)) ，存在正常数c2和⾃然数n2，使得对所有n≥n2，有g1(n) ≤c2g(n) 。令c3=max{c1, c2}，n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。则对所有的n ≥n3，有f1(n) +g1(n) ≤c1f(n) + c2g(n)≤c3f(n) + c3g(n)= c3(f(n) + g(n))≤c32 max{f(n),g(n)}= 2c3h(n) = O(max{f(n),g(n)}) .4. 求证最优装载问题具有贪⼼选择性质。（最优装载问题：有⼀批集装箱要装上⼀艘载重量为c 的轮船。其中集装箱i 的重量为Wi 。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 设集装箱已依其重量从⼩到⼤排序，(x 1,x 2,…,x n )是最优装载问题的⼀个最优解。⼜设1min{|1}i i nk i x ≤≤== 。如果给定的最优装载问题有解，则有1k n ≤≤。）证明： 四、解答题1. 机器调度问题。问题描述：现在有n 件任务和⽆限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为s i ，完成时间为f i ，s i问题实例：若任务占⽤的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要⼏台机器？（提⽰：使⽤贪⼼算法）画出⼯作在对应的机器上的分配情况。2. 已知⾮齐次递归⽅程：f (n)bf (n 1)g(n)f (0)c =-+??=? ，其中，b 、c 是常数，g(n)是n 的某⼀个函数。则f(n)的⾮递归表达式为：nnn i i 1f (n)cb b g(i)-==+∑。现有Hanoi 塔问题的递归⽅程为：h(n)2h(n 1)1h(1)1=-+??=? ，求h(n)的⾮递归表达式。解：利⽤给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：n 1n 1n 1i i 1n 1n 22n h(n)cbb g(i)22 (22121)----=--=+=+++++=-∑3. 单源最短路径的求解。问题的描述：给定带权有向图（如下图所⽰）G =(V,E)，其中每条边的权是⾮负实数。另外，还给定V 中的⼀个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这⾥路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法：现采⽤Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填⼊下表中。43 2 1 100 30 maxint10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代4. 请写出⽤回溯法解装载问题的函数。装载问题：有⼀批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且121niiw c c=≤+∑。装载问题要求确定是否有⼀个合理的装载⽅案可将这n个集装箱装上这2艘轮船。如果有，找出⼀种装载⽅案。解：void backtrack (int i){// 搜索第i层结点if (i > n) // 到达叶结点更新最优解bestx,bestw;return;r -= w[i];if (cw + w[i] <= c) {// 搜索左⼦树x[i] = 1;cw += w[i];backtrack(i + 1);cw -= w[i]; }if (cw + r > bestw) {x[i] = 0; // 搜索右⼦树backtrack(i + 1); }r += w[i];}5. ⽤分⽀限界法解装载问题时，对算法进⾏了⼀些改进，下⾯的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采⽤这样的⽅式，算法在执⾏上有什么不同。解答：斜线标识的部分完成的功能为：提前更新bestw值；这样做可以尽早的进⾏对右⼦树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第⼀个叶结点时才更新bestw。因此在算法搜索到第⼀个叶⼦结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成⽴。也就是说，此时右⼦树测试不起作⽤。为了使上述右⼦树测试尽早⽣效，应提早更新bestw。⼜知算法最终找到的最优值是所求问题的⼦集树中所有可⾏结点相应重量的最⼤值。⽽结点所相应得重量仅在搜索进⼊左⼦树是增加，因此，可以在算法每⼀次进⼊左⼦树时更新bestw的值。7. 最长公共⼦序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共⼦序列。由最长公共⼦序列问题的最优⼦结构性质建⽴⼦问题最优值的递归关系。⽤c[i][j]记录序列Xi和Yj的最长公共⼦序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共⼦序列。故此时C[i][j]=0。其它情况下，由最优⼦结构性质可建⽴递归关系如下：00,0 [][][1][1]1,0;max{[][1],[1][]},0;i ji ji jc i j c i j i j x yc i j c i j i j x y===--+>=-->≠在程序中，b[i][j]记录C[i][j]的值是由哪⼀个⼦问题的解得到的。（2） 函数LCS 实现根据b 的内容打印出Xi 和Yj 的最长公共⼦序列。请填写程序中的空格，以使函数LCS 完成构造最长公共⼦序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。8.对下⾯的递归算法，写出调⽤f(4)的执⾏结果。⼀、填空题1.的⼀系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。2.算法的复杂性有_____________和___________之分，衡量⼀个算法好坏的标准是______________________。3.某⼀问题可⽤动态规划算法求解的显著特征是____________________________________。4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的⼀个最长公共⼦序列_____________________________。5.⽤回溯法解问题时，应明确定义问题的解空间，问题的解空间⾄少应包含___________。6.动态规划算法的基本思想是将待求解问题分解成若⼲____________，先求解___________，然后从这些____________的解得到原问题的解。7.以深度优先⽅式系统搜索问题解的算法称为_____________。8.0-1背包问题的回溯算法所需的计算时间为_____________,⽤动态规划算法所需的计算时间为____________。9.动态规划算法的两个基本要素是___________和___________。10.⼆分搜索算法是利⽤_______________实现的算法。⼆、综合题（50分）1.写出设计动态规划算法的主要步骤。2.流⽔作业调度问题的johnson算法的思想。3.若n=4，在机器M1和M2上加⼯作业i所需的时间分别为ai 和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度⽅案，并计算最优值。4.使⽤回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求⽤⼀棵完全⼆叉树表⽰其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。5.设S=｛X1，X2，···，Xn｝是严格递增的有序集，利⽤⼆叉树的结点来存储S中的元素，在表⽰S的⼆叉搜索树中搜索⼀个元素X，返回的结果有两种情形，（在⼆叉搜索树的内结点中找到X=Xi ，其概率为bi。（2）在⼆叉搜索树的叶结点中确定X∈（Xi ，Xi+1），其概率为ai。在表⽰S的⼆叉搜索树T中，设存储元素Xi的结点深度为Ci ；叶结点（Xi，Xi+1）的结点深度为di，则⼆叉搜索树T的平均路长p为多少？假设⼆叉搜索树T[i][j]=｛Xi ，Xi+1，···，Xj｝最优值为m[i][j]，1）W[i][j]= ai-1+bi+···+bj+aj，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？6.描述0-1背包问题。三、简答题（30分）1.流⽔作业调度中，已知有n个作业，机器M1和M2上加⼯作业i所需的时间分别为ai 和bi，请写出流⽔作业调度问题的johnson法则中对ai和bi的排序算法。（函数名可写为sort(s,n)）2.最优⼆叉搜索树问题的动态规划算法（设函数名binarysearchtree)）答案：⼀、填空1．确定性有穷性可⾏性 0个或多个输⼊⼀个或多个输出2.时间复杂性空间复杂性时间复杂度⾼低3. 该问题具有最优⼦结构性质4.{BABCD}或{CABCD}或{CADCD｝5.⼀个（最优）解6.⼦问题⼦问题⼦问题7.回溯法8. o(n*2n) o(min{nc,2n})9.最优⼦结构重叠⼦问题10.动态规划法 ⼆、综合题1.①问题具有最优⼦结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解；2. ①令N 1={i|a i =b i }；②将N 1中作业按a i 的⾮减序排序得到N 1’，将N 2中作业按b i 的⾮增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满⾜Johnson 法则的最优调度。3.步骤为：N1={1，3}，N2={2，4}；N 1’={1，3}， N 2’={4，2}； 最优值为：384.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为：该问题的最优值为：16 最优解为：（1，1，0） 5.⼆叉树T 的平均路长P=∑=+n i 1Ci)(1*bi +∑=nj 0dj *aj{m[i][j]=0 (i>j)6.已知⼀个背包的容量为C ，有n 件物品，物品i 的重量为W i ，价值为V i ，求应如何选择装⼊背包中的物品，使得装⼊背包中物品的总价值最⼤。 三、简答题 sort(flowjope s[],int n) {int i,k,j,l;for(i=1;i<=n-1;i++)//-----选择排序m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0){k=i;while(k<=n&&s[k].tag!=0) k++;，跳出if(k>n) break;//-----没有aielse{for(j=k+1;j<=n;j++)if(s[j].tag==0)if(s[k].a>s[j].a) k=j;swap(s[i].index,s[k].index);swap(s[i].tag,s[k].tag);}}的下标l=i;//-----记下当前第⼀个bifor(i=l;i<=n-1;i++){k=i;for(j=k+1;j<=n;j++)if(s[k].bswap(s[i].index,s[k].index); //-----只移动index和tagswap(s[i].tag,s[k].tag);}} binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) {int i,j,k,t,l;for(i=1;i<=n+1;i++){w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w[i][j];if(t{m[i][j]=t;s[i][j]=k;}}}}⼀、填空题（本题15分，每⼩题1分）1、算法就是⼀组有穷的，它们规定了解决某⼀特定类型问题的。2、在进⾏问题的计算复杂性分析之前，⾸先必须建⽴求解问题所⽤的计算模型。3个基本计算模型是、、。3、算法的复杂性是的度量，是评价算法优劣的重要依据。4、计算机的资源最重要的是和资源。因⽽，算法的复杂性有和之分。5、f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O( )6、贪⼼算法总是做出在当前看来的选择。也就是说贪⼼算法并不从整体最优考虑，它所做出的选择只是在某种意义上的。7、许多可以⽤贪⼼算法求解的问题⼀般具有2个重要的性质：性质和性质。⼆、简答题（本题25分，每⼩题5分）1、简单描述分治法的基本思想。2、简述动态规划⽅法所运⽤的最优化原理。3、何谓最优⼦结构性质？4、简单描述回溯法基本思想。5、何谓P、NP、NPC问题三、算法填空（本题20分，每⼩题5分）1、n后问题回溯算法(1)⽤⼆维数组A[N][N]存储皇后位置,若第i⾏第j列放有皇后,则A[i][j]为⾮0值,否则值为0。(2)分别⽤⼀维数组M[N]、L[2*N-1]、R[2*N-1]表⽰竖列、左斜线、右斜线是否放有棋⼦，有则值为1,否则值为0。for(j=0;jif( 1 ) /*安全检查*/{ A[i][j]=i+1; /*放皇后*/2 ；if(i==N-1) 输出结果；else 3 ；; /*试探下⼀⾏*/4 ； /*去皇后*/5 ；;}2、数塔问题。有形如下图所⽰的数塔，从顶部出发，在每⼀结点可以选择向左⾛或是向右⾛，⼀起⾛到底层，要求找出⼀条路径，使路径上的值最⼤。for(r=n-2;r>=0;r--) //⾃底向上递归计算for(c=0; 1 ;c++)if( t[r+1][c]>t[r+1][c+1]) 2 ；else 3 ；3、Hanoi算法Hanoi(n,a,b,c)if （n==1） 1 ；else{ 2 ；3 ；Hanoi(n-1,b, a, c);}4、Dijkstra算法求单源最短路径d[u]:s到u的距离 p[u]:记录前⼀节点信息Init-single-source(G,s)for each vertex v∈V[G]do { d[v]=∞; 1 }d[s]=0Relax(u,v,w)if d[v]>d[u]+w(u,v)then { d[v]=d[u]+w[u,v];2}dijkstra(G,w,s)1. Init-single-source(G,s)2. S=Φ3. Q=V[G]
发布评论