【正文】 將記錄序列分成若干子序列，分別對每個子序列進行插入排序。 A．采用鏈地址法處理沖突時，查找一個元素的時間是相同的 B．采用鏈地址法處理沖突時，若插入規(guī)定總是在鏈首，則插入任一個元素的時間是相同的 C．用鏈地址法處理沖突，不會引起二次聚集現(xiàn)象 D．用鏈地址法處理沖突，適合表長不確定的情況 （ 14）設哈希表長為 14，哈希函數(shù)是 H(key)=key%11，表中已有數(shù)據(jù)的關鍵字為 15， 38， 61， 84共四個，現(xiàn)要將關鍵字為 49的元素加到表中，用二次探測法解決沖突，則放入的位置是（ ）。 A．根結點至多有 m棵子樹 B．所有葉子都在同一層次上 C．非葉結點至少有 m/2 (m為偶數(shù) )或 m/2+1（ m為奇數(shù)）棵子樹 D．根結點中的數(shù)據(jù)是有序的 終極任務 （完成每任務加經(jīng)驗值 100） 教材 P1203頁， 1．選擇題 （ 10）下面關于 B和 B+樹的敘述中，不正確的是（ ）。 A． 3 B． 4 C． 5 D． 6 （ 6）折半搜索與二叉排序樹的時間性能（ ）。 O(1)? 2022年 8月 14日 隨機探測法）線性探測法拉鏈法）()1l n (1)()111(21(21????????????A S LA S LA S LASL與裝填因子 ?有關！既不是嚴格的 O(1)，也不是 O(n) 哈希表的查找效率分析 2022年 8月 14日 ?對哈希表技術具有 很好的平均性能 ，優(yōu)于一些傳統(tǒng)的技術 ?鏈地址法 優(yōu)于開地址法 ?除留余數(shù)法 作哈希函數(shù)優(yōu)于其它類型函數(shù) 幾點結論 2022年 8月 14日 （ 折半查找 ）的查找算法及其性能分析方法； 二叉排序樹的構造和查找 算法及其性能分析方法； 插入 算法，了解二叉排序樹的刪除算法； （除留余數(shù)法） 的構造 解決沖突的方法 及其特點 ? 開放地址法（ 線性探測法、二次探測法） ? 鏈地址法 ? 給定實例計算平均查找長度 ASL， ASL依賴于 裝填因子 ? 小結 終極任務 （完成每任務加經(jīng)驗值 100） 教材 P1203頁， 1．選擇題 （ 1）對 n個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（ ）。 缺點： 可能使第 i個哈希地址的同義詞存入第 i+1個地址，這樣本應存入第 i+1個哈希地址的元素變成了第 i+2個哈希地址的同義詞， …… ，產(chǎn)生 “ 聚集 ” 現(xiàn)象，降低查找效率。 缺點： 要占用連續(xù)地址空間，空間效率低。 … 14 … 11 … 9 … 內(nèi)容 地址 … 39 … 25 24 23 14 11 9 23 25 39 例 2 2022年 8月 14日 根據(jù)哈希函數(shù) H（ k）＝ k 查找 key=9,則訪問 H(9)=9號地址，若內(nèi)容為 9則成功； 若查不到，則返回一個特殊值，如空指針或空記錄。在等概率的前提下，上述兩圖的 平均查找長度 為： )(35/)54321()()23221(11右圖左圖????????????????niiiniiicpcp40 24 55 12 37 12 24 37 40 55 查找的性能分析 2022年 8月 14日 平均查找長度和二叉樹的形態(tài)有關，即， 最好： log2n（形態(tài)勻稱，與二分查找的判定樹相似） 最壞 : （ n+1)/2（單支樹） 查找的性能分析 40 24 55 12 37 12 24 37 40 55 )(35/)54321()()23221(11右圖左圖????????????????niiiniiicpcp 2022年 8月 14日 問題：如何提高二叉排序樹的查找效率？ 盡量讓二叉樹的形狀均衡 ?左、右子樹是平衡二叉樹； ?所有結點的左、右子樹深度之差的絕對值 ≤ 1 平衡二叉樹 平衡因子 :該結點左子樹與右子樹的高度差 2022年 8月 14日 ? 任一結點的平衡因子只能?。? 0 或 1；如果樹中任意一個結點的平衡因子的絕對值大于 1，則這棵二叉樹就失去平衡，不再是 AVL樹； ? 對于一棵有 n個結點的 AVL樹，其 高度保持在O(log2n)數(shù)量級， ASL也保持在 O(log2n)量級。 –被刪結點缺右子樹 ，可以拿它的左子女結點頂替它的位置，再釋放它。 【 算法思想 】 2022年 8月 14日 BSTree SearchBST(BSTree T,KeyType key) { if((!T) || key==T) return T。 2022年 8月 14日 查找成功時比較次數(shù)：為該結點在判定樹上的層次數(shù)，不超過樹的深度 d = ? log2 n ? + 1 查找不成功的過程就是走了一條從根結點到外部結點的路徑 d或d1。 2022年 8月 14日 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 21 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 折半查找 若 k==R[mid].key，查找成功 若 kR[mid].key，則 high=mid1 若 kR[mid].key，則 low=mid+1 2022年 8月 14日 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 找 70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1