數(shù)據(jù)結(jié)構(gòu)習(xí)題課8

數(shù)據(jù)結(jié)構(gòu)習(xí)題第8章第一頁(yè)，編輯于星期三：五點(diǎn)三十五分。2023最新整理收集do

something第8章作業(yè)8-48-7，8-8，8-9，8-108-138-22，8-23第二頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-4設(shè)有關(guān)鍵詞為A、B、C和D，按照不同的輸入順序，共可能組成多少種不同的二叉查找樹(shù)。請(qǐng)畫(huà)出其中高度較小的6種。第三頁(yè)，編輯于星期三：五點(diǎn)三十五分。參考答案以A為根的BST共5種B為第2個(gè)元素：2種C為第2個(gè)元素：1種（高度為2）D為第2個(gè)元素：2種以B為根的BST共2種（高度為2）以C為根的BST共2種（高度為2）以D為根的BST共5種（類似A）一共有14種。高度為2的有6種，為3的有8種第四頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-7畫(huà)出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹(shù)，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。第五頁(yè)，編輯于星期三：五點(diǎn)三十五分。參考答案ASLsucc=(1+2*2+3*4+4*3)/10=29/10ASLunsucc=(5*3+6*4)/11=39/114528169710a5a8a9a10a2a1a3a6a4a73a2第六頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-8對(duì)長(zhǎng)度為12的有序表（a1,a2,…,a12）（其中ai<aj，當(dāng)i<j時(shí)）進(jìn)行折半查找，在設(shè)定查找不成功的情況時(shí)，關(guān)鍵詞x<a1,

x>a12,

ai<x<ai+1（i=1,2,…,11）等情況發(fā)生的概率相等，則查找不成功的平均查找長(zhǎng)度是多少？第七頁(yè)，編輯于星期三：五點(diǎn)三十五分。56391711812a6a9a11a12a3a1a4a7a5a82410a2a10第八頁(yè)，編輯于星期三：五點(diǎn)三十五分。二叉判定樹(shù)如下：ASLUNSUCC＝En/(n+1)＝(3*3+4*10)/13＝49/13參考答案56391711812a6a9a11a12a3a1a4a7a5a82410a2a10第九頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-9假設(shè)按下述遞歸方法進(jìn)行順序表的查找：若表長(zhǎng)n≤10，則進(jìn)行順序查找，否則進(jìn)行折半查找。試畫(huà)出對(duì)表長(zhǎng)n=50的順序表進(jìn)行上述查找時(shí)，描述該查找的判定樹(shù)，并求出在等概率情況下查找成功的平均查找長(zhǎng)度。第十頁(yè)，編輯于星期三：五點(diǎn)三十五分。ASL=(1+2*2+3*4+(4+5+6+7+8)*8+9*3)/50=284/50參考答案26-3013-171-519-2432-3725123863144a25a38a44a12a6a18a31187-1145-5039-43a2第十一頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-10已知下列關(guān)鍵詞和它們對(duì)應(yīng)的散列函數(shù)值：由此構(gòu)造哈希表，用線性探測(cè)法沖突，計(jì)算平均查找長(zhǎng)度ASL。若用拉鏈法解決沖突情況又如何?keyZhaoSunLiWangChenLiuZhangH(key)6574164第十二頁(yè)，編輯于星期三：五點(diǎn)三十五分。參考答案線性探測(cè)法（假設(shè)散列表的長(zhǎng)度是8，下標(biāo)從0開(kāi)始）查找成功ASL=(1*5+3*1+7*1)/7=15/7下標(biāo)元素7Li6Zhao5Sun4Wang32Zhang1Chen0Liu第十三頁(yè)，編輯于星期三：五點(diǎn)三十五分。拉鏈法（假設(shè)散列表長(zhǎng)度是8，下標(biāo)從0開(kāi)始）查找成功ASL=(1*5+2*1+2*1)/7=9/7下標(biāo)指針76543Λ2Λ10ΛLiΛZhaoLiuΛSunΛWangZhangΛChenΛ第十四頁(yè)，編輯于星期三：五點(diǎn)三十五分。合并拉鏈法（算法C）拉鏈法（假設(shè)散列表的長(zhǎng)度是8，下標(biāo)從0開(kāi)始）查找成功ASL=(1*5+2*1+2*1)/7=9/7下標(biāo)元素Link7Li-16Zhao35Sun-14Wang23Liu-12Zhang-11Chen-10第十五頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-13已知序列(17,31,13,11,20,35,25,8,4,11,24,40,27)，請(qǐng)畫(huà)出該序列的二叉查找樹(shù)，并分別給出下列操作后的二叉查找樹(shù)。（1）插入數(shù)據(jù)9（2）刪除節(jié)點(diǎn)17（3）再刪除節(jié)點(diǎn)13第十六頁(yè)，編輯于星期三：五點(diǎn)三十五分。參考答案動(dòng)態(tài)插入創(chuàng)建二叉查找樹(shù)：(17,31,13,11,20,35,25,8,4,11,24,40,27)171731173113173113111731131120173113112035第十七頁(yè)，編輯于星期三：五點(diǎn)三十五分。(17,31,13,11,20,35,25,8,4,11,24,40,27)1731131120352517311311203584244027第十八頁(yè)，編輯于星期三：五點(diǎn)三十五分。插入數(shù)據(jù)9251731131120358424402792517311311203584244027第十九頁(yè)，編輯于星期三：五點(diǎn)三十五分。刪除17251731131120358424402724203113112535844027第二十頁(yè)，編輯于星期三：五點(diǎn)三十五分。再刪除節(jié)點(diǎn)1324203113112535844027242031118253544027第二十一頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-22編寫判定給定的二叉樹(shù)是否是二叉查找樹(shù)的算法。第二十二頁(yè)，編輯于星期三：五點(diǎn)三十五分。[提示]判定二叉樹(shù)是否為二叉查找樹(shù)是建立在中根遍歷的框架基礎(chǔ)下，在遍歷中附設(shè)一指針pre指向當(dāng)前訪問(wèn)節(jié)點(diǎn)的中根直接前驅(qū)，每訪問(wèn)一個(gè)節(jié)點(diǎn)便比較前驅(qū)節(jié)點(diǎn)pre和此節(jié)點(diǎn)是否有序，若遍歷結(jié)束后各節(jié)點(diǎn)和其中根直接前驅(qū)均滿足有序，則此二叉樹(shù)為二叉查找樹(shù)；否則，只要有一個(gè)節(jié)點(diǎn)不滿足，那么此二叉樹(shù)就不是二叉查找樹(shù)。第二十三頁(yè)，編輯于星期三：五點(diǎn)三十五分。算法BST(t.pre,flag)/*使用中根遍歷和pre指針判斷t是否是二叉查找樹(shù)*/B1[特判]

flag

TRUE.

IFt=NULLTHENRETURN.B2[中根遍歷]BST(left(t),pre,flag).IF(!flag)THENRETURN.IF(pre!=NULL

AND

data(pre)>data(t)

)

THEN(flag

FALSE.RETURN.).pret. BST(right(t),pre,flag).▌第二十四頁(yè)，編輯于星期三：五點(diǎn)三十五分。C++boolbst(BinTreeNode<T>*t,BinTreeNode<T>*&pre)/*t指向根結(jié)點(diǎn)；pre指向t的中根前驅(qū)，初值NULL*/{if(t==NULL)returntrue;if(!bst(left(t),pre))returnfalse;if(pre&&pre->data>t->data))returnfalse;pre=t;returnbst(right(t),pre);}第二十五頁(yè)，編輯于星期三：五點(diǎn)三十五分。8-23給定整型數(shù)組B[0..m,0..n].已知B中數(shù)據(jù)在每一維方向上都按從小到大的次序排列。且整型變量x在B中存在。試設(shè)計(jì)一個(gè)算法，找出一對(duì)滿足B[i,j]=x的i,j值，要求比較次數(shù)不超過(guò)m+n.第二十六頁(yè)，編輯于星期三：五點(diǎn)三十五分?！咎崾尽勘绢}中主要是要確定每次進(jìn)行比較的對(duì)象。其中，二維數(shù)組右上角的元素是一個(gè)較為特殊的元素?？梢灾鸫胃S數(shù)組右上角的元素進(jìn)行比較。每次比較有3種可能的結(jié)果：若相等則結(jié)束比較；若右上角的元素小于x，則可斷定二維數(shù)組的最上面一行中肯定不包含x，下次比較時(shí)搜索范圍即可減少一行；若右上角的元素大于x，則可斷定二維數(shù)組的最右面一列中肯定不包含x，下次比較時(shí)搜索范圍即可減少一列。這樣，每次至少可使搜索范圍減少一列或一行，最多經(jīng)過(guò)m+n次即可找到x.第二十七頁(yè)，編輯于星期三：五點(diǎn)三十五分。參考答案算法Find(B,m,n,x)/*在B中查找x，時(shí)間復(fù)雜度O(m+n)*/F1[初始化]i←0.j←n.F2[比較B[i,j]與x]WHILE(i<=mANDj>=0)DO(IF(B[i,j]=x)THENRETURNTRUE.

IF(B[i,j]>x)THENi←i+1.IF(B[i,j]<x)THENj←j-1.)RETURNFALSE.▌第二十八頁(yè)，編輯于星期三：五點(diǎn)三十五分。1.（8分）數(shù)組A中存放n個(gè)整數(shù)（0<=A[i]<=10000，1<=i<=n），設(shè)計(jì)算法求出數(shù)組A中的第k小數(shù)（1<=k<=n<=10000）。例如：若數(shù)組A中包含4個(gè)整數(shù)為1、9、4、16，則A中第2小數(shù)為4.(1)給出算法的基本設(shè)計(jì)思想

（2分），高效算法有額外加分（2分）；(2)描述算法，并要求對(duì)算法中的關(guān)鍵步驟給出注釋（3分）；(3)給出算法的時(shí)間復(fù)雜性分析（1分）。第二十九頁(yè)，編輯于星期三：五點(diǎn)三十五分。分析本題方法較多，典型有三種。

方法一：先排序（任意一種排序方法），輸出第k大的數(shù)O(nlogn)；方法二：執(zhí)行k步選擇最小值，可以用堆優(yōu)化；O(k*n)

方法三：利用快排的分劃思想O(logn*logn)。

方法四：桶排序O(n)

方法三、四都認(rèn)為是較優(yōu)的算法。第三十頁(yè)，編輯于星期三：五點(diǎn)三十五分。參考答案（方法三）算法思想：利用快排的分劃思想求第k小元素。若分劃位置j==k，則查找成功；若j>k則在(j+1,e)這段里查找第k小位置;若j<k，則在(s..j-1)查找第k小位置時(shí)間復(fù)雜度（logn*logn）第三十一頁(yè)，編輯于星期三：五點(diǎn)三十五分。算法描述：intsearch(intk,intn){ints=1,e=n;while(1){inti=s,j=e;while(i<j){ while(a[j]>=a[i]&&j>=i)j--; while(a[j]>=a[i]&&j>=i)i++; if(i<j)swap(a[i][j]) }if(k==j)returnj;if(k>j)s=j+1;if(k<j)

}}第三十二頁(yè)，編輯于星期三：五點(diǎn)三十五分。

第1步：s=1，e=n;

第2步：循環(huán)做如下操作

2.1分劃，得到i.2.2如果k==i，那么返回A[i];

如果k>i，那么s=i+1,k=k-i;