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