作者liljimmy (吉米)
看板Grad-ProbAsk
標題[理工] 109 交大資工 8、9、12、14
時間Sat Jan 2 03:46:46 2021
https://i.imgur.com/tlRer8G.jpg
這題的23小題（答案是BD)選項B想不透為什麼是O(logn)，看起來應該是O(1)才對....
https://i.imgur.com/1SvjOXF.jpg
26題（答案是ACE)的C選項那個遞迴式不知道怎麼判斷...有大神幫忙說明一下嗎QQ實在是想
不到。
https://i.imgur.com/JrzeXFW.jpg
請問這個如何把圖改成可以執行Ford-Fulkerson的圖...怎麼畫都畫不出來。
另外問個31小題的C選項錯在哪
https://i.imgur.com/3GBLsLD.jpg
這題答案給A，但我隨便建造一棵BST然後把x node設在leaf，最後的結果y都是x的parent n
ode，跟a選項的意思不一樣
謝謝各位過目，懇求各位幫忙解題，祝各位考生最後衝刺順利！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.44.192 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1609530408.A.828.html
1F：→ mathtsai: 23.b 快速冪 回答B是dp A是快速冪 01/02 10:35
2F：→ mathtsai: 26.C 根據定義 前i-1個的sum必須小於等於6ai 01/02 10:43
3F：→ mathtsai: 31 p1是s,p2是t 這樣就能看成flow問題 01/02 11:24
4F：→ mathtsai: 最後一題我怎麼看全部選項都錯 求解釋QQ 01/02 11:39
5F：→ mathtsai: 最後一題 successor是指BST中的下一個元素 01/02 19:28
6F：→ mathtsai: 所以他的找法y一定是successor 我誤以為是指child了QQ 01/02 19:28
7F：推 coco5747769: 14.他給的code裡面if跑完y會是x的右子樹最小的node， 01/22 02:33
8F：→ coco5747769: 也就是在作in-order traversal 輸出在x後面的數字稱 01/22 02:33
9F：→ coco5747769: 做題目裡說的successor 可以查查看後繼節點有些這樣 01/22 02:33
10F：→ coco5747769: 翻譯。如果是predecessor 就是中序輸出x前面的數字 01/22 02:33
11F：→ coco5747769: ，會是x的左子樹裡最大的數字。但是while後面我就 01/22 02:33
12F：→ coco5747769: 看不懂要幹嘛ㄌ 01/22 02:33
13F：推 nctujumpegg: while後面是把y和y的右子點x，一層層網上移 01/23 08:53
14F：→ nctujumpegg: 直到y=nil 但本題有說y is not equal to nil 01/23 08:56
15F：→ nctujumpegg: 所以只能是if中的情況 或是x為y的左子點 01/23 08:59
16F：→ nctujumpegg: 兩者皆符合A選項的敘述 01/23 08:59