歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > DOCX文檔下載  

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

  • 資源ID:124216595       資源大?。?span id="tmz2k4d" class="font-tahoma">31.51KB        全文頁數(shù):21頁
  • 資源格式: DOCX        下載積分:20積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺(tái)登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要20積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請(qǐng)知曉。

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

第九章查找9.25int Search_Sq(SSTable ST,int key)/在有序表上順序查找的算法,監(jiān)視哨設(shè)在高下標(biāo)端ST.elemST.length+1.key=key;for(i=1;ST.elemi.key>key;i+);if(i>ST.lengthllST.elemi.key<key) return ERROR;return i;/Search_Sq分析:本算法查找成功情況下的平均查找長(zhǎng)度為ST.length/2,不成功情況下為ST.length.9.26 int Search_Bin_Recursive(SSTable ST,int key,int low,int high)/折 半查找的遞歸算 法if(low>high) return 0; 查找不到時(shí)返回 0mid=(low+high)/2;if(ST.elemmid.key=key) return mid;else if(ST.elemmid.key>key)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);/Search_Bin_Recursive9.27 int Locate_Bin(SSTable ST,int key)/折半查找,返回小于或等于待查元素的最后一個(gè)結(jié)點(diǎn)號(hào)int *r;r=ST.elem;if(keyvrA.key) return 0;else if(key>=rST.length.key) return ST.length;low=1;high=ST.length;while(lowv=high) mid=(low+high)/2;if(key>=rmid.key&&keyvrmid+1.key) 查找結(jié)束的條件 return mid;else if(key<rmid.key) high=mid;else low=mid; /本算法不存在查找失敗的情況,不需要return 0;/Locate_Bin9.28typedef struct int maxkey;int firstloc;Index;typedef struct int *elem;int length;Index idxMAXBLOCK; 每塊起始位置和最大元素,其中idx0不 利用,其內(nèi)容初始化為0,0以利于折半查找int blknum; /塊的數(shù)目 IdxSqList; /索引順序表類型int Search_IdxSeq(IdxSqList L,int key)/分塊查找,用折半查找法確定記錄所在塊, 塊內(nèi)采用順序查找法if(key>L.idxL.blknum.maxkey) return ERROR; /超 過最大元素low=1;high=L.blknum;found=0;while(low<=high&&!found) /折半查找記錄所在塊號(hào)midmid=(low+high)/2;if(key<=L.idxmid.maxkey&&key>L.idxmid-1.maxkey)found=1;else if(key>L.idxmid.maxkey)low=mid+1;else high=mid-1;i=L.idxmid.firstloc; /塊的下界j=i+blksize-1; /塊的上界temp=L.elemi-1; /保存相鄰元素L.elemi-1=key; /設(shè)置監(jiān)視哨for(k=j;L.elemk!=key;k-); /順序查找L.elemi-1=temp; /恢復(fù)元素if(k<i) return ERROR; /未找到return k;/Search_IdxSeq分析:在塊內(nèi)進(jìn)行順序查找時(shí),如果需要設(shè)置監(jiān)視哨,則必須先保存相鄰塊的相鄰 元素,以免數(shù)據(jù)丟失.9.29typedef struct LNode *h; /h指向最小元素LNode *t; /t指向上次查找的結(jié)點(diǎn) CSList;LNode *Search_CSList(CSList &L,int key)/在有序單循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)上的查找 算法,假定每次查找都成功if(L.t->data=key) return L.t;else if(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指針return p;/Search_CSList分析:由于題目中假定每次查找都是成功的,所以本算法中沒有關(guān)于查找失敗的處 理.由微積分可得,在等概率情況下,平均查找長(zhǎng)度約為n/3.9.30typedef struct DLNode *pre;int data;DLNode *next; DLNode;typedef struct DLNode *sp;int length; DSList; /供查找的雙向循環(huán)鏈表類型DLNode *Search_DSList(DSList &L,int key)/在有序雙向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)上的查找算法,假定每次查找都成功p=L.sp;if(p->data>key)while(p->data>key) p=p->pre;L.sp=p;else if(p->data<key)while(p->data<key) p=p->next;L.sp=p;return p;/Search_DSList分析:本題的平均查找長(zhǎng)度與上一題相同,也是n/3.9.31int last=0,flag=1;int Is_BSTree(Bitree T)/判斷二叉樹T是否二叉排序樹,是則返回1,否則返回0if(T->lchild&&flag) Is_BSTree(T->lchild);if(T->data<last) flag=0; /與 其中序前驅(qū)相比較last=T->data;if(T->rchild&&flag) Is_BSTree(T->rchild);return flag;/Is_BSTree9.32int last=0;void MaxLT_MinGT(BiTree T,int x)/找到二叉排序樹T中小于x的最大元素和大于x的最小元素if(T->lchild) MaxLT_MinGT(T->lchild,x); 本算法仍是借助中序遍歷來實(shí)現(xiàn)if(last<x&&T->data>=x) /找到了小于x的最大元素printf("a=%dn",last);if(last<=x&&T->data>x) /找到了大于x的最小元素printf("b=%dn”,T->data);last=T->data;if(T->rchild) MaxLT_MinGT(T->rchild,x);/MaxLT_MinGT9.33void Print_NLT(BiTree T,int x)/從大到小輸出二叉排序樹T中所有不小于x的元素if(T->rchild) Print_NLT(T->rchild,x);if(T->data<x) exit(); /當(dāng)遇到小于x的元素時(shí)立即結(jié)束運(yùn)行 printf("%dn",T->data);if(T->lchild) Print_NLT(T->lchild,x); /先右后左的中序遍歷/Print_NLT9.34void Delete_NLT(BiTree &T,int x)/刪除二叉排序樹T中所有不小于x元素結(jié)點(diǎn),并釋放空間if(T->rchild) Delete_NLT(T->rchild,x);if(T->data<x) exit(); /當(dāng)遇到小于x的元素時(shí)立即結(jié)束運(yùn)行q=T;T=T->lchild;free(q); /如果樹根不小于x,則刪除樹根,并以左子樹的根作為新的樹根if(T) Delete_NLT(T,x); /繼續(xù)在左子樹中執(zhí)行算法/Delete_NLT9.35void Print_Between(BiThrTree T,int a,int b)/打印輸出后繼線索二叉排序樹 T 中所 有大于a且小于b的元素P=T;while(!p->ltag) p=p->lchild; /找到最小元素while(p&&p->data<b)if(p->data>a) printf("%dn",p->data); /輸出符合條件的元素if(p->rtag) p=p->rtag;elsep=p->rchild;while(!p->ltag) p=p->lchild; 轉(zhuǎn)到中序后繼/while/Print_Between9.36void BSTree_Insert_Key(BiThrTree &T,int x)/在后繼線索二叉排序樹 T 中插入元 素xif(T->data<x) /插入到右側(cè)if(T->rtag) /T沒有右子樹時(shí),作為右孩子插入p=T->rchild;q=(BiThrNode*)malloc(sizeof(BiThrNode);q->data=x;T->rchild=q;T->rtag=0;q->rtag=1;q->rchild=p; /修改原線索else BSTree_Insert_Key(T->rchild,x);/T 有右子樹時(shí),插入右子樹中/ifelse if(T->data>x) /插入到左子樹中if(!T->lchild) /T沒有左子樹時(shí),作為左孩子插入q=(BiThrNode*)malloc(sizeof(BiThrNode);q->data=x;T->lchild=q;q->rtag=1;q->rchild=T; /修改自身的線索else BSTree_Insert_Key(T->lchild,x);/T 有左子樹時(shí),插入左子樹中/if/BSTree_Insert_Key9.37Status BSTree_Delete_key(BiThrTree &T,int x)/在后繼線索二叉排序樹 T 中刪除 元素xBTNode *pre,*ptr,*suc;/ptr為x所在結(jié)點(diǎn),pre和suc分別指向ptr的前驅(qū)和后繼p=T;last=NULL; /last始終指向當(dāng)前結(jié)點(diǎn)p的前一個(gè)(前驅(qū))while(!p->ltag) p=p->lchild; /找到中序起始元素while(p)if(p->data=x) /找到了元素x結(jié)點(diǎn)pre=last;ptr=p;else if(last&&last->data=x) suc=p; /找到了 x 的后繼if(p->rtag) p=p->rtag;elsep=p->rchild;while(!p->ltag) p=p->lchild; 轉(zhuǎn)到中序后繼last=p;/while /借助中序遍歷找到元素x及其前驅(qū)和后繼結(jié)點(diǎn)if(!ptr) return ERROR; /未找到待刪結(jié)點(diǎn)Delete_BSTree(ptr); /刪除 x 結(jié)點(diǎn)if(pre&&pre->rtag)pre->rchild=suc; /修改線索return OK;/BSTree_Delete_keyvoid Delete_BSTree(BiThrTree &T)/課本上給出的刪除二叉排序樹的子樹T的算 法,按照線索二叉樹的結(jié)構(gòu)作了一些改動(dòng)q=T;if(!T->ltag&&T->rtag) /結(jié)點(diǎn)無右子樹,此時(shí)只需重接其左子樹T=T->lchild;else if(T->ltag&&!T->rtag) 結(jié)點(diǎn)無左子樹,此時(shí)只需重接其右子樹T=T->rchild;else if(!T->ltag&&!T->rtag) 結(jié)點(diǎn)既有左子樹又有右子樹p=T;r=T->lchild;while(!r->rtag)s=r;r=r->rchild; /找到結(jié)點(diǎn)的前驅(qū)r和r的雙親sT->data=r->data; /用 r 代替 T 結(jié)點(diǎn)if(s!=T)s->rchild=r->lchild;else s->lchild=r->lchild; /重接r的左子樹到其雙親結(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í)修改線索,則問題反而復(fù)雜化了.9.38void BSTree_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_Mergevoid Insert_Node(Bitree &T,BTNode *S)/把樹結(jié)點(diǎn)S插入到T的合適位置上if(S->data>T->data)if(!T->rchild) T->rchild=S;else Insert_Node(T->rchild,S);else if(S->data<T->data)if(!T->lchild) T->lchild=S;else Insert_Node(T->lchild,S);S->lchild=NULL; /插入的新結(jié)點(diǎn)必須和原來的左右子樹斷絕關(guān)系S->rchild=NULL; /否則會(huì)導(dǎo)致樹結(jié)構(gòu)的混亂/Insert_Node分析:這是一個(gè)與課本上不同的插入算法.在合并過程中,并不釋放或新建任何結(jié) 點(diǎn),而是采取修改指針的方式來完成合并.這樣,就必須按照后序序列把一棵樹中 的元素逐個(gè)連接到另一棵樹上,否則將會(huì)導(dǎo)致樹的結(jié)構(gòu)的混亂.9.39void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)/把 二叉排序樹 T 分裂為 兩棵二叉排序樹A和B,其中A的元素全部小于等于x,B的元素全部大于xif(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);else Insert_Node(B,T); /將元素結(jié)點(diǎn)插入合適的樹中/BSTree_Splitvoid Insert_Node(Bitree &T,BTNode *S)/把樹結(jié)點(diǎn)S插入到T的合適位置上if(!T) T=S; /考慮到剛開始分裂時(shí)樹A和樹B為空的情況else if(S->data>T->data) /其余部分與上一題同if(!T->rchild) T->rchild=S;else Insert_Node(T->rchild,S);else if(S->data<T->data)if(!T->lchild) T->lchild=S;else Insert_Node(T->lchild,S);S->lchild=NULL;S->rchild=NULL;/Insert_Key 9.40typedef struct int data;int bf;int lsize; /lsize域表示該結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)總數(shù)加1BlcNode *lchild,*rchild; BlcNode,*BlcTree; /含lsize域的平衡二叉排序樹類型BTNode *Locate_BlcTree(BlcTree T,int k)/在含 lsize 域的平衡二叉排序樹 T 中確 定第k小的結(jié)點(diǎn)孑指針if(!T) return NULL; /k小于1或大于樹結(jié)點(diǎn)總數(shù)if(T->lsize=k) return T; /就是這個(gè)結(jié)點(diǎn)else if(T->lsize>k)return Locate_BlcTree(T->lchild,k); /在左子樹中尋找else return Locate_BlcTree(T->rchild,k-T->lsize); /在右子樹中尋找,注意要修改 k 的值/Locate_BlcTree9.41typedef struct enum LEAF,BRANCH tag; / 結(jié)點(diǎn)類型標(biāo)識(shí)int keynum;BPLink parent; /雙親指針int keyMAXCHILD; /關(guān)鍵字union BPLink childMAXCHILD;/非 葉結(jié)點(diǎn)的孩子指針 struct rectype *infoMAXCHILD;/葉子結(jié)點(diǎn)的信息指針BPNode *next; /指向下一個(gè)葉子結(jié)點(diǎn)的鏈接 leaf; BPNode,*BPLink,*BPTree;/B+樹及其結(jié)點(diǎn)類型Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)/B+樹中按關(guān)鍵字隨 機(jī)查找的算法,返回包含關(guān)鍵字的葉子結(jié)點(diǎn)的指針ptr以及關(guān)鍵字在葉子結(jié)點(diǎn)中 的位置posp=T;while(p.tag=BRANCH) /沿分支向下查找for(i=0;i<p->keynum&&key>p->keyi;i+); /確定關(guān)鍵字所在子樹if(i=p->keynum) return ERROR; 關(guān)鍵字太大 p=p->childi;for(i=0;i<p->keynum&&key!=p->keyi;i+); /在葉子結(jié)點(diǎn)中查找if(i=p->keynum) return ERROR; /找 不到關(guān)鍵字ptr=p;pos=i;return OK;/BPTree_Search9.42void TrieTree_Insert_Key(TrieTree &T,StringType key)/在 Trie 樹 T 中插入字符串 key,StringType的結(jié)構(gòu)見第四章q=(TrieNode*)malloc(sizeof(TrieNode);q->kind=LEAF;q->lf.k=key; /建葉子結(jié)點(diǎn)klen=key0;p=T;i=1;while(p&&i<=klen&&p->bh.ptrord(keyi)last=p;p=p->bh.ptrord(keyi);i+;/自上而下查找if(p->kind=BRANCH) /如果最后落到分支結(jié)點(diǎn)(無同義詞):p->bh.ptrord(keyi)=q; /直接連上葉子 p->bh.num+;else /如果最后落到葉子結(jié)點(diǎn)(有同義詞):r=(TrieNode*)malloc(sizeof(TrieNode); /建立新的分支結(jié)點(diǎn)last->bh.ptrord(keyi-1)=r; /用新分支結(jié)點(diǎn)取代老葉子結(jié)點(diǎn)和上一層的聯(lián)系r->kind=BRANCH;r->bh.num=2;r->bh.ptrord(keyi)=q;r->bh.ptrord(p->lf.ki)=p; /新分支結(jié)點(diǎn)與新老兩個(gè)葉子結(jié)點(diǎn)相連/TrieTree_Insert_Key分析:當(dāng)自上而下的查找結(jié)束時(shí),存在兩種情況.一種情況,樹中沒有待插入關(guān)鍵字的同義詞,此時(shí)只要新建一個(gè)葉子結(jié)點(diǎn)并連到分支結(jié)點(diǎn)上即可.另一種情況,有同 義詞,此時(shí)要把同義詞的葉子結(jié)點(diǎn)與樹斷開,在斷開的部位新建一個(gè)下一層的分支 結(jié)點(diǎn),再把同義詞和新關(guān)鍵字的葉子結(jié)點(diǎn)連到新分支結(jié)點(diǎn)的下一層.9.43Status TrieTree_Delete_Key(TrieTree &T,StringType key)/在 Trie 樹 T 中刪除字符 串keyp=T;i=1;while(p&&p->kind=BRANCH&&iv=key0) 查找待刪除元素last=p;p=p->bh.ptrord(keyi);i+;if(p&&p->kind=LEAF&&p->lf.k=key) /找到了待刪除元素last->bh.ptrord(keyi-1)=NULL;free(p);return OK;else return ERROR; /沒找到待刪除元素/TrieTree_Delete_Key9.44void Print_Hash(HashTable印/按第一個(gè)字母順序輸出Hash表中的所有關(guān)鍵字,其中處理沖突采用線性探測(cè)開放定址法for(i=1;iv=26;i+)for(j=i;H.elemj.key;j=(j+1)%hashsizesizeindex) 線性探測(cè) if(H(H.elemj.key)=i) printf("%sn",H.elemj);/Print_Hashint H(char *s)/求 Hash 函數(shù)if(s) return s0-96; /求關(guān)鍵字第一個(gè)字母的字母序號(hào)(小寫)else return 0;/H9.45typedef *LNodeMAXSIZE CHashTable; 鏈地址 Hash 表類型Status Build_Hash(CHashTable &T,int m/輸入一組關(guān)鍵字,建立 Hash 表,表長(zhǎng)為 m用鏈地址法處理沖突.if(m<1) return ERROR;T=malloc(m*sizeof(WORD); / 建立表頭指針向量for(i=0;i<m;i+) Ti=NULL;while(key=Inputkey()!=NULL) /假定Inputkey函數(shù)用于從鍵盤輸入關(guān)鍵字q=(LNode*)malloc(sizeof(LNode);q->data=key;q->next=NULL;n=H(key);if(!Tn) Tn=q; /作為鏈表的第一個(gè)結(jié)點(diǎn)elsefor(p=Tn;p->next;p=p->next);p->next=q; /插入鏈表尾部.本算法不考慮排序問題./whilereturn OK;/Build_Hash9.46Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)/根 據(jù)行列值在Hash表表示的稀疏矩陣中確定元素key的位置kh=2*(100*(row/10)+col/10); /作者設(shè)計(jì)的 Hash 函數(shù)while(H.elemh.key&&!EQ(H.elemh.key,key)h=(h+1)%20000;if(EQ(H.elemh.key,key) k=h;else k=NULL;/Locate_Hash分析:本算法所使用的Hash表長(zhǎng)20000,裝填因子為50%,Hash函數(shù)為行數(shù)前兩位 和列數(shù)前兩位所組成的四位數(shù)再乘以二,用線性探測(cè)法處理沖突.當(dāng)矩陣的元素是 隨機(jī)分布時(shí),查找的時(shí)間復(fù)雜度為0(1).另解:第九章查找習(xí)題及答案題號(hào):1 2 3 4 5 6 7 8 9 10 11 12 13 1419 20 21 22 23 一、基礎(chǔ)知識(shí)題1. 對(duì)含有n個(gè)互不相同元素的集合,同時(shí)找最大元和最小元至少需進(jìn)行多少次比較答:我們可以設(shè)立兩個(gè)變量max和min用于存放最大元和最小元的位置,第一次取兩個(gè)元素進(jìn)行比較,大的放而ax,小的放入min,從第2次 開始,每次取一個(gè)元素先和max比較,如果大于max則以它替換max,并結(jié)束本次比較;若小于nax則再與min相比較,在最好的情況下,一路比 較下去都不用和min相比較,所以這種情況下,至少要進(jìn)行V1次比較就能找到最大元和最小元。(順便說一下,最壞情況下,要進(jìn)行!n-3次比較才能得到結(jié)果)2. 若對(duì)具有n個(gè)元素的有序的順序表和無序的順序表分別進(jìn)行順序查找,試在下述兩種情況下分別討論兩者在等概率時(shí)的平均查找長(zhǎng)度)查找不成功,即表中無關(guān)鍵字等于給定值:的記錄;(2)查找成功,即表中有關(guān)鍵字等于給定值的記錄。答:查找不成功時(shí),需進(jìn)行n+1次比較才能確定查找失敗。因此平均查找長(zhǎng)度為+1,這時(shí)有序表和無序表是一樣的。查找成功時(shí),平均查找長(zhǎng)度為n+1)/2,有序表和無序表也是一樣的。因?yàn)轫樞虿檎覍?duì)表的原始序列的有序性不感興趣。3. 畫出對(duì)長(zhǎng)度為18的有序的順序表進(jìn)行二分查找的判定樹,并指出在等概率時(shí)查找成功的平均查找長(zhǎng)度,以及查找失敗時(shí)所需的最多的關(guā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í),最多的關(guān)鍵字比較次樹不超過判定樹的深度,此處為如圖:4. 為什么有序的單鏈表不能進(jìn)行折半查找答:因?yàn)殒湵頍o法進(jìn)行隨機(jī)訪問,如果要訪問鏈表的中間結(jié)點(diǎn)就必須先從頭結(jié)點(diǎn)開始進(jìn)行依次訪問,這就要浪費(fèi)很多時(shí)間還不如進(jìn)行順序查找,而且,用鏈存儲(chǔ)結(jié)構(gòu)將無法判定二分的過程是否結(jié)束,因此無法用鏈表實(shí)現(xiàn)二分查找。5. 設(shè)有序表為(a,b,c,e,f,g,i,j,k,p,q),請(qǐng)分別畫出對(duì)給定值b,g和n進(jìn)行折半查找的過程。解:b的查找過程如下 (其中括號(hào)表示當(dāng)前查找區(qū)間,圓括號(hào)表示當(dāng)前比較的關(guān)鍵字下標(biāo): 1 2 345 678910111213第一次比較:a bcd ef (g)hijkpq第二次比較:a b(c)d efghijkpq第三次比較:a(b)cd efghijkpq經(jīng)過三次比較,查找成功。g的查找過程如下:a b c d e f (g) h i j k p q一次比較成功。n的查找過程如下:下標(biāo):1 2 3 4 5 6 7 8 9 10 11 12 13第一次比較: a b c d e f (g) h i j k p q第二次比較: a b c d e f g h i (j) k p q第三次比較:a bc d e fgh ijk (p) q第四次比較:a bc d e fgh ijk p q經(jīng)過四次比較,查找失敗。6. 將(for, case, while, class, protected, virtual, public,private, do, template, const ,if,int)中的關(guān)鍵字依次插入初態(tài)為空的二叉排序樹中,請(qǐng)畫出所得到的楸然后畫出刪去for之后的二叉排序樹T',若再將for插入T'中得到的二叉排序樹T''是否與T相同?最后給出T”的先序、中序和后序序列。答:見題圖:T”的先序序列是:do case class const while protected private iffor int virtual public templateT”的中序序列是: case class const do for if int privateprotected public template virtual whileT”的后序序列是:const class case for int if private templatepublic virtual protected while do二叉排序樹T如下圖:刪去for后的二叉排序樹如下圖:圈內(nèi)的for表示再插入后的結(jié)點(diǎn):7. 對(duì)給定的關(guān)鍵字集合,以不同的次序插入初始為空的樹中,是否有可能得到同一棵二叉排序樹答:有可能。如有兩個(gè)序列:3, 1,2, 4和3, 4, 1,2,它們插入空樹所得的二叉排序樹是相同的。8. 將二叉排序樹T的先序序列中的關(guān)鍵字依次插入一空樹中,所得和二叉排序樹與T"是否相同?為什么?答:這兩棵二叉樹完全相同。9. 設(shè)二叉排序樹中關(guān)鍵字由1至1000的整數(shù)構(gòu)成,現(xiàn)要查找關(guān)鍵字為63的結(jié)點(diǎn),下述關(guān)鍵字序列哪一個(gè)不可能是在二叉排序樹上查找到的序列(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è)初始為空的二叉排序樹中,結(jié)果可以發(fā)現(xiàn)c)序列所形成的不是一條路徑,而是有分支的,可見它是不可能在查找過程中訪問到的序列。10. 設(shè)二叉排序樹中關(guān)鍵字互不相同,則其中最小元必?zé)o左孩子,最大元必?zé)o右孩子。此命題是否正最小元和最大元一定是葉子嗎一個(gè)新結(jié)點(diǎn)總是插在二叉排序樹的某葉子上嗎答:此命題正確。假設(shè)最小元有左孩子,則根據(jù)二叉排序樹性質(zhì),此左孩子應(yīng)比最小元更小,如此一來就產(chǎn)生矛盾了此最小元不可能有左孩子, 對(duì)于最大元也是這個(gè)道理。但最大元和最小元不一定是葉子,它也可以是根、內(nèi)部結(jié)點(diǎn)分支結(jié)點(diǎn))等,這得根據(jù)插入結(jié)點(diǎn)時(shí)的次序而定。如,1,2, 4這個(gè)集合,根據(jù)不同的插入次序可以得到不同的二叉排序樹:/ O1 040202/ O1 03040403020102/ 01 04/03新結(jié)點(diǎn)總是插入在二叉排序樹的某個(gè)葉子上的。11. 在一棵m階的B-樹中,當(dāng)將一關(guān)鍵字插入某結(jié)點(diǎn)而引起該結(jié)點(diǎn)的分裂時(shí)此結(jié)點(diǎn)原有多少個(gè)關(guān)鍵字若刪去某結(jié)點(diǎn)中的一個(gè)關(guān)鍵字,而導(dǎo)致結(jié)點(diǎn)合并時(shí),該結(jié)點(diǎn)中原有幾個(gè)關(guān)鍵字答:在此樹中,若由于一關(guān)鍵字的插入某結(jié)點(diǎn)而引起該結(jié)點(diǎn)的分裂時(shí),則該結(jié)點(diǎn)原有1個(gè)關(guān)鍵字。若刪去某結(jié)點(diǎn)中一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并時(shí),該結(jié)點(diǎn)中原有rm/2-il個(gè)關(guān)鍵字。12. 在一棵B-樹中,空指針數(shù)總是比關(guān)鍵字?jǐn)?shù)多一個(gè),此說法是否正礴問包含8個(gè)關(guān)鍵字的3階B-樹(即2-3樹)最多有幾個(gè)結(jié)點(diǎn)?最少有幾個(gè)結(jié)點(diǎn)?畫出這兩種情況的B-樹。答:這個(gè)說法是正確的。包含8個(gè)關(guān)鍵字的3階B-樹最多有7個(gè)結(jié)點(diǎn),最少有4個(gè)結(jié)點(diǎn)。見題圖。:圖如下:13. 從空樹開始,依次輸入20,30,50,52,60,68, 70,畫出建立2-3樹的過程。并畫出刪除50和68后的B-樹狀態(tài)。答:過程如下:(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個(gè)關(guān)鍵字的m階B-樹中進(jìn)行查找,至多讀盤多少次完全平衡的二叉排序樹的讀盤次數(shù)大約比它大多少倍答:在含有n個(gè)關(guān)鍵字的m階B-樹中進(jìn)行查找至多讀盤次數(shù)不超過5-樹高h(yuǎn),即logt(n+1)/2)+1,(注,此處t為底,值是除根外的每個(gè)內(nèi)部結(jié)點(diǎn)的最小度數(shù)m/2r).完全平衡的二叉樹高為lgn,所以它的讀盤次數(shù)至多也是lgn,它與上述B-樹的讀盤次數(shù)的比值約為lgt倍(此處底是2).16. 為什么在內(nèi)存中使用的3-樹通常是3階的,而不使用更高階的3-樹?答:因?yàn)椴檎业炔僮鞯腸pu時(shí)間在B-樹上是O(lgn(m/lgt),而m/lgt>1,所以m較大時(shí)它所費(fèi)時(shí)間比平衡的二叉排序樹上相應(yīng)操作時(shí)間大得多因此,僅在內(nèi)存中使用的B-樹通常取最小值3.17. 為什么二叉排序樹長(zhǎng)高時(shí),新結(jié)點(diǎn)總是一個(gè)葉子,而-樹長(zhǎng)高時(shí),新結(jié)點(diǎn)總是根哪一種長(zhǎng)高能保證樹平衡答:因?yàn)樵诙媾判驑渲校P(guān)鍵字總是作為一個(gè)葉子結(jié)點(diǎn)插入以原來的樹中,所以當(dāng)樹增高時(shí)新結(jié)點(diǎn)總是一個(gè)葉子;而B-樹中關(guān)鍵字插入總是插入到葉子結(jié)點(diǎn)內(nèi)部,在葉結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目尚未超過它能夠容納的數(shù)目之前是不會(huì)增加結(jié)點(diǎn)的,當(dāng)關(guān)鍵字?jǐn)?shù)超過結(jié)點(diǎn)可容納的數(shù)目時(shí),葉結(jié)點(diǎn)就會(huì)發(fā)生分裂,產(chǎn)生一個(gè)新結(jié)點(diǎn)但不一定引起樹增高,并且將其中的中間結(jié)點(diǎn)傳至上一層,只有當(dāng)這種分裂操作傳遞至根結(jié)點(diǎn)并引起根結(jié)點(diǎn)的分裂時(shí),才能引起樹高增加,此時(shí)產(chǎn)生一個(gè)新的根結(jié)點(diǎn)。所以說樹長(zhǎng)高時(shí),新結(jié)點(diǎn)總是根。顯然,后一種長(zhǎng)高總能保證樹的平衡。18. 已知關(guān)鍵字序列為(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BATM為它們?cè)O(shè)計(jì)一個(gè)散列函數(shù),將其映射到區(qū)畫.n-1上,要求碰撞盡可能的少。這里 n=11,13,17,19.解:我的設(shè)計(jì)的散列函數(shù)是這樣的,把關(guān)鍵字串中的每一個(gè)字符按其所在位置分別將其CII值乘以一個(gè)不同的數(shù),然后把這些值相加的和去對(duì)求余,余數(shù)即為散列表中的位置。函數(shù)如下:int Hash (char key)return (int)(key0+key1*0.618+key2*10)%n;我們可以設(shè)計(jì)一個(gè)程序來看看用這個(gè)散列函數(shù)得到的所有關(guān)鍵字映射到區(qū)間的位置:#include <stdio.h>#define n 11 file&#58/先用11來代入,我們可以用13, 17, 19依次代入驗(yàn)證int Hash (char key)return (int)(key0+key1*0.618+key2*10)%n;file&#58/此處我用了系數(shù)1,0.618和10,你也可以用其他的數(shù)代入看有沒有更好的系數(shù)void main()chars104 = "PAL”,"LAP”,"PAr,"MAP”,"PAT',"PET',"SET',"SAT',"TAT',"BAT'/以上用一個(gè)二維數(shù)組來存放關(guān)鍵字序列int i;for(i=0; i<10;i+)printf('%d ”,Hash(3);19. 對(duì)于一組給定的、固定不變的關(guān)鍵字序列,有可能設(shè)計(jì)出無沖突的散列,函數(shù)時(shí)稱H為完備的散列函數(shù)perfecthashing function,)若H能無沖突地將關(guān)鍵字完全填滿散列表,貝H是最小完備minimalperfect)的散列函數(shù)。通常找完備的散列函數(shù)非常困難,找最小完備的散列函數(shù)就更困難。請(qǐng)問:(1)若h是已知關(guān)鍵字集合的完備的散列函數(shù),若要增加一個(gè)新的關(guān)鍵字到集合一般情況下!還是完備的嗎(2) 已知關(guān)鍵字集合為81,129, 301,38, 434, 216, 412, 487, 234),散列函數(shù)為i(x) = (x+18)/63請(qǐng)問H是完備的嗎它是最小完備的嗎(3) 考慮由字符串構(gòu)成的關(guān)鍵字集合ret,Jane,Shirley,Bryce,Michelle,Heather試為散列表0.6設(shè)計(jì)一個(gè)完備的散列函數(shù)。提示:考慮每個(gè)字符串的第3個(gè)字符,即s2)答:一般情況下H不是完備的,如果說插入一個(gè)新的關(guān)鍵字它還是完備的,那么再插入一個(gè)不是永遠(yuǎn)是完備的散列函數(shù)了所以一般情況下它不能總是完備的,只有一些很少的情況下它還可能是完備的。這個(gè)H是完備的,其函數(shù)值依次為:2, 5, 0, 7, 3, 6, 8, 4。如果散列表詢=9時(shí),它就是最小完備的。(3)這個(gè)函數(shù)如下:int Hash (char key) return key2%7;20. 設(shè)散列函數(shù)為i(key)=key%101解決沖突的方法為線性探查,表中用”表示空單元。若刪去散列度中的304即令HT1=-1)之后,在表1T 中查找707將會(huì)發(fā)生什么若將刪去的表項(xiàng)標(biāo)記為2”,查找時(shí)探查到2繼續(xù)向前搜索,探查到時(shí)終止搜索。請(qǐng)問用這種方法刪4后能否正確 地查找到707?0123100HT |202 |304 |507 |707 |.|答:查找707時(shí),首先根據(jù)散列函數(shù)計(jì)算得出該元素應(yīng)在散列表中單元,但是在)單元沒有找到,因此將向下一單元探查,結(jié)果發(fā)現(xiàn)該單元是 -1(為空單元,所以結(jié)束查找,這將導(dǎo)致07無法找到。如果改用'-2"作為刪除標(biāo)記,則可以正確找到7所在的結(jié)點(diǎn)。21. 設(shè)散列表長(zhǎng)度為1,散列函數(shù)!(x)=x%11,給定的關(guān)鍵字序列為1,13, 13, 34, 38, 33, 27, 22,試畫出分別用拉鏈法和線性探查法解決沖突 時(shí)所構(gòu)造的散列表,并求出在等概率情況下,這兩咱方法查找成功和失敗時(shí)的平均查找長(zhǎng)度。請(qǐng)問裝填因子的值是什么答:拉鏈法如下圖:(后面的框框就不畫了T0.100| 33 22 A1| 1 12 34 A2| 13 A3| A |4| A |5| 38 27 A6| A |7| A |8| A |10| A I線性探查法如下圖:下標(biāo) 0123 45678910T0.10|33|1 |13|12|34|38|27|22 |探查次數(shù)1113417 8用拉鏈法的查找成功平均查找長(zhǎng)度為:ASLscuu=(1*4+2*3+3*1)/8=1.625查找失敗時(shí)平均查找長(zhǎng)度為:ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73用線性探查法查找成功時(shí)平均查找長(zhǎng)度為:ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25查找失敗時(shí)平均查找長(zhǎng)度為:ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3裝填因子a拉鏈=4/11=0.36 a線性探查=8/11=0.7322 .假定有k個(gè)關(guān)鍵字互為同義詞,若用線性探查法把這些同義詞存入散列表中,至少要進(jìn)行多少次探查答:至少要進(jìn)行1+2+3.+k-1+次探查。也就是說,在散列表的一連串連續(xù)空間內(nèi),第一個(gè)關(guān)鍵字只需探查一次,第二個(gè)就2要探查如此這般,第個(gè)關(guān)鍵字就要探查次才能找到位置存放。所以至少要把它們?nèi)悠饋聿艍颉?3.為什么說當(dāng)裝填因子非常接近時(shí),線性探查類似于順序查?為什么說當(dāng)裝填因子比較小比如a =0.7左右)時(shí),散列查找的平均查找時(shí)間為。?答:當(dāng)a非常接近1時(shí),整個(gè)散列表幾乎被裝滿。由于線性探查法在關(guān)鍵字同義時(shí)解決沖突的辦法是線性地向后查找,當(dāng)整個(gè)表幾乎裝滿時(shí),它 就很類似于順序查找了。當(dāng)a比較小時(shí),關(guān)鍵字碰撞的幾率比較小,一般情況下只要按照散列函數(shù)計(jì)算出的結(jié)果能性就找到相應(yīng)結(jié)點(diǎn),因此它的平均查找時(shí)間接近 于1.

注意事項(xiàng)

本文(《數(shù)據(jù)結(jié)構(gòu)題集》答案 第9章 查找)為本站會(huì)員(lis****210)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!