南邮数据结构课后习题课.ppt

习题课一,1.5确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。,习题一（第18页）,(1)i=1;k=0;dok=k+10*i;i+;while(i=n-1),答：划线语句的执行次数为n-1。O(n),(2）i=1;x=0;dox+;i=2*i;while（in）;,划线语句的执行次数为log2n。O(log2n),(3)for(inti=1;i=n;i+)for(intj=1;j=i;j+)for(intk=1;k=(y+1)*(y+1)y+;,2.1利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。,划线语句的执行次数为。O(),习题二（第37页）,#include#includeseqlist0.h#includeconio.htemplatevoidInterSection(SeqList,2.1利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。,templatevoidDifference(SeqList,voidmain()SeqListLA(10),LB(10);for(inti=1;i=8;i+)LA.Insert(i,i);for(i=1;i=3;i+)LB.Insert(i,i+3);InterSection(LA,LB);Difference(LA,LB);,templatevoidSeqList:Invert1()Ttemp;for(inti=0;ilink=first;first=p;p=q;,2.7单链表中结点按元素值递增链接，在类SingleList中增加一个成员函数，直接实现删除结点值在a至b之间的结点(ab)。,templatevoidSingleList:DeleteAb(Ta,Tb)Node*p=first,*q=first;while(p思考结点a和b有没有删除掉？,习题三（第50页）,3.1设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。1)A,B,C,D,E2)A,C,E,B,D3)C,A,B,D,E4)E,D,C,B,A答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3）也不能。(1)能。push,pop,push,pop,push,pop,push,pop,push,pop(4)能。push,push,push,push,push,pop,pop,pop,pop,pop,3.2设计2个栈共享一个数组，画出示意图。,定义一个足够大的栈空间。该空间的两端分别设为两个栈的栈底，用bottom1和bottom2指示，让两个栈的栈顶，用top1和top2指示，都向中间伸展，直到两个栈的栈顶相遇，才会发生溢出。栈空，两栈均空：top1=0且top2=n-1栈满：top1=top2-1,写出下列表达式的后缀表达式：(a+b)/(c+d)ab+cd+/b2-4*a*cb24a*c*-,编程实现利用队列将栈中元素逆置的算法templatevoidinvertstack(SeqStack,4.1给出三维数组元素Aijk的存储地址loc(Aijk)。,习题四（第68页）,答：设有三维数组声明为An1n2n3，每个元素占m个存储单元，则loc(Aijk)=loc(A000)+m*(i*n2*n3+j*n3+k),4.5给出下列稀疏矩阵的行优先和列优先顺序存储的三元组表。,设计递归算法，对整数数组An，求数组A的最大整数；求数组A中n个整数的平均值。/求数组的最大值intMaximum(inta,intn)if(n=1)returna0;/数组只有一个元素时返回a0elseif(Maximum(a,n-1)lchild);p-lchild=Exch(p-rchild);p-rchild=q;,6.10将图题6-24中的树转换成二叉树，并将图6-23中的二叉树转换成森林。,6.11给出对图6-24中的树的先序遍历和后序遍历的结果。答：先序：A，D，E，F，J，G，M，B，L，H，C，K后序：J，G，F，E，D，M，H，L，K，C，B，A,分别以下列数据为输入，构造最小堆。80，10，70，20，60，30，50，40,WPL=(7+9+12)*2+5*3+(2+3)*4=91(注意是叶子结点带权路径长度之和)A:1010B:1011C:100D:00E:01F: