数据结构习题课

.,数据结构习题第1章,吉林大学计算机科学与技术学院谷方明,.,感谢二班、三班的学委把作业按学号排序。这是一种积极的习惯。,.,课堂练习,求下述计算f=1！+2！+3！+n！的算法的时间复杂性voidfactorsum(intn)inti,j；intf,w；f=0；for(i=1;i0等等,.,作业15,题目描述试用ADL语言编写一个算法，判断任一整数n是否为素数,.,考察知识点,用ADL描述算法特殊情况判断初始化核心处理步骤后处理算法的正确性证明很难，但验证较容易。用边界条件和特殊数据验证，人工模拟算法执行。分析算法的效率,.,参考答案1,算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1n1？IF(n1)THEN(flagfalse.RETURN.)S2初始化i2.flagtrue.S3求余判断WHILE(in-1)DO(IF(nMODi)=0THEN(flagfalse.RETURN.)ii+1.),.,参考答案2,算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1n1？IF(n1)THEN(flagfalse.RETURN.)S2初始化i2.flagtrue.S3求余判断WHILE(inDIV2)DO(IF(nMODi)=0THEN(flagfalse.RETURN.)ii+1.),.,参考答案3,算法S(n.flag)/*判断整数n是否为素数，将结果保存到变量flag*/S1n1？IF(n1)THEN(flagfalse.RETURN.)S2初始化i2.flagtrue.S3求余判断WHILE(in1/2)DO(IF(nMODi)=0THEN(flagfalse.RETURN.)ii+1.),.,作业情况,正确率不到50%有问题的做法特殊情况没有处理：1和2.不理解程序语句？For处理：IF(n%i=0)THENflag0.ELSEflag1.无返回值:RETURN.FORTODOIFDO,.,用ADL描述算法,输入输出参数的确定：临时变量不是参数符号“.”的应用分隔输入输出参数一条语句的结束；能判断语句结束的问题可略去符号“”的应用：标志算法结束混杂C+语言FORi=2TOn-1STEPi+DO步骤说明有且精,.,1-6,分析下面程序段的时间复杂性ints=0,i,j,k;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;kj;k+)s+;,.,参考答案,以s+为基本运算对每个i，分析(j,k)两重循环的次数j=0循环次数为0j=1循环次数为1j=i循环次数为i因此对每个i，(j,k)二重循环的次数为i*(i+1)/2总循环次数为sigma(i*(i+1)/2)i=0.nT(n)=n*(n+1)*(n+2)/6，算法的阶为O(n3),.,作业情况,正确率约60%有分析步骤直接给结果有问题的做法三重循环，所以O(n3)推导出错,.,1-9,将下列算法时间复杂性O(n),O(2n),O(log2n),O(nlog2n),O(n5),O(n2+1),O(n3-n2)按由低到高的顺序排列。其中，n是输入数据的规模。,.,参考答案,O(log2n)O(n)O(nlog2n)O(n2+1)O(n3-n2)O(n5)2,.,算法SM的改进算法BS算法BS（A,i,j.fmax,fmin）/*在数组A的第i至第j个元素间寻找最大和最小元素，已知ij;假定A中元素互异*/BS1.递归出口IFijTHEN(fmaxfminAi.RETURN.)IFij1THEN(IFAiAjTHEN(fmaxAj.fminAi).ELSE(fmaxAi.fminAj).RETURN).BS2.取中值mid(ij)/2BS3.递归调用BS(A,i,mid.gmax,gmin).BS(A,mid1,j.hmax,hmin).BS4.合并fmaxmaxgmax,hmax.fminmingmin,hmin.,.,考察知识点,数学归纳法证明归纳基础n=?时，*，命题成立。归纳假设步骤假设n=k是，有*，当n=k+1时，推出命题也成立用数学归纳法证明第一数学归纳法(假设n=k，往推n=k+1)第二数学归纳法(假设n=k，往推n=k+1，强数学归纳法)两者等价,.,本题的数学归纳法证明思路证明n=3时成立假设n=k时都成立,证明n=k+1时也成立思路可以不写出来,.,参考答案,n=3时，T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命题成立。假设n，即k所以有T()5*()/3-2,T()5*()/3-2成立,.(2)又知k+1=+,(3)由(1)(2)(3)，T(k+1)=T()+T()+2,5*/3-25*/3-2+2=5*(+)/3-2=5*(k+1)/3-2综上，命题得证。,.,作业情况,正确率约50%由3=n=k，往推n=2*k，n=2*k+1也正确分n=2*k，n=2*k+1讨论k+1=有问题的做法弱假设：设n=k时成立设n=k时成立，即T(k)=5*k/3-2利用(3*n/2-2)结论由(1)、(2)、(3)直接得到，不用数学归纳法经分析得，T(n)=logn往年：通过观察可知T(n+1)=T(n)+1?,.,1-12,给出算法BS的非递归算法，并说明算法最多需要多大的辅助空间。,.,算法BS(A,s,e.fmax,fmin)/*求数组A的s到e中的元素的最大最小值，用栈去递归，确保sfn)THENmifm.)t(l,r,ma,mi).),.,ELSE(mid(L+R)div2.p(mid+1,R,B).p(L,mid,R).)B3结果(s,e,e,fmax,fmin)t.,.,参考答案,