《算法分析与设计习题集答案》由会员分享，可在线阅读，更多相关《算法分析与设计习题集答案（32页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计习题集基础篇1、 算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算（书上定义）特征：输入、输出、有穷性、明确性、有效性区别：算法是完成特定任务的有限指令集。程序是用计算机语言编写的写成特定任务的指令序列。2、 算法的时间复杂度指的是什么？如何表示？算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。（百度百科）3、 算法的空间复杂度指的是什么？如何表示？一个程序的空间复杂度是指运行完一个程序所
2、需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)
3、其中n为问题的规模，S(n)表示空间复杂度。4、 什么是最坏时间复杂性？什么是最好时间复杂性？答：最坏情况时间复杂性：最好情况时间复杂性：I*是DN中使T(N, I*)达到Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率5、 什么是递归算法？什么是递归函数？递归算法（包括直接递归和间接递归子程序）都是通过自己调用自己，将求解问题转化成性质相同的子问题，最终达到求解的的。递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对相关且必要的信息的保存与恢复，从而省略了求解过程中的许多细节的描述。【课本】直接递归 子程序在运行完成前调用它们自己。间接递归 子程序在运行过程中调用
4、其它子程序，其他子程序反过来调用这个调用子程序。递归函数，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。网上：答：（1）递归算法:直接或间接地调用自身的算法；（2）递归函数:用函数自身给出递归定义的函数。6、 分治法的设计思想是什么？将整个问题分成若干个小问题后分而治之给定一个有n个输入的函数，分治策略建议将输入分为k个不同的子集，1kn，从而产生k个子问题。当输入规模n取值较大时，可以将这n个输入分成k（1100递归体是：M（M（x+11）x 100实现本题功能的递归函数如下：intm ( intx ) int y;if ( x100 )return
5、(x-10 );else y =m(x+11) ;return (m (y );procedure M(x) if x100 then return(x-10) else return M(M(x+11) endifend M12、 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下：voiddel ( seqlist*a )inti=0, j;while ( i
6、length)if ( a-datai!= a-datai+1)i+;else for ( j=i; jlength; 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 jlchild=Null&rooot-rchild=Nu
7、ll) 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=CO
8、UNTNODE(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);ret
9、urn(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 re
10、turn(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(c,d); else if m!=0/若两组硬币重量相等，则剩下一个为假币 retu
