課后答案網(wǎng) 9 章 集合 一、基礎(chǔ)知識題 若對長度均為 n 的有序的順序表和無序的順序表分別進行順序查找，試在下列三種情況下分別討論二者在等概率情況下平均查找長度是否相同？ （ 1）查找不成功，即表中沒有和關(guān)鍵字 K 相等的記錄； （ 2）查找成功，且表中只有一個和關(guān)鍵字 K 相等的記錄； （ 3）查找成功，且表中有多個和關(guān)鍵字 K 相等的記錄，要求計算有多少個和關(guān)鍵字 K 相等的記錄。 【解答】 （ 1）平均查找長度不相同。前者在 n+1 個位置均可能失敗，后者失敗時的查找長度都是 n+1。 （ 2）平均查找長度相同。在 n 個位置上均可能成功 。 （ 3）平均查找長度不相同。前者在某個位置上 (1 f 是 p 的雙親 if(p-i) f=p;p=p- s=(; 申請結(jié)點空間 s-i; s- s-if(f= T=s; 根結(jié)點 if(s- f-s; 左子女 f-s; 右子樹根結(jié)點的值大于等于根結(jié)點的值 算法結(jié)束 寫刪除二叉排序樹中值是 X 的結(jié)點的算法。要求刪除結(jié)點后仍然是二叉排序樹，并且高度沒有增長。 【題目分析】在二叉排序樹上刪除結(jié) 點，首先要查找該結(jié)點。查找成功后，若該結(jié)點無左子樹，則可直接將其右子樹的根結(jié)點接到其雙親結(jié)點上；若該結(jié)點有左子樹，則將其左子樹中按中序遍歷的最后一個結(jié)點代替該結(jié)點，從而不增加樹的高度。 X) 在二叉排序樹 ，刪除其關(guān)鍵字為 X 的結(jié)點 f,p=p & p-X) 查找值為 X 的結(jié)點 if(p-) f=p; p=p- f=p; p=p- if(p= 無關(guān)鍵字為 X 的結(jié)點 n” ); ); p- 被刪結(jié)點無左子樹 if(f-p) f-p- 將被刪結(jié)點的右子樹接到其雙親上 f-p- q=p; s=p- 被刪結(jié)點有左子樹 s-= 查左子樹中最右下的結(jié)點 (中序最后結(jié)點 ) q=s; s=s- p-s- 結(jié)點值用其左子樹最右下的結(jié)點的值代替 if(q=p) p-s- 被刪結(jié)點左子 樹的根結(jié)點無右子女 q-s- s 是被刪結(jié)點左子樹中序序列最后一個結(jié)點 s); 算法結(jié)束 設(shè)二叉排序樹的各個元素值均不相同，設(shè)計一個遞歸算法按遞減次序打印各元素的值。 【題目分析】按著“右子樹根結(jié)點左子樹”遍歷二叉排序樹，并輸出結(jié)點的值。 按遞減次序輸出二叉排序樹結(jié)點的值 課后答案網(wǎng) s,p= s 是元素為二叉樹結(jié)點指針的棧，容量足夠大 ; p | ) p) s+p; bt=p- 沿右子樹向下 if() p=s p- p=p- 結(jié)束 以下是遞歸輸出，算法思想是一樣的。 按遞 減次序輸出二叉排序樹結(jié)點的值 p= if(p) 中序遍歷右子樹 p- 訪問根結(jié)點 中序遍歷左子樹 結(jié)束 記錄 ， 關(guān)鍵字值從小到大順序存儲在數(shù)組 r1.，在 rn+1處設(shè)立一個監(jiān)視哨，其關(guān)鍵字值為 + ; 試寫一查找給定關(guān)鍵字 k 的算法 ;并畫出此查 找過程的判定樹，求出在等概率情況下查找成功時的平均查找長度。 r， n， k) 在 n 個關(guān)鍵字從小到大排列的順序表中，查找關(guān)鍵字為 k 的結(jié)點 rn+1 在高端設(shè)置監(jiān)視哨 i=1; riX) 查找值為 X 的結(jié)點， f 指向當(dāng)前結(jié)點的雙親 f=p; if(p-p=p- 課后答案網(wǎng) p) 無值為 x 的 結(jié)點，插入之 p=(); p-; p- p-if(t= t=p; 若初始為空樹，則插入結(jié)點為根結(jié)點 if(f-) f-p; f-p; p-; 查詢成功，值域為 X 的結(jié)點的 1 設(shè)一棵平衡二叉樹的每個結(jié)點都標(biāo)明了平衡因子 b，試設(shè)計一個算法，求平衡二叉樹的高度。 【題目分析】 因為二叉樹各結(jié)點已標(biāo)明了平衡因子 b，故從根結(jié)點開始記樹的層次。根結(jié)點的層次為 1，每下一層，層次加 1，直到層數(shù)最大的葉子結(jié)點，這就是平衡二叉樹的高度。當(dāng)結(jié)點的平衡因子 b 為 0 時，任選左、右一分枝向下查找，若 b 不為 0，則沿左 (當(dāng) b=1 時 )或右 (當(dāng) b= )子樹向下查找。 t) 求平衡二叉樹 t 的高度 ; p=t; p) ; 樹的高度增 1 if(p- 1 沿右分枝向下 p=p- 0 沿左分枝向下 ( 平衡二叉樹的高度 算法結(jié)束 二叉排序樹的存儲 結(jié)構(gòu)為： *一個結(jié)點 *x 的 的值是以該結(jié)點為根的子樹中結(jié)點的總數(shù)（包括 *x 本身）。例如，下圖中 x 所指結(jié)點的 為 4。設(shè)樹高為 h，試寫一時間為 O(h)的算法 ， x)返回 x 所指結(jié)點在二叉排序樹 T 的中序序列里的排序序號，即：求 x結(jié)點是根為 T 的二叉排序樹中第幾 個最小元素。 【題目分析】 因為 T 是二叉排序樹，則可利用二叉排序樹的性質(zhì)，從根往下查找結(jié)點 *x。若 T 的左子樹為空，則其中序序號為 1，否則為 T-。設(shè) T 的中序序號為 r，其左子女 p 的中序序號和右子女 q 的中序序號分別為 r+q-。 ， x) 在二叉排序樹 T 上，求結(jié)點 x 的中序序號 - r=T-; r=1; 根結(jié)點的中序序號 ) -x- 到左子樹去查找 T=T-) -r= r= - 到右子樹去查找 T=T-) -r=r+T-; r=r+1; 課后答案網(wǎng) r); 返回 *x 結(jié)點的中序序號 0); T 樹上無 x 結(jié)點 結(jié)束算法 法 2：本題的另一種解法是設(shè) r 是以 *x 為根的中序序號。初始時，若 x 的左子樹為空， r=1;否則，r=x-。利用結(jié)點的雙親域，上溯至根 結(jié)點，即可求得 *x 的中序序號。 ， x) 在二叉排序樹 T 上，求結(jié)點 x 的中序序號 if(x-r=x-; r=1; x 的這個序號是暫時的 p=x; p 要上溯至根結(jié)點 T，求出 *x 的中序序號 p!=T) if(p=p- p 是其雙親的右子女， if(p-r+; p 結(jié)點的雙親排在 p 結(jié)點的前面 r=r+p-; 雙親及左子樹均排在 p 前面 p=p- r); 知某哈希表 裝填因子小于 1，哈希函數(shù) H(關(guān)鍵字的第一個字母在字母表中的序號。 (1) 處理沖突的方法為線性探測再散列。編寫按第一個字母的順序輸出哈希表中所有關(guān)鍵字的算法。 (2) 處理沖突的方法為鏈地址法。編寫一個計算在等概率情況下查找不成功的平均查找長度的算法。 【題目分析】 本題未直接給出哈希表表長，但已給出裝填因子小于 1，且哈希函數(shù) H(k)為關(guān)鍵字第一個字母在字母表中的序號，字母 A的序號為 1，表長可設(shè)為 n(n 27)，而鏈地址法中，表長 26。查找不成功是指碰到空指針為止 (另一種觀點是空指針不計算比較次數(shù) )。 (1)h)按關(guān)鍵字第一個字母在字母表中的順序輸出各關(guān)鍵字 i,j; i=1;i 26； i+) 哈希地址 1 到 26 j=1； n” ); hj!= 設(shè)哈希表初始值為 if(hj)=i) 取關(guān)鍵字第一字母在字母表中的序號 %s”， hj)； j=(j+1)% n； 2)h) 鏈地址解決沖突的哈希表查找不成功時平均查找長度 i,j; ; 記查找不成功的總的次數(shù) p; i=1; j; ( 課后答案網(wǎng) 一個 100*100 的稀疏矩陣，其中 1%的元素為非零元素，現(xiàn)要求用哈希表作存儲結(jié)構(gòu)。 （ 1）請設(shè)計一個哈希表 （ 2）請寫一個對你所設(shè)計的哈希表中給定行值和列值存取矩陣元素的算法；并對算法所需時間和用一維數(shù)組 (每個分量存放一個非零元素的行值、列值和元素值 )作存儲結(jié)構(gòu)時存取元素的算法進行比較。 【題目分析】非零元素個數(shù)是 100，負(fù)載因子取 長 125 左右，取 p 為 127，散列地址為 0 到 126。哈希函數(shù)用 H(k)=(3*i+2*j) % 127， i， j 為行值和列值。 #m 127 i,j; v;m) 生成稀疏矩陣的哈希表，表中元素值初始化為 0 k=0； k100； k+) i,&j,& 設(shè)元素值為整型 h=(3*i+2*j)% m; 計算哈希地址 Th0