※ 引述《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