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

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

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

在哈希表中查找成功和不成功時(shí)的平均查找長(zhǎng)度如何計(jì)算？

我不知道你所說的平均搜索長(zhǎng)度是什么意思。一般來說，哈希表會(huì)在考試中測(cè)試，因?yàn)槠渌谋容^簡(jiǎn)單。

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

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

ASL=p1c1，P2C2，p3c3…

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

其中C是每個(gè)數(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