作者mingrong2 (mingrong)
看板Examination
标题[课业] 资料结构
时间Fri Mar 22 17:08:44 2013
问题一:
设一表格长度为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
1F：推 leohi:问题2 我觉得塞入第一个的碰撞机率 是0/m 之後依序1/m 2/m 03/22 17:36
2F：→ leohi:所以应该是/m 不知道这个想法对不对~烦请版友指证 谢谢~ 03/22 17:37
3F：推 carterdunk:题目出得不好 题意不清 两题都是... 03/22 17:44
4F：→ carterdunk:第二题 平均碰撞次数 第二个node插入的时候 03/22 17:44
5F：→ carterdunk:第一次碰撞机率为1/m*1 第二次? (1/m)^2*2? 03/22 17:45
6F：→ carterdunk:只算第一次碰撞的机率? 第二次怎麽算 演算法没写清楚 03/22 17:46
7F：推 leohi:我好像想错了QAQ 请跳过我的想法orz 03/22 17:46
8F：→ kyc1023:第二题 应该跟L大讲的一样 就想成每一次插入时 m个位置都 03/22 17:54
9F：→ kyc1023:试一次 算碰撞次数在平均m 再全部加起来 03/22 17:56
10F：→ kyc1023:第一题不用考虑长度i吗 不是算平均长度吗 03/22 17:58
考虑长度i是什麽意思??它sigma是从i=1累加到i=n
11F：推 Mewra:因为每个slot都有机会填入资料跟碰撞 所以要用m 03/22 18:04
12F：推 asdd:平均长度怎没考虑？ 03/22 18:23
13F：推 Mewra:我第一题答案是sigma pi(ci+1) 03/22 18:52
14F：推 Mewra:喔 我弄错了 不过对一个点 查询长度不是要较比较次数少1吗? 03/22 18:56
15F：→ malowda:第一次碰撞表中只有1个有放资料所以是1/M 第二次碰撞表里 03/23 10:33
→ 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)
16F：→ kyc1023:第一题题目 有点看不懂 是要算平均次数? 03/26 16:18