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

首元结点、头结点、头指针区别首元结点、头结点、头指针区别习题选讲习题选讲栈与队列栈与队列树与二叉树树与二叉树第1页第1页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第2页第2页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第3页第3页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第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.n B.n/2 C.(n-1)/2 D.(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页 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页第8页 rnext=p;r=p;if(r!=NULL)rnext=NULL;return(head);第9页第9页linklistcreatelistr1()charch;linklisthead=(linklist)malloc(sizeof(listnode);listnode*p，*rr=head;while(ch=getchar()!=np=(listnode*)malloc(sizeof(listnode);pdata=ch;rnext=p;r=p;rnext=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 b、无论链表是否为空，其头指针是指向头结点、无论链表是否为空，其头指针是指向头结点在非空指针（空表中头结点指针域为空），因此在非空指针（空表中头结点指针域为空），因此空表和非空表处理也就统一了。空表和非空表处理也就统一了。第15页第15页2.21voidreverse(SqList&A)/顺序表就地逆置for(i=1,j=A.length;ij;i+,j-)A.elemiA.elemj;/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)/链表就地逆置;为简化算法,假设表长不小于2Rev(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;in;I+)if(L-datai=x)for(j=I;jn;j+)L-dataj=L-dataj+1;L-n-;第20页第20页L指向无头结点线性链表，写出删除链表中从下标为指向无头结点线性链表，写出删除链表中从下标为I结点开结点开始连续始连续k个结点算法个结点算法LinklistDel(linklistL,intI,intk)pnodep,q;intj=0;p=L;while(p-link!=NULL&jlink;j+for(j=1;jlink;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;elseq=r;r=r-link;P=p-link第22页第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页第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后面形成链表后面形成链表hchc=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-datanext;/p是最后一个是最后一个小于小于mink元素元素if(p-next)/假如尚有比假如尚有比mink更大元素更大元素q=p-next;while(q-datanext;/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前驱前驱前驱前驱pp-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-infoinfo)p3-info=p1-info;p1=p1-link;elsep3-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页设有两个栈都采用顺序存储表示，并且共有一个存储区，设有两个栈都采用顺序存储表示，并且共有一个存储区，现采用栈顶相对，迎面增长方式存储，写出对两个站进行现采用栈顶相对，迎面增长方式存储，写出对两个站进行插入删除操作。插入删除操作。分析：两个栈栈底分别设在数组两个断点，用两个指针批示两个栈栈顶，两个栈迎面增长，当两个栈定相遇时发生溢出。#definemaxsize100Typedefstructtstackdatatypedatamaxsize;Inttop1,top2;Intstacksize;tstack;第33页第33页(1)初始化算法：Stateinitstack(tstack*ts)ts=(tstack*)malloc(sizeof(sturcttstack);if(ts=NULL)printf(“outofspacen”);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-datats-top1=x;Elsetop2-;ts-datats-top2=x;Retrunok;第35页第35页出栈算法：出栈算法：Pop(tstack*ts,intI,datatypex)if(I=0)if(top1=-1)returnerror;X=ts-datats-top1;Top1-;elseif(top2=maxsize)returnerror;X=ts-datats-top2;Top2+;Returnx;第36页第36页3.17intIsReverse()/判断输入字符串中判断输入字符串中&前和前和&后部分是否为逆串后部分是否为逆串,是是则返回则返回1,不然返回不然返回0InitStack(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,不然返回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)return0;return1;/Palindrome_Testabcba第38页第38页递归算法为：long Fib(int n)long Fib(int n)if(n=1|n=2)/if(n=1|n=2)/终止递归条件终止递归条件 return 1;return 1;else else return Fib(n-1)+Fib(n-2);return Fib(n-1)+Fib(n-2);第39页第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)=1F(n)=f(n-1)+1/n有下列递归算法：Voidprint(intw)intI;if(w!=0)print(w-1);for(I=1;Inext)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插入顺序表适当位置，该表有序。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页第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首元素，则AB。第47页第47页算法思绪：首先找出A、B最大共同前缀；然后求出A和B，之后在按比较规则进行比较，AB函数返回1；A=B返回0；AB返回-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(Ai=Bi)i+;/*找最大共同前缀*/for(j=i;jm;j+)ASj-i=Aj;ms+;/*求A,ms为A长度*/for(j=i;j0|ms0&ns0&AS0data=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);elsepop(s,a);pop(s,b);r=compute(b,*p,a);/假设compute为执行双目运算过程push(s,r);/elsep+;/whilepop(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条边无向图是一个森林，(nk),则该森林中有多少棵树？解：设森林中有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页例例例例9 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+;Elsecountleaf(t-lchild);countleaf(t-rchild);第63页第63页例例例例1010voidBitree_Revolute(BitreeT)/互换所有结点左右子树T-lchildT-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两个根依次类推直到L和R结点数为1先根和后根不能拟定举反例先根：abcd后根：dcba第65页第65页例11：voidPreOrder_Nonrecursive(BitreeT)/先序遍历二叉树非递归算法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第66页第66页例例8：给定序列：给定序列F=6,8,10,12,14,16(1)按表中元素顺序依次插入一棵初始为空二叉树排序按表中元素顺序依次插入一棵初始为空二叉树排序树，并求其在等概率下查找成功平均查找长度。树，并求其在等概率下查找成功平均查找长度。(2)按表中元素顺序结构一棵平衡二叉树，并求其在等按表中元素顺序结构一棵平衡二叉树，并求其在等概率下查找成功平均查找长度，与（概率下查找成功平均查找长度，与（1）比较，得什么）比较，得什么结论。结论。第67页第67页6810121416ASL=1/6(1+2+3+4+5+6)=3.5(1)二叉排序树二叉排序树第68页第68页1214861610(2)平衡二叉树ASL=1/6(1+2*2+3*3)=2.3第69页第69页例例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）结构哈希表，并求等概率情况下查）结构哈希表，并求等概率情况下查找成功时平均查找长度。找成功时平均查找长度。第70页第70页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第71页第71页ASL=1/9(1*7+2*1+3*1)=129=1.33第72页第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页第73页将上述算法中划线语句改为：KRmid.key:h=mid.改动后，算法能否正常工作？请阐明原因。若算法不能正常工作，给出一个查找序列和一个犯错情况查找键值；若能正常工作，请给出一个查找序列和查找某个键值比较次数。（本题分，每题分）第74页第74页（1）通过改动以后，有也许出现死循环，比如当查找键值K小于有序表中最小键值时，就会出现死循环。故算法不能正常进行。（2）假设有序表查找序列为（2，3，4，5，6），当待查键值K=1时，出现死循环。第75页第75页