数据结构课后习题及其他期末复习资料.ppt

首元结点、头结点、头指针的区别首元结点、头结点、头指针的区别习题选讲习题选讲栈与队列栈与队列树与二叉树树与二叉树2.1 单项选择题单项选择题1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__ __ A. 110 B. 108 C. 100 D. 1202. 线性表的顺序存储结构是一种__ _的存储结构，而链式存储结构是一种__ _的存储结构A．随机存取 B．索引存取 C．顺序存取 D．散列存取3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ _A. 正确 B. 不正确4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ _A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续或不连续都可以BACBD5. 在以下的叙述中，正确的是__ _线性表的顺序存储结构优于链表存储结构线性表的顺序存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构优于顺序存储结构6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__ _。

A. 正确 B. 不正确7. 不带头结点的单链表head为空的判定条件是____A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL8. 带头结点的单链表head为空的判定条件是____A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULLCAAB9. 非空的循环单链表head的尾结点（由p所指向）满足____A. p->next= =NULL B. p= =NULLC. 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->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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. n B. n/2 C. (n-1)/2 D. (n+1)/2 BAD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.BB首元结点、头结点、头指针的区别首元结点：首元结点：链表中存储线形表中第一个数据元素的结点头结点头结点：在链表首元结点之前附设一个结点该结点的数据域不存储数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理头指针：头指针：是指向链表中第一个结点（头结点或首元结点）    的指针若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的头指针为空                    linklist creater( ) { char ch; linklist head; 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  r–>next=p; r=p; } if (r!=NULL) r–>next=NULL; return(head); }linklist createlistr1(  ){  char  ch;  linklist head=(linklist)malloc(sizeof(listnode));    listnode  *p，，*r    r=head;    while((ch=getchar( ))!=‵\n′{           p=(listnode*)malloc(sizeof(listnode));           p–>data=ch;           r–>next=p;           r=p;         }       r–>next=NULL;       return(head);   }说明：第一个生成的结点是开始结点，将开始说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，始结点的位置是存放在头指针（指针变量）中， 而其余结点的位置是在其前趋结点的指针域中。

而其余结点的位置是在其前趋结点的指针域中算法中的第一个算法中的第一个if语句就是用来对第一个位置语句就是用来对第一个位置上的插入操作做特殊处理上的插入操作做特殊处理 求表长算法思路：设一个移动指针ｐ和计数器ｊ，初始化后，ｐ所指结点后面若还有结点，ｐ向后移动，计数器加11)设L是带头结点的单链表(线性表的长度不包括头结点)算法如下：   加头没加尾加头没加尾int  Length_LinkList1 (LinkList L){ Lnode  * p=L;   /* p指向头结点*/   int  j=0;   while (p->next)     { p=p->next; j++ }   /* p所指的是第 j 个结点*/   return  j;}(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;}在上面的算法中，第一个结点的处理和其它结点是不在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，接前驱结点，它的地址就是整个链表的指针， 需要放需要放在链表的头指针变量中；而其它结点有直接前驱结点，在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。

其地址放入直接前驱结点的指针域如果我们在链表的开始结点之前附加一个结点，如果我们在链表的开始结点之前附加一个结点，并称它为并称它为头结点头结点，那么会带来以下两个优点：，那么会带来以下两个优点：       a、、由于开始结点的位置被存放在头结点的由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊和在表的其它位置上的操作一致，无需进行特殊处理；处理；b b、、无论链表是否为空，其头指针是指向头结点无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了因此空表和非空表的处理也就统一了2.21 void reverse(SqList &A)//顺序表的就地逆置{  for(i=1,j=A.length;iA.elem[j];}//reverse 例例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;    }}该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)2.22 void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2Rev(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;}已知线性表已知线性表A的长度为的长度为n，，并且采用顺序存储结构，写一并且采用顺序存储结构，写一算法删除线性表中所有值为算法删除线性表中所有值为X的元素的元素Del (sqlist L,datatype x){int I,j;  for(I=0;in;I++)     if(L->data[i]==x)    {for(j=I;jn;j++)        L->data[j]=L->data[j+1];         L->n--;            }}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;j<=k;j++)      {q=p->link;        p->link=q->link;        free(q); }Return(L);}删除单链表中值相同的多余结点删除单链表中值相同的多余结点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}}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;}}归并两个单链表为一个单链表归并两个单链表为一个单链表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);}12、归并两个线性表void merge1(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 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList hc)//把链表把链表hb接在接在ha后面形成链表后面形成链表hc{  hc=ha;p=ha;  while(p->next) p=p->next;  p->next=hb;  return(hc);}//ListConcat 2.19 Status Delete_Between(Linklist L,int mink,int maxk)//删除元素删除元素递增排列的链表递增排列的链表L中值大于中值大于mink且小于且小于maxk的所有元素的所有元素{ p=L;  while(p->next->data<=mink) p=p->next; //p是最后一个是最后一个                                                                不大于不大于mink的元素的元素  if(p->next)    //如果还有比如果还有比mink更大的元素更大的元素  { q=p->next;    while(q->datanext; //q是第一个不小于是第一个不小于maxk的元素的元素    p->next=q;  }}//Delete_Between 2.31 Status Delete_Pre(listnode *s)//删除单循环链表中结删除单循环链表中结点点s的直接前驱的直接前驱{  p=s;  while(p->next->next!=s) p=p->next; //找到找到s的前驱的的前驱的前驱前驱p  p->next=s;  return OK;}//Delete_Pre 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->link=list3;       return list;}     while(p1!=list1||p2!=list2)     {p3->link=(Pnode)malloc(sizeof(struct Node));        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;          return list3;}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);解决计算机与打印机之间速度不匹配的问题，需要解决计算机与打印机之间速度不匹配的问题，需要设置一个数据缓冲区，应是一个什么结构设置一个数据缓冲区，应是一个什么结构判断一个队列Q（元素最多为n)为空的条件是：Q->rear==Q->front判断一个队列Q（元素最多为n)为满的条件是：Q->rear-Q->front==n判断一个循环队列Q（元素最多为n)为空的条件是：判断一个循环队列Q（元素最多为n)为满的条件是：Q->rear==Q->frontQ->front==Q->rear+1)%n设有两个栈都采用顺序存储表示，并且共有一个存储区，设有两个栈都采用顺序存储表示，并且共有一个存储区，现采用栈顶相对，迎面增长的方式存储，写出对两个站进现采用栈顶相对，迎面增长的方式存储，写出对两个站进行插入删除的操作。

行插入删除的操作分析：两个栈的栈底分别设在数组的两个断点，，用两个指针指示两个栈的栈顶，两个栈迎面增长，当两个栈定相遇时发生溢出define maxsize  100Typedef struct tstack{datatype data[maxsize];Int top1,top2;Int stacksize;}tstack;(1)初始化算法：State initstack(tstack *ts){ts=(tstack*)malloc(sizeof(sturct tstack));  if(ts==NULL)    printf(“out of space\\n”);Ts->stacksize=maxsize;Ts->top1=-1;Ts->top2=maxsize;Return OK;}入栈算法：Push(tstack *ts,int I,datatype x){if(top1==top2）return(overflow);If(I==0){top1++;  ts->data[ts->top1]=x;  }Else{top2--; ts->data[ts->top2]=x;  }Retrun ok;}出栈算法：出栈算法：Pop(tstack *ts,int I,datatype x){if(I==0) {if(top1==-1) return error;X=ts->data[ts->top1];Top1--;}else{if(top2==maxsize) return error;X=ts->data[ts->top2];Top2++;}Return x;}3.17 int IsReverse()//判断输入的字符串中判断输入的字符串中'&'前和前和'&'后部分是否为逆串后部分是否为逆串,是则返回是则返回1,否则返回否则返回0{  InitStack(s);  while((e=getchar())!='&')  {    if(e==’@’) return 0;//不允许在不允许在’&’之前出现之前出现’@’    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@3.31 int Palindrome_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) return 0;  }  return 1; }//Palindrome_Test abcba@递归算法为：long￿Fib(int￿n){if(n==1||n==2)￿//终止递归条件终止递归条件￿return￿1;￿else￿return￿Fib(n-1)+Fib(n-2);￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿} ￿非递归算法为￿￿￿￿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;i<=n;i++)￿￿￿￿￿{￿c=a+b;￿￿//求出当前项￿￿￿￿￿￿￿￿￿￿￿a=b;//把前面第1项赋给前面第2项￿￿￿￿￿￿￿￿￿￿￿￿b=c;//把当前项赋给前面第1项￿￿￿￿￿￿￿￿}￿￿￿￿￿￿￿￿￿return￿c;//返回所求的第n项￿￿￿￿￿￿} 若将f=1+1/2+1/3+…….+1/n   (n>3)转化为递归函数，其递归出口是                   ，递归体是                      。

F(1)=1F(n)=f(n-1)+1/n有如下递归算法：Void print(int w)  {int I;    if(w!=0)      {print(w-1);        for(I=1;I<=w;I++)           printf(“%3d”,w);        printf(“\n”);       }    }Print（4）的结果是：12233   344   4   4有一个不带头结点的单链表h，设计如下递归算法：1、求以h为头指针的单链表的结点个数设count(h)为计算单链表h的结点个数，递归模型如下：Count(h)=0     h=nullCount(h)=1+count(h->next)Int count(listnode h){if (h==null)  return  0;  else    return(1+count(h->next)); }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);}3、反向显示以h为头指针的单链表的所有结点值Void revtraverse(listnode h){if(h=null)   return;  revtraverse(h->next);  printf(“%d”,h->data); }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;     free(p);     return(1);    }  else     delnode(h->next,x));}2.11设顺序表va中的数据元素递增有序，试写一算法将X插入顺序表的适当位置，该表有序。

Void insert(vector a[],int n,int x){ int I,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++;}比较两个线性表的大小两个线性表的比较依据下列方法：设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′首元素，则AB  算法思路：首先找出A、B的最大共同前缀；然后求出A′和B′，之后在按比较规则进行比较，A>B 函数返回1；A=B返回0；A0 || ms>0 && ns>0 && AS[0]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);}int GetValue_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);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;} 【例例1】试找出分别满足下面条件的所有二叉树：试找出分别满足下面条件的所有二叉树：（（1））前前序序序序列列和和中中序序序序列列相相同同；；   （（2））中中序序序序列列和和后后序序序列相同；序列相同；（（3））前前序序序序列列和和后后序序序序列列相相同同；；   （（4））前前序序、、中中序序、、后后序序列均相同。

序序列均相同解：解：（（1））       空二叉树或任一结点均无左子树的非空二叉树空二叉树或任一结点均无左子树的非空二叉树（（2））       空二叉树或任一结点均无右子树的非空二叉树空二叉树或任一结点均无右子树的非空二叉树（（3））       空二叉树或仅有一个结点的二叉树空二叉树或仅有一个结点的二叉树（（4））       同（同（3））【例例2】已知一棵二叉树的前已知一棵二叉树的前序遍历的结果序列是序遍历的结果序列是           ABECDFGHIJ   中序遍历的结果序列是中序遍历的结果序列是           EBCDAFHIGJ   试画出这棵二叉树试画出这棵二叉树 【【解答解答】】前序序列前序序列 ABECDFGHIJ，，中序序列中序序列 EBCDAFHIGJ 时：时：AEBCDFHIGJABECDHIGJF 前序序列前序序列 ABECDFGHIJ  中序序列中序序列 EBCDAFHIGJABFGCEDHIJABECDFGJHI例例3：一棵二叉树的层序序列为：一棵二叉树的层序序列为ABCDEFGHIJ,中序列为中序列为DBGEHJACIF,求这棵二叉树求这棵二叉树ACBDEFGHJI例例4、已知一棵树的先根遍历序列、已知一棵树的先根遍历序列GFKDAIEBCHJ,后根后根遍历序列为遍历序列为DIAEKFCJHBG,求对应的树。

求对应的树树的先根对应二叉树的先序，树的后根对应二叉树的中树的先根对应二叉树的先序，树的后根对应二叉树的中序遍历序遍历例5、若n个节点k条边的无向图是一个森林，(n>k),则该森林中有多少棵树？解：设森林中有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+1M=n-k【例例8】假定用于通信的电文仅由假定用于通信的电文仅由 8 个字母个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成组成, 各字母在电文中出现的频率各字母在电文中出现的频率分别为分别为 5, 25, 3, 6, 10, 11, 36, 4试为这为这 8 个字母设计不等长个字母设计不等长 Huffman 编码编码, 并给出该电文的总码数并给出该电文的总码数 【【解答解答】】0000  0001  001  0100   0101011    10       11则则Huffman编码为编码为  c1     c2     c3       c4        c5     c6    c7     c80100   10 0000   0101    001   011   11   0001电文总码数为电文总码数为    4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 +    3 * 10 + 3 * 11 + 2 * 36 + 4 * 4    = 257例例例例9 9 int LeafCount(Bitree T)//求二叉树中叶子结点的数目{  if(!T) return 0; //空树没有叶子  else if(!T->lchild&&!T->rchild) return 1; //叶子结点  else return LeafCount(T->lchild)+LeafCount(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree 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);}}例例例例10  10  void Bitree_Revolute(Bitree T)//交换所有结点的左右子树{  T->lchild<->T->rchild; //交换左右子树  if(T->lchild) Bitree_Revolute(T->lchild);  if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树}//Bitree_Revolute 证明：如果给了一棵二叉树结点的先根次序和对称次序则此二叉树即可构造出来。

如果给了先根和后根次序行吗？举出不行的例子证明(1)由先根次序可以确定二叉树的根R(2)已知D后，通过对陈次序可以确定D的两棵子树L和R(3)LR确定后，又可以根据先根和中根确定LR的两个根依次类推直到L和R的结点数为1先根和后根不能确定举反例先根：abcd后根：dcba例11：void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法{  InitStack(S);  Push(S,T); //根指针进栈  while(!StackEmpty(S))  {    while(Gettop(S,p)&&p)    {      visit(p->data);      push(S,p->lchild);    } //向左走到尽头    pop(S,p);    if(!StackEmpty(S))    {     pop(S,p);     push(S,p->rchild); //向右一步    }  }//while}//PreOrder_Nonrecursive 例例8：给定序列：给定序列F={6,8,10,12,14,16}(1)按表中元素的顺序依次插入一棵初始为空的二叉树按表中元素的顺序依次插入一棵初始为空的二叉树排序树，并求其在等概率下查找成功的平均查找长度。

排序树，并求其在等概率下查找成功的平均查找长度2)按表中元素的顺序构造一棵平衡二叉树，并求其在按表中元素的顺序构造一棵平衡二叉树，并求其在等概率下查找成功的平均查找长度，与（等概率下查找成功的平均查找长度，与（1）比较，得）比较，得什么结论什么结论6810121416ASL=1/6(1+2+3+4+5+6)=3.5(1)二叉排序树二叉排序树1214861610(2)平衡二叉树ASL=1/6(1+2*2+3*3)=2.3例例9：设哈希函数为：：设哈希函数为：H(key)=3key%13,并采用开放地址并采用开放地址法中的随机探测再散列法处理冲突，探测的下一地址计算法中的随机探测再散列法处理冲突，探测的下一地址计算公式为：公式为：d1=H(key)di=(di-1+5key)%13   (I=2,3,4……)试在试在0-12的散列地址空间对关键字序列（的散列地址空间对关键字序列（14，，67，，42，，95，，74，，3，，59，，81，，77）构造哈希表，并求等概率情况下）构造哈希表，并求等概率情况下查找成功时的平均查找长度查找成功时的平均查找长度H(14)=3*14%13=31H(67)=3*67%13=61H(42)= 3*42%13=91H(95)= 3*95%13=121H(74)= 3*74%13=11H(3)= 3*3%13=9 冲突H(3)=(9+5*3)%13=112H(59)=3*59%13=8 1H(81)= 3*81%13=9 冲突H(81)=(9+5*81)%13=11 冲突H(81)=(11+5*81)%13=0 3H(77)= 3*77%13=101ASL=1/9(1*7+2*1+3*1)=129=1.33.设n个元素的有序表为Ｒ，Ｋ为一个给定的值，二分查找算法如下： int binsearch(sqlist R, keytype K) {j=1;h=n ;suc=0; while((j<=h)&&(!suc)) {mid =(j+h)/2; switch {case K=R[mid].key: suc=1; break; case KR[mid].key: j=mid+1 } } if (suc) return(mid); else return(0);}将上述算法中划线语句改为：K

若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数本题６分，每小题３分）（1）经过改动以后，有可能出现死循环，比如当查找的键值K小于有序表中的最小键值时，就会出现死循环故算法不能正常进行 （2）假设有序表的查找序列为（2，3，4，5，6），当待查的键值K=1时，出现死循环。