《数据结构题集》第9章查找

《数据结构题集》答案第9章查找《数据结构题集》答案第9章查找/《数据结构题集》答案第9章查找第九章查找9.25intSearch_Sq(SSTableST,intkey)//在有序表上一次序查找的算法,监督哨设在高低标端{ST.elem[ST.length+1].key=key;for(i=1;ST.elem[i].key>key;i++);if(i>ST.length||ST.elem[i].key<key)returnERROR;returni;}//Search_Sq剖析:本算法查找成功状况下的均匀查找长度为ST.length/2,不行功状况下为ST.length.9.26intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法{if(low>high)return0;//查找不到时返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive9.27intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一个结点号{int*r;r=ST.elem;if(key<r.key)return0;elseif(key>=r[ST.length].key)returnST.length;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key>=r[mid].key&&key<r[mid+1].key)//查找结束的条件returnmid;elseif(key<r[mid].key)high=mid;elselow=mid;}//本算法不存在查找失败的状况,不需要return0;}//Locate_Bin9.28typedefstruct{intmaxkey;intfirstloc;}Index;typedefstruct{int*elem;intlength;Indexidx[MAXBLOCK];//每块开端位置和最大元素

,此中

idx[0]

不利用,其内容初始化为{0,0}以利于折半查找intblknum;//块的数量}IdxSqList;//索引次序表种类intSearch_IdxSeq(IdxSqListL,intkey)//

分块查找,用折半查找法确立记录所在块,块内采纳次序查找法{if(key>L.idx[L.blknum].maxkey)returnERROR;//low=1;high=L.blknum;found=0;

超出最大元素while(low<=high&&!found)//折半查找记录所在块号mid{mid=(low+high)/2;if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)found=1;elseif(key>L.idx[mid].maxkey)low=mid+1;elsehigh=mid-1;}i=L.idx[mid].firstloc;//块的下界j=i+blksize-1;//块的上界temp=L.elem[i-1];//保留相邻元素L.elem[i-1]=key;//设置监督哨for(k=j;L.elem[k]!=key;k--);//次序查找L.elem[i-1]=temp;//恢复元素if(k<i)returnERROR;//未找到returnk;}//Search_IdxSeq剖析:在块内进行次序查找时,假如需要设置监督哨,则一定先保留相邻块的相邻元素,免得数据丢掉.9.29typedefstruct{LNode*h;//hLNode*t;//t

指向最小元素指向上一次查找的结点}CSList;LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表储存结构上的查找算法,假定每次查找都成功{if(L.t->data==key)returnL.t;elseif(L.t->data>key)for(p=L.h,i=1;p->data!=key;p=p->next,i++);elsefor(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);L.t=p;//更新t指针returnp;}//Search_CSList剖析:因为题目中假定每次查找都是成功的,所以本算法中没有对于查找失败的办理.由微积分可得,在等概率状况下,均匀查找长度约为n/3.9.30typedefstruct{DLNode*pre;intdata;DLNode*next;}DLNode;typedefstruct{DLNode*sp;intlength;}DSList;//供查找的双向循环链表种类DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表储存结构上的查找算法,假定每次查找都成功{p=L.sp;if(p->data>key){while(p->data>key)p=p->pre;L.sp=p;}elseif(p->data<key){while(p->data<key)p=p->next;L.sp=p;}returnp;}//Search_DSList剖析:此题的均匀查找长度与上一题同样,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T能否二叉排序树,是则返回1,不然返回0{if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data<last)flag=0;//与此中序前驱对比较last=T->data;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法还是借助中序遍向来实现if(last<x&&T->data>=x)//

找到了小于

x的最大元素printf("a=%d\n",last);if(last<=x&&T->data>x)//

找到了大于

x的最小元素printf("b=%d\n",T->data);last=T->data;if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{if(T->rchild)Print_NLT(T->rchild,x);if(T->data<x)exit( );//当碰到小于printf("%d\n",T->data);if(T->lchild)Print_NLT(T->lchild,x);//}//Print_NLT

x的元素时立刻结束运转先右后左的中序遍历9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并开释空间{if(T->rchild)Delete_NLT(T->rchild,x);if(T->data<x)exit( );//q=T;T=T->lchild;free(q);//假如树根不小于if(T)Delete_NLT(T,x);//

当碰到小于x的元素时立刻结束运转x,则删除树根,并以左子树的根作为新的树根持续在左子树中履行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于

a且小于

b的元素{p=T;while(!p->ltag)p=p->lchild;//while(p&&p->data<b)

找到最小元素{if(p->data>a)printf("%d\n",p->data);//

输出切合条件的元素if(p->rtag)p=p->rtag;else{p=p->rchild;while(!p->ltag)p=p->lchild;}//转到中序后继}//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{if(T->data<x)//插入到右边{if(T->rtag)//T

没有右子树时

,作为右孩子插入{p=T->rchild;q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->rchild=q;T->rtag=0;q->rtag=1;q->rchild=p;//改正原线索}elseBSTree_Insert_Key(T->rchild,x);//T

有右子树时

,插入右子树中}//ifelseif(T->data>x)//{

插入到左子树中if(!T->lchild)//T

没有左子树时

,作为左孩子插入{q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->lchild=q;q->rtag=1;q->rchild=T;//改正自己的线索}elseBSTree_Insert_Key(T->lchild,x);//T

有左子树时

,插入左子树中}//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素

x{BTNode*pre,*ptr,*suc;//ptr

为x所在结点

,pre

和suc分别指向

ptr

的前驱和后继p=T;last=NULL;//last一直指向目前结点p的前一个(前驱)while(!p->ltag)p=p->lchild;//找到中序开端元素while(p){if(p->data==x)//

找到了元素

x结点{pre=last;ptr=p;}elseif(last&&last->data==x)suc=p;//找到了x的后继if(p->rtag)p=p->rtag;else{p=p->rchild;while(!p->ltag)p=p->lchild;}//转到中序后继last=p;}//while//借助中序遍历找到元素x及其前驱和后继结点if(!ptr)returnERROR;//未找到待删结点Delete_BSTree(ptr);//删除x结点if(pre&&pre->rtag)pre->rchild=suc;//改正线索returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,依据线索二叉树的结构作了一些变动{q=T;if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树T=T->lchild;elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树T=T->rchild;elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树{p=T;r=T->lchild;while(!r->rtag){s=r;r=r->rchild;//找到结点的前驱r和r的双亲s}T->data=r->data;//用r取代T结点if(s!=T)s->rchild=r->lchild;elses->lchild=r->lchild;//重接r的左子树到其双亲结点上q=r;}//elsefree(q);//删除结点}//Delete_BSTree剖析:本算法采纳了先求出x结点的前驱和后继,再删除x结点的方法,这样改正线索时会比较简单,直接让前驱的线索指向后继就行了.假如试图在删除x结点的同时改正线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//

把二叉排序树

S归并到

T中{if(S->lchild)BSTree_Merge(T,S->lchild);if(S->rchild)BSTree_Merge(T,S->rchild);//Insert_Key(T,S);//插入元素}//BSTree_Merge

归并子树voidInsert_Node(Bitree&T,BTNode*S)//

把树结点

S插入到

T的适合地点上{if(S->data>T->data){if(!T->rchild)T->rchild=S;elseInsert_Node(T->rchild,S);}elseif(S->data<T->data){if(!T->lchild)T->lchild=S;elseInsert_Node(T->lchild,S);}S->lchild=NULL;//插入的新结点一定和本来的左右子树隔离关系S->rchild=NULL;//不然会致使树结构的杂乱}//Insert_Node剖析:这是一个与课本上不一样的插入算法.在归并过程中,其实不开释或新建任何结点,而是采纳改正指针的方式来达成归并.这样,就一定依据后序序列把一棵树中的元素逐一连结到另一棵树上,不然将会致使树的结构的杂乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,此中A的元素所有小于等于x,B的元素所有大于x{if(T->lchild)BSTree_Split(T->lchild,A,B,x);if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树if(T->data<=x)Insert_Node(A,T);elseInsert_Node(B,T);//将元素结点插入适合的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//

把树结点

S插入到

T的适合地点上{if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的状况elseif(S->data>T->data)//其余部分与上一题同{if(!T->rchild)T->rchild=S;elseInsert_Node(T->rchild,S);}elseif(S->data<T->data){if(!T->lchild)T->lchild=S;elseInsert_Node(T->lchild,S);}S->lchild=NULL;S->rchild=NULL;}//Insert_Key9.40typedefstruct{intdata;intbf;intlsize;//lsize域表示该结点的左子树的结点总数加1BlcNode*lchild,*rchild;}BlcNode,*BlcTree;//含lsize域的均衡二叉排序树种类BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的均衡二叉排序树T中确立第k小的结点指针{if(!T)returnNULL;//k小于1或大于树结点总数if(T->lsize==k)returnT;//就是这个结点elseif(T->lsize>k)returnLocate_BlcTree(T->lchild,k);//在左子树中找寻elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中找寻,注意要改正k的值}//Locate_BlcTree9.41typedefstruct{enum{LEAF,BRANCH}tag;//结点类型表记intkeynum;BPLinkparent;//双亲指针intkey[MAXCHILD];//重点字union{BPLinkchild[MAXCHILD];//非叶结点的孩子指针struct{rectype*info[MAXCHILD];//叶子结点的信息指针BPNode*next;//

指向下一个叶子结点的链接}leaf;}}BPNode,*BPLink,*BPTree;//B+

树及其结点种类StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+

树中按关键字随机查找的算法

,返回包括重点字的叶子结点的指针

ptr

以及重点字在叶子结点中的地点pos{p=T;while(p.tag==BRANCH)//{

沿分支向下查找for(i=0;i<p->keynum&&key>p->key[i];i++);//if(i==p->keynum)returnERROR;//重点字太大p=p->child[i];

确立重点字所在子树}for(i=0;i<p->keynum&&key!=p->key[i];i++);//在叶子结点中查找if(i==p->keynum)returnERROR;//找不到重点字ptr=p;pos=i;returnOK;}//BPTree_Search9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//入字符串key,StringType的结构见第四章

在Trie

树T中插{q=(TrieNode*)malloc(sizeof(TrieNode));q->kind=LEAF;q->lf.k=key;//建叶子结点klen=key[0];p=T;i=1;while(p&&i<=klen&&p->bh.ptr[ord(key[i])]){last=p;p=p->bh.ptr[ord(key[i])];i++;}//自上而下查找if(p->kind==BRANCH)//假如最后落到分支结点(无同义词):{p->bh.ptr[ord(key[i])]=q;//p->bh.num++;

直接连上叶子}else//

假如最后落到叶子结点

(有同义词

):{r=(TrieNode*)malloc(sizeof(TrieNode));//成立新的分支结点last->bh.ptr[ord(key[i-1])]=r;//用新分支结点取代老叶子结点和上一层的联系r->kind=BRANCH;r->bh.num=2;r->bh.ptr[ord(key[i])]=q;r->bh.ptr[ord(p->lf.k[i])]=p;//

新分支结点与新老两个叶子结点相连}}//TrieTree_Insert_Key剖析:当自上而下的查找结束时,存在两种状况.一种状况,树中没有待插入重点字的同义词,此时只需新建一个叶子结点并连到分支结点上即可.另一种状况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新重点字的叶子结点连到新分支结点的下一层.9.43StatusTrieTree_Delete_Key(TrieTree&T,StringTypekey)//删除字符串key

在

Trie

树T中{p=T;i=1;while(p&&p->kind==BRANCH&&i<=key[0])//查找待删除元素{last=p;p=p->bh.ptr[ord(key[i])];i++;}if(p&&p->kind==LEAF&&p->lf.k=key)//找到了待删除元素{last->bh.ptr[ord(key[i-1])]=NULL;free(p);returnOK;}elsereturnERROR;//没找到待删除元素}//TrieTree_Delete_Key9.44voidPrint_Hash(HashTableH)//按第一个字母次序输出Hash表中的所相重点字,此中办理矛盾采纳线性探测开放定址法{for(i=1;i<=26;i++)for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])//线性探测if(H(H.elem[j].key)==i)printf("%s\n",H.elem[j]);}//Print_HashintH(char*s)//{

求Hash函数if(s)returns[0]-96;//

求重点字第一个字母的字母序号

(小写)elsereturn0;}//H9.45typedef*LNode[MAXSIZE]CHashTable;//

链地点

Hash表种类StatusBuild_Hash(CHashTable&T,intm)//长为m,用链地点法办理矛盾.

输入一组重点字

,成立

Hash表,表{if(m<1)returnERROR;T=malloc(m*sizeof(WORD));//

成立表头指针向量for(i=0;i<m;i++)T[i]=NULL;while((key=Inputkey( ))!=NULL)//

假定

Inputkey

函数用于从键盘输入关键字{q=(LNode*)malloc(sizeof(LNode));q->data=key;q->next=NULL;n=H(key);if(!T[n])T[n]=q;//作为链表的第一个结点else{for(p=T[n];p->next;p=p->next);p->next=q;//插入链表尾部.本算法不考虑排序问题.}}//whilereturnOK;}//Build_Hash9.46StatusLocate_Hash(HashTableH,introw,intcol,KeyTypekey,int&k)//依据队列值在Hash表表示的稀少矩阵中确立元素key的地点k{h=2*(100*(row/10)+col/10);//作者设计的Hash函数while(H.elem[h].key&&!EQ(H.elem[h].key,key))h=(h+1)%20000;if(EQ(H.elem[h].key,key))k=h;elsek=NULL;}//Locate_Hash剖析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所构成的四位数再乘以二,用线性探测法办理矛盾.当矩阵的元素是随机散布时,查找的时间复杂度为O(1).另解：第九章查找习题及答案题号：151617181920212223一、基础知识题1.对含有n个互不同样元素的会合，同时找最大元和最小元起码需进行多少次比较?答：我们能够建立两个变量max和min用于寄存最大元和最小元(的地点)，第一次取两个元素进行比较，大的放入max，小的放入min，从第2次开始，每次取一个元素先和max比较，假如大于max则以它替代max，并结束本次比较；若小于max则再与min对比较，在最好的状况下，一路比较下去都不用和min对比较，所以这类状况下，起码要进行n-1次比较就能找到最大元和最小元。(趁便说一下，最坏状况下，要进行2n-3次比较才能获得结果)2.若对拥有n个元素的有序的次序表和无序的次序表分别进行次序查找，试在下述两种状况下分别议论二者在等概率时的均匀查找长度：(1)查找不行功，即表中无重点字等于给定值K的记录；(2)查找成功，即表中相重点字等于给定值K的记录。答：查找不行功时，需进行n+1次比较才能确立查找失败。所以均匀查找长度为n+1，这时有序表和无序表是同样的。查找成功时，均匀查找长度为(n+1)/2,有序表和无序表也是同样的。因为次序查找对表的原始序列的有序性不感兴趣。画出对长度为18的有序的次序表进行二分查找的判断树，并指出在等概率时查找成功的均匀查找长度，以及查找失败时所需的最多的重点字比较次数。答：请看题图。等概率状况下，查找成功的均匀查找长度为：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556也能够用公式代，大概为：ASL=(18+1)lg(18+1)/18-1=3.346查找失败时，最多的重点字比较次树不超出判断树的深度，此处为5.如图：4.为何有序的单链表不可以进行折半查找?答：因为链表没法进行随机接见，假如要接见链表的中间结点，就一定先重新结点开始进行挨次接见，这就要浪费好多时间，还不如进行次序查找，并且，用链储存结构将没法判断二分的过程能否结束，所以没法用链表实现二分查找。5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。解：b的查找过程以下(此中括号表示目前查找区间，圆括号表示目前比较的重点字)下标：第一次比较：[abcdef(g)hijkpq]第二次比较：[ab(c)def]ghijkpq第三次比较：[a(b)]cdefghijkpq经过三次比较，查找成功。的查找过程以下：[abcdef(g)hijkpq]一次比较成功。的查找过程以下：下标：第一次比较：[abcdef(g)hijkpq]第二次比较：abcdefg[hi(j)kpq]第三次比较：abcdefghij[k(p)q]第四次比较：abcdefghij[k]pq]经过四次比较，查找失败。将(for,case,while,class,protected,virtual,public,private,do,template,const,if,int)中的重点字挨次插入初态为空的二叉排序树中，请画出所获得的树T。而后画出删去for以后的二叉排序树T',若再将for插入T'中获得的二叉排序树T''能否与T同样?最后给出T"的先序、中序和后序序列。答：见题图:T"的先序序列是：docaseclassconstwhileprotectedprivateifforintvirtualpublictemplateT"的中序序列是：caseclassconstdoforifintprivateprotectedpublictemplatevirtualwhileT"的后序序列是：constclasscaseforintifprivatetemplatepublicvirtualprotectedwhiledo二叉排序树T以下列图：删去for后的二叉排序树以下列图：圈内的for表示再插入后的结点：7.对给定的重点字会合，以不一样的序次插入初始为空的树中，能否有可能获得同一棵二叉排序树?答：有可能。若有两个序列：3，1，2，4和3，4，1，2，它们插入空树所得的二叉排序树是同样的。8.将二叉排序树T的先序序列中的重点字挨次插入一空树中，所得和二叉排序树T'与T"能否同样?为何?答：这两棵二叉树完整同样。9.设二叉排序树中重点字由1至1000的整数构成，现要查找重点字为363的结点，下述重点字序列哪一个不行能是在二叉排序树上查找到的序列?(a)2，252，401，398，330,344，397，363；(b)924,220,911,244,898,258,362,363;(c)925,202,911,240,912,245,363;(d)2,399,387,219,266,382,381,278,363.答：(c)是不行能查找到的序列。我们能够把这四个序列各插入到一个初始为空的二叉排序树中，结果能够发现，(c)序列所形成的不是一条路径，而是有分支的，可见它是不行能在查找过程中接见到的序列。10.设二叉排序树中重点字互不同样，则此中最小元必无左孩子，最大元必无右孩子。此命题能否正确?最小元和最大元必定是叶子吗?一个新结点老是插在二叉排序树的某叶子上吗?答：此命题正确。假定最小元有左孩子，则依据二叉排序树性质，此左孩子应比最小元更小，这样一来就产生矛盾了，所以最小元不行能有左孩子，对于最大元也是这个道理。但最大元和最小元不必定是叶子，它也能够是根、内部结点(分支结点)等，这得依据插入结点时的序次而定。如3，1，2，4这个会合，依据不一样的插入序次能够获得不一样的二叉排序树：○3\○1○4\○2○2\○1○3\○4○4\○3\○2\○1○2\○1○4/○3新结点老是插入在二叉排序树的某个叶子上的。11.在一棵m阶的B-树中，当将一重点字插入某结点而惹起该结点的分裂时，此结点原有多少个重点字?若删去某结点中的一个重点字，而致使结点归并时，该结点中原有几个重点字?答：在此树中，若因为一重点字的插入某结点而惹起该结点的分裂时，则该结点原有m-1个重点字。若删去某结点中一个重点字而致使结点归并时，该结点中原有┌m/2┐-1个重点字。12.在一棵B-树中，空指针数老是比重点字数多一个，此说法能否正确?请问包括8个重点字的3阶B-树(即2-3树)最多有几个结点?最罕有几个结点?画出这两种状况的B-树。答：这个说法是正确的。包括8个重点字的3阶B-树最多有7个结点，最罕有4个结点。见题图。:图以下：13.从空树开始，挨次输入20，30，50，52，60，68，70，画出成立2-3树的过程。并画出删除50和68后的B-树状态。答：过程以下：(1)插入20，30：(2)插入50：(3)插入52：(4)插入60：(5)插入68：(6)插入70：(7)删去50：(8)删去6814。画出挨次插入z,v,o,p,w,y到图9.12(h)所示的5阶B-树的过程。答：如图：第一步，插入z:第二、三步,插入v,o：第四五六步，插入p,w,y:15.在含有n个重点字的m阶B-树中进行查找，至多读盘多少次?完整均衡的二叉排序树的读盘次数大概比它大多少倍?答：在含有n个重点字的m阶B-树中进行查找至多读盘次数不超出B-树高h，即logt((n+1)/2)+1,(注，此处t为底，值是除根外的每个内部结点的最小度数┌m/2┐).完整均衡的二叉树高为lgn,所以它的读盘次数至多也是lgn，它与上述B-树的读盘次数的比值约为lgt倍(此处底是2).16.为何在内存中使用的B-树往常是3阶的，而不使用更高阶的B-树?答：因为查找等操作的cpu时间在B-树上是O(lgn?(m/lgt)),而m/lgt>1,所以m较大时它所费时间比均衡的二叉排序树上相应操作时间大得多，所以，仅在内存中使用的B-树往常取最小值3.17.为何二叉排序树长高时，新结点老是一个叶子，而B-树长高时，新结点老是根?哪一种长高能保证树均衡?答：因为在二叉排序树中，重点字老是作为一个叶子结点插入以本来的树中，所以当树增高时，新结点老是一个叶子；而B-树中重点字插入老是插入到叶子结点内部，在叶结点中的重点字数量还没有超出它能够容纳的数量以前是不会增添结点的，当重点字数超出结点可容纳的数量时，叶结点就会发生疏裂，产生一个新结点(但不必定惹起树增高)，并且将此中的中间结点传至上一层，只有当这类分裂操作传达至根结点并惹起根结点的分裂时，才能惹起树高增添，此时产生一个新的根结点。所以说B树长高时，新结点老是根。明显，后一种长高总能保证树的均衡。18.已知重点字序列为(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT)试为它们设计一个散列函数，将其映照到区间[0..n-1]上，要求碰撞尽可能的少。这里n=11,13,17,19.解：我的设计的散列函数是这样的，把重点字串中的每一个字符按其所在地点分别将其ASCII值乘以一个不一样的数，而后把这些值相加的和去对n求余，余数即为散列表中的地点。函数以下：intHash(charkey[]){return(int)(key[0]+key[1]*0.618+key[2]*10)%n;}我们能够设计一个程序来看看用这个散列函数获得的所相重点字映照到区间的地点：#include<stdio.h>#definen11file://先用11来代入，我们能够用13，17，19挨次代入考证intHash(charkey[]){return(int)(key[0]+key[1]*0.618+key[2]*10)%n;file://此处我用了系数1，0.618和10，你也能够用其余的数代入看有没有更好的系数}voidmain( ){chars[10][4]={"PAL","LAP","PAM","MAP","PAT","PET","SET","SAT","TAT","BAT"};以上用一个二维数组来寄存重点字序列inti;for(i=0;i<10;i++){printf("%d",Hash(s));}}19.对于一组给定的、固定不变的重点字序列，有可能设计出无矛盾的散列函数H，此时称H为齐备的散列函数(perfecthashingfunction)，若H能无矛盾地将重点字完整填满散列表，则称H是最小齐备(minimalperfect)的散列函数。往常找齐备的散列函数特别困难，找最小齐备的散列函数就更困难。请问：(1)若h是已知重点字会合K的齐备的散列函数，若要增添一个新的重点字到会合K，一般状况下H还是齐备的吗?(2)已知重点字会合为(81，129，301，38，434，216，412，487，234)，散列函数为H(x)=(x+18)/63,请问H是齐备的吗?它是最小齐备的吗?(3)考虑由字符串构成的重点字会合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，试为散列表[0..6]设计一个齐备的散列函数。(提示：考虑每个字