※ 引述《fzrmitsul (我的妹妹很可愛)》之銘言： : 1.假設有一程式在某台電腦中執行需要100秒，其中乘法指令共花掉80秒。若想縮短 : 執行時間，前提是只增加乘法器的速度，試問該乘法器至少需提升幾時間，才能 : 將執行時間從100秒縮短為25秒? : (a)4倍 (b)5倍 (c)12倍 (d)16倍 : 不知這題該怎麼算。 乘法指令80秒 => 其他指令20秒 ∴TOTAL 100秒->25秒 => 乘法指令80秒->5秒 1/5 ÷1/80 = 16倍 答案為D : 2.若以函數f(關鍵值)=(關鍵值+i*5) mod 23建立hashing table，其中i代表碰撞發生 : 次數。當關鍵值分別為43,20,66,23,91的資料依序被存在原先為空的雜湊表中 : 則全部儲存完後，下面哪個位址尚未儲存關鍵值? : (a)0 (b)7 (c)20 (d)21 : 我算的結果是f(43)=x..餘20 : f(20)=x..餘20..發生碰撞(那是要把這個關鍵值存在哪呢?21嗎?) : f(66)=x...餘2 : f(23)=x...餘0 : f(91)=x...餘22 : 為什麼答案會是d呢??那為什麼不是b呢?? : 可能觀念有錯。請各位先進糾正.. f(20)為25 ∵f(43) = 20 f(20) = 20 發生碰撞 => i = 1 => f(20) = (20+1*5)%23 = 2 f(66) = 20 發生碰撞 => i = 2 => f(66) = (66+2*5)%23 = 7 f(23) = 0 f(91) = 22 所以答案當然為D 如果只是依照公式來算，A也是考量答案 所以我認為題目沒有寫清楚 正確的函數表示應該是： f(關鍵值) = 關鍵值 % 23 = A => 當之前沒有出現過A的結果 f(關鍵值) = (關鍵值+iA*5) % 23 => 當A之前已經出現過 iA = A累積出現的次數 = 發生碰撞的次數 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.117.92.133