数据结构习题课-课件

数据结构习题数据结构习题 第第 1 章章l感谢二班、三班的学委把作业按学号排序。这是一种积极的习惯。课堂练习课堂练习求下述计算f=1！+2！+3！+n！的算法的时间复杂性void factorsum(int n)int i,j int i,j；int f,wint f,w；f=0f=0；for(i=1;i=n;i+)for(i=1;i=n;i+)w=1 w=1；for(j=1;j=i;j+)for(j=1;j=i;j+)w=w*j;w=w*j;f=f+w;f=f+w;return return；参考答案参考答案l以乘法为基本运算l最坏时间复杂度为T(n)=n(n+1)/2，l渐近表示法O(n2)（或算法是n2 阶的）1-21-2l设数据的逻辑结构为L=(N,R)，其中，lN=a,b,c,d,elR=r,lr=,l请画出对应的逻辑结构，说明是何种结构l图型结构：a有多个后继，e有多个前驱参考答案参考答案aedbc作业情况作业情况l正确率：超过80%l用圆圈表示结点，用直线箭头表示边l结点名一般写在圆圈内l有问题的画法l无向边l边共用线l交叉：尽量避免作业作业1 14 4l题目描述：【3】【10分钟】用反证法证明 是无理数。参考答案参考答案l假设 不是无理数，那么 一定是有理数，即存在p、q，使得 =p/q，p、q互质。整理得p2=2*q2，因此p是偶数。设p=2*k，则有q2=2*k2，因此q也是偶数。这与p、q互质矛盾。l因此 是无理数。其它做法其它做法l有一种证法：p、q互质得到p2、q2互质。由p2=2*q2，可得p2、q2有公约数q2。（需要说明q不是1）l唯一分解定理：2班李百林l三种证法的同学：3班徐文峰（几何法）。作业情况作业情况l正确率70%左右l有问题的说法l因为 不是有理数或找不到分数、循环小数表示l因为 是无理数？l（p,q）=2：改成p、q有公约数2l表示成p/q，p、q互为质数，q1或q0等等作业作业1 15 5l题目描述 试用ADL语言编写一个算法，判断任一整数 n 是否为素数考察知识点考察知识点l用ADL描述算法l特殊情况判断l初始化l核心处理步骤l后处理l算法的正确性l证明很难，但验证较容易。用边界条件和特殊数据验证，人工模拟算法执行。l分析算法的效率参考答案参考答案1 1算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果保存到变量flag*/S1n1 1？IF(n1 1)THEN(flagfalse.RETURN.)S2初始化初始化 i2.flagtrue.S3求余判断求余判断 WHILE(in-1)DO (IF(n MOD i)=0 THEN (flagfalse.RETURN.)ii+1.)参考答案参考答案2 2算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果保存到变量flag*/S1n1 1？IF(n1 1)THEN(flagfalse.RETURN.)S2初始化初始化 i2.flagtrue.S3求余判断求余判断 WHILE(i n DIV 2 )DO (IF(n MOD i)=0 THEN (flagfalse.RETURN.)ii+1.)参考答案参考答案3 3算法算法 S(n.flag)/*判断整数判断整数n是否为素数，将结果保存到变量是否为素数，将结果保存到变量flag*/S1n1 1？IF(n1 1)THEN(flagfalse.RETURN.)S2初始化初始化 i2.flagtruetrue.S3求余判断求余判断 WHILE(i n 1/2 )DO (IF(n MOD i)=0 THEN (flagfalse.RETURN.)ii+1.)作业情况作业情况l正确率不到50%l有问题的做法l特殊情况没有处理：1和2.l不理解程序语句？lFor处理：IF(n%i=0)THEN flag 0.ELSE 0.ELSE flag 1.1.l无返回值:RETURN.lFOR TO i DOlIF DO用用ADLADL描述算法描述算法l输入输出参数的确定：临时变量不是参数l符号“.”的应用l分隔输入输出参数l一条语句的结束；能判断语句结束的问题可略去l符号“”的应用：标志算法结束l混杂C+语言lFOR i=2 TO n-1 STEP i+DO l步骤说明有且精1-61-6l分析下面程序段的时间复杂性int s=0,i,j,k;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;kj;k+)s+;参考答案参考答案l以s+为基本运算l对每个i，分析(j,k)两重循环的次数lj=0 循环次数为 0lj=1 循环次数为 1llj=i 循环次数为 il因此对每个i，(j,k)二重循环的次数为i*(i+1)/2l总循环次数为sigma(i*(i+1)/2)i=0.nlT(n)=n*(n+1)*(n+2)/6，算法的阶为O(n3)作业情况作业情况l正确率约60%l有分析步骤l直接给结果l有问题的做法l三重循环，所以O(n3)l推导出错1-91-9l将下列算法时间复杂性O(n),O(2n),O(log2n),O(nlog2n),O(n5),O(n2+1),O(n3-n2)按由低到高的顺序排列。其中，n是输入数据的规模。参考答案参考答案lO(log2n)O(n)O(nlog2n)lO(n2+1)O(n3-n2)O(n5)2算法算法算法算法 SM SM 的改进算法的改进算法的改进算法的改进算法 BS BS 算法算法算法算法BSBS（A,i,j.fmax,fminA,i,j.fmax,fmin）/*/*在数组在数组在数组在数组 A A 的第的第的第的第 i i 至第至第至第至第 j j 个元素间寻找最大和最小个元素间寻找最大和最小个元素间寻找最大和最小个元素间寻找最大和最小 元素，已知元素，已知元素，已知元素，已知 i i j;j;假定假定假定假定A A 中元素互异中元素互异中元素互异中元素互异*/*/BS1.BS1.递归出口递归出口递归出口递归出口 IF i IF i j THEN(fmax j THEN(fmax fminfmin Ai.RETURN.)Ai.RETURN.)IF i IF i j j 1 THEN 1 THEN (IF Ai (IF Ai Aj THEN(fmax Aj THEN(fmax Aj.fminAj.fmin Ai).Ai).ELSE(fmax ELSE(fmax Ai.fminAi.fmin Aj).RETURN).Aj).RETURN).BS2.BS2.取中值取中值取中值取中值 mid mid (i i j)/2j)/2 BS3.BS3.递归调用递归调用递归调用递归调用 BS(A,i,mid.gmax,gmin).BS(A,mid BS(A,i,mid.gmax,gmin).BS(A,mid 1,j.hmax,1,j.hmax,hmin).hmin).BS4.BS4.合并合并合并合并 fmaxfmax maxgmax,hmax.maxgmax,hmax.fminfmin mingmin,hmin.mingmin,hmin.考察知识点考察知识点l数学归纳法证明l归纳基础 n=?时，*，命题成立。l归纳假设步骤 假设n=k是，有*，当n=k+1时，推出命题也成立l用数学归纳法证明l第一数学归纳法 (假设n=k，往推n=k+1)l第二数学归纳法(假设n=k，往推n=k+1，强数学归纳法)l两者等价l本题的数学归纳法证明思路l证明 n=3 时成立l假设 n=k 时都成立,证明 n=k+1时也成立l思路可以不写出来参考答案参考答案ln=3 时，时，T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命题成立。，命题成立。l假设假设n ，即即k 所以有所以有T()5*()/3-2,5*()/3-2,T()5*(5*()/3-2)/3-2 成立成立,.(2)又知又知 k+1=+k+1=+,(3)由由(1)(2)(3)，T(k+1)=T()+T()+2,5*/3-2 5*/3-25*/3-2+2 5*/3-2+2 =5*(+)/3-2 =5*(+)/3-2 =5*(k+1)/3-2 =5*(k+1)/3-2 综上，命题得证。综上，命题得证。作业情况作业情况l正确率约50%l由3=n=k，往推n=2*k，n=2*k+1也正确l分n=2*k，n=2*k+1讨论 k+1=l有问题的做法l弱假设：设n=k时成立l设n=k时成立，即 T(k)=5*k/3-2l利用(3*n/2 -2)结论l由(1)、(2)、(3)直接得到，不用数学归纳法l经分析得，T(n)=lognl往年：通过观察可知 T(n+1)=T(n)+1?1-121-12l给出算法BS的非递归算法，并说明算法最多需要多大的辅助空间。算法算法 BS(A,s,e.fmax,fmin)/*求数组求数组A的的s到到e中的元素的最大最小值，用栈去递归，确保中的元素的最大最小值，用栈去递归，确保s=e*/B1初始化，创建辅助分解栈初始化，创建辅助分解栈 p 和合并栈和合并栈 t CREATS(p).CREATS(t).p p(s,e,e).(s,e,e).B2迭代迭代 WHILE(NOT StackEmpty(s)DO (L,R,B)(L,R,B)p.p.IF(L=R)THEN (max minmin AL.AL.WHILE(NOT StackEmpty(t)AND R(StackTop(t)+1=L AND B(StackTop(t)=B)(left,right,bound,fm,fn)(left,right,bound,fm,fn)t t.L left.IF(mafn)THEN mi fm.fm.)t t (l,r,ma,mi(l,r,ma,mi).)ELSE(mid(L+R)div 2.(L+R)div 2.p p(mid+1,R,(mid+1,R,B B).).p p(L,mid,(L,mid,R R).).)B3结果结果 (s,e,e,fmax,fmin)(s,e,e,fmax,fmin)t t.参考答案参考答案l辅助空间l问题分解栈P:(log2n+1)*2l问题合并栈T:2*4lvoid bs(int a,int s,int e,int&fmin,int&fmax)l/*使用倍增法，求最大最小*/llint len=1;l lwhile(s+len=e)l l for(i=s;i+2*len-1ai+len)swap(ai,ai+len);l if(ai+len-1ai+2*len-1)swap(ai+len-1,ai+2*len-1);l l if(i+lenai+len)swap(ai,ai+len);l if(ai+len-1ae)swap(ai+len-1,ae);l l len*=2;llfmin=as,fmax=ae;l