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

习题课一1.5确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。习题一（第18页）(1)i=1;k=0;do{k=k+10*i;i++;}while(i=n-1)答：划线语句的执行次数为n-1。O(n)(2）i=1;x=0;do{x++;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=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6。O(n3)(4）x=n;y=0;while(x=(y+1)*(y+1))y++;2.1利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。x划线语句的执行次数为。O()x习题二（第37页）#includeiostream.h#includeseqlist0.h#includeconio.htemplateclassTvoidInterSection(SeqListT&LA,SeqListT&LB){intm=LB.Length();SeqListTLC(10);//生成一个新的集合Tx;for(inti=1;i=m;i++)//遍历集合B的每个元素{LB.Find(i,x);if(LA.Search(x))LC.Insert(LC.Length()+1,x);}coutLC;}2.1利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。templateclassTvoidDifference(SeqListT&LA,SeqListT&LB){intm=LA.Length();SeqListTLC(10);Tx;for(inti=1;i=m;i++){LA.Find(i,x);if(LB.Search(x)==0)LC.Insert(LC.Length()+1,x);}coutLC;}voidmain(){SeqListintLA(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);}templateclassTvoidSeqListT::Invert1(){Ttemp;for(inti=0;ilength;i++){Find(length,temp);//得到序列的最后一个元素Delete(length);Insert(i,temp);}2.2(2)在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。利用类SeqList提供的操作直接实现2.2(2)在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。templateclassTvoidSeqListT::Invert(){Te;for(inti=0;ilength/2;i++){e=elements[i];elements[i]=elements[length-1-i];elements[length-1-i]=e;}}O(n)2.5在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。templateclassTvoidSingleListT::invert(){NodeT*p=first,*q;first=NULL;while(p){q=p-link;p-link=first;first=p;p=q;}}2.7单链表中结点按元素值递增链接，在类SingleList中增加一个成员函数，直接实现删除结点值在a至b之间的结点(ab)。templateclassTvoidSingleListT::DeleteAb(Ta,Tb){NodeT*p=first,*q=first;while(p&&p-datab)if(p-data=a){q=p;p=p-link;}elseif(q==first){q=p-link;deletep;p=first=q;}else{q-link=p-link;deletep;p=q-link;}}思考结点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,pop3.2设计2个栈共享一个数组，画出示意图。定义一个足够大的栈空间。该空间的两端分别设为两个栈的栈底，用bottom1和bottom2指示，让两个栈的栈顶，用top1和top2指示，都向中间伸展，直到两个栈的栈顶相遇，才会发生溢出。栈空，两栈均空：top1=0且top2=n-1栈满：top1=top2-10n-1↑↑↑↑bottom1top1top2bottom2⑷写出下列表达式的后缀表达式：①(a+b)/(c+d)ab+cd+/②b^2-4*a*cb2^4a*c*-⑿编程实现利用队列将栈中元素逆置的算法templateclassTvoidinvertstack(SeqStackT&s){SeqQueueTq(20);while(!s.IsEmpty()){q.EnQueue(s.Top());s.Pop();}while(!q.IsEmpty()){s.Push(q.Front());q.DeQueue();}}4.1给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。习题四（第68页）答：设有三维数组声明为A[n1][n2][n3]，每个元素占m个存储单元，则loc(A[i][j][k])=loc(A[0][0][0])+m*(i*n2*n3+j*n3+k)rcvrcv4.5给出下列稀疏矩阵的行优先和列优先顺序存储的三元组表。⑴设计递归算法，对整数数组A[n]，①求数组A的最大整数；②求数组A中n个整数的平均值。//求数组的最大值intMaximum(inta[],intn){if(n==1)returna[0];//数组只有一个元素时返回a[0]else{if(Maximum(a,n-1)a[n-1])returna[n-1];elsereturnMaximum(a,n-1);}}//求数组的平均值floatAverage(inta[],intn){if(n==1)returnfloat(a[0]);elsereturn(Average(a,n-1)*(n-1)+a[n-1])/n;}习题五（第81页）5.2设计一个递归算法，实现对一个有序表的顺序搜索。templateclassTintSeqListT::Search4(constT&x)const{elements[length]=1000;returnSch4(x,0);}templateclassTintSeqListT::Sch4(constT&x,inti)const{if(xelements[i])return0;elseif(x==elements[i])return++i;elsereturnSch4(x,i+1);}63941171121086525.3画出对长度为12的有序表进行对半查找的二叉判定树，并求等概率搜索时，成功搜索的平均搜索长度解：1二叉判定树如下：2成功搜索的平均搜索长度由于第i层有2i个结点，故平均搜索长度为：ASLlog2(n+1)//P.77习题六（第107页）6.2（2）对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？答：（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵6.4求一棵二叉树的叶子结点个数；templateclassTintBTreeT::Leaves(){intcount=0;Leaf(root,count);returncount;}templateclassTvoidBTreeT::Leaf(BTNodeT*t,int&count){if(t){if((t-lchild==NULL)&&(t-rchild==NULL))count++;Leaf(t-lchild,count);Leaf(t-rchild,count);}}其中Leaves声明为public型，Leaf声明为private型。6.4设对一棵二叉树进行中序遍历和后序遍历的结果分别为：（1）中序遍历BDCEAFHG（2）后序遍历DECBHGFA画出该二叉树。答：6.5写出图6-23的遍历结果。先序：ADEHFJGBCK中序：HEJFGDABKC后序：HJGFEDKCBA6.6（6）设计算法，交换一棵二叉树中每个结点的左、右子树。templateclassTvoidBTreeT::Exch(BTNodeT*p){if(p){BTNodeT*q=Exch(p-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，40WPL=(7+9+12)*2+5*3+(2+3)*4=91(注意是叶子结点带权路径长度之和)A:1010B:1011C:100D:00E:01F:11（编码不是唯一的）6.14设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率。（1)画出哈夫曼树（2）计算带权路径长度(3)求各字符的编码