[理工] [資演]-交大111-資訊聯招

[ISLAND1999 (jwj7788)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1674282665.A.A52.html
推 tinhanho: 先push3 再push5  stack(5 3 5 4 7 9 0) 所以 top 3rd
→ tinhanho: 一樣 C要選 你push反了吧?
感謝回復，但是C問的不是top second跟 third element一樣嗎?
推 tinhanho: double linked list 因為不用從頭開始找 所以比較快
推 nofucknolove: 12 我猜教授(A)可能要考相同的會不會push到一起？所
→ nofucknolove: 以不選；(C)應該也是要接著A看，然後A內給的順序就
→ nofucknolove: 是先5再3，所以第2、3一樣
→ nofucknolove: Double在刪除tail時可知道前者：O(1)
→ nofucknolove: Single要從頭在trail一次：O(n)
→ nofucknolove: 要insert到list也是同上
感謝回復，那我了解了
推 tinhanho: 26的B應該是要考慮碰撞的問題 不是那麼直觀的O(N)
推 nofucknolove: 26 要找successor key應該是要建balanced BST去找吧
※ 編輯: ISLAND1999 (111.246.171.17 臺灣), 01/21/2023 16:14:59
→ ISLAND1999: 回t大 請問要考慮碰撞是什麼意思?
→ ISLAND1999: 回n大 所以nlg n是指建樹所花的時間嗎
推 tinhanho: 沒看到second抱歉 那我也不知道了欸 C為啥是對的
推 tinhanho: 26B應該是N大說的那樣比較對
推 A4P8T6X9: 26C 是對的，因為可以根據 input 找一個特別的完美 h
→ A4P8T6X9: ash function 達成
推 A4P8T6X9: 26B 在 c++ unordered_set 可以 O(N) 做到