順序查找n個元素的順序表，當使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為？所有n個元素都需要比較一次，但沒有一個成功。最后，哨兵還需要比較一次，哪個比較成功?？偣策M行了N 1比較。示例：有五個元素：

順序查找n個元素的順序表，當使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為？

所有n個元素都需要比較一次，但沒有一個成功。最后，哨兵還需要比較一次，哪個比較成功?？偣策M行了N 1比較。示例：有五個元素：1、2、3、4、5。你要找的元素是8。那么8是哨兵。順序如下：8、1、2、3、4、5。從5開始，你需要比較6次。比較是成功的。sentinel的下標是0，因此返回值是0。

在哈希表中查找成功和不成功時的平均查找長度如何計算？

我不知道你所說的平均搜索長度是什么意思。一般來說，哈希表會在考試中測試，因為其他的比較簡單。

對于具有N個數(shù)據(jù)元素的查找表，成功查找的平均長度為ASL=∑Pici（I=1，2，3，…），N）。其中：Pi是查找表中第I個數(shù)據(jù)元素的概率，CI是找到第I個數(shù)據(jù)元素時進行比較的次數(shù)。

眾所周知，要散列的線性表是（38、25、74、63、52、48），散列函數(shù)是h（k）=kmod7。如果使用線性檢測的開放地址方法來處理沖突，則平均查找長度為：

ASL=p1c1，P2C2，p3c3…

ASL=1/N（C1，C2，C3…]…

其中C是每個數(shù)字的查詢數(shù)

根據(jù)h（k）=kmod7，

38----1

25----1

74----2

63----1

52----4

48----3

所以ASL=1/6（1 1 4 3）=2