作者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/cn.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