【正文】 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ASL=(1*6+2*4+3+4)/12= 關鍵字 (19,14,23,1,68,20,84,27,55,11,10,79) 哈希表的查找 2022年 8月 14日 使用平均查找長度 ASL來衡量查找算法， ASL取決于 ? 哈希函數(shù) ? 處理沖突的方法 ? 哈希表的裝填因子 哈希表的長度表中填入的記錄數(shù)??哈希表的查找效率分析 ? 越大，表中記錄數(shù)越多，說明表裝得越滿，發(fā)生沖突的可能性就越大，查找時比較次數(shù)就越多。 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個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（ ）。 A． (n1)/2 B． n/2 C． (n+1)/2 D． n （ 2）適用于折半查找的表的存儲方式及元素排列要求為（ ） A．鏈接方式存儲，元素無序 B．鏈接方式存儲，元素有序 C．順序方式存儲，元素無序 D．順序方式存儲，元素有序 （ 3）當在一個有序的順序表上查找一個數(shù)據(jù)時，既可用折半查找，也可用順序查找，但前者比后者的查找速度（ ） A．必定快 B．不一定 C．在大部分情況下要快 D．取決于表遞增還是遞減 終極任務 （完成每任務加經(jīng)驗值 100） 教材 P1203頁， 1．選擇題 （ 4）折半查找有序表（ 4， 6， 10， 12， 20， 30， 50， 70， 88，100）。若查找表中元素 58，則它將依次與表中（ ）比較大小，查找結果是失敗。 A． 20， 70， 30， 50 B． 30， 88， 70， 50 C． 20， 50 D． 30， 88， 50 （ 5）對 22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（ ）次關鍵字。 A． 3 B． 4 C． 5 D． 6 （ 6）折半搜索與二叉排序樹的時間性能（ ）。 A．相同 B．完全不同 C．有時不相同 D．數(shù)量級都是 O(log2n) 終極任務 （完成每任務加經(jīng)驗值 100） 教材 P1203頁， 1．選擇題 （ 7）分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是（ ）。 A．（ 100， 80， 90， 60， 120， 110， 130） B．（ 100， 120， 110， 130， 80， 60， 90） C．（ 100， 60， 80， 90， 120， 110， 130） D． (100， 80， 60， 90， 120， 130， 110) （ 8）在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為 A，并已知 A的左孩子的平衡因子為 0右孩子的平衡因子為 1，則應作（ ）型調整以使其平衡。 A． LL B． LR C． RL D． RR （ 9）下列關于 m階 B樹的說法錯誤的是（ ）。 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． B樹和 B+樹都是平衡的多叉樹 B． B樹和 B+樹都可用于文件的索引結構 C． B樹和 B+樹都能有效地支持順序檢索 D． B樹和 B+樹都能有效地支持隨機檢索 （ 11） m階 B樹是一棵（ ）。 A． m叉排序樹 B． m叉平衡排序樹 C． m1叉平衡排序樹 D． m+1叉平衡排序樹 （ 12）下面關于哈希查找的說法，正確的是（ ）。 A．哈希函數(shù)構造的越復雜越好，因為這樣隨機性好，沖突小 B．除留余數(shù)法是所有哈希函數(shù)中最好的 C．不存在特別好與壞的哈希函數(shù)，要視情況而定 D．哈希表的平均查找長度有時也和記錄總數(shù)有關 終極任務 （完成每任務加經(jīng)驗值 100） 教材 P1203頁， 1．選擇題 （ 13）下面關于哈希查找的說法，不正確的是（ ）。 A．采用鏈地址法處理沖突時，查找一個元素的時間是相同的 B．采用鏈地址法處理沖突時，若插入規(guī)定總是在鏈首，則插入任一個元素的時間是相同的 C．用鏈地址法處理沖突，不會引起二次聚集現(xiàn)象 D．用鏈地址法處理沖突，適合表長不確定的情況 （ 14）設哈希表長為 14，哈希函數(shù)是 H(key)=key%11，表中已有數(shù)據(jù)的關鍵字為 15， 38， 61， 84共四個，現(xiàn)要將關鍵字為 49的元素加到表中，用二次探測法解決沖突，則放入的位置是（ ）。 A． 8 B． 3 C． 5 D． 9 （ 15）采用線性探測法處理沖突，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的關鍵字 ( )。 A．不一定都是同義詞 B．一定都是同義詞 C．一定都不是同義詞 D．都相同 預習任務（經(jīng)驗值 200） ？ ？ ？ ？它是利用哪兩種現(xiàn)象提高排序效率的？ 比較關鍵字大小 和 移動記錄位置 對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 插入排序、交換排序（快速排序）、選擇排序（堆排序）、歸并排序、基數(shù)排序 對待排記錄序列先作“宏觀”調整，再作“微觀”調整。將記錄序列分成若干子序列，分別對每個子序列進行插入排序。 插入排序在記錄個數(shù)較少和序列基本有序條件下效率高的現(xiàn)象。