資料結構 - 考試

By Emma
at 2013-03-22T17:08

Table of Contents

問題一:
設一表格長度為n,表格內第i項目之取用機率為Pi，
查詢表內第i項目比較之次數為Ci，請寫出平均查詢長度之公式!

答案:ΣCiPi+1

這題我認為答案是ΣCiPi，不知道為什麼會多加1

問題二:

如果hash table有m個位置，現在有n個資料要依序插入，
請計算整個插入過程中，平均會有幾次碰撞?

這題我的計算是:
(0+1+2+....+n-1)/n
但是答案卻是:
(0+1+2+....+n-1)/m

這是我搞錯還是答案錯了阿??
不是要除以資料數才對嗎?

麻煩知道的大大為我解答一下，感謝><

--

All Comments

By Tom
at 2013-03-23T05:38

問題2 我覺得塞入第一個的碰撞機率是0/m 之後依序1/m 2/m

By Tom
at 2013-03-25T04:13

所以應該是/m 不知道這個想法對不對~煩請版友指證謝謝~

By Tom
at 2013-03-28T22:47

題目出得不好題意不清兩題都是...
第二題平均碰撞次數第二個node插入的時候

By Erin
at 2013-04-01T21:32

第一次碰撞機率為1/m*1 第二次? (1/m)^2*2?

By Emma
at 2013-04-03T23:18

只算第一次碰撞的機率? 第二次怎麼算演算法沒寫清楚

By Odelette
at 2013-04-08T20:52

我好像想錯了QAQ 請跳過我的想法orz

By Michael
at 2013-04-13T20:01

第二題應該跟L大講的一樣就想成每一次插入時 m個位置都

By Lauren
at 2013-04-16T16:37

試一次算碰撞次數在平均m 再全部加起來

By Eden
at 2013-04-18T10:21

第一題不用考慮長度i嗎不是算平均長度嗎

By Caitlin
at 2013-04-21T15:06

因為每個slot都有機會填入資料跟碰撞所以要用m

By Eden
at 2013-04-21T21:14

平均長度怎沒考慮？

By Poppy
at 2013-04-25T20:03

我第一題答案是sigma pi(ci+1)

By Megan
at 2013-04-27T10:05

喔我弄錯了不過對一個點查詢長度不是要較比較次數少1嗎?

By Una
at 2013-04-30T09:13

第一次碰撞表中只有1個有放資料所以是1/M 第二次碰撞表裡

By Sarah
at 2013-05-02T18:35

第一題題目有點看不懂是要算平均次數?

Related Posts

藍一鴻財政學題庫班

By Isabella
at 2013-03-22T16:40

對非本科系的我財政讀的真辛苦用看的大概可以懂但因不常接觸也忘的快想請問大家有沒有人上過藍一鴻老師的題庫班是針對申論題嗎？因為只有四堂課不知道效果好不好謝謝大家 - ...

請問法院組織法

By Olga
at 2013-03-22T16:23

去年法官法新修正公佈，請問對考法組的有影響嗎？看了市面上法組的解題書，有很多用到法官法的題型，請問法官法需要背嗎？謝謝各位不吝指教。 -- posted from android bbs reader on my samsung GT-I9100 https://market.android.com/de ...

醫檢執照考分數

By Tom
at 2013-03-22T16:00

這次考了2月的醫檢師執照考，對了好幾遍答案，結果平均60.41，會不會很危險呢？？想說要來找工作了... - ...

特殊考場申請疑問

By Kama
at 2013-03-22T15:29

請問各位參加國家考試有無申,靠墊, 椅墊,桌椅分離等特殊需求申請特殊考場對考試有無影響因為沒有與大家一同考試可否麻煩有申請過的考生,再協助回答一下在特殊考場考試的經驗謝謝 - ...

基本電學練習題

By Tom
at 2013-03-22T14:55

( A ) 1. 精密儀表所用電阻器，必須用溫度係數為 (A)大 (B)小 (C)可變 (D)無關之材料。可以幫我解釋原因嗎謝謝。 - ...