[課業] 資料結構

看板Examination作者 (mingrong)時間12年前 (2013/03/22 17:08), 編輯推噓7(7推 0噓 9→)
留言16則, 6人參與, 最新討論串1/2 (看更多)
問題一: 設一表格長度為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 這是我搞錯還是答案錯了阿?? 不是要除以資料數才對嗎? 麻煩知道的大大為我解答一下，感謝>< -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 124.199.76.237
推
03/22 17:36, , 1F
問題2 我覺得塞入第一個的碰撞機率 是0/m 之後依序1/m 2/m
03/22 17:36, 1F
→
03/22 17:37, , 2F
所以應該是/m 不知道這個想法對不對~煩請版友指證 謝謝~
03/22 17:37, 2F
推
03/22 17:44, , 3F
題目出得不好 題意不清 兩題都是...
03/22 17:44, 3F
→
03/22 17:44, , 4F
第二題 平均碰撞次數 第二個node插入的時候
03/22 17:44, 4F
→
03/22 17:45, , 5F
第一次碰撞機率為1/m*1 第二次? (1/m)^2*2?
03/22 17:45, 5F
→
03/22 17:46, , 6F
只算第一次碰撞的機率? 第二次怎麼算 演算法沒寫清楚
03/22 17:46, 6F
推
03/22 17:46, , 7F
我好像想錯了QAQ 請跳過我的想法orz
03/22 17:46, 7F
→
03/22 17:54, , 8F
第二題 應該跟L大講的一樣 就想成每一次插入時 m個位置都
03/22 17:54, 8F
→
03/22 17:56, , 9F
試一次 算碰撞次數在平均m 再全部加起來
03/22 17:56, 9F
→
03/22 17:58, , 10F
第一題不用考慮長度i嗎 不是算平均長度嗎
03/22 17:58, 10F
考慮長度i是什麼意思??它sigma是從i=1累加到i=n
推
03/22 18:04, , 11F
因為每個slot都有機會填入資料跟碰撞 所以要用m
03/22 18:04, 11F
推
03/22 18:23, , 12F
平均長度怎沒考慮？
03/22 18:23, 12F
推
03/22 18:52, , 13F
我第一題答案是sigma pi(ci+1)
03/22 18:52, 13F
推
03/22 18:56, , 14F
喔 我弄錯了 不過對一個點 查詢長度不是要較比較次數少1嗎?
03/22 18:56, 14F
→
03/23 10:33, , 15F
第一次碰撞表中只有1個有放資料所以是1/M 第二次碰撞表裡
03/23 10:33, 15F
→ malowda:有2個資料機率是2/M沒錯阿那來的(1/M)^2* 第二題了解了，但第一題還是沒有結論出來orz....有誰知道嗎??? ※ 編輯: mingrong2 來自: 114.34.31.118 (03/23 19:16) ※ 編輯: mingrong2 來自: 114.34.31.118 (03/23 19:17)
→
03/26 16:18, , 16F
第一題題目 有點看不懂 是要算平均次數?
03/26 16:18, 16F
‣ 更多 mingrong2 的文章
文章代碼(AID): #1HJ1-UOF (Examination)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
課業
0
11
[課業] 資料結構 資料結構
qaz5620
11年前, 04/25
在新視窗開啟完整討論串 (共2篇)
‣ 更多 mingrong2 的文章
文章代碼(AID): #1HJ1-UOF (Examination)