※ 引述《yijia1127 (我不是豪野人)》之銘言：
: 1. E
: 2. A (不會)
: 3. C
: 4. A
: 5. D
: 6. D
: 7. E
: 8. C
: 9. D
: 10. C
: 11. E
: 12. E
: 13. B
: 14. E
: 15. ABC (不會,E看不太懂要不要選)
: 16. ABCE
: 17. AC
: 18. ABE (不知道C要不要跟著一起選)
: 19. ACE
: 20. B
: 21. B
: 22. BC
: 主要想請教大家第2,15,18題的答案
: 18題的後面如果已經多做一輪(E選項)，那麽前面的for loop是否還需要多做一輪(C選項)
: 謝
我想問ㄧ下第13題
https://imgur.com/sFE2XVo
我覺得答案應該是(C)
因為pivot在最右邊 所以需要跟ㄧ個大於pivot的做交換
不知道有沒有錯
還有第16題
https://imgur.com/GJysBux
(B)應該不能選吧
應該是
If X is a NP-complete problem
then every NP problem can polynomial reduce to X
第17題
https://imgur.com/hkTRinA
(B)應該可以選吧 NP-complete ㄧ定是 NP-hard 吧
(E) Y 應該是NP-complete 不過他說他是 NP-hard 應該也沒錯吧
請知道的大神 幫我解惑ㄧ下
最後附上第3題
https://imgur.com/zAgrsiJ
SB 我畫的ㄧ個反例 應該是沒有問題吧
https://imgur.com/oPUJ7Ew
你看第12題出do-while的條件,就會發現是要跟i交換才對
作者:
sooge (老衲)
2019-01-19 15:18:00這個程式碼的if判斷是不是有點累贅，其實可以直接接swap就好了?
Y是NP-hard，不是NP-C，因為沒證明Y屬於NP
作者:
sooge (老衲)
2019-01-19 15:32:00你自己帶個例子進去就會知道選C會發生什麼事 直接是錯的
作者:
sooge (老衲)
2019-01-19 15:35:00然後你說的沒錯 pivot要和一個大於pivot的做交換，你do while迴圈做完後i停的點會大於pivot，而j停的點會小於pivot更正，上面的大於和小於應該是大於等於和小於等於
作者:
FRAXIS (喔喔)
2019-01-19 21:45:0016 (b) 是對的 你說的也是對的 這是 NPC 定義的一部分
作者:
skyHuan (Huan)
2019-01-21 01:12:00作者: kurtis6741 (KurtHappy) 2019-01-21 09:14:00
不好意思 想請問第三題你畫的反例題目上說unique lightest edge應該是指只有唯一的最小權重覺得題目敘述跟你畫的圖應該不一樣
作者:
skyHuan (Huan)
2019-01-21 10:50:003的SB中央考好幾次了，考這種有爭議的真的...他應該是說cycle中有唯一最小邊但不保證是圖中最小，所以不一定在MST，要選false，如果改成最大必不在MST中就要選true