第九章查找

第九章习题解答9.1解：(1)相同，平均查找长度为)1n(43(2)相同，平均查找长度为)1n(21(3)对于有序顺序表，平均查找长度为21kn，对于无序顺序表，则为)1n(21。9.2解：1.查找e的过程如下：2.查找f的过程如下：abcdefglmhabcdefglmh3.查找g的过程如下：abcdefglmhabcdefglmhabcdefglh9.3解：9.243342211101ASL9.4解：68.53987654834221501ASL注意：到表长=10时要进行顺序查找；9.5解：8.36554734221201ASL9.7解：443221111a(n为1时)54423121a2（n为2时）178)3(4)2(2)1(11nnnnnan（n为n时）N172)1N(N817N8asN1nN1nnN81721NASL（)8(1npi）9.9解：(1)5.3615243332211121ASL(2)有序表为：AprAugDecFebJanJulyJuneMarMayNovOctSep08.3)4*53*42*21*1(*121ASL(3)17.3)5*14*43*42*21*1(*121ASL9.10共有30种542137654231765427613574213657642139.11对于深度为N的完全二叉树一共有2^N-1个节点。根据平衡二叉树的性质，不难得到，对于N2的平衡二叉树，其前N-2层必然是完全二叉树。有12个结点，71-23，而12151-24,即前三层为完全二叉树，占有7个结点，还有5个结点。最大可加2层。即最大层数为5层。JanDevMarAugFebJuneNovAprJulyMayOctSep9.19因为哈希函数：11)3(HMODkk而用开放地址法处理冲突，MODmdkeyHi))((Hi,而)110)7((MODkidi关键字序列：2241534630130167131211322267413053460113上方为比较次数，下方为数值。对于22，41，53，46直接采用哈希函数即可，不用处理冲突。对30，211)30*3()30(HMOD,而2位置被41占有，此时1110)30*7(1MODd,311)12(MODHi,比较次数为2，依次类推。75.1)2*32*24*1(*81ASL9.20哈希函数为mMODiH(K),(i为首尾字母在字母表中序号的总和)关键字有12个，装填因子为0.75，即哈希表长度为16，即m为13处理冲突方法为开放地址法；ZHAOQIANSUNLIZHOUWUZHENGWANGCHANGCHAOYANGJIN413133214744333010183224哈希表：111211242884413031443321473310183224012345678910111213141592.2)2*82*43*25*1(121ASL9.21对应的数值为：JanFebMarAprMayJuneJulyAugSepOctNovDec10613113101011915144（1）开放地址法（哈希函数为：2)(ixH）12111124525611461013131010191514012345678910111213141575.01612a查找成功：5.2))1(11(*21aS查找不成功：5.8))1(11(*212aU(2)链地址法表示中止符查找成功：75.121aS查找不成功：22.1Uaea9.25#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includeiostreamusingnamespacestd;intsearch(int*p,intm,intk){//p为静态表，m为要查找的数，k为长度inti;p[k-1]=m;for(i=0;ik-1;i++)if(p[i]==m)012345678910111213141511410610101313151419break;returni;}int_tmain(intargc,_TCHAR*argv[]){intk,i,m,n;cout请输入你要的字符个数：;cink;int*p=newint[k+1];cout请输入第一个数:;cinp[0];coutendl请按从大到小输入：endl;for(i=1;ik;){cinp[i];if(p[i]p[i-1])cout输入错误，请重新输入;elsei++;}cout请输入要查找的数字：;cinm;n=search(p,m,k+1);if(nk)cout已找到endl;elsecout没有找到endl;return0;}等概率下查找成功平均查找长度：42)1(snASL查找不成功平均查找长度：81nASLus9.2610876531#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includeiostreamusingnamespacestd;intsearch(int*p,intlow,inthigh,intk){//p为静态表，k为要查找的数intmid;if(lowhigh)return-1;else{mid=(low+high)/2;if(p[mid]==k)returnmid;if(kp[mid])returnsearch(p,low,mid-1,k);/*在序列的前半部分查找*/elsereturnsearch(p,mid+1,high,k);/*在序列的后半部分查找*/}}int_tmain(intargc,_TCHAR*argv[]){intk,i,m,n;cout请输入你要的字符个数：;cink;int*p=newint[k];cout请输入第一个数:;cinp[0];coutendl请按从大到小输入：endl;for(i=1;ik;){cinp[i];if(p[i]p[i-1])cout输入错误，请重新输入;elsei++;}cout请输入要查找的数字：;cinm;n=search(p,0,k-1,m);if(n!=-1)cout已找到endl;elsecout没有找到endl;return0;}9.27#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includeiostreamusingnamespacestd;intsearch(int*p,intm,intk){//p为静态表，m为要查找的数k为长度inti=0;if(mp[0])return-1;elseif(m=p[k-1])returnk-1;elsewhile(ik-1){if(m=p[i]&&mp[i+1])returni;i++;}}int_tmain(intargc,_TCHAR*argv[]){intk,i,m,n;cout请输入你要的字符个数：;cink;int*p=newint[k];cout请输入第一个数:;cinp[0];coutendl请按从小到大输入：endl;for(i=1;ik;){cinp[i];if(p[i]p[i-1])cout输入错误，请重新输入:;elsei++;}cout请输入要查找的数字：;cinm;n=search(p,m,k);if(n=0&&nk-1)cout已找到endl;elsecout没有找到endl;return0;}9.32#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includeiostreamusingnamespacestd;#definecount10typedefstructbitnode{intdata;structbitnode*lch,*rch;}bitnode;bitnode*InsertBST(bitnode*p,intk){bitnode*q;if(p){if(kp-data)p-lch=InsertBST(p-lch,k);//插入到*p的左子树中elsep-rch=InsertBST(p-rch,k);//插入到*p的右子树中}else{q=(bitnode*)malloc(sizeof(bitnode));q-data=k;q-lch=NULL;q-rch=NULL;p=q;}returnp;}int*iorder(bitnode*p,int*k,int&m)//中序{if(!p)returnk;else{iorder(p-lch,k,m);k[m]=p-data;m++;iorder(p-rch,k,m);}returnk;}voidfind(int*k,intx){inti,a,b;if(x==k[0]){a=0;b=k[1];}elseif(x==k[count-1]){a=k[count-2];b=0;}elsefor(i=1;icount-1;i++)if(x==k[i]){a=k[i-1];b=k[i+1];}printf(最靠近x的而且小于x的值a：%d\n,a);printf(最靠近x的而且大于x的值b：%d\n,b);}voidpreorderbtree(bitnode*T){if(!T)return;else{preorderbtree(T-lch);printf(%d,T-data);preorderbtree(T-rch);}}int_tmain(intargc,_TCHAR*argv[]){intk[count]={45,24,53,20,28,50,60,18,30,70};int*m=newint[count];inti,n,a=0;bitnode*p;p=NULL;for(i=0;icount;i++)p=InsertBST(p,k[i]);printf(p的中序为：\n);preorderbtree(p);printf(\n);m=iorder(p,m,a);printf(请输入元素x:);scanf_s(%d,&n);find(m,n);return0;}9.33#includestdafx.h#includestdio.h#includestdlib.h#includestring.h#includeiostreamusingnamespacestd;#definecount10typedefstructbitnode{intdata;structbitnode*lch,*rch;}bitnode;bitnode*InsertBST(bitnode*p,intk){bitnode*q;if(p){if(kp-data)p-lch=InsertBST(p-lch,k);//插入到*p的左子树中elsep-rch=InsertBST(p-rch,k);//插入到*p的右子树中}else{q=(bitnode*)malloc(sizeof(bitnode));q-data=k;q-lch=NULL;q-rch=NULL;p=