作者zelkova (祥)
看板Grad-ProbAsk
标题[理工] [DS] Some Problem..
时间Mon Jan 31 03:34:23 2011
Q1. The conditions of worst case are the same for bubble sort and quick sort.
Sorted 在 quick sort 是 worst case, 但对 bubble sort 应该是best case不是吗?
Q2.
http://www.lib.ntu.edu.tw/exam/graduate/96/96412.pdf
第15题(d)的 maximum clique 顶点数应该是3吗? 答案是5?
Q3. Ａ－Ｃ－Ｅ
｜ ／｜
Ｂ－Ｄ－Ｆ 的BFS
答案是A,B,D,E,C,F... 感觉是A,B,C,D,E,F捏...
Q4.
http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/MA02_95_04.pdf
Q: 第4题的A*解答是
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
感结怪怪的..是否应该为
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 1 1 1
0 0 1 1 1
谢谢!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.135.91.184
1F：推 ybite:Q4我也怀疑答案是错的 01/31 10:20
2F：→ zelkova:嗯恩谢谢 01/31 11:20
3F：→ zelkova:刚刚再看一次Q3突然想到, 解答应该是解成DFS吧.. 01/31 11:21
4F：推 boy5548:对 Q3解答是DFS= = 01/31 11:25
5F：推 cakeboy:他没限制的话,DFS应该会有很多解 01/31 11:50
6F：→ zelkova:我忘了加上"start from A" @@! 01/31 12:10
7F：→ aoqq12:Q1 应该是false 不过你说法怪怪的 应该是说bubble的worst 02/01 14:07
8F：→ aoqq12:case 是 quick sort的worst 02/01 14:07
9F：→ aoqq12:但反之则不是 02/01 14:08
10F：→ aoqq12:不一定对bubble是best 02/01 14:24
11F：→ aerystyle:Q2答案是3，因为最大的完全子图是K3 02/05 20:39
12F：→ aerystyle:Q3答案是对的，题目是按照字母顺序去决定下一个拜访的点 02/05 20:40
13F：→ aerystyle:Q4你的答案是对的 02/05 20:41