《數(shù)據(jù)結(jié)構(gòu)題集》第9章查找

《數(shù)據(jù)結(jié)構(gòu)題集》答案第9章查找《數(shù)據(jù)結(jié)構(gòu)題集》答案第9章查找/《數(shù)據(jù)結(jié)構(gòu)題集》答案第9章查找第九章查找9.25intSearch_Sq(SSTableST,intkey)//在有序表上一次序查找的算法,監(jiān)督哨設(shè)在高低標(biāo)端{(lán)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剖析:本算法查找成功狀況下的均勻查找長(zhǎng)度為ST.length/2,不行功狀況下為ST.length.9.26intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的遞歸算法{if(low>high)return0;//查找不到時(shí)返回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)//折半查找,返回小于或等于待查元素的最后一個(gè)結(jié)點(diǎn)號(hào){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)//查找結(jié)束的條件returnmid;elseif(key<r[mid].key)high=mid;elselow=mid;}//本算法不存在查找失敗的狀況,不需要return0;}//Locate_Bin9.28typedefstruct{intmaxkey;intfirstloc;}Index;typedefstruct{int*elem;intlength;Indexidx[MAXBLOCK];//每塊開(kāi)端位置和最大元素

,此中

idx[0]

不利用,其內(nèi)容初始化為{0,0}以利于折半查找intblknum;//塊的數(shù)量}IdxSqList;//索引次序表種類intSearch_IdxSeq(IdxSqListL,intkey)//

分塊查找,用折半查找法確立記錄所在塊,塊內(nèi)采納次序查找法{if(key>L.idx[L.blknum].maxkey)returnERROR;//low=1;high=L.blknum;found=0;

超出最大元素while(low<=high&&!found)//折半查找記錄所在塊號(hào)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;//設(shè)置監(jiān)督哨for(k=j;L.elem[k]!=key;k--);//次序查找L.elem[i-1]=temp;//恢復(fù)元素if(k<i)returnERROR;//未找到returnk;}//Search_IdxSeq剖析:在塊內(nèi)進(jìn)行次序查找時(shí),假如需要設(shè)置監(jiān)督哨,則一定先保留相鄰塊的相鄰元素,免得數(shù)據(jù)丟掉.9.29typedefstruct{LNode*h;//hLNode*t;//t

指向最小元素指向上一次查找的結(jié)點(diǎn)}CSList;LNode*Search_CSList(CSList&L,intkey)//在有序單循環(huán)鏈表儲(chǔ)存結(jié)構(gòu)上的查找算法,假定每次查找都成功{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剖析:因?yàn)轭}目中假定每次查找都是成功的,所以本算法中沒(méi)有對(duì)于查找失敗的辦理.由微積分可得,在等概率狀況下,均勻查找長(zhǎng)度約為n/3.9.30typedefstruct{DLNode*pre;intdata;DLNode*next;}DLNode;typedefstruct{DLNode*sp;intlength;}DSList;//供查找的雙向循環(huán)鏈表種類DLNode*Search_DSList(DSList&L,intkey)//在有序雙向循環(huán)鏈表儲(chǔ)存結(jié)構(gòu)上的查找算法,假定每次查找都成功{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剖析:此題的均勻查找長(zhǎng)度與上一題同樣,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判斷二叉樹(shù)T能否二叉排序樹(shù),是則返回1,不然返回0{if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data<last)flag=0;//與此中序前驅(qū)對(duì)比較last=T->data;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序樹(shù)T中小于x的最大元素和大于x的最小元素{if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法還是借助中序遍向來(lái)實(shí)現(xiàn)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)//從大到小輸出二叉排序樹(shù)T中所有不小于x的元素{if(T->rchild)Print_NLT(T->rchild,x);if(T->data<x)exit( );//當(dāng)碰到小于printf("%d\n",T->data);if(T->lchild)Print_NLT(T->lchild,x);//}//Print_NLT

x的元素時(shí)立刻結(jié)束運(yùn)轉(zhuǎn)先右后左的中序遍歷9.34voidDelete_NLT(BiTree&T,intx)//刪除二叉排序樹(shù)T中所有不小于x元素結(jié)點(diǎn),并開(kāi)釋空間{if(T->rchild)Delete_NLT(T->rchild,x);if(T->data<x)exit( );//q=T;T=T->lchild;free(q);//假如樹(shù)根不小于if(T)Delete_NLT(T,x);//

當(dāng)碰到小于x的元素時(shí)立刻結(jié)束運(yùn)轉(zhuǎn)x,則刪除樹(shù)根,并以左子樹(shù)的根作為新的樹(shù)根持續(xù)在左子樹(shù)中履行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印輸出后繼線索二叉排序樹(shù)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;}//轉(zhuǎn)到中序后繼}//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后繼線索二叉排序樹(shù)T中插入元素x{if(T->data<x)//插入到右邊{if(T->rtag)//T

沒(méi)有右子樹(shù)時(shí)

,作為右孩子插入{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

有右子樹(shù)時(shí)

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

插入到左子樹(shù)中if(!T->lchild)//T

沒(méi)有左子樹(shù)時(shí)

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

有左子樹(shù)時(shí)

,插入左子樹(shù)中}//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后繼線索二叉排序樹(shù)T中刪除元素

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

為x所在結(jié)點(diǎn)

,pre

和suc分別指向

ptr

的前驅(qū)和后繼p=T;last=NULL;//last一直指向目前結(jié)點(diǎn)p的前一個(gè)(前驅(qū))while(!p->ltag)p=p->lchild;//找到中序開(kāi)端元素while(p){if(p->data==x)//

找到了元素

x結(jié)點(diǎn){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;}//轉(zhuǎn)到中序后繼last=p;}//while//借助中序遍歷找到元素x及其前驅(qū)和后繼結(jié)點(diǎn)if(!ptr)returnERROR;//未找到待刪結(jié)點(diǎn)Delete_BSTree(ptr);//刪除x結(jié)點(diǎn)if(pre&&pre->rtag)pre->rchild=suc;//改正線索returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//課本上給出的刪除二叉排序樹(shù)的子樹(shù)T的算法,依據(jù)線索二叉樹(shù)的結(jié)構(gòu)作了一些變動(dòng){q=T;if(!T->ltag&&T->rtag)//結(jié)點(diǎn)無(wú)右子樹(shù),此時(shí)只需重接其左子樹(shù)T=T->lchild;elseif(T->ltag&&!T->rtag)//結(jié)點(diǎn)無(wú)左子樹(shù),此時(shí)只需重接其右子樹(shù)T=T->rchild;elseif(!T->ltag&&!T->rtag)//結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù){p=T;r=T->lchild;while(!r->rtag){s=r;r=r->rchild;//找到結(jié)點(diǎn)的前驅(qū)r和r的雙親s}T->data=r->data;//用r取代T結(jié)點(diǎn)if(s!=T)s->rchild=r->lchild;elses->lchild=r->lchild;//重接r的左子樹(shù)到其雙親結(jié)點(diǎn)上q=r;}//elsefree(q);//刪除結(jié)點(diǎn)}//Delete_BSTree剖析:本算法采納了先求出x結(jié)點(diǎn)的前驅(qū)和后繼,再刪除x結(jié)點(diǎn)的方法,這樣改正線索時(shí)會(huì)比較簡(jiǎn)單,直接讓前驅(qū)的線索指向后繼就行了.假如試圖在刪除x結(jié)點(diǎn)的同時(shí)改正線索,則問(wèn)題反而復(fù)雜化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//

把二叉排序樹(shù)

S歸并到

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

歸并子樹(shù)voidInsert_Node(Bitree&T,BTNode*S)//

把樹(shù)結(jié)點(diǎn)

S插入到

T的適合地點(diǎn)上{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;//插入的新結(jié)點(diǎn)一定和本來(lái)的左右子樹(shù)隔離關(guān)系S->rchild=NULL;//不然會(huì)致使樹(shù)結(jié)構(gòu)的雜亂}//Insert_Node剖析:這是一個(gè)與課本上不一樣的插入算法.在歸并過(guò)程中,其實(shí)不開(kāi)釋或新建任何結(jié)點(diǎn),而是采納改正指針的方式來(lái)達(dá)成歸并.這樣,就一定依據(jù)后序序列把一棵樹(shù)中的元素逐一連結(jié)到另一棵樹(shù)上,不然將會(huì)致使樹(shù)的結(jié)構(gòu)的雜亂.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序樹(shù)T分裂為兩棵二叉排序樹(shù)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);//分裂左右子樹(shù)if(T->data<=x)Insert_Node(A,T);elseInsert_Node(B,T);//將元素結(jié)點(diǎn)插入適合的樹(shù)中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//

把樹(shù)結(jié)點(diǎn)

S插入到

T的適合地點(diǎn)上{if(!T)T=S;//考慮到剛開(kāi)始分裂時(shí)樹(shù)A和樹(shù)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域表示該結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)總數(shù)加1BlcNode*lchild,*rchild;}BlcNode,*BlcTree;//含lsize域的均衡二叉排序樹(shù)種類BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的均衡二叉排序樹(shù)T中確立第k小的結(jié)點(diǎn)指針{if(!T)returnNULL;//k小于1或大于樹(shù)結(jié)點(diǎn)總數(shù)if(T->lsize==k)returnT;//就是這個(gè)結(jié)點(diǎn)elseif(T->lsize>k)returnLocate_BlcTree(T->lchild,k);//在左子樹(shù)中找尋elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子樹(shù)中找尋,注意要改正k的值}//Locate_BlcTree9.41typedefstruct{enum{LEAF,BRANCH}tag;//結(jié)點(diǎn)類型表記intkeynum;BPLinkparent;//雙親指針intkey[MAXCHILD];//重點(diǎn)字union{BPLinkchild[MAXCHILD];//非葉結(jié)點(diǎn)的孩子指針struct{rectype*info[MAXCHILD];//葉子結(jié)點(diǎn)的信息指針BPNode*next;//

指向下一個(gè)葉子結(jié)點(diǎn)的鏈接}leaf;}}BPNode,*BPLink,*BPTree;//B+

樹(shù)及其結(jié)點(diǎn)種類StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+

樹(shù)中按關(guān)鍵字隨機(jī)查找的算法

,返回包括重點(diǎn)字的葉子結(jié)點(diǎn)的指針

ptr

以及重點(diǎn)字在葉子結(jié)點(diǎn)中的地點(diǎn)pos{p=T;while(p.tag==BRANCH)//{

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

確立重點(diǎn)字所在子樹(shù)}for(i=0;i<p->keynum&&key!=p->key[i];i++);//在葉子結(jié)點(diǎn)中查找if(i==p->keynum)returnERROR;//找不到重點(diǎn)字ptr=p;pos=i;returnOK;}//BPTree_Search9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//入字符串key,StringType的結(jié)構(gòu)見(jiàn)第四章

在Trie

樹(shù)T中插{q=(TrieNode*)malloc(sizeof(TrieNode));q->kind=LEAF;q->lf.k=key;//建葉子結(jié)點(diǎn)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)//假如最后落到分支結(jié)點(diǎn)(無(wú)同義詞):{p->bh.ptr[ord(key[i])]=q;//p->bh.num++;

直接連上葉子}else//

假如最后落到葉子結(jié)點(diǎn)

(有同義詞

):{r=(TrieNode*)malloc(sizeof(TrieNode));//成立新的分支結(jié)點(diǎn)last->bh.ptr[ord(key[i-1])]=r;//用新分支結(jié)點(diǎn)取代老葉子結(jié)點(diǎn)和上一層的聯(lián)系r->kind=BRANCH;r->bh.num=2;r->bh.ptr[ord(key[i])]=q;r->bh.ptr[ord(p->lf.k[i])]=p;//

新分支結(jié)點(diǎn)與新老兩個(gè)葉子結(jié)點(diǎn)相連}}//TrieTree_Insert_Key剖析:當(dāng)自上而下的查找結(jié)束時(shí),存在兩種狀況.一種狀況,樹(shù)中沒(méi)有待插入重點(diǎn)字的同義詞,此時(shí)只需新建一個(gè)葉子結(jié)點(diǎn)并連到分支結(jié)點(diǎn)上即可.另一種狀況,有同義詞,此時(shí)要把同義詞的葉子結(jié)點(diǎn)與樹(shù)斷開(kāi),在斷開(kāi)的部位新建一個(gè)下一層的分支結(jié)點(diǎn),再把同義詞和新重點(diǎn)字的葉子結(jié)點(diǎn)連到新分支結(jié)點(diǎn)的下一層.9.43StatusTrieTree_Delete_Key(TrieTree&T,StringTypekey)//刪除字符串key

在

Trie

樹(shù)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;//沒(méi)找到待刪除元素}//TrieTree_Delete_Key9.44voidPrint_Hash(HashTableH)//按第一個(gè)字母次序輸出Hash表中的所相重點(diǎn)字,此中辦理矛盾采納線性探測(cè)開(kāi)放定址法{for(i=1;i<=26;i++)for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])//線性探測(cè)if(H(H.elem[j].key)==i)printf("%s\n",H.elem[j]);}//Print_HashintH(char*s)//{

求Hash函數(shù)if(s)returns[0]-96;//

求重點(diǎn)字第一個(gè)字母的字母序號(hào)

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

鏈地點(diǎn)

Hash表種類StatusBuild_Hash(CHashTable&T,intm)//長(zhǎng)為m,用鏈地點(diǎn)法辦理矛盾.

輸入一組重點(diǎn)字

,成立

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

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

假定

Inputkey

函數(shù)用于從鍵盤(pán)輸入關(guān)鍵字{q=(LNode*)malloc(sizeof(LNode));q->data=key;q->next=NULL;n=H(key);if(!T[n])T[n]=q;//作為鏈表的第一個(gè)結(jié)點(diǎn)else{for(p=T[n];p->next;p=p->next);p->next=q;//插入鏈表尾部.本算法不考慮排序問(wèn)題.}}//whilereturnOK;}//Build_Hash9.46StatusLocate_Hash(HashTableH,introw,intcol,KeyTypekey,int&k)//依據(jù)隊(duì)列值在Hash表表示的稀少矩陣中確立元素key的地點(diǎn)k{h=2*(100*(row/10)+col/10);//作者設(shè)計(jì)的Hash函數(shù)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表長(zhǎng)20000,裝填因子為50%,Hash函數(shù)為行數(shù)前兩位和列數(shù)前兩位所構(gòu)成的四位數(shù)再乘以二,用線性探測(cè)法辦理矛盾.當(dāng)矩陣的元素是隨機(jī)散布時(shí),查找的時(shí)間復(fù)雜度為O(1).另解：第九章查找習(xí)題及答案題號(hào)：151617181920212223一、基礎(chǔ)知識(shí)題1.對(duì)含有n個(gè)互不同樣元素的會(huì)合，同時(shí)找最大元和最小元起碼需進(jìn)行多少次比較?答：我們能夠建立兩個(gè)變量max和min用于寄存最大元和最小元(的地點(diǎn))，第一次取兩個(gè)元素進(jìn)行比較，大的放入max，小的放入min，從第2次開(kāi)始，每次取一個(gè)元素先和max比較，假如大于max則以它替代max，并結(jié)束本次比較；若小于max則再與min對(duì)比較，在最好的狀況下，一路比較下去都不用和min對(duì)比較，所以這類狀況下，起碼要進(jìn)行n-1次比較就能找到最大元和最小元。(趁便說(shuō)一下，最壞狀況下，要進(jìn)行2n-3次比較才能獲得結(jié)果)2.若對(duì)擁有n個(gè)元素的有序的次序表和無(wú)序的次序表分別進(jìn)行次序查找，試在下述兩種狀況下分別議論二者在等概率時(shí)的均勻查找長(zhǎng)度：(1)查找不行功，即表中無(wú)重點(diǎn)字等于給定值K的記錄；(2)查找成功，即表中相重點(diǎn)字等于給定值K的記錄。答：查找不行功時(shí)，需進(jìn)行n+1次比較才能確立查找失敗。所以均勻查找長(zhǎng)度為n+1，這時(shí)有序表和無(wú)序表是同樣的。查找成功時(shí)，均勻查找長(zhǎng)度為(n+1)/2,有序表和無(wú)序表也是同樣的。因?yàn)榇涡虿檎覍?duì)表的原始序列的有序性不感興趣。畫(huà)出對(duì)長(zhǎng)度為18的有序的次序表進(jìn)行二分查找的判斷樹(shù)，并指出在等概率時(shí)查找成功的均勻查找長(zhǎng)度，以及查找失敗時(shí)所需的最多的重點(diǎn)字比較次數(shù)。答：請(qǐng)看題圖。等概率狀況下，查找成功的均勻查找長(zhǎng)度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556也能夠用公式代，大概為：ASL=(18+1)lg(18+1)/18-1=3.346查找失敗時(shí)，最多的重點(diǎn)字比較次樹(shù)不超出判斷樹(shù)的深度，此處為5.如圖：4.為何有序的單鏈表不可以進(jìn)行折半查找?答：因?yàn)殒湵頉](méi)法進(jìn)行隨機(jī)接見(jiàn)，假如要接見(jiàn)鏈表的中間結(jié)點(diǎn)，就一定先重新結(jié)點(diǎn)開(kāi)始進(jìn)行挨次接見(jiàn)，這就要浪費(fèi)好多時(shí)間，還不如進(jìn)行次序查找，并且，用鏈儲(chǔ)存結(jié)構(gòu)將沒(méi)法判斷二分的過(guò)程能否結(jié)束，所以沒(méi)法用鏈表實(shí)現(xiàn)二分查找。5.設(shè)有序表為(a,b,c,e,f,g,i,j,k,p,q),請(qǐng)分別畫(huà)出對(duì)給定值b,g和n進(jìn)行折半查找的過(guò)程。解：b的查找過(guò)程以下(此中括號(hào)表示目前查找區(qū)間，圓括號(hào)表示目前比較的重點(diǎn)字)下標(biāo)：第一次比較：[abcdef(g)hijkpq]第二次比較：[ab(c)def]ghijkpq第三次比較：[a(b)]cdefghijkpq經(jīng)過(guò)三次比較，查找成功。的查找過(guò)程以下：[abcdef(g)hijkpq]一次比較成功。的查找過(guò)程以下：下標(biāo)：第一次比較：[abcdef(g)hijkpq]第二次比較：abcdefg[hi(j)kpq]第三次比較：abcdefghij[k(p)q]第四次比較：abcdefghij[k]pq]經(jīng)過(guò)四次比較，查找失敗。將(for,case,while,class,protected,virtual,public,private,do,template,const,if,int)中的重點(diǎn)字挨次插入初態(tài)為空的二叉排序樹(shù)中，請(qǐng)畫(huà)出所獲得的樹(shù)T。而后畫(huà)出刪去for以后的二叉排序樹(shù)T',若再將for插入T'中獲得的二叉排序樹(shù)T''能否與T同樣?最后給出T"的先序、中序和后序序列。答：見(jiàn)題圖:T"的先序序列是：docaseclassconstwhileprotectedprivateifforintvirtualpublictemplateT"的中序序列是：caseclassconstdoforifintprivateprotectedpublictemplatevirtualwhileT"的后序序列是：constclasscaseforintifprivatetemplatepublicvirtualprotectedwhiledo二叉排序樹(shù)T以下列圖：刪去for后的二叉排序樹(shù)以下列圖：圈內(nèi)的for表示再插入后的結(jié)點(diǎn)：7.對(duì)給定的重點(diǎn)字會(huì)合，以不一樣的序次插入初始為空的樹(shù)中，能否有可能獲得同一棵二叉排序樹(shù)?答：有可能。若有兩個(gè)序列：3，1，2，4和3，4，1，2，它們插入空樹(shù)所得的二叉排序樹(shù)是同樣的。8.將二叉排序樹(shù)T的先序序列中的重點(diǎn)字挨次插入一空樹(shù)中，所得和二叉排序樹(shù)T'與T"能否同樣?為何?答：這兩棵二叉樹(shù)完整同樣。9.設(shè)二叉排序樹(shù)中重點(diǎn)字由1至1000的整數(shù)構(gòu)成，現(xiàn)要查找重點(diǎn)字為363的結(jié)點(diǎn)，下述重點(diǎn)字序列哪一個(gè)不行能是在二叉排序樹(shù)上查找到的序列?(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)是不行能查找到的序列。我們能夠把這四個(gè)序列各插入到一個(gè)初始為空的二叉排序樹(shù)中，結(jié)果能夠發(fā)現(xiàn)，(c)序列所形成的不是一條路徑，而是有分支的，可見(jiàn)它是不行能在查找過(guò)程中接見(jiàn)到的序列。10.設(shè)二叉排序樹(shù)中重點(diǎn)字互不同樣，則此中最小元必?zé)o左孩子，最大元必?zé)o右孩子。此命題能否正確?最小元和最大元必定是葉子嗎?一個(gè)新結(jié)點(diǎn)老是插在二叉排序樹(shù)的某葉子上嗎?答：此命題正確。假定最小元有左孩子，則依據(jù)二叉排序樹(shù)性質(zhì)，此左孩子應(yīng)比最小元更小，這樣一來(lái)就產(chǎn)生矛盾了，所以最小元不行能有左孩子，對(duì)于最大元也是這個(gè)道理。但最大元和最小元不必定是葉子，它也能夠是根、內(nèi)部結(jié)點(diǎn)(分支結(jié)點(diǎn))等，這得依據(jù)插入結(jié)點(diǎn)時(shí)的序次而定。如3，1，2，4這個(gè)會(huì)合，依據(jù)不一樣的插入序次能夠獲得不一樣的二叉排序樹(shù)：○3\○1○4\○2○2\○1○3\○4○4\○3\○2\○1○2\○1○4/○3新結(jié)點(diǎn)老是插入在二叉排序樹(shù)的某個(gè)葉子上的。11.在一棵m階的B-樹(shù)中，當(dāng)將一重點(diǎn)字插入某結(jié)點(diǎn)而惹起該結(jié)點(diǎn)的分裂時(shí)，此結(jié)點(diǎn)原有多少個(gè)重點(diǎn)字?若刪去某結(jié)點(diǎn)中的一個(gè)重點(diǎn)字，而致使結(jié)點(diǎn)歸并時(shí)，該結(jié)點(diǎn)中原有幾個(gè)重點(diǎn)字?答：在此樹(shù)中，若因?yàn)橐恢攸c(diǎn)字的插入某結(jié)點(diǎn)而惹起該結(jié)點(diǎn)的分裂時(shí)，則該結(jié)點(diǎn)原有m-1個(gè)重點(diǎn)字。若刪去某結(jié)點(diǎn)中一個(gè)重點(diǎn)字而致使結(jié)點(diǎn)歸并時(shí)，該結(jié)點(diǎn)中原有┌m/2┐-1個(gè)重點(diǎn)字。12.在一棵B-樹(shù)中，空指針數(shù)老是比重點(diǎn)字?jǐn)?shù)多一個(gè)，此說(shuō)法能否正確?請(qǐng)問(wèn)包括8個(gè)重點(diǎn)字的3階B-樹(shù)(即2-3樹(shù))最多有幾個(gè)結(jié)點(diǎn)?最罕有幾個(gè)結(jié)點(diǎn)?畫(huà)出這兩種狀況的B-樹(shù)。答：這個(gè)說(shuō)法是正確的。包括8個(gè)重點(diǎn)字的3階B-樹(shù)最多有7個(gè)結(jié)點(diǎn)，最罕有4個(gè)結(jié)點(diǎn)。見(jiàn)題圖。:圖以下：13.從空樹(shù)開(kāi)始，挨次輸入20，30，50，52，60，68，70，畫(huà)出成立2-3樹(shù)的過(guò)程。并畫(huà)出刪除50和68后的B-樹(shù)狀態(tài)。答：過(guò)程以下：(1)插入20，30：(2)插入50：(3)插入52：(4)插入60：(5)插入68：(6)插入70：(7)刪去50：(8)刪去6814。畫(huà)出挨次插入z,v,o,p,w,y到圖9.12(h)所示的5階B-樹(shù)的過(guò)程。答：如圖：第一步，插入z:第二、三步,插入v,o：第四五六步，插入p,w,y:15.在含有n個(gè)重點(diǎn)字的m階B-樹(shù)中進(jìn)行查找，至多讀盤(pán)多少次?完整均衡的二叉排序樹(shù)的讀盤(pán)次數(shù)大概比它大多少倍?答：在含有n個(gè)重點(diǎn)字的m階B-樹(shù)中進(jìn)行查找至多讀盤(pán)次數(shù)不超出B-樹(shù)高h(yuǎn)，即logt((n+1)/2)+1,(注，此處t為底，值是除根外的每個(gè)內(nèi)部結(jié)點(diǎn)的最小度數(shù)┌m/2┐).完整均衡的二叉樹(shù)高為lgn,所以它的讀盤(pán)次數(shù)至多也是lgn，它與上述B-樹(shù)的讀盤(pán)次數(shù)的比值約為lgt倍(此處底是2).16.為何在內(nèi)存中使用的B-樹(shù)往常是3階的，而不使用更高階的B-樹(shù)?答：因?yàn)椴檎业炔僮鞯腸pu時(shí)間在B-樹(shù)上是O(lgn?(m/lgt)),而m/lgt>1,所以m較大時(shí)它所費(fèi)時(shí)間比均衡的二叉排序樹(shù)上相應(yīng)操作時(shí)間大得多，所以，僅在內(nèi)存中使用的B-樹(shù)往常取最小值3.17.為何二叉排序樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)老是一個(gè)葉子，而B(niǎo)-樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)老是根?哪一種長(zhǎng)高能保證樹(shù)均衡?答：因?yàn)樵诙媾判驑?shù)中，重點(diǎn)字老是作為一個(gè)葉子結(jié)點(diǎn)插入以本來(lái)的樹(shù)中，所以當(dāng)樹(shù)增高時(shí)，新結(jié)點(diǎn)老是一個(gè)葉子；而B(niǎo)-樹(shù)中重點(diǎn)字插入老是插入到葉子結(jié)點(diǎn)內(nèi)部，在葉結(jié)點(diǎn)中的重點(diǎn)字?jǐn)?shù)量還沒(méi)有超出它能夠容納的數(shù)量以前是不會(huì)增添結(jié)點(diǎn)的，當(dāng)重點(diǎn)字?jǐn)?shù)超出結(jié)點(diǎn)可容納的數(shù)量時(shí)，葉結(jié)點(diǎn)就會(huì)發(fā)生疏裂，產(chǎn)生一個(gè)新結(jié)點(diǎn)(但不必定惹起樹(shù)增高)，并且將此中的中間結(jié)點(diǎn)傳至上一層，只有當(dāng)這類分裂操作傳達(dá)至根結(jié)點(diǎn)并惹起根結(jié)點(diǎn)的分裂時(shí)，才能惹起樹(shù)高增添，此時(shí)產(chǎn)生一個(gè)新的根結(jié)點(diǎn)。所以說(shuō)B樹(shù)長(zhǎng)高時(shí)，新結(jié)點(diǎn)老是根。明顯，后一種長(zhǎng)高總能保證樹(shù)的均衡。18.已知重點(diǎn)字序列為(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT)試為它們?cè)O(shè)計(jì)一個(gè)散列函數(shù)，將其映照到區(qū)間[0..n-1]上，要求碰撞盡可能的少。這里n=11,13,17,19.解：我的設(shè)計(jì)的散列函數(shù)是這樣的，把重點(diǎn)字串中的每一個(gè)字符按其所在地點(diǎn)分別將其ASCII值乘以一個(gè)不一樣的數(shù)，而后把這些值相加的和去對(duì)n求余，余數(shù)即為散列表中的地點(diǎn)。函數(shù)以下：intHash(charkey[]){return(int)(key[0]+key[1]*0.618+key[2]*10)%n;}我們能夠設(shè)計(jì)一個(gè)程序來(lái)看看用這個(gè)散列函數(shù)獲得的所相重點(diǎn)字映照到區(qū)間的地點(diǎn)：#include<stdio.h>#definen11file://先用11來(lái)代入，我們能夠用13，17，19挨次代入考證intHash(charkey[]){return(int)(key[0]+key[1]*0.618+key[2]*10)%n;file://此處我用了系數(shù)1，0.618和10，你也能夠用其余的數(shù)代入看有沒(méi)有更好的系數(shù)}voidmain( ){chars[10][4]={"PAL","LAP","PAM","MAP","PAT","PET","SET","SAT","TAT","BAT"};以上用一個(gè)二維數(shù)組來(lái)寄存重點(diǎn)字序列inti;for(i=0;i<10;i++){printf("%d",Hash(s));}}19.對(duì)于一組給定的、固定不變的重點(diǎn)字序列，有可能設(shè)計(jì)出無(wú)矛盾的散列函數(shù)H，此時(shí)稱H為齊備的散列函數(shù)(perfecthashingfunction)，若H能無(wú)矛盾地將重點(diǎn)字完整填滿散列表，則稱H是最小齊備(minimalperfect)的散列函數(shù)。往常找齊備的散列函數(shù)特別困難，找最小齊備的散列函數(shù)就更困難。請(qǐng)問(wèn)：(1)若h是已知重點(diǎn)字會(huì)合K的齊備的散列函數(shù)，若要增添一個(gè)新的重點(diǎn)字到會(huì)合K，一般狀況下H還是齊備的嗎?(2)已知重點(diǎn)字會(huì)合為(81，129，301，38，434，216，412，487，234)，散列函數(shù)為H(x)=(x+18)/63,請(qǐng)問(wèn)H是齊備的嗎?它是最小齊備的嗎?(3)考慮由字符串構(gòu)成的重點(diǎn)字會(huì)合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，試為散列表[0..6]設(shè)計(jì)一個(gè)齊備的散列函數(shù)。(提示：考慮每個(gè)字