[理工] [DS] 97成大資工
考題:
http://0rz.tw/gEZfS
我DS部份第二題跟第三題都有點問題..
這份好難= ="
不知有沒有版友可以給一點協助
第二大題是非題的(b)我覺得答案是false ,因為可以有一個點他連到他自己(loop),
所以這樣就滿足有incoming edge跟outgoing edge (?),但只有一個點,
可是我看到的參考答案給True.
第三大題我(a)就不知道怎麼下手了
quadratic probing依照書上寫的話,
應該是依序找 h(k),h(k)+1^2 ,h(k)-1^2 ,h(k)+2^2 ,h(k)-2^2...
但這題看step就不太像,所以就不知道該怎麼證了
但後來看wiki上的意思
似乎只要滿足h(k)+P2(i)就算是quadratic probing了是嗎?
(P2(i)是指i的2次多項式)
如果是這樣就可以證
以上希望有人可以給點幫助 謝謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.83.166
→
02/06 16:15, , 1F
02/06 16:15, 1F
恩 那應該就是維基上說的
→
02/06 16:17, , 2F
02/06 16:17, 2F
→
02/06 16:20, , 3F
02/06 16:20, 3F
→
02/06 16:25, , 4F
02/06 16:25, 4F
→
02/06 16:26, , 5F
02/06 16:26, 5F
我的意思是
如果只有一個點x 他的邊指向他自己
╭-╮
像這樣 x<╯ 這樣有符合前面幾句的題意嗎?
因為題目沒有說 acyclic啊
如果這種有符合題意的話答案應該就是false吧
※ 編輯: jameschou 來自: 59.112.83.166 (02/06 17:47)