作者ISLAND1999 (jwj7788)
看板Grad-ProbAsk
標題[理工] [資演]-交大111-資訊聯招
時間Sat Jan 21 14:31:03 2023
https://i.imgur.com/E97oAhY.jpg
https://i.imgur.com/GldHFVw.png
先附上題目與交大的解答，題目是網路上找到的
12.BCE
16.D
26.ABC
12題因為C是對的
所以A選項的pushing 3 and 5是指先push 5再pust 3
這樣stack裡面才會變成top=3 content=(3, 5, 5, 4, 7, 9, 0)
我寫題目的時候是理解成先push 3再push 5，所以沒選C，
想請問題目這樣寫是固定都先push後面嗎，還是是看教授心情QQ
16題的D想知道為什麼doubly linked list會比single快
我查到merge sort for single linked list是O(n*logn)
連結:
https://www.geeksforgeeks.org/merge-sort-for-linked-list/
26題的B想問為什麼worse case會是O(NlgN)
我的想法是只要拿一個值來記錄比自己大又差最少的key是哪個，
最多跑完N個sluts應該就能知道誰是successor?
以上是我的問題，先在這謝謝過年還願意回答小弟問題的大大們
預祝新年快樂
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.246.171.17 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1674282665.A.A52.html
1F：推 tinhanho: 先push3 再push5 stack(5 3 5 4 7 9 0) 所以 top 3rd 01/21 15:00
2F：→ tinhanho: 一樣 C要選 你push反了吧? 01/21 15:01
感謝回復，但是C問的不是top second跟 third element一樣嗎?
3F：推 tinhanho: double linked list 因為不用從頭開始找 所以比較快 01/21 15:03
4F：推 nofucknolove: 12 我猜教授(A)可能要考相同的會不會push到一起？所 01/21 15:05
5F：→ nofucknolove: 以不選；(C)應該也是要接著A看，然後A內給的順序就 01/21 15:05
6F：→ nofucknolove: 是先5再3，所以第2、3一樣 01/21 15:05
7F：→ nofucknolove: Double在刪除tail時可知道前者：O(1) 01/21 15:09
8F：→ nofucknolove: Single要從頭在trail一次：O(n) 01/21 15:09
9F：→ nofucknolove: 要insert到list也是同上 01/21 15:09
感謝回復，那我了解了
10F：推 tinhanho: 26的B應該是要考慮碰撞的問題 不是那麼直觀的O(N) 01/21 15:11
11F：推 nofucknolove: 26 要找successor key應該是要建balanced BST去找吧 01/21 15:16
※ 編輯: ISLAND1999 (111.246.171.17 臺灣), 01/21/2023 16:14:59
12F：→ ISLAND1999: 回t大 請問要考慮碰撞是什麼意思? 01/21 16:21
13F：→ ISLAND1999: 回n大 所以nlg n是指建樹所花的時間嗎 01/21 16:22
14F：推 tinhanho: 沒看到second抱歉 那我也不知道了欸 C為啥是對的 01/21 16:31
15F：推 tinhanho: 26B應該是N大說的那樣比較對 01/21 16:49
16F：推 A4P8T6X9: 26C 是對的，因為可以根據 input 找一個特別的完美 h 01/23 21:59
17F：→ A4P8T6X9: ash function 達成 01/23 21:59
18F：推 A4P8T6X9: 26B 在 c++ unordered_set 可以 O(N) 做到 01/23 22:01