阿摩線上測驗 登入

申論題資訊

試卷:110年 - 110 關務特種考試_四等_資訊處理:程式設計概要#98238
科目:程式設計
年份:110年
排序:0

申論題內容

一、令一雜湊函式 f(p) = p mod 13,且該函式以線性探測(Linear Probing)處理碰撞,若依序輸入下列資料 47、11、26、62、50、25、39、76,請問該筆資料中最大搜尋次數為何?

詳解 (共 1 筆)

詳解 提供者:hchungw
要解決這個問題,我們需要按順序將資料插入到雜湊表中,並計算每個數據插入所需的搜尋次數。使用雜湊函式 
?
(
?
)
=
?
m
o
d


13
f(p)=pmod13 和線性探測法來處理碰撞。
首先,確定每個數據的初始雜湊位置:
47 mod 13 = 8
11 mod 13 = 11
26 mod 13 = 0
62 mod 13 = 10
50 mod 13 = 11(碰撞)
25 mod 13 = 12
39 mod 13 = 0(碰撞)
76 mod 13 = 11(碰撞)
根據線性探測法逐一處理碰撞,並計算每個數據插入時所需的搜尋次數:
47:插入位置 8,無碰撞,搜尋次數為 1。
11:插入位置 11,無碰撞,搜尋次數為 1。
26:插入位置 0,無碰撞,搜尋次數為 1。
62:插入位置 10,無碰撞,搜尋次數為 1。
50:插入位置 11,碰撞,線性探測至位置 12,無碰撞,搜尋次數為 2。
25:插入位置 12,無碰撞,搜尋次數為 1。
39:插入位置 0,碰撞,線性探測至位置 1,無碰撞,搜尋次數為 2。
76:插入位置 11,碰撞,線性探測至位置 12,碰撞,再探測至位置 0,碰撞,再探測至位置 1,碰撞,再探測至位置 2,無碰撞,搜尋次數為 5。
因此,這些數據中最大搜尋次數為 5。