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

《邮数据结构课件后习题课件.ppt》由会员分享，可在线阅读，更多相关《邮数据结构课件后习题课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题课一习题课一1.5 1.5 确确定定下下列列各各程程序序段段的的程程序序步步，确确定定划划线线语语句句的的执执行行次数，计算它们的渐近时间复杂度。次数，计算它们的渐近时间复杂度。习题一（第习题一（第1818页）页）(1)(1)i=1;k=0;i=1;k=0;do do k=k+10*i;i+k=k+10*i;i+;while(i=n-1)while(i=n-1)答：答：划线语句的执行次数为划线语句的执行次数为 n-1 n-1。O(n)O(n)(2(2）i=1;x=0;i=1;x=0;do do x+;i=2*i;x+;i=2*i;while while（inin）;划线语句的执行次数为划线

2、语句的执行次数为 loglog2 2n n。O(logO(log2 2n)n)(3)(3)for(for(intint i=1;i=n;i+)i=1;i=n;i+)for(for(intint j=1;j=i;j+)j=1;j=i;j+)for(for(intint k=1;k=j;k+)k=1;k=(y+1)*(y+1)while(x=(y+1)*(y+1)y+y+;2.12.1 利利用用线线性性表表类类LinearListLinearList提提供供的的操操作作，涉涉及及实实现现两两个个集合的交和差运算集合的交和差运算。划线语句的执行次数为划线语句的执行次数为 。O()O()习题二（第习题

3、二（第3737页）页）#include include.h#include seqlist0.h#include seqlist0.h#include#include conioconio.h.htemplate template voidvoid InterSection InterSection(SeqListSeqList&LA,&LA,SeqListSeqList&LB)&LB)intint m=LB.Length();m=LB.Length();SeqList SeqList LC(10);LC(10);/生成一个新的集合生成一个新的集合 T x;T x;for(for(intint

4、 i=1;i=m;i+)i=1;i=m;i+)/遍历集合遍历集合B B的的每个元素每个元素 LB.Find(i,x);LB.Find(i,x);if(LA.Search(x)LC.Insert(LC.Length()+1,x);if(LA.Search(x)LC.Insert(LC.Length()+1,x);cout coutLC;LC;2.12.1 利利用用线线性性表表类类LinearListLinearList提提供供的的操操作作，涉涉及及实实现现两两个个集合的交和差运算集合的交和差运算。template template void Difference(void Difference(

5、SeqListSeqList&LA,&LA,SeqListSeqList&LB)&LB)int int m=LA.Length();m=LA.Length();SeqList SeqList LC(10);LC(10);T x;T x;for(for(intint i=1;i=m;i+)i=1;i=m;i+)LA.Find(i,x);LA.Find(i,x);if(LB.Search(x)=0)LC.Insert(LC.Length()+1,x);if(LB.Search(x)=0)LC.Insert(LC.Length()+1,x);cout coutLC;LC;void main()voi

6、d main()SeqListSeqList LA(10),LB(10);LA(10),LB(10);for(for(intint i=1;i=8;i+)LA.Insert(i,i);i=1;i=8;i+)LA.Insert(i,i);for(i=1;i=3;i+)LB.Insert(i,i+3);for(i=1;i=3;i+)LB.Insert(i,i+3);InterSection InterSection(LA,LB);(LA,LB);Difference(LA,LB);Difference(LA,LB);template template voidvoid SeqList SeqLis

7、t:Invert1():Invert1()T temp;T temp;for(for(intint i=0;ilength;i+)i=0;ilength;i+)Find(length,temp);Find(length,temp);/得到序列的最后一个元素得到序列的最后一个元素Delete(length);Delete(length);Insert(i,temp);Insert(i,temp);2.2(2)2.2(2)在类在类LinearList LinearList 中增加一个成员函数，将顺序表逆置，中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。利用类实现该函数并分析算

8、法的时间复杂度。利用类SeqList SeqList 提供的操作提供的操作直接实现直接实现2.2(2)2.2(2)在类在类LinearList LinearList 中增加一个成员函数，将顺序表中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类逆置，实现该函数并分析算法的时间复杂度。不利用类SeqListSeqList 提供的操作直接实现。提供的操作直接实现。template template voidvoid SeqList SeqList:Invert():Invert()T e;T e;for(for(intint i=0;ilength i=0;ilength

9、/2/2;i+);i+)e=elementsi;e=elementsi;elementsi=elementslength-1-i;elementsi=elementslength-1-i;elementslength-1-i=e;elementslength-1-i=e;O(n)O(n)2.5 2.5 在在类类SingleListSingleList中中增增加加一一个个成成员员函函数数，将将单单链链表表逆置运算，直接实现该函数并分析其时间复杂度。逆置运算，直接实现该函数并分析其时间复杂度。template template voidvoid SingleList SingleList:inve

10、rt():invert()Node*p=first,*q;Node*p=first,*q;first=NULL;first=NULL;while(p)while(p)q=p-link;q=p-link;p-link=first;p-link=first;first=p;first=p;p=q;p=q;2.7 2.7 单单链链表表中中结结点点按按元元素素值值递递增增链链接接，在在类类SingleListSingleList中中增增加加一一个个成成员员函函数数，直直接接实实现现删删除除结结点点值值在在a a至至b b之之间间的的结结点点(a a b)b)。template template voi

11、dvoid SingleList SingleList:DeleteAbDeleteAb(T a,T b)(T a,T b)Node*p=first,*q=first;Node*p=first,*q=first;while(p&p-datadatadatadatalink;q=p;p=p-link;else if(q=first)else if(q=first)q=p-link;delete p;p=first=q;q=p-link;delete p;p=first=q;else else q-link=p-link;delete p;p=q-link;q-link=p-link;delete

12、 p;p=q-link;思考结点思考结点a a和和b b有没有删除掉？有没有删除掉？习题三（第习题三（第5050页）页）3.13.1 设设A A、B B、C C、D D、E E五五个个元元素素依依次次进进栈栈(进进栈栈后后可可立立即即出出栈栈)，问问能能否否得得到到下下列列序序列列。若若能能得得到到，则则给给出出相相应应的的pushpush和和poppop序列；若不能，则说明理由。序列；若不能，则说明理由。1)1)A,B,C,D,E A,B,C,D,E 2)2)A,C,E,B,D A,C,E,B,D 3)C,A,B,D,E3)C,A,B,D,E 4)E,D,C,B,A4)E,D,C,B,A答答

13、：2 2）和和3 3）不不能能。对对2 2）中中的的E E，B B，D D而而言言，E E最最先先出出栈栈则则表表明明，此此时时B B和和D D均均在在栈栈中中，由由于于，B B先先于于D D进进栈栈，所所以以应应有有D D先出栈。同理先出栈。同理3 3）也不能。）也不能。(1)(1)能能。push,pop,push,pop,push,pop,push,pop,push,pop push,pop,push,pop,push,pop,push,pop,push,pop(4)(4)能。能。push,push,push,push,push,pop,pop,pop,pop,poppush,push,p

14、ush,push,push,pop,pop,pop,pop,pop3.2 3.2 设计设计2 2个栈共享一个数组，画出示意图。个栈共享一个数组，画出示意图。定定义义一一个个足足够够大大的的栈栈空空间间。该该空空间间的的两两端端分分别别设设为为两两个个栈栈的的栈栈底底，用用bottom1bottom1和和bottom2bottom2指指示示，让让两两个个栈栈的的栈栈顶顶，用用top1top1和和top2top2指指示示，都都向向中中间间伸伸展展，直直到到两两个个栈栈的的栈栈顶顶相相遇遇，才会发生溢出。才会发生溢出。栈空，两栈均空：栈空，两栈均空：top1=0top1=0且且 top2=n-1to

15、p2=n-1栈满：栈满：top1=top2-1top1=top2-1 0 0 n-1n-1 bottom1 top1 top2 bottom1 top1 top2 bottom2 bottom2写出下列表达式的后缀表达式：写出下列表达式的后缀表达式：(a+b)/(c+d)a+b)/(c+d)ab ab+cdcd+/+/b2-4*a*c b24a*c*-b2-4*a*c b24a*c*-编程实现利用队列将栈中元素逆置的算法编程实现利用队列将栈中元素逆置的算法 templatevoidinvertstack(SeqStack&s)SeqQueueq(20);while(!s.IsEmpty()q.

16、EnQueue(s.Top();s.Pop();while(!q.IsEmpty()s.Push(q.Front();q.DeQueue();4.14.1给给出三出三维维数数组组元素元素AijkAijk的存的存储储地址地址loc(Aijk)loc(Aijk)。习题四（第习题四（第6868页）页）答答：设设有有三三维维数数组组声声明明为为AnAn1 1nn2 2nn3 3，每每个个元元素素占占m m个个存存储单元，则储单元，则 loc(Aijk)=loc(A000)+m*(i*nloc(Aijk)=loc(A000)+m*(i*n2 2*n*n3 3+j*n+j*n3 3+k)+k)r c vr

17、 c vr c vr c v4.5 4.5 给给出出下下列列稀稀疏疏矩矩阵阵的的行行优优先先和和列列优优先先顺顺序序存存储储的的三三元元组组表。表。设计递归算法，对整数数组设计递归算法，对整数数组AnAn，求数组求数组A A的最大整数；的最大整数；求数组求数组A A中中n n个整数的平均值。个整数的平均值。/求数组的最大值求数组的最大值 intint Maximum(Maximum(intint a,a,intint n)n)if(n=1)return a0;/if(n=1)return a0;/数组只有一个元素时返回数组只有一个元素时返回a0a0 else else if(Maximum(a

18、,n-1)an-1)return an-1;if(Maximum(a,n-1)an-1)return an-1;else return Maximum(a,n-1);else return Maximum(a,n-1);/求数组的平均值求数组的平均值 float Average(float Average(intint a,a,intint n)n)if(n=1)return float(a0);if(n=1)return float(a0);else return(Average(a,n-1)*(n-1)+an-1)/n;else return(Average(a,n-1)*(n-1)+an

19、-1)/n;习题五（第习题五（第8181页）页）5.2 5.2 设计一个递归算法，实现对一个有序表的顺序搜索。设计一个递归算法，实现对一个有序表的顺序搜索。templatetemplateint SeqListint SeqList:Search4(const T&x)const:Search4(const T&x)const elementslength=1000;elementslength=1000;return Sch4(x,0);return Sch4(x,0);templatetemplateint SeqListint SeqList:Sch4(const T&x,:Sch4(c

20、onst T&x,intint i)const i)const if(xelementsi)return 0;if(xelementsi)return 0;else if(x=elementsi)return+i;else if(x=elementsi)return+i;else return Sch4(x,i+1);else return Sch4(x,i+1);6 63 39 94 411117 71 1121210108 86 65 52 25.3 5.3 画画出出对对长长度度为为1212的的有有序序表表进进行行对对半半查查找找的的二二叉叉判判定定树树，并求等概率搜索时，成功搜索的平均搜

21、索长度并求等概率搜索时，成功搜索的平均搜索长度解：解：1 1 二叉判定树如下：二叉判定树如下：2 2成功搜索的平均搜索长度成功搜索的平均搜索长度3 3 由于第由于第i i层有层有2 2i i个结点，故平均搜索长度为：个结点，故平均搜索长度为：4 4ASL ASL log log2 2(n+1)/P.77(n+1)/P.77习题六（第习题六（第107107页）页）6.26.2（2 2）对对于于三三个个结结点点A A，B B和和C C，可可分分别别组组成成多多少少不不同同的的无无序树、有序树和二叉树？序树、有序树和二叉树？答：（答：（1 1）无序树：）无序树：9 9棵棵 （2 2）有序树：）有序树

22、：1212棵棵 （3 3）二叉树：）二叉树：3030棵棵6.4 6.4 求一棵二叉树的叶子结点个数；求一棵二叉树的叶子结点个数；template template int BTreeint BTree:Leaves():Leaves()intint count=0;count=0;Leaf(root,count);Leaf(root,count);return count;return count;template template void void BTreeBTree:Leaf(:Leaf(BTNodeBTNode*t,*t,intint&count)&count)if(t)if(t)i

23、f(t-if(t-lchildlchild=NULL)&(t-=NULL)&(t-rchildrchild=NULL)count+;=NULL)count+;Leaf(t-Leaf(t-lchildlchild,count);,count);Leaf(t-Leaf(t-rchildrchild,count);,count);其中其中LeavesLeaves声明为声明为publicpublic型，型，LeafLeaf声明为声明为privateprivate型。型。6.4 6.4 设设对对一一棵棵二二叉叉树树进进行行中中序序遍遍历历和和后后序序遍遍历历的的结结果果分分别别为：为：（1 1）中序遍历

24、）中序遍历 B D C E A F H G B D C E A F H G （2 2）后序遍历后序遍历 D E C B H G F A D E C B H G F A 画出该二叉树。画出该二叉树。答：答：6.5 6.5 写出图写出图6-236-23的遍历结果。的遍历结果。先序：先序：ADEHFJGBCKADEHFJGBCK中序：中序：HEJFGDABKCHEJFGDABKC后序：后序：HJGFEDKCBAHJGFEDKCBA6.66.6（6 6）设设计计算算法法，交交换换一一棵棵二二叉树中每个结点的左、右子树。叉树中每个结点的左、右子树。template template voidvoid B

25、Tree BTree:ExchExch(BTNodeBTNode*p)*p)if(p)if(p)BTNodeBTNode*q=*q=ExchExch(p-(p-lchildlchild););p-p-lchildlchild=ExchExch(p-(p-rchildrchild););p-p-rchildrchild=q;=q;6.10 6.10 将将图图题题6-246-24中中的的树树转转换换成成二二叉叉树树，并并将将图图6-236-23中中的的二二叉树转换成森林。叉树转换成森林。6.11 6.11 给出对图给出对图6-246-24中的树的先序遍历和后序遍历的结果。中的树的先序遍历和后序遍历

26、的结果。答：先序：答：先序：A A，D D，E E，F F，J J，G G，M M，B B，L L，H H，C C，K K 后序：后序：J J，G G，F F，E E，D D，M M，H H，L L，K K，C C，B B，A A 分别以下列数据为输入，构造最小堆。分别以下列数据为输入，构造最小堆。80 80，1010，7070，2020，6060，3030，5050，40 40 WPL=(7+9+12)*2+5*3+(2+3)WPL=(7+9+12)*2+5*3+(2+3)*4=91(*4=91(注意是叶子结点带注意是叶子结点带权路径长度之和权路径长度之和)A:1010 A:1010 B:1011 B:1011 C:100 C:100 D:00 D:00 E:01 E:01 F:11 F:11（编码不是唯一的）编码不是唯一的）6.14 6.14 设设S=A,B,C,D,E,FS=A,B,C,D,E,F，W=2,3,5,7,9,12W=2,3,5,7,9,12，对字符集合对字符集合进行哈夫曼编码，进行哈夫曼编码，W W为各字符的频率。为各字符的频率。（1)1)画出哈夫曼树画出哈夫曼树（2 2）计算带权路径长度）计算带权路径长度(3)(3)求各字符的编码求各字符的编码