1. 如何比喻平均查找長度
以二分查找方法從長度為10的有序表中查找一個元素時，平均查找長度為4。
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。
二分查找的時間復雜度是O（2為底的log(n)），也就是說它的平均查找長度只和該有序表的長度有關，當長度為10時，平均查找長度為log10（2為底），其>3，<4，所以平均查找長度為4次。
(1)順序存儲平均搜索長度擴展閱讀：
二分查找的查找過程：
首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。
重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
2. 採用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為多少
(1+n)/2
(1+2+3+...+n)/n = (1+n)/2
對於任意一個序列以及一個給定的元素，將給定元素與序列中元素依次比較，直到找出與給定關鍵字相同的元素，或者將序列中的元素與其都比較完為止。
順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素佔用存儲單元的長度。
(2)順序存儲平均搜索長度擴展閱讀：
刪除L的第i個數據元素，並用e返回其值。
Status ListDelete(SqList &L,int i,ElemType &e) // 演算法2.5
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1
ElemType *p,*q;
if(i<1||i>L.length) // i值不合法
return ERROR;
p=L.elem+i-1; // p為被刪除元素的位置
e=*p; // 被刪除元素的值賦給e
q=L.elem+L.length-1; // 表尾元素的位置
for(++p;p<=q;++p) // 被刪除元素之後的元素左移
*(p-1)=*p;
L.length--; // 表長減1
return OK;
}
3. 長度為10的表，採用順序查找法，平均查找長度ASL是 緊急，在線等
1 查找的基本概念
查找 就是在給定的DS中找出滿足某種條件的結點；若存在這樣的結點，查找成功；否則，查找失敗。
查找表 是一組待查數據元素的集合。
靜態查找 是僅僅進行查詢和檢索操作，不改變查找表中數據元素間的邏輯關系的查找。
動態查找 是除了進行查詢和檢索操作外，還對查找表進行插入、刪除操作的查找，動態地改變查找表中數據元素之間的邏輯關系。
平均查找長度 （ASL-Average Search Length）：在查找過程中，對每個結點記錄中的關鍵字要進行反復比較，以確定其位置。因此，與關鍵字進行比較的平均次數，就成為平均查找長度。它是用來評價一個演算法好壞的一個依據。
對含有n個數據元素的查找表，查找成功時的平均查找長度為：
，其中，n是結點的個數；pi是查找第i個結點的概率；ci是找到第i個結點所需比較的次數。
2 線性表的查找
就介紹三種在線性表中進行查找的方法：順序查找、折半查找和分塊查找。
2.1 順序查找
演算法思想：又稱線性查找，是一種最簡單的查找方法。從第1個元素到最後1個元素，逐個進行比較，直至找到為止。
查找表的存儲結構：既適用於順序存儲結構，也適用於鏈式存儲結構。
例，對關鍵字序列{26，5，37，1，61，11，59，15，48，19}，希望查找關鍵字：37
順序查找演算法框圖：
在等概率情況下，順序查找成功的平均查找長度為：
順序查找演算法簡單，但查找效率低。
2.2 折半查找(又稱二分查找)
是查找一個已排好序的表的最好方法。演算法思想：
將有序數列的中點設置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。即通過一次比較，將查找區間縮小一半。
二分查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，二分查找的先決條件是查找表中的數據元素必須有序。
演算法步驟：
step1 首先確定整個查找區間的中間位置，mid = （ left + right ）/ 2；
step2 用待查關鍵字值與中間位置的關鍵字值進行比較：若相等，則查找成功；若大於，則在後半區域繼續進行二分查找；若小於，則在前半區域繼續進行二分查找。
Step3 對確定的縮小區域再按二分公式，重復上述步驟；
最後 得到結果：要麼，查找成功，要麼，查找失敗。
存儲結構：用一維數組存放。
例，對有序表關鍵字序列{5，10，19，21，31，37，42，48，50，52}，查找k為19及66的記錄。
演算法描述：
折半查找中查到每一個記錄的比較次數可通過二叉樹來描述。
因此折半查找成功時進行的比較次數最多不超過樹的深度。等概率時，折半查找的平均長度為：
當n很大時，ASLbin = log2(n+1)-1。
2.3 分塊查找(又稱索引順序查找)
是順序查找和折半查找的折中改進方法。
方法描述：將n個數據元素「按塊有序」劃分為m塊（m £ n）。每一塊中的結點不必有序，但塊與塊之間必須「按塊有序」，即第1快中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素，……。每個塊中元素不一定是有序的。
演算法描述：
step1 先選取各塊中的最大關鍵字構成一個索引表；
step2 查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；在已確定的塊中用順序法進行查找。
例
分塊查找的平均查找長度為：
ASLbs = Lb + Lw
3 二叉排序樹的查找
前三種查找方法各有千秋。二分法查找效率高，順序法可以採用鏈表存儲結構，操作靈活。但最好是既有二分法的高效率，又有鏈表靈活性的查找方法。二叉排序樹實際上就是將數據元素組織成二叉樹形式，以達到與二分法相同的查找效率，而又具有鏈表的插入、刪除操作的靈活性。
二叉排序樹查找步驟：
step1 首先建立起二叉排序樹。
step2 將待查關鍵字值與樹根結點進行比較，若相等，查找成功；
step3 否則根據比較結果確定查找路徑：若小於根結點的關鍵字值，則與左子樹的根結點的關鍵字值進行比較；若大於等於根結點的關鍵字值，則與右子樹的根結點的關鍵字值進行比較。
step4 重復上述步驟，直到要麼找到，查找成功；要麼找不到，查找失敗。
顯然，類同折半查找，與關鍵字最大比較次數為樹的深度。因此，二叉樹的構造對二叉樹的查找效率有很大的影響。
例，若按關鍵字序列{45，24，55，12，37，53，60，28，40，70}構造二叉樹，則
若按關鍵字序列{12，24，28，37，40，45，53，55，60，70}構造二叉樹，則
兩棵二叉樹的深度分別為4和10。
二叉排序樹的平均查找長度為O(log2n)。
4 散列表的查找
前面討論的查找方法中，結點在表中的位置是隨機的，其位置與關鍵字之間不存在對應關系。因此在查找時，總是進行一系列的和關鍵字的比較，查找的效率與查找過程中進行比較的次數有關。散列表的查找則是一種不用比較而直接計算出記錄所在地址，直接進行查找的方法。散列查找也稱為哈希查找(Hashing)。
4.1 散列表的概念
散列表 由散列函數的值組成的表。散列查找是建立在散列表的基礎上，它是線性表的一種重要存儲方式和檢索方法。在散列表中可以實現對數據元素的快速檢索。
散列函數 散列表中元素是由散列函數確定的。將數據元素的關鍵字K作為自變數，通過一定的函數關系（稱為散列函數），計算出的值，即為該元素的存儲地址。表示為：
Addr = H（key）
例：以學生的學號作為學生記錄的關鍵字，取學號的後兩位作為散列後的地址，則可以得到下列這個關鍵字和地址的散列表：
顯然，採用的散列函數為 H(k)=k-525000。
通常關鍵字集合比地址集合大得多，散列函數是個壓縮函數，這樣就會產生不同的關鍵字映射到同一散列地址的情況。如：
可見，三個不同的學號關鍵字，散列到同一地址79上。這種現象叫沖突。為了不產生沖突現象就要求使用均勻的散列函數，即散列地址是均勻分布的。但由於關鍵字集合比地址集合大得多，不可能完全避免沖突，因此在沖突出現時就要有解決辦法。
4.2 散列函數的構造
散列函數是一個映射，它的設置很靈活，只要使得任何關鍵字由此所得的散列函數值都出現在表長允許的范圍內即可。建立散列函數的原則:
(1) 均勻性: H（key）的值均勻分布在散列表中；
(2) 簡單性: 以提高地址計算的速度。
散列函數常用的構造方法：
數字選擇法
平方取中法
折疊法
除留余數法（求模取余法）
基數轉換法
隨機數法
4.2.1 數字選擇法
若事先知道關鍵字集合，當關鍵字的位數比散列表地址位數多時，則可選取數字分布比較均勻的若干位組成散列地址。
選取的原則：盡量避免計算出的地址有沖突。
例： 有一組由8位數字組成的關鍵字，如表15.2左邊一列所示。
分析這6個關鍵字可發現，前3位是相同的，第五位也只取2、7兩個值，分布不均勻。第4、6、7、8位數字則分布較為均勻，因此，可根據散列表的長度取其中幾位或它們的組合作為散列地址。例如，若表長為1000（地址為0～999），則可取4、6、7位的三位數字作為散列地址；若表長為100（地址為0～99），則可取4、6與7、8位之和並捨去進位作為散列地址。
這種方法的前提是：必須能預先估計到所有關鍵字的每一位上各中數字的分布情況。
4.2.2 平方取中法
通過關鍵字的平方值擴大差別，取關鍵字平方後的中間幾位或其組合作為散列地址。因為乘積的中間幾位數和乘數的每一位都相關，故由此產生的散列地址也較均勻，所取位數由散列表的表長決定。這是一種較常用的構造散列函數的方法。通常在選定散列函數時不知道關鍵字的全部情況，取其中的哪幾位也不一定合適，在這種情況下，取一個數平方後的中間幾位數作散列地址。
例： 關鍵字為 （0100，0110，1010，1001，0111）
關鍵字的平方結果（0010000，0012100，1020100，1002001，0012321）
若表長為1000，則可取其中間三位作為散列地址集，即
（100，121，201，020，123）
4.2.3 折疊法
若關鍵字位數很多，可將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為散列地址。折疊法又分移位疊加和邊界疊加兩種。移位疊加是將各段最低位對齊，然後相加；邊界疊加則是兩個相鄰的段沿邊界來回折疊，然後對齊相加。
例如：某資料室藏書近萬冊。採用國際標准圖書編號（ISBN），每個編號10位十進制數字。可用折疊法構造一個4位數的哈希函數。
例： 關鍵字 key=58242324169，取散列表長度為1000，則
4.2.4 除留余數法
取關鍵字被某個不大於散列表表長m的數p除後所得余數為散列地址。
H（key） = key % p
這是一種最簡單，也是最常用的構造散列函數的方法。
例：關鍵字 32834872 ，散列表長為4位十進制數。
p值可取小於9999的數，例如，取5000；
H（key）= 32834872 % 5000 = 4872
由經驗得知：通常選p為小於散列表長的最大素數。
4.2.5 基數轉換法
把關鍵字看成是另一個進制上的數後，再把它轉換成原來進制上的數，取其中的若干位作為散列地址。一般取大於原來基數的數作為轉換的基數，並且兩個基數要互素。
4.2.6 隨機數法
選取一個隨機函數，取關鍵字的隨機函數值作為它的散列地址，即
H(key)=random(key)
其中random為隨機函數。
通常，當關鍵字長度不等時採用此法構造散列地址較適當。
我自己家的電腦有點問題，不能算出來啦，你自己參考一下吧
4. 分塊檢索中，若索引表和各塊內均用順序查找，則有900個元素線性表，若分成25塊，求其平均查找長度
長度為n(900)的表分成均等的b（25）個子表，則每個子表的長度為s，b=n/s（900/25=36）。
順序查找時成功的平均查找長度為：
（b+s)/2+1=(25+36)/2+1=44
例如：
每塊最佳長度為：根號625= 25，即每塊25個結點，一共分為25塊，此時平均查找長度=2((25+1)/2)= 26
(4)順序存儲平均搜索長度擴展閱讀：
分塊查找的速度雖然不如折半查找演算法，但比順序查找演算法快得多，同時又不需要對全部節點進行排序。當節點很多且塊數很大時，對索引表可以採用折半查找，這樣能夠進一步提高查找的速度。
分塊查找由於只要求索引表是有序的，對塊內節點沒有排序要求，因此特別適合於節點動態變化的情況。當增加或減少節以及節點的關鍵碼改變時，只需將該節點調整到所在的塊即可。在空間復雜性上，分塊查找的主要代價是增加了一個輔助數組。
5. 對於長度為9的順序存儲的有序表，若採用二分查找，則平均查找長度為( )除以9。
選C
首先你知道原理吧
第五個查找1次
第二個和第七個查找兩次
第一，第三和第六，第八要查找三次
第四和第九要查找四次
一共25次
6. 順序查找法平均查找長度是多少
最好的情況：目標在第一個,一次找到
·····
最壞的情況：目標在最後一個,n次找到
那麼：
平均長度：
（1+2+···+n）/n
=(n(n+1)/2)/n
=(n+1)/2