作者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