数据结构课后习题及其他期末复习资料市公开课金奖市赛课一等奖课件

首元结点、头结点、头指针区别习题选讲栈与队列树与二叉树第1页第1页2.1单选题1.一个向量（即一批地址连续存储单元）第一个元素存储地址是100，每个元素长度为2，则第5个元素地址是__

__。

A.110B.108C.100D.1202.线性表顺序存储结构是一个__

_存储结构，而链式存储结构是一个__

_存储结构。A．随机存取B．索引存取C．顺序存取D．散列存取3.线性表逻辑顺序与存储顺序总是一致，这种说法__

_。A.正确B.不正确4.线性表若采用链式存储结构时，要求内存中可用存储单元地址__

_。A.必须是连续B.部分地址必须是连续C.一定是不连续D.连续或不连续都能够BACBD第2页第2页5.在下列叙述中，正确是__

_。线性表顺序存储结构优于链表存储结构线性表顺序存储结构适合用于频繁插入/删除数据元素情况线性表链表存储结构适合用于频繁插入/删除数据元素情况线性表链表存储结构优于顺序存储结构6.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__

_。A.正确B.不正确7.不带头结点单链表head为空鉴定条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL8.带头结点单链表head为空鉴定条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULLCAAB第3页第3页9.非空循环单链表head尾结点（由p所指向）满足____。A.p->next==NULLB.p==NULLC.p->next==headD.p==head10.在双向循环链表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->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;CDC第4页第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->next->next；C.p->next=p->next;D.p=p->next->next；14.从一个含有n个结点单链表中查找其值等于x结点时，在查找成功情况下，需平均比较____个结点。A.nB.n/2C.(n-1)/2D.(n+1)/2

BAD第5页第5页15.在一个含有n个结点有序单链表中插入一个新结点并仍然有序时间复杂度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)1.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.C12.B13.A14.D15.BB第6页第6页首元结点、头结点、头指针区别首元结点：链表中存储线形表中第一个数据元素结点头结点：在链表首元结点之前附设一个结点。该结点数据域不存储数据元素，其作用是为了对链表进行操作时，能够对空表、非空表情况以及对首元结点进行统一处理。头指针：是指向链表中第一个结点（头结点或首元结点）指针。若链表中附设头结点，则无论线性表是否为空表，头指针均不为空，不然表示空表头指针为空。

第7页第7页

linklistcreater(){charch;linklisthead;listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head==NULL){head=p;r=head;}else

第8页第8页

r–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}第9页第9页linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*rr=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}第10页第10页说明：第一个生成结点是开始结点，将开始结点插入到空表中，是在当前链表第一个位置上插入，该位置上插入操作和链表中其它位置上插入操作处理是不同，原因是开始结点位置是存放在头指针（指针变量）中，而其余结点位置是在其前趋结点指针域中。算法中第一个if语句就是用来对第一个位置上插入操作做特殊处理。第11页第11页

求表长算法思绪：设一个移动指针ｐ和计数器ｊ，初始化后，ｐ所指结点后面若尚有结点，ｐ向后移动，计数器加1。(1)设L是带头结点单链表(线性表长度不包括头结点)。算法下列：

加头没加尾intLength_LinkList1(LinkListL){Lnode*p=L;/*p指向头结点*/intj=0;while(p->next){p=p->next;j++}/*p所指是第j个结点*/returnj;}第12页第12页(2)设L是不带头结点单链表。算法下列：intLength_LinkList2(LinkListL){Lnode*p=L;intj;if(p==NULL)return0;/*空表情况*/j=1;/*在非空表情况下，p所指是第一个结点*/;while(p->next){p=p->next;j++}returnj;}第13页第13页在上面算法中，第一个结点处理和其它结点是不同，原因是第一个结点加入时链表为空，它没有直接前驱结点，它地址就是整个链表指针，需要放在链表头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点指针域。第14页第14页假如我们在链表开始结点之前附加一个结点，并称它为头结点，那么会带来下列两个长处：a、由于开始结点位置被存储在头结点指针域中，因此在链表第一个位置上操作就和在表其它位置上操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点在非空指针（空表中头结点指针域为空），因此空表和非空表处理也就统一了。第15页第15页2.21voidreverse(SqList&A)//顺序表就地逆置

{

for(i=1,j=A.length;i<j;i++,j--)

A.elem[i]<->A.elem[j];

}//reverse第16页第16页例2.5已知单链表H，写一算法将其倒置。

算法思绪：依次取原链表中每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法下列：

voidreverse(LinklistH){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页第17页该算法只是对链表中顺序扫描一边即完毕了倒置，因此时间性能为O(n)。第18页第18页2.22voidLinkList_reverse(Linklist&L)//链表就地逆置;为简化算法,假设表长不小于2

Rev(linklistL)//带头结点单链表{Pnodep,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页第19页已知线性表A长度为n，并且采用顺序存储结构，写一算法删除线性表中所有值为X元素Del(sqlistL,datatypex){intI,j;for(I=0;i<L->n;I++)if(L->data[i]==x){for(j=I;j<L->n;j++)L->data[j]=L->data[j+1];L->n--;}}第20页第20页L指向无头结点线性链表，写出删除链表中从下标为I结点开始连续k个结点算法LinklistDel(linklistL,intI,intk){pnodep,q;intj=0;p=L;while(p->link!=NULL&&j<i){p=p->link;j++}for(j=1;j<=k;j++){q=p->link;p->link=q->link;free(q);}Return(L);}第21页第21页删除单链表中值相同多出结点Diff_link(Linklistllist){pnodep,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页第22页Voiddiff_link(linklistL){pnodep,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;}elser=r->link;}}第23页第23页归并两个单链表为一个单链表Linklistcombine(linklistx,linklisty){linklistllist=(linklist)malloc(sizeof(structNode));Pnodep=llist,px=x->link,py=y->link;While(px!=NULL||py!=NULL){

if(px!=NULL){p->link=(linklist)malloc(sizeof(structNode));p=p->link;P->info=px->info;px=px->link;}if(py!=NULL){p->link=(linklist)malloc(sizeof(structNode));p=p->link;P->info=px->info;py=py->link;}}P->link=NULL;Return(llist);}第24页第24页12、归并两个线性表voidmerge1(LinkList&A,LinkList&B,LinkList&C)//把链表A和B合并为C,A和B元素间隔排列,且使用原存储空间

{

p=A->next;q=B->next;C=A;

while(p&&q)

{

s=p->next;p->next=q;//将B元素插入

t=q->next;q->next=s;//如A非空,将A元素插入

p=s;q=t;

}//while

}//merge1第25页第25页2.15voidListConcat(LinkListha,LinkListhb,LinkListhc)//把链表hb接在ha后面形成链表hc

{

hc=ha;p=ha;

while(p->next)p=p->next;

p->next=hb;

return(hc);}//ListConcat第26页第26页2.19StatusDelete_Between(LinklistL,intmink,intmaxk)//删除元素递增排列链表L中值不小于mink且小于maxk所有元素

{

p=L;

while(p->next->data<=mink)p=p->next;//p是最后一个小于mink元素

if(p->next)

//假如尚有比mink更大元素

{

q=p->next;

while(q->data<maxk)q=q->next;//q是第一个不小于maxk元素

p->next=q;

}

}//Delete_Between第27页第27页2.31StatusDelete_Pre(listnode*s)//删除单循环链表中结点s直接前驱

{

p=s;

while(p->next->next!=s)p=p->next;//找到s前驱前驱p

p->next=s;

returnOK;

}//Delete_Pre第28页第28页Linklistcombine(Linklistlist1,Linklistlist2){Linklistlist3=(Linklist)malloc(sizeof(structNode));Pnodep1=list1->link,p2=list2->link,p3=list3;if(p1==list1&&p2==list2){list3->link=list3;returnlist;}while(p1!=list1||p2!=list2){p3->link=(Pnode)malloc(sizeof(structNode));p3=p3->link;if(p2==list2||(p1!=list1&&p1->info<=p2->info){p3->info=p1->info;p1=p1->link;}

else{p3->info=p2->info;p2=p2->link;}}p3->link=list3;returnlist3;}第29页第29页2.32P指向双向链表中间结点，写出完毕下列功效语句。（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页第30页处理计算机与打印机之间速度不匹配问题，需要设置一个数据缓冲区，应是一个什么结构。判断一个队列Q（元素最多为n)为空条件是：Q->rear==Q->front判断一个队列Q（元素最多为n)为满条件是：Q->rear-Q->front==n第31页第31页判断一个循环队列Q（元素最多为n)为空条件是：判断一个循环队列Q（元素最多为n)为满条件是：Q->rear==Q->frontQ->front==Q->rear+1)%n第32页第32页设有两个栈都采用顺序存储表示，并且共有一个存储区，现采用栈顶相对，迎面增长方式存储，写出对两个站进行插入删除操作。分析：两个栈栈底分别设在数组两个断点，，用两个指针批示两个栈栈顶，两个栈迎面增长，当两个栈定相遇时发生溢出。#definemaxsize100Typedefstructtstack{datatypedata[maxsize];Inttop1,top2;Intstacksize;}tstack;第33页第33页(1)初始化算法：Stateinitstack(tstack*ts){ts=(tstack*)malloc(sizeof(sturcttstack));if(ts==NULL)printf(“outofspace\\n”);Ts->stacksize=maxsize;Ts->top1=-1;Ts->top2=maxsize;ReturnOK;}第34页第34页入栈算法：Push(tstack*ts,intI,datatypex){if(top1==top2）return(overflow);If(I==0){top1++;ts->data[ts->top1]=x;}Else{top2--;ts->data[ts->top2]=x;}Retrunok;}第35页第35页出栈算法：Pop(tstack*ts,intI,datatypex){if(I==0){if(top1==-1)returnerror;X=ts->data[ts->top1];Top1--;}else{if(top2==maxsize)returnerror;X=ts->data[ts->top2];Top2++;}Returnx;}第36页第36页3.17intIsReverse()//判断输入字符串中'&'前和'&'后部分是否为逆串,是则返回1,不然返回0

{

InitStack(s);

while((e=getchar())!='&')

{

if(e==’@’)return0;//不允许在’&’之前出现’@’

push(s,e);}

while((e=getchar())!='@')

{

if(StackEmpty(s))return0;

pop(s,c);

if(e!=c)return0;

}

if(!StackEmpty(s))return0;

return1;

}//IsReverseabcde&edcba@第37页第37页3.31intPalindrome_Test()//判别输入字符串是否回文序列,是则返回1,不然返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{

Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)return0;

}

return1;}//Palindrome_Testabcba@第38页第38页递归算法为：longFib(intn){if(n==1||n==2)//终止递归条件return1;elsereturnFib(n-1)+Fib(n-2);

}

第39页第39页非递归算法为longFib1(intn){inta,b,c;//C代表当前项，a和b分别代表当前项前面第2项和第1项a=b=1;//给a和b赋初值1if(n==1||n==2)return1;elsefor(inti=3;i<=n;i++){c=a+b;//求出当前项a=b;//把前面第1项赋给前面第2项b=c;//把当前项赋给前面第1项}returnc;//返回所求第n项}

第40页第40页若将f=1+1/2+1/3+…….+1/n(n>3)转化为递归函数，其递归出口是，递归体是。F(1)=1F(n)=f(n-1)+1/n有下列递归算法：Voidprint(intw){intI;if(w!=0){print(w-1);for(I=1;I<=w;I++)printf(“%3d”,w);printf(“\n”);}}Print（4）结果是：1233444第41页第41页有一个不带头结点单链表h，设计下列递归算法：1、求以h为头指针单链表结点个数设count(h)为计算单链表h结点个数，递归模型下列：Count(h)=0h=nullCount(h)=1+count(h->next)Intcount(listnodeh){if(h==null)return0;elsereturn(1+count(h->next));}第42页第42页2、正向显示以h为头指针单链表所有节点值递归模型：Traverse(h)h=null不做任何事Traverse(h)=输出*h结点之值；traverse(h->next)其它情况Voidtraverse（listnodeh){if(h==null)return;printf(“%d”,h->data);traverse(h->next);}第43页第43页3、反向显示以h为头指针单链表所有结点值Voidrevtraverse(listnodeh){if(h=null)return;revtraverse(h->next);printf(“%d”,h->data);}第44页第44页4、删除以h为头指针单链表中值为x第一个结点Intdelnode(listnodeh,intx){listnodep;if(h==null)return0;if(h->data==x){p=h;h=h->next;free(p);return(1);}elsedelnode(h->next,x));}第45页第45页2.11设顺序表va中数据元素递增有序，试写一算法将X插入顺序表适当位置，该表有序。Voidinsert(vectora[],intn,intx){intI,j;if(x>a[n])a[n+1]=x;else{I=1;while(x>=a[I])I++;for(j=n;j>=I;j--)a[j+1]=a[j];a[I]=x;n++;}第46页第46页比较两个线性表大小。两个线性表比较依据下列办法：设A、B是两个线性表，均用向量表示，表长分别为m和n。A′和B′分别为A和B中除去最大共同前缀后子表。比如A=(x,y,y,z,x,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′首元素，则A<B；不然，A>B。第47页第47页算法思绪：首先找出A、B最大共同前缀；然后求出A′和B′，之后在按比较规则进行比较，A>B函数返回1；A=B返回0；A<B返回-1。算法下列：intcompare(A,B,m,n)intA[],B[];intm,n;{inti=0,j,AS[],BS[],ms=0,ns=0;/*AS,BS作为A′,B′*/

第48页第48页while(A[i]==B[i])i++;/*找最大共同前缀*/

for(j=i;j<m;j++){AS[j-i]=A[j];ms++;}/*求A′,ms为A′长度*/for(j=i;j<n;j++){BS[j-i]=B[j];ns++;}/*求B′,ms为B′长度*/if(ms==ns&&ms==0)return0;elseif(ms==0&&ns>0||ms>0&&ns>0&&AS[0]<BS[0])return–1;elsereturn1;}第49页第49页node*link(x,y)node*x,*y;{node*r,*s,*p,*q,*z;z=(node*)malloc(sizeof(node));r=z;p=x;q=y;While(p!=NULL||q!NULL){if(p!=NULL){s=(node*)malloc(sizeof(node));s->data=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页第50页intGetValue_NiBoLan(char*str)//对逆波兰式求值

{

p=str;InitStack(s);//s为操作数栈

while(*p)

{

if(*p是数)push(s,*p);

else

{

pop(s,a);pop(s,b);

r=compute(b,*p,a);//假设compute为执行双目运算过程

push(s,r);

}//else

p++;

}//while

pop(s,r);returnr;

}//GetValue_NiBoLanCompute(intb,charc,inta){floatd;switch(c)case‘+’:d=b+a;break;case‘-’:d=b-a;break;case’*’:d=b*a;break;case‘/’:d=b/a;break;}第51页第51页【例1】试找出分别满足下面条件所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同。解：（1）

空二叉树或任一结点均无左子树非空二叉树（2）

空二叉树或任一结点均无右子树非空二叉树（3）

空二叉树或仅有一个结点二叉树（4）

同（3）第52页第52页【例2】已知一棵二叉树前序遍历结果序列是

ABECDFGHIJ中序遍历结果序列是

EBCDAFHIGJ试画出这棵二叉树。第53页第53页

【解答】前序序列

ABECDFGHIJ，中序序列EBCDAFHIGJ时：AEBCDFHIGJABECDHIGJF第54页第54页

前序序列

ABECDFGHIJ中序序列EBCDAFHIGJABFGCEDHIJABECDFGJHI第55页第55页例3：一棵二叉树层序序列为ABCDEFGHIJ,中序列为DBGEHJACIF,求这棵二叉树ACBDEFGHJI第56页第56页例4、已知一棵树先根遍历序列GFKDAIEBCHJ,后根遍历序列为DIAEKFCJHBG,求相应树。树先根相应二叉树先序，树后根相应二叉树中序遍历第57页第57页例5、若n个节点k条边无向图是一个森林，(n>k),则该森林中有多少棵树？解：设森林中有m棵树，每棵树顶点数为….例6、深度为5二叉树至多有结点数为多少？（深度从1开始计数）A16B30C31D32例7、高度为h二叉树上只有度为0和2结点，则这类二叉树中所包括结点数至少为多少？（从1开始计数）A2hB2h-1C2h+1Dh+1M=n-k第58页第58页【例8】假定用于通信电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8构成,各字母在电文中出现频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文总码数。第59页第59页

【解答】

00000001001010001010111011第60页第60页则Huffman编码为c1c2c3c4c5c6c7c8010010 00000101001011110001电文总码数为

4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257第61页第61页例9intLeafCount(BitreeT)//求二叉树中叶子结点数目

{

if(!T)return0;//空树没有叶子

elseif(!T->lchild&&!T->rchild)return1;//叶子结点

elsereturnLeafCount(T->lchild)+LeafCount(T->rchild);//左子树叶子数加上右子树叶子数

}//LeafCount_BiTree第62页第62页Intleafnum=0;Voidcountleaf(bintreet){if(t==null)return0;If(t->lchild==null&&t->rchild==null){leafnum++;}Else{countleaf(t->lchild);countleaf(t->rchild);}}第63页第63页例10voidBitree_Revolute(BitreeT)//互换所有结点左右子树

{

T->lchild<->T->rchild;//互换左右子树

if(T->lchild)Bitree_Revolute(T->lchild);

if(T->rchild)Bitree_Revolute(T->rchild);//左右子树再分别互换各自左右子树

}//Bitree_Revolute第64页第64页证实：假如给了一棵二叉树结点先根顺序和对称顺序则此二叉树即可结构出来。假如给了先根和后根顺序行吗？举出不行例子。证实(1)由先根顺序能够拟定二叉树根R(2)已知D后，通过对陈顺序能够拟定D两棵子树L和R(3)LR拟定后，又能够依据先根和中根拟定LR两个