作者dbzgtgwduo (迪歐麥斯威爾)
看板Army-Sir
標題Re: [問題] 99計概第34題
時間Thu Feb 4 16:18:15 2010
※ 引述《BNMAA (o,o,o)》之銘言：
: 按照題目所給的graph
: A
: / \
: B C
: / \ \
: D-E----F
: 既沒指定DFS的起點
: 也沒說明訪問鄰居的順序
: 好吧 四個選項都是A開頭 算它有指定起點為A好了
: 那 (B)ABDEFC 跟 (C)ACFEDB 都是合法的DFS走訪順序
: 對於tree來講 DFS就是preorder traversal
: 但這題的graph並不是tree阿阿阿~~
: 只因為它畫起來長得跟tree有點像 就要先走左邊嗎？
: 本科系的寫到這題應該都會眉頭一皺吧...?
這個很明顯的就不是「樹」，題目也沒說它是「樹」。
在上資料結構、演算法裡面的「圖」的時候，不然在考試的時候老師也一定會說
當寫這種路徑的題目時，如果題目沒指定，就以最小的節點當頭
如果同時有兩個路徑可以走，就先選擇小的走
不然寫出來的答案會千奇百怪，什麼答案都有，老師要怎麼改？
考研究所的時候補習班老師也有特別強調，有時題目上也會說
所以這應該算是一種不成文的規定吧！
PS. 應推文的要求舉出例證 (資料來源：google 隨便找)
中文題目：
國立東華大學資管系94 學年度第二學期演算法期末考試
出處：
http://faculty.ndhu.edu.tw/~jjs/96_2_exam/95_algo_final.pdf
五. 針對第一題的圖形, 請由A 作為起點, 以分別以：
(1) DFS(Depth-First Search)演算法, 以及
(2) BFS(Breadth-First Search)演算法之走訪順序將圖中所有nodes
一一列出（
相鄰nodes 之選擇順序依照英文字母順序）? （15%）
英文題目：
中原大學95 學年度碩士班入學考試
出處：
http://www3.lib.cycu.edu.tw/exams_new/master/mcs/95/mcs95002.pdf
10. Given the undirected graph below, please answer the following
questions:
(a) Use the Breath- first search (BFS) to traverse the graph with
node a as the starting node. Determine the BFS sequence
(
Note: At any moment, if more than one node can be visited next,
always select the one in alphabetic order)(2%)
(b) Instead, use the Depth-First search (DFS) to traverse the graph
with node a as the starting node. Determine the DFS sequence
(
Similarly, when more than one node can be visited next,
always select the one in alphabetic order)(2%).
有很多題目是沒寫要求的，試問，如果每個人都隨便找一個當起點，不按順序搜尋
那一個期末考或研究所考試可能有幾百種答案，那教授這一題要改到什麼時候？
所以考研究所如果題目沒寫條件，你又沒有照這種「不成文的規定」寫答案的話
有很大的可能會被撇掉，被撇的機率與節點的數目成正比
選項四個都從A開頭就是照字母順序從小到大
如果要選(C)這種答案的話應該是 FEDBAC，字母由大到小搜尋
不過說歸說，如果差這 2.5 分就從預官變預士的話，還是可以去要分數看看
這是預官考試，不是專業考試，可能不會要求的這麼......標準？
God bless you.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.120.14.105
1F：→ Roy75117:120耶～母校推一下XD 02/04 16:23
2F：推 lcd0507:我沒看過題目上有說要從小的開始走ㄝ 02/04 18:13
3F：推 lcd0507:可否舉例?? 02/04 18:15
4F：推 lcd0507:我覺得補習班老師的說法是要讓學生有"解題"規則可循吧 02/04 18:23
5F：→ lcd0507:但不代表其他的答案是錯的 02/04 18:24
6F：→ lcd0507:通常研究所考試這種題目大家都知道沒有固定答案 02/04 18:25
※ 編輯: dbzgtgwduo 來自: 140.120.14.105 (02/04 19:15)
7F：推 euphrate:慘 不去怪出題者明顯的題意不清 反怪應試者沒合理假設? 02/04 22:14
8F：推 chevalierxd:雖然我看不懂大家再寫甚麼 但是我猜B!!這題有問題XDD 02/04 22:17
9F：推 BNMAA:我是不會因為這點分數就變成預士啦 只是寫到這題就很不爽 02/05 00:05
10F：→ BNMAA:這很明顯條件不足啊。我能接受的答案是BC，但我寫A 02/05 00:06
11F：→ BNMAA:是覺得這麼明顯的錯誤應該會送分吧 02/05 00:07
12F：→ BNMAA:選擇題是讀卡不是用人力批改 我不認為答題者有義務要做超出 02/05 00:08
13F：→ BNMAA:題意之外的假設。 02/05 00:08