数据结构课后习题及其他期末复习资料省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,首元结点、头结点、头指针区分,习题选讲,栈与队列,树与二叉树,第1页,2.1,单项选择题,1.,一个向量（即一批地址连续存放单元）第一个元素存放地址是,100,，每个元素长度为,2,，则第,5,个元素地址是,_,_,。,A.110 B.108 C.100 D.120,2.,线性表次序存放结构是一个,_,_,存放结构，而链式存放结构是一个,_,_,存放结构。,A,随机存取,B,索引存取,C,次序存取,D,散列存取,3.,线性表逻辑次序与存放次序总是一致，这种说法,_,_,。,A.,正确,B.,不正确,4.,线性表若采取链式存放结构时，要求内存中可用存放单元地址,_,_,。,A.,必须是连续,B.,部分地址必须是连续,C.,一定是不连续,D.,连续或不连续都能够,B,A,C,B,D,第2页,5.,在以下叙述中，正确是,_,_,。,线性表次序存放结构优于链表存放结构,线性表次序存放结构适合用于频繁插入,/,删除数据元素情况,线性表链表存放结构适合用于频繁插入,/,删除数据元素情况,线性表链表存放结构优于次序存放结构,6.,每种数据结构都具备三个基本运算：插入、删除和查找，这种说法,_,_,。,A.,正确,B.,不正确,7.,不带头结点单链表,head,为空判定条件是,_,。,A.head=NULL B.head-next=NULL,C.head-next=head D.head!=NULL,8.,带头结点单链表,head,为空判定条件是,_,。,A.head=NULL B.head-next=NULL,C.head-next=head D.head!=NULL,C,A,A,B,第3页,9.,非空循环单链表,head,尾结点（由,p,所指向）满足,_,。,A.p-next=NULL B.p=NULL,C.p-next=head D.p=head,10.,在双向循环链表,p,所指结点之后插入,s,所指结点操作是A.p-right=s;s-left=p;p-right-left=s;s-right=p-right;,B.p-right=s;p-right-left=s;s-left=p;s-right=p-right;,C.s-left=p;s-right=p-right;p-right=s;p-right-left=s;,D.s-left=p;s-right=p-right;p-right-left=s;p-right=s;,11.,在一个单链表中，已知,q,所指结点是,p,所指结点前驱结点，若在,q,和,p,之间插入,s,结点，则执行,_,。,A.s-next=p-next;p-nexts;B.p-next=s-next;s-next=p;,C.q-next=s;s-next=p;D.p-next=s;s-next=q;,C,D,C,第4页,12.,在一个单链表中，若,p,所指结点不是最终结点，在,p,之后插入,s,所指结点，则执行,_,。,A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;,C.s-next=p-next;p=s;C.p-next=s;s-next=p;,13.,在一个单链表中，若删除,p,所指结点后续结点，则执行,_,。,A.p-next=p-next-next,；,B.p=p-next;p-next=p-nextnext,；,C.p-next=p-next;D.p=p-next-next,；,14.,从一个含有,n,个结点单链表中查找其值等于,x,结点时，在查找成功情况下，需平均比较,_,个结点。,A.n B.n/2 C.(n-1)/2 D.(n+1)/2,B,A,D,第5页,15.,在一个含有,n,个结点有序单链表中插入一个新结点并依然有序时间复杂度是,_ _,。,A.O(1)B.O(n)C.O(n2)D.O(nlog2n),1.B 2.A,C 3.B 4.D 5.C 6.A 7.A 8.B,9.C 10.D 11.C 12.B 13.A 14.D 15.B,B,第6页,首元结点、头结点、头指针区分,首元结点：,链表中存放线形表中第一个数据元素结点,头结点,：,在链表首元结点之前附设一个结点。该结点数据域不存放数据元素，其作用是为了对链表进行操作时，能够对空表、非空表情况以及对首元结点进行统一处理。,头指针：,是指向链表中第一个结点（头结点或首元结点）,指针。若链表中附设头结点，则不论线性表是否为空表，,头指针均不为空，不然表示空表头指针为空。,第7页,linklist creater(),char ch;,linklist head;,listnode *p，*r;/(，*head;),head=NULL;r=NULL;,while(ch=getchar()!=n),p=(listnode*)malloc(sizeof(listnode);,pdata=ch;,if(head=NULL),head=p;r=head;,else,第8页,rnext=p;,r=p;,if(r!=NULL),rnext=NULL;,return(head);,第9页,linklist createlistr1(),char ch;,linklist head=(linklist)malloc(sizeof(listnode);,listnode *p，*r,r=head;,while(ch=getchar()!=n,p=(listnode*)malloc(sizeof(listnode);,pdata=ch;,rnext=p;,r=p;,rnext=NULL;,return(head);,第10页,说明：第一个生成结点是开始结点，将开始结点插入到空表中，是在当前链表第一个位置上插入，该位置上插入操作和链表中其它位置上插入操作处理是不一样，原因是开始结点位置是存放在头指针（指针变量）中，而其余结点位置是在其前趋结点指针域中。算法中第一个if语句就是用来对第一个位置上插入操作做特殊处理。,第11页,求表长,算法思绪：设一个移动指针和计数器，初始化后，所指结点后面若还有结点，向后移动，计数器加1。,(1)设L是带头结点单链表(线性表长度不包含头结点)。,算法以下：,加头没加尾,int Length_LinkList1(LinkList L),Lnode *p=L;/*p指向头结点*/,int j=0;,while(p-next),p=p-next;j+/*p所指是第 j 个结点*/,return j;,第12页,(2)设L是不带头结点单链表。,算法以下：,int Length_LinkList2(LinkList L),Lnode *p=L;,int j;,if(p=NULL)return 0;/*空表情况*/,j=1;/*在非空表情况下，p所指是第一个结点*/;,while(p-next),p=p-next;j+,return j;,第13页,在上面算法中，第一个结点处理和其它结点是不,同，原因是第一个结点加入时链表为空，它没有直,接前驱结点，它地址就是整个链表指针，需要放,在链表头指针变量中；而其它结点有直接前驱结点，,其地址放入直接前驱结点指针域。,第14页,假如我们在链表开始结点之前附加一个结点，并称它为,头结点,，那么会带来以下两个优点：,a、因为开始结点位置被存放在头结点指针域中，所以在链表第一个位置上操作就,和在表其它位置上操作一致，无需进行特殊处理；,b、不论链表是否为空，其头指针是指向头结点在非空指针（空表中头结点指针域为空），所以空表和非空表处理也就统一了。,第15页,2.21,void reverse(SqList&A)/,次序表就地逆置,for(i=1,j=A.length;iA.elemj;/reverse,第16页,例2.5,已知单链表H，写一算法将其倒置。,算法思绪：依次取原链表中每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法以下：,void reverse(Linklist H),LNode *p;,p=H-next;/*p指向第一个数据结点*/,H-next=NULL;/*将原链表置为空表H*/,while(p),q=p;p=p-next;,q-next=H-next;/*将当前结点插到头结点后面*/,H-next=q;,第17页,该算法只是对链表中次序扫描一边即完成了倒置，所以时间性能为O(n)。,第18页,2.22,void LinkList_reverse(Linklist&L)/,链表就地逆置,;,为简化算法,假设表长大于,2,Rev(linklist L)/带头结点单链表,Pnode p,q,r;,p=L-link;if(p=NULL)return;,q=p-link;if(q=NULL)return;,r=q-link;,while(r!=NULL),q-link=p;,p=q;,q=r;,r=r-link;,q-link=p;,L-link-link=NULL;,L-link=q;,第19页,已知线性表A长度为n，而且采取次序存放结构，写一算法删除线性表中全部值为X元素,Del(sqlist L,datatype x),int I,j;,for(I=0;in;I+),if(L-datai=x),for(j=I;jn;j+),L-dataj=L-dataj+1;,L-n-;,第20页,L 指向无头结点线性链表，写出删除链表中从下标为I结点开始连续k个结点算法,Linklist Del(linklist L,int I,int k),pnode p,q;,int j=0;,p=L;,while(p-link!=NULL&jlink;j+,for(j=1;jlink;,p-link=q-link;,free(q);,Return(L);,第21页删除单链表中值相同多出结点,Diff_link(Linklist llist),pnode p,q,r;,p=llist-link;,while(p!=NULL),q=p;,r=q-link;,while(r!=NULL),if(r-info=p-info),t=r-link;,q-link=t;,free(r);,r=t;,else q=r;r=r-link;,P=p-link,第22页,Void diff_link(linklist L),pnode p,q,r;,for(p=L-link;p!=NULL;p-link),for(r=p,q=p-link;q!=NULL;q=q-link),if(p-info=q-info),r-link=q-link;,free(q);,q=r;,else r=r-link;,第23页,归并两个单链表为一个单链表,Linklist combine(linklist x,linklist y),linklist llist=(linklist)malloc(sizeof(struct Node);,Pnode p=llist,px=x-link,py=y-link;,While(px!=NULL|py!=NULL)if(px!=NULL),p-link=(linklist)malloc(sizeof(struct Node);,p=p-link;,P-info=px-info;,px=px-link;,if(py!=NULL),p-link=(linklist)malloc(sizeof(struct Node);,p=p-link;,P-info=px-info;,py=py-link;,P-link=NULL;,Return(llist);,第24页,12、归并两个线性表,void merge1(LinkList/while/merge1,第25页,2.15,void ListConcat(LinkList ha,LinkList hb,LinkList hc)/,把链表,hb,接在,ha,后面形成链表,hchc=ha;p=ha;while(p-next)p=p-next;p-next=hb;return(hc);,/ListConcat,第26页,2.19,Status Delete_Between(Linklist L,int mink,int maxk)/删除元素递增排列链表L中值大于mink且小于maxk全部元素p=L;while(p-next-datanext;/p是最终一个,小于mink元素if(p-next)/假如还有比mink更大元素q=p-next;while(q-datanext;/q是第一个大于maxk元素p-next=q;/Delete_Between,第27页,2.31,Status Delete_Pre(listnode*s)/,删除单循环链表中结点,s,直接前驱,p=s;while(p-next-next!=s)p=p-next;/,找到,s,前驱前驱,pp-next=s;return OK;/Delete_Pre,第28页,Linklist combine(Linklist list1,Linklist list2),Linklist list3=(Linklist)malloc(sizeof(struct Node);,Pnode p1=list1-link,p2=list2-link,p3=list3;,if(p1=list1&p2=list2),list3-linklist3;,return list;,while(p1!=list1|p2!=list2),p3-link=(Pnode)malloc(sizeof(struct Node);,p3=p3-link;,if(p2=list2|(p1!=list1&p1-infoinfo),p3-info=p1-info;,p1=p1-link;,else,p3-info=p2-info;,p2=p2-link;,p3-link=list3;,return list3;,第29页,2.32,P,指向双向链表中间结点，写出完成以下功效语句。,（1）在p结点后插入指针S所指向结点。,（2）删除P所指结点前驱结点3）删除P结点。,(1)s-pre=p;,s-next=p-next;,p-next-pre=s;,p-next=s;,(2)q=p-pre;,p-pre=q-pre;,q-pre-next=p;,free(q);,(3)p-pre-next=p-next;,p-next-pre=p-pre;,free(p);,第30页,处理计算机与打印机之间速度不匹配问题，需要设置一个数据缓冲区，应是一个什么结构。,判断一个队列Q（元素最多为n)为空条件是：,Q-rear=Q-front,判断一个队列Q（元素最多为n)为满条件是：,Q-rear-Q-front=n,第31页,判断一个循环队列Q（元素最多为n)为空条件是：,判断一个循环队列Q（元素最多为n)为满条件是：,Q-rear=Q-front,Q-front=Q-rear+1)%n,第32页,设有两个栈都采取次序存放表示，而且共有一个存放区，现采取栈顶相对，迎面增加方式存放，写出对两个站进行插入删除操作。,分析：两个栈栈底分别设在数组两个断点，用两个指针指示两个栈栈顶，两个栈迎面增加，当两个栈定相遇时发生溢出。,#define maxsize 100,Typedef struct tstack,datatype datamaxsize;,Int top1,top2;,Int stacksize;,tstack;,第33页,(1)初始化算法：,State initstack(tstack*ts),ts=(tstack*)malloc(sizeof(sturct tstack);,if(ts=NULL),printf(“out of spacen”);,Ts-stacksize=maxsize;,Ts-top1=-1;,Ts-top2=maxsize;,Return OK;,第34页,入栈算法：,Push(tstack*ts,int I,datatype x),if(top1=top2）return(overflow);,If(I=0),top1+;,ts-datats-top1=x;,Else,top2-;,ts-datats-top2=x;,Retrun ok;,第35页,出栈算法：,Pop(tstack*ts,int I,datatype x),if(I=0),if(top1=-1)return error;,X=ts-datats-top1;,Top1-;,else,if(top2=maxsize)return error;,X=ts-datats-top2;,Top2+;,Return x;,第36页,3.17,int IsReverse()/,判断输入字符串中,&,前和,&,后部分是否为逆串,是则返回,1,不然返回,0InitStack(s);while(e=getchar()!=/,不允许在,&,之前出现,push(s,e);while(e=getchar()!=)if(StackEmpty(s)return 0;pop(s,c);if(e!=c)return 0;if(!StackEmpty(s)return 0;return 1;/IsReverse,abcde&edcba,第37页,3.31,int Palindrome_Test()/,判别输入字符串是否回文序列,是则返回,1,不然返回,0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);/,同时使用栈和队列两种结构,while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b)return 0;return 1;/Palindrome_Test,abcba,第38页,递归算法为：,long Fib(int n),if(n=1|n=2)/终止递归条件,return 1;,else,return Fib(n-1)+Fib(n-2);,第39页,非递归算法为,long Fib1(int n),int a,b,c;/C代表当前项，a和b分别代表当前项前面第2项和第1项,a=b=1;/给a和b赋初值1,if(n=1|n=2),return 1;,else,for(int i=3;i3)转化为递归函数，其,递归出口是 ，递归体是 。,F(1)=1,F(n)=f(n-1)+1/n,有以下递归算法：,Void print(int w),int I;,if(w!=0),print(w-1);,for(I=1;Inext),Int count(listnode h),if(h=null),return 0;,else,return(1+count(h-next);,第42页,2、正向显示以h为头指针单链表全部节点值,递归模型：,Traverse(h)h=null 不做任何事,Traverse(h)=输出*h结点之值；traverse(h-next)其它情况,Void traverse（listnode h),if(h=null),return;,printf(“%d”,h-data);,traverse(h-next);,第43页,3、反向显示以h为头指针单链表全部结点值,Void revtraverse(listnode h),if(h=null),return;,revtraverse(h-next);,printf(“%d”,h-data);,第44页,4、删除以h为头指针单链表中值为x第一个结点,Int delnode(listnode h,int x),listnode p;,if(h=null),return 0;,if(h-data=x),p=h;,h=h-next;,freep);,return(1);,else,delnode(h-next,x);,第45页,2.11,设次序表va中数据元素递增有序，试写一算法将X插入次序表适当位置，该表有序。,Void insert(vector a,int n,int x),int I,j;,if(xan)an+1=x;,else,I=1;,while(x=aI)I+;,for(j=n;j=I;j-)aj+1=aj;,aI=x;n+;,第46页,比较两个线性表大小。两个线性表比较依据以下方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。A和B分别为 A 和 B 中除去最大共同前缀后子表。,比如A=(x,y,y,zx,z)，B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为(x,y,y,z)。,则 A=（x,z），B=（y,x,x,z），,若A=B=空表，则A=B；,若A=空表且B空表，或二者均不空且A首元素小于B首元素，则AB。,第47页,算法思绪：首先找出A、B最大共同前缀；然后求出A和B，之后在按比较规则进行比较，AB 函数返回1；A=B返回0；AB返回-1。,算法以下：,int compare(A,B,m,n),int A,B;,int m,n;,int i=0,j,AS,BS,ms=0,ns=0;/*AS,BS作为A,B*/,第48页,while(Ai=Bi)i+;/*找最大共同前缀/,for(j=i;jm;j+),ASj-i=Aj;ms+;/*求A,ms为A长度*/,for(j=i;jdata=p-data;,r-next=s;,r=s;,p=p-next;,If(q!=NULL),s=(node*)malloc(sizeof(node);,s-data=q-data;,r-next=s;,r=s;,q=q-next;,r-next=NULL;,return(z);,第50页,int GetValue_NiBoLan(char*str)/,对逆波兰式求值,p=str;InitStack(s);/s,为操作数栈,while(*p)if(*p,是数,)push(s,*p)elsepop(s,a);pop(s,b);r=compute(b,*p,a);/,假设,compute,为执行双目运算过程,push(s,r);/elsep+;/whilepop(s,r);return r;/GetValue_NiBoLan,Compute(int b,char c,int a),float d;,switch(c),case+:d=b+a;break;,case-:d=b-a;break;,case*:d=b*a;break;,case/:d=b/a;break;,第51页,【,例1,】,试找出分别满足下面条件全部二叉树：,（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；,（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同。,解：,（1）空二叉树或任一结点均无左子树非空二叉树,（2）空二叉树或任一结点均无右子树非空二叉树,（3）空二叉树或仅有一个结点二叉树,（4）同（3）,第52页,【,例2,】,已知一棵二叉树前序遍历结果序列是,ABECDFGHIJ,中序遍历结果序列是,EBCDAFHIGJ,试画出这棵二叉树。,第53页,【,解答,】,前序序列,A,BECDFGHIJ,，中序序列,EBCD,A,FHIGJ,时：,A,EBCD,FHIGJ,A,B,E,CD,HIGJ,F,第54页,前序序列,A,BECDFGHIJ,中序序列,EBCD,AFHIGJ,A,B,F,G,C,E,D,HI,J,A,B,E,C,D,F,G,J,H,I,第55页,例3：一棵二叉树层序序列为ABCDEFGHIJ,中序列为DBGEHJACIF,求这棵二叉树,A,C,B,D,E,F,G,H,J,I,第56页,例4、已知一棵树先根遍历序列GFKDAIEBCHJ,后根遍历序列为DIAEKFCJHBG,求对应树。,树先根对应二叉树先序，树后根对应二叉树中序遍历,第57页,例5、若n个节点k条边无向图是一个森林，(nk),则该森林中有多少棵树？,解：设森林中有m棵树，每棵树顶点数为.,例6、深度为5二叉树至多有结点数为多少？（深度从1开始计数）,A 16 B 30 C 31 D 32,例7、高度为h二叉树上只有度为0和2结点，则这类二叉树中所包含结点数最少为多少？（从1开始计数）,A 2h B 2h-1 C 2h+1 D h+1,M=n-k,第58页,【,例8,】,假定用于通信电文仅由 8 个字母,c1,c2,c3,c4,c5,c6,c7,c8,组成,各字母在电文中出现频率分别为,5,25,3,6,10,11,36,4,。试为这 8 个字母设计不等长 Huffman 编码,并给出该电文总码数。,第59页,【,解答,】,0000 0001 001 0100 0101,011 10 11,第60页,则,Huffman,编码为,c1 c2 c3 c4 c5 c6 c7 c8,0100 100000 0101 001 011 11 0001,电文总码数为,4*5+2*25+4*3+4*6+,3*10+3*11+2*36+4*4,=257,第61页,例9,int LeafCount(Bitree T)/求二叉树中叶子结点数目if(!T)return 0;/空树没有叶子else if(!T-lchild/左子树叶子数加上右子树叶子数/LeafCount_BiTree,第62页,Int leafnum=0;,Void countleaf(bintree t),if(t=null),return 0;,If(t-lchild=null&t-rchild=null),leafnum+;,Else,countleaf(t-lchild);,countleaf(t-rchild);,第63页,例10,void Bitree_Revolute(Bitree T)/,交换全部结点左右子树,T-lchildT-rchild;/,交换左右子树,if(T-lchild)Bitree_Revolute(T-lchild);if(T-rchild)Bitree_Revolute(T-rchild);/,左右子树再分别交换各自左右子树,/Bitree_Revolute,第64页,证实：假如给了一棵二叉树结点先根次序和对称次序,则此二叉树即可结构出来。假如给了先根和后根次序行吗？,举出不行例子。,证实,(1)由先根次序能够确定二叉树根R,(2)已知D后，经过对陈次序能够确定D两棵子树L和R,(3)LR确定后，又能够依据先根和中根确定LR两个根,依次类推直到L和R结点数为1,先根和后根不能确定举反例,先根：abcd,后根：dcba,第65页,例11：void PreOrder_Nonrecursive(Bitree T)/先序遍历二叉树非递归算法InitStack(S);Push(S,T);/根指针进栈while(!StackEmpty(S)while(Gettop(S,p)/向左走到尽头,pop(S,p);if(!StackEmpty(S)pop(S,p);push(S,p-rchild);/向右一步/while/PreOrder_Nonrecursive,第66页,例8：给定序列F=6,8,10,12,14,16,(1)按表中元素次序依次插入一棵初始为空二叉树排序树，并求其在等概率下查找成功平均查找长度。,(2)按表中元素次序结构一棵平衡二叉树，并求其在等概率下查找成功平均查找长度，与（1）比较，得什么结论。,第67页,6,8,10,12,14,16,ASL=1/6(1+2+3+4+5+6)=3.5,(1)二叉排序树,第68页,12,14,8,6,16,10,(2)平衡二叉树,ASL=1/6(1+2*2+3*3)=2.3,第69页,例9：设哈希函数为：H(key)=3key%13,并采取开放地址法中随机探测再散列法处理冲突，探测下一地址计算公式为：d,1,=H(key),d,i,=(d,i-1,+5key)%13 (I=2,3,4),试在0-12散列地址空间对关键字序列（14，67，42，95，74，3，59，81，77）结构哈希表，并求等概率情况下查找成功时平均查找长度。,第70页,H(14)=3*14%13=3,1,H(67)=3*67%13=6,1,H(42)=3*42%13=9,1,H(95)=3*95%13=12,1,H(74)=3*74%13=1,1,H(3)=3*3%13=9 冲突,H(3)=(9+5*3)%13=112,H(59)=3*59%13=8,1,H(81)=3*81%13=9 冲突,H(81)=(9+5*81)%13=11 冲突,H(81)=(11+5*81)%13=0,3,H(77)=3*77%13=10,1,第71页,ASL=1/9(1*7+2*1+3*1)=129=1.33,第72页,.设n个元素有序表为，为一个给定值，二分查找算法以下：,int binsearch(sqlist R,keytype K),j=1;h=n;suc=0;,while(j=h)&(!suc),mid=(j+h)/2;,switch,case K=Rmid.key:suc=1;break;,case,KRmid.key:j=mid+1,if(suc)return(mid);else return(0);,第73页,将上述算法中划线语句改为：KRmid.key:h=mid.,改动后，算法能否正常工作？请说明原因。,若算法不能正常工作，给出一个查找序列和一个犯错情况查找键值；若能正常工作，请给出一个查找序列和查找某个键值比较次数。（本题分，每小题分）,第74页,（1）经过改动以后，有可能出现死循环，比如当查找键值K小于有序表中最小键值时，就会出现死循环。故算法不能正常进行。,（2）假设有序表查找序列为（2，3，4，5，6），当待查键值K=1时，出现死循环。,第75页,