算法分析与设计习题集答案(共32页).doc

精选优质文档-倾情为你奉上算法分析与设计习题集基础篇1、 算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算（书上定义）特征：输入、输出、有穷性、明确性、有效性区别：算法是完成特定任务的有限指令集。程序是用计算机语言编写的写成特定任务的指令序列。2、 算法的时间复杂度指的是什么？如何表示？的时间复杂度是一个，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的的长度的函数。时间复杂度常用表述，不包括这个函数的低阶项和首项系数。（百度百科）3、 算法的空间复杂度指的是什么？如何表示？一个的是指运行完一个程序所需内存的大小。利用的，可以对程序的运行所需要的内存多少有个预先估计。一个执行时除了需要和存储本身所使用的指令、常数、和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。执行时所需包括以下两部分。（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（、简单）等所占的空间。这部分属于静态空间。（2）可变空间，这部分空间的主要包括动态分配的空间，以及栈所需的空间等。这部分的空间大小与有关。一个所需的用f(n)表示。S(n)=O(f(n)其中n为问题的规模，S(n)表示。4、 什么是最坏时间复杂性？什么是最好时间复杂性？答：最坏情况时间复杂性：最好情况时间复杂性：I*是DN中使T(N, I*)达到Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率5、 什么是递归算法？什么是递归函数？递归算法（包括直接递归和间接递归子程序）都是通过自己调用自己，将求解问题转化成性质相同的子问题，最终达到求解的的。递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对相关且必要的信息的保存与恢复，从而省略了求解过程中的许多细节的描述。【课本】直接递归 子程序在运行完成前调用它们自己。间接递归 子程序在运行过程中调用其它子程序，其他子程序反过来调用这个调用子程序。递归函数，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。网上：答：（1）递归算法:直接或间接地调用自身的算法；（2）递归函数:用函数自身给出递归定义的函数。6、 分治法的设计思想是什么？将整个问题分成若干个小问题后分而治之给定一个有n个输入的函数，分治策略建议将输入分为k个不同的子集，1<kn，从而产生k个子问题。当输入规模n取值较大时，可以将这n个输入分成k（1<kn）个不同子集合的情况下，得到k个不同的可独立求解的子问题，求出这些子问题的解之后，再用适当的方法把它们合并成整个问题的解。这就是分治法。如果子问题仍然较大，可以再次使用分治策略。更精确地说，分治策略将输入划分为与原问题同类型的k个子问题。许多时候，k=2。7、 动态规划基本步骤是什么？答：（1）找出最优解的性质，并刻划其结构特征; （2）递归地定义最优值;（3）以自底向上的方式计算出最优值;(4)根据计算最优值时得到的信息，构造最优解。8、 回溯法与分枝限界法之间的相同点是什么？不同之处在哪些方面？答：同：他们同是在问题的解空间树上搜索问题解的算法； 异：（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解； （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 9、 分枝限界法的基本思想是什么？答：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。10、 限界函数的功能是什么？答：用限界函数剪去得不到最优解的子树11、 设某一函数定义如下：编写一个递归函数计算给定x的M（x）的值。本函数是一个递归函数，其递归出口是：M（x）= x-10x>100递归体是：M（M（x+11）x 100实现本题功能的递归函数如下：intm ( intx ) int y;if ( x>100 )return(x-10 );else y =m(x+11) ;return (m (y );procedure M(x) if x>100 then return(x-10) else return M(M(x+11) endifend M12、 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下：voiddel ( seqlist*a )inti=0, j;while ( i<a->length)if ( a->datai!= a->datai+1)i+;else for ( j=i; j<a->length; j+)a->dataj=a->dataj+1;a->length-;procedure del(A,LINK,n)/A(1:n)是元素按元素值非递减有序排列的顺序表，LINK(1:n)每个数的下一个数所在的下标，等于0时表示后面再没有数了，初始时为2，3，4n,0 global integer A(1:n),LINK(1:n) integer i,j; i1; while LINK(i)>0 do jLINK(i) while j<n and A(i)=A(j) do/查找是否为相同的数 jLINK(j); repeat LINK(i)j;/将i的LINK指向j，忽略中间相同的数 ij; repeatend del13、 分别写出求二叉树结点总数及叶子总数的算法。计算结点总数int CountNode(BinTree *root) int num1,num2; if(root=Null) return(0); else if(root->lchild=Null&&rooot->rchild=Null) return(1); else num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); procedure COUNTNODE(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD integer num1,num2; if T!=0 then if LCHILD(T)=0 and RCHILD(T)=0 then/既没有左孩子，也没有右孩子，则为叶子节点 return(1); else num1=COUNTNODE(LCHILD(T); num2=COUNTNODE(RCHILD(T); return(num1+num2+1);/将左右子树的结点数加起来，再加本身，相当时树的后序遍历 endfi endif return(0);end COUNTNODE 计算叶子总数int CountLeafs(BinTree *root) int num1,num2; if(root=Null) return(0); else if(root->lchild=Null&&root->rchild=Null) return(1); else num1=CountLeafs(root->lchild);num2=CountLeafs(root->rchild);return(num1+num2); procedure COUNTLEAFS(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD integer num1,num2; if T!=0 then if LCHILD(T)=0 and RCHILD(T)=0 then/既没有左孩子，也没有右孩子，则为叶子节点 return(1); else num1=COUNTLEAFS(LCHILD(T); num2=COUNTLEAFS(RCHILD(T); return(num1+num2);/将左右子树的结点数加起来，再加本身，相当时树的后序遍历 endfi endif return(0);/T为空时，没有结点end COUNTLEAFS分治术14、 有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。procedure SELECKP(p,q)/A是一个全程数组，分别表示n个硬币的重量，在本题中表示15个硬币；p和q表示假币所在的一组硬币的起始和终止编号；最后返回硬币的编号；在主程序中调用SELECKP(1,15) if p=q then return(p); endif; global ingeger A(p:q);integer a,b,c,d,m; ap;/第一组数的起始编号 dq;/第二组硬币的终止编号 m0;/最多余的一个硬币所在的编号 if(ISODD(q-p+1)/如果该组硬币数量为d奇数 then mq;/最后一个数不作比较 dd-1; edif c(a+d+1)/2;/第二组硬币的起始编号编号 bb-1;/第一组硬币的终止编号 /将该组硬币分为平均分为两组，然后用天平比较两组重量，将轻的一组递归调用本方法 If WEIGHT(a,b)<WEIGHT(c,d) then return(SELECKP(a,b); else if WEIGHT(a,b)>WEIGHT(c,d) then return(SELECKP(c,d); else if m!=0/若两组硬币重量相等，则剩下一个为假币 return(m); else /如果两组硬币重量相等，且没有不比较的硬币，即本次检查的硬币总数为偶数，表示没有硬币 print("没有假币"); return(0); endifend SELECKP15、 利用分治策略，在n个不同元素中找出第k个最小元素。procedure SELECT(A,n,k) /在数组A(1),A(n)中找出第k小元素s并把它放在位置k，假设1<=k<=n。将剩下的元素按如下方式重新排列，使A(k)=t,有A(m)<=t，有A(m)<=t;对于k<m<=n,有A(m)>=t.A(n+1)=+/ integer n,k,m,r,j; m1rn+1;A(n+1)+; loop /每当进入这一循环时，1<=m<=r<=n+1/ jr/将剩下的元素的最大下标加1后置给j/ call PARTITION(m,j) /返回j，它使得A(j)，它使得A(j)是第j小的值 case :k=j:return /找到该元素该元素为A(j) :k<j:rj /j是新的上界,k在m与j之间 :else:mj+1 /j+1是新的下界，k在j+1与m之间 endcase repeatend SELECT procedure PARTITION(m,p) integer m,p,i;global A(m:p-1); vA(m);im;/A(m)是划分元素/ loop loop ii+1 until A(i)>=v repeat /i由左向右移 loop pp-1 until A(p)<=v repeat /p由左向右移 if i<p-1 then call A(i)A(p) /A(i)和A(p)换位 else exit endif repeat A(m)A(p);A(p)v /划分元素在位置p/end PARTITION16、 设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。（1）每个选手必须与其它n-1选手各赛一次；（2）每个选手一天只能赛一次。procedure TOURNAMENT(n)/A(1:n,1:n)为全程数组，A(i,j)表示第i天第j个队所比赛的对手,若轮空则为0 globel integer A(1:n,1:n) if n=1 then A(1,1)=1; return; endif if ISODD(n) then/当队数为奇数时，增加一个虚拟队员 TOURNAMENT(n+1); return; endif TOURNAMENT(n/2);/是偶数时，递归调用，返回时合并 call MAKECOPY(n);/主要是将左上角的递归计算出的小块中的所有数字按照其相对位置抄写到右下角，将左上角小块中的所有数字加n/2后按照其相对位置抄写到左下角，将左下角小块中的所有数字按照相对位置抄到右上角。end COUNTLEAFS 17、 已知序列503，87，512，61，908，170，897，275，652，462，写一个自底向上的归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。void Merge(ElemType *r，ElemType *rf，int u，int v，int t)for(i=u，j=v，k=u；i<v&&j<=t；k+)if(ri.key<rj.key)rfk=ri；i+；elserfk=rj；j+；if(i<v) rfkt=riv-1；if(j<=t) rfkt=rjt；void MergeSort(S_TBL *p，ElemType *rf)/*对*p表归并排序，*rf为与*p表等长的辅助数组*/ElemType *q1，*q2；q1=rf；q2=p->elem；for(len=1；len<p->length；len=2*len) /*从q2归并到q1*/for(i=1；i+2*len-1<=p->length；i=i+2*len)Merge(q2，q1，i，i+len，i+2*len-1)； /*对等长的两个子表合并*/if(i+len-1<p->length)Merge(q2，q1，i，i+len，p->length)； /*对不等长的两个子表合并*/elseif(i<=p->length)while(i<=p->length) /*若还剩下一个子表，则直接传入*/q1i=q2i；q1<->q2； /*交换，以保证下一趟归并时，仍从q2归并到q1*/if(q1!=p->elem) /*若最终结果不在*p表中，则传入之*/for(i=1；i<=p->length；i+)p->elemi=q1i；Procedure MERGESORT(low, high)/A(low : high)是一个全程数组，它含有high-low+10个待分类的元素/ Integer low, high; If low < high then mid int(low+high)/2) /求这个集合的分割点/ call MERGESORT(low, mid) /将一个子集合分类/ call MERGESORT(mid+1, high)/将另一个子集合分类/ cal MERGE(low,mid,high) /归并两个已分类的子集合/ EndifendMERGESORTProcedure MERGE(low, mid, high)/A(low : high)是一个全程数组，它含有两个放在A（low : mid）和A（mid+1 : high）中的已分类的子集合。目标是将这两个已分类的集合归并成一个集合，并存放到A(low : high)中/使用一个辅助数组B(low : high)/ Integer h, I, j, k, low, mid, high; /lowmid<high/ Global A(low : high); local B(low : high) h low;/A中第一队列的队头 ilow; /第三队列，即B的队头 jmid+1;/A中第二队列的队头 while hmid and jhigh do /当两个集合都没有取尽时/ if A(h)A(j) then B(i) A(h); hh+1 else B(i) A(j); jj+1 endif ii+1 repeat if h>mid then/处理剩余的元素/ for kj to high do /第二队列未处理完 B(i) A(k);ii+1 repeat Else for kh to mid do/第一队列未处理完 B(i) A(k); ii+1 repeat endif for k low to high do /将已归并的集合复制到A/ A(k) B(k) repeatendMERGE归并过程（黄色底纹的是每次归并的数）1234567891005038751261908170897275652462187503512619081708972756524622875035126190817089727565246238750351261908170897275652462461875035129081708972756524625618750351290817089727565246266187503512908170275897652462761875035129081702758974626528618750351290817027546265289796187170275462503512652897908贪心法18、 设有n个文件f1，f2，fn要求存放在一个磁盘上，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1，p2，pn，且=1。磁头从当前磁道移到被检索信息磁道所需的时间可用这两个磁道之间的径向距离来度量。如果文件fi存放在第i道上，1in则检索这n个文件的期望时间是。其中d(i，j)是第i道与第j道之间的径向距离。磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间达到最小。试设计一个解此问题的算法，并分析算法的正确性与计算复杂性。/*磁盘文件最优存储问题具有贪心选择性质：先将n个文件从大到小按概率进行排序。假设排序后有p1>=p2>=>=pn。贪心选择性质表示每次所选择加入的对象文件，都能得到当前的最优值，即使得期望检索时间达到最小。在磁盘最优存储问题中，要想使期望检索时间达到最小。那么就要使两个概率较大者的径向距离越小越好。因此第一次从p1>=p2>=>=pn中选取P1所对应的文件f1置于中心磁道上。随后从剩余概率队列中选取概率最大和次最大者所对应的文件放在靠着f1的左磁道，和f1的右磁道。这将得到初始的最优值。同样地，继续选择剩余概率队列中概率最大和次最大者所对应的文件分别置于靠着刚才所得最优位置的左磁道和右磁道上，将得到新的最优值。所以磁盘最优存储问题具有贪心选择性质。 最优子结构性质：按照这n个文件的排序概率(p1>=p2>=>=pn)假设排序后的理想最优序列为： f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（n为奇数）。若n为偶数个，则补上一个数0。那么不管n为奇数或者是偶数，其理想最优序列都可以表示为f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（因为加上一个0，对其达到最小期望检索时间无影响，所以可以进行此处理。） 利用反证法思想假设存在一个 f（n-1）,f(n-3),f(n-5),f(j)f4,f2,f1,f3,f5,f(i)f(n-2),fn。该序列是原序列对调f(i)与f(j)的位置所得。该序列所得到的期望检索时间小于上面的贪心策略时间。经验证发现，该序列所获得的期望检索时间>原所获得的期望检索时间。与最优值相矛盾。故贪心解为最优解。*/procedure GreedySearch(P,A,n) /P(1:n)是按照P(i)>=P(i+1)排序的n个文件读取的概率；A(1:n)表示对应的文件序号；X(1:n)表示n个文件分别所放的在磁盘上的存储位置，即所要求的解 integer P(1:n),A(1:n); integer i,k, n; kn/2; /取中间位置,除法为向下取整/ X(k)A(1); /中间位置放概率最大的文件/ for i2 to n by +2 do X(k+i/2)A(i); repeat for i3 to n by +2 do X(k-i/2)A(i); repeatend GreedySearch19、 设有n个正整数，编写一个算法将他们连接成一排，组成一个最大的多位整数。用贪心法求解本题。procedure MAXINT(A,n)/A(1:n)是由n个整数组成的数组，S(1:n)是将A中每个数转化为字符串得到的数组 integer A(1:,i,j,a,b; string B(1:n),s for i1 to n-1 do for i1 to n do aSTRINT(B(i),B(j); bSTRINT(B(j),B(i); for a<b then call INTERCHANGE(B(i),B(j);/将字符串拼接再转化为字符串 endif repeat repeat for i1 to n do/将B按顺序拼接起来主为最大的整数 ss+B(i)end SORTTN20、 键盘输入一个高精度的正整数N（此整数中没有0），去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小（输出应包括所去掉的数字的位置和组成的新的正整数，N不超过240位）。/*最优解是删除出现的第一个左边>右边的数，因为删除之后高位减小，很容易想.那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解.*/procedure GreedyDelet(N,S,X)/N表示高精度的正整数（此整数中没有0），要去掉S个整数，X(1:s)表示删除数字的位置 real X(1:s) char* ntN;/把整数转化为字符串处理 integer sS; while s>0 do i=0;/从串首开始 while i<length(nt) and ni<ni+1 do i+; repeat delet(nt,i);/删除串n的第i个字符 s-; X(S-s)i; repeat print(X);/输出每次删除的位置 print(nt);/输出最后组成的新的整数end GreedyDelet21、 对于下图给出的有向网，写出用Dijkstra方法求从顶点A到图中其它顶点的最短路径的算法，并写出执行算法过程中顶点的求解次序及从顶点A到各顶点路径的长度。procedure SHORTEST-PATHS(v,COST,DIST,n) /G是一个n结点的有向图，它由其成本邻接矩阵COST(n,n)表示DIST(j)被置以结点v到结点j的最短路径长度，这里1<=j<=n; DIST(v)被为0 boolean S(1:n);real COST(1:n,1:n),DIST(1:n) integer u,v,n,num,i,w for i1 to n do /将集合S初始化为空 S(i)0; DIST(j)COST(v,j); repeat S(v)1; /将结点v计入集合S DIST(v)0; for num2 to n-1 do /确定由结点v出发的n-1条路 选取结点u，它使得在S(w)=0 的条件下，DIST(u)=minDIST(w) S(u) 1;/结点计入S for 所有S(w)=0 的结点w do DIST(w)min(DIST(w),DIST(u)+COST(u,w) repeat repeatend SHORTEST-PATHSABCDEFGA048+1528+40B+012+C+043+13+D+0183323E+33+0+F+9+0+G+200执行踪迹迭代选取的结点SSABCDEFG置初值-A048+1528+401DA,D048+152848382EA,D,E04861152848383GA,D,E,G04861152848384BA,D,E,G,B04860152848385FA,D,E,G,B,F048571528483822、 对于上图给出的有向图，写出最小成本生成树，给出求解算法。ACFBEDG91220181523Line procedure KRUSKAL(E,COST,n, T, mincost)/G有n个结点，E是G的边集，COST（u, v）是边（u, v）的成本。T是最小成本生成树的边集，mincost是它的成本。/ 1 real mincost, COST(1: n, 1: n) 2 integer PARENT(1:n), T(1:n-1, 2), n 3 以边成本为元素构造一个min-堆 4 PARENT -1 5 imincost0 6 while i<n-1 and 堆非空 do 7 从堆中删去最小成本边(u, v)并重新构造堆 8 jFIND(u); kFIND(v) 9 if jk then ii+1 10 T(i, 1)u; T(I,2)v 11 mincostmincost+COST(u, v) 12 call UNION(j, k) 13 endif 14 repeat 15 if in-1 then print(no spanning tree) endif 16 return 17 end KRUSKAL动态规划23、 求出上图中每对结点间的最短距离的算法，并给出计算结果。line procedure ALL-PATHS(COST, A, n) integer i, j, k, n; real COST(n, n), A(n, n)1 for i1 to n do 2 for j1 to n do3 A(i,j) COST(i,j)4 repeat5 repeat6 for k1 to n do7 for i1 to n do8 for j1 to n do 9 A (i,j) minA(i,j), A(i,k)+A(k,j)10 repeat11 repeat12 repeat13 end ALL-PATHSABCDEFGA0485715284838B01255732578C043611366D420183323E337604699F95270075G29729020024、 下图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?line procedure FGRAPH(E, k, n, P)/多段图的向前处理算法,输入是按照段的给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边(i,j)的成本。P(1:k)是最小成本路径/1 real COST(n), integer D(n-1),P(k), r, j, k, n2 COST(n)03 for jn-1 to 1 by -1 do 4 设r是一个这样的结点，<j, r>E且使c(j, r)+COST(r)取最小值。5 COST（j）c(j, r)+COST(r)6 D(j) r7 repeat/找一条最小成本路径8 P(1) 1;P(k) n9 for j2 to k-1 do/找路径上的第j个结点10 P(j) D(P(j-1)11 repeat12 end FGRAPH最短路程:1371011(13)25、 已知序列a1，a2，an，试设计一算法，从中找出一子序列 ai1 < ai2 < < aik使k达到最大，并讨论其复杂性。算法一：pro