資料結構實踐項目——查找（一）

本文針對：

0801 查找問題導學

0802 線性表的順序查找

0803 線性表的折半查找

0804 索引存儲結構

0805 分塊查找

0806 二叉排序樹

0807 二叉排序樹（續）

0808 平衡二叉樹

1、對于a[0..10]有序表{12,18,24,35,47,50,62,83,90,115,134}

（1）用二分查找法查找 90時，需進行多少次查找可确定成功？

（2）當查找47時需進行多少次查找可确定成功？

（3）查找100時，需進行多少次查找才能确定不成功？

（4）求成功和不成功時的平均查找長度。

（5）構造對于這個序列的判定樹，并再求成功和不成功時的平均查找長度。

2、現給出一個分塊有序的資料表，每塊中元素的個數s=8，其中的資料有：

22,4,23,11,20,2,15,13,30,45,26,34,29,35,26,36,55,98,56,74,61,90,80,96,127,158,116,114,128,113,115,102,184,211,243,188,187,218,195,210,279,307,492,452,408,361,421,399,856,523,704,703,697,535,534,739

（1）構造索引表，并畫出索引存儲結構；

（2）請描述查找61的過程，需要多少次比較；

（3）請描述查找739的過程，需要多少次比較；

（4）請描述查找200的過程，經過多少次比較後才能确定找不到。

3、将整數序列{43,52,75,24,10,38,67,55,63,60}中的數依次插入到一棵空的二叉排序樹中，構造出相應的二叉排序樹，要求用圖形給出構造過程。

4、将整數序列{43,52,75,24,10,38,67,55,63,60}依次插入到一棵空的平衡二叉樹中，試構造相應的平衡二叉樹，要求用圖形給出構造過程。

【項目1 - 驗證算法】

運作并本周視訊中所講過的算法，觀察結果并領會算法。

1、認真閱讀并驗證折半查找算法。請用有序表{12,18,24,35,47,50,62,83,90,115,134}作為測試序列，分别對查找90、47、100進行測試。

2、認真閱讀并驗證分塊查找算法。請用22,4,23,11,20,2,15,13,30,45,26,34,29,35,26,36,55,98,56, 74,61,90,80,96,127,158,116,114,128,113,115,102,184,211,243,188,187,218,195,210,279,307,492,452,408,361,421,399,856,523,704,703,697,535,534,739(共n=56個資料，每塊資料個數s=8)作為資料表，自行構造索引表，分别對查找61、739、200進行測試。

3、認真閱讀并驗證二叉排序樹相關算法。

（1）由整數序列{43,52,75,24,10,38,67,55,63,60}構造二叉排序樹；

（2）輸出用括号法表示的二叉排序樹；

（3）用遞歸算法和非遞歸算法查找關鍵字55；

（4）分别删除43和55，輸出删除後用括号法表示的二叉排序樹。

4、認真閱讀并驗證平衡二叉樹相關算法。

（1）由整數序列{43,52,75,24,10,38,67,55,63,60}構造avl樹；

（2）輸出用括号法表示的avl樹；

（3）查找關鍵字55；

【項目2 - 二叉樹排序樹中查找的路徑】

設計一個算法，輸出在二叉排序中查找時查找某個關鍵字經過的路徑。

【項目3 - 是否二叉排序樹？】

設計一個算法，判斷給定的二叉樹是否是二叉排序樹。