第7题
Given input{4371,1323,6173,4199,4344,9679,1989}and a hash funtion
h(X) = (X mod 10),show the results:
(b) open addressing hash table using quadratic probing (F(i)=3*i^2)
正常来说quadratic probing(二次方探测)应该是当f(x)发生溢位时
下一次探测的位址是(f(x)+i^2) mod b与(f(x)-i^2) mod b才对
所以若依照题目上的(F(i) = 3*i^2)的方式假如位置3发生溢位
我应该把资料放在 3*3^2 =27?还是再mod 10 = 7???是这样吗?
第8题
如果有题目再好不过了，因为题目有点长，我打关键字就好
(1)Merge Sort (2)Heap Sort (3)MST (4)Floyd-Warshall algo
(5)Find Max independent (6)Huffman's algo (7)Strassen's algo
(8)OBST (9)LCS problem (10) Ford-Fulkerson algo
有哪几个属于(a)Divide and Conquer (b)Dynamic Programming
(c)Greedy method (d)Others
这些算法都知道，但是无法很明确的肯定是哪个，想对对答案
(a)5 (b) 1,4,6,7,8,9 (c) 3,10 (d)2 求解感谢

7,要mod/8(a)1,7 / 8(b) 4,8,9 / 8(c) 2,3,6/ 8(d)5,10

heap 不太会说是贪婪吧？

恩，我也觉得Heap Sort只是把MAX heap的Root删除 然后调整感觉不出来有用到哪个话说7是因为那个算法的关系？不然MatrixChain不是Dp解吗

不是 一个是矩阵乘法 另一个是多个矩阵用什么顺序乘在一起

heap sort分类到greedy确实不太好 , 但原本的想法只是heap sort的过程确实也满足条件比较放宽的local最佳解

7.F(i)应该是mod10吧

像题目那样如果资料第一次放在9 所以第二次放在3*3^2mod10那第3次失败后 是否是放在3*10mod10?再失败就3*11mod?

题目给的F(i)不是实际值,而是相对于hame value的偏移量第一次失败是放[9+F(1)]mod10=(9+9)mod10=8

但F(1)不是3*1^2=3吗？ 所以是(9+3)mod10等于2囉?

对 , sry 我带错惹

恩 感谢你的解惑

7.100交大考过,没看Cormen会误解 8.heap sort => other