[問題] 99計概第34題

看板Army-Sir作者 (o,o,o)時間16年前 (2010/02/04 13:40), 編輯推噓17(17推 0噓 16→)
留言33則, 18人參與, 最新討論串1/2 (看更多)
按照題目所給的graph A / \ B C / \ \ D-E----F 既沒指定DFS的起點 也沒說明訪問鄰居的順序 好吧 四個選項都是A開頭 算它有指定起點為A好了 那 (B)ABDEFC 跟 (C)ACFEDB 都是合法的DFS走訪順序 對於tree來講 DFS就是preorder traversal 但這題的graph並不是tree阿阿阿~~ 只因為它畫起來長得跟tree有點像 就要先走左邊嗎？ 本科系的寫到這題應該都會眉頭一皺吧...? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.240.242.207
→
02/04 13:42, , 1F
這題完全不懂啊
02/04 13:42, 1F
推
02/04 13:42, , 2F
之前修資結的印象 都從左邊先走...一次走到底
02/04 13:42, 2F
→
02/04 13:43, , 3F
洪兔沒教你說字母前面的先走起嗎XD
02/04 13:43, 3F
推
02/04 13:46, , 4F
沒說是中序？後序？前序？ 所以我把它當中序＝＝！
02/04 13:46, 4F
→
02/04 13:47, , 5F
2F: 樹習慣是這樣 但這題不是樹
02/04 13:47, 5F
→
02/04 13:48, , 6F
3F: DFS沒有這種規定 端看鄰居的list怎麼maintain
02/04 13:48, 6F
推
02/04 14:06, , 7F
這題是真的不會，算此次的難題之一吧
02/04 14:06, 7F
推
02/04 14:15, , 8F
這題我就BC二猜一，然後猜錯了 = =
02/04 14:15, 8F
→
02/04 14:16, , 9F
我還是覺得兩種都是合法的DFS啊
02/04 14:16, 9F
推
02/04 14:18, , 10F
這有兩個答案吧
02/04 14:18, 10F
推
02/04 14:32, , 11F
跟樹無關喔，這不是樹的走訪，有篇文我看了就覺得沒錯
02/04 14:32, 11F
→
02/04 14:33, , 12F
02/04 14:33, 12F
→
02/04 14:34, , 13F
雖然也寫錯了，當作學到一件事好了...
02/04 14:34, 13F
→
02/04 14:36, , 14F
6F_BNMAA:文中說「DFS通常也會有著循序、漸增的特質」
02/04 14:36, 14F
推
02/04 14:38, , 15F
(原來我是賽對的)
02/04 14:38, 15F
推
02/04 14:42, , 16F
賽對+1
02/04 14:42, 16F
推
02/04 14:43, , 17F
就理論上來說DFS是不會唯一,但是這是考試不得已還是選B好
02/04 14:43, 17F
推
02/04 15:50, , 18F
如果用陣列來實作或許會符合循序漸增
02/04 15:50, 18F
→
02/04 15:51, , 19F
用adjacent list 就要看node擺的位置不一定按照順序吧??
02/04 15:51, 19F
→
02/04 15:52, , 20F
如果照書上演算法寫的定義應該bc都對吧
02/04 15:52, 20F
推
02/04 16:04, , 21F
就把英文字母當做優先順序 不然ㄧ開始從A幹嘛
02/04 16:04, 21F
→
02/04 16:14, , 22F
to R:那是nonsense 我迴圈也可以從後面跑回來
02/04 16:14, 22F
推
02/04 16:14, , 23F
j大胡扯 = = A是因為他是root
02/04 16:14, 23F
→
02/04 16:15, , 24F
for (i = |N(v)| - 1; i >= 0; i--) dfs_visit(N(v)[i]);
02/04 16:15, 24F
→
02/04 16:15, , 25F
這題根本就沒人規定提取鄰居的priority如何決定
02/04 16:15, 25F
→
02/04 16:15, , 26F
怎麼能說DFS出來的序列是唯一？
02/04 16:15, 26F
→
02/04 16:18, , 27F
我的看法同lcd0507
02/04 16:18, 27F
※ 編輯: BNMAA 來自: 123.240.242.207 (02/04 16:18)
推
02/04 16:29, , 28F
graph沒有root.tree才有 從A來是因為他四個選項都是A先= =
02/04 16:29, 28F
推
02/04 17:31, , 29F
純推香蕉 真的是眉頭一皺 XD
02/04 17:31, 29F
推
02/04 22:15, , 30F
我猜B耶~~這題有問題啦(敲碗)
02/04 22:15, 30F
推
02/05 00:44, , 31F
這題B或C都可給對,但不該送分,因題目沒有問題
02/05 00:44, 31F
推
02/05 00:55, , 32F
BC都可以吧
02/05 00:55, 32F
→
07/06 07:07, , 33F
希望對您有幫助 http://www.94istudy.com
07/06 07:07, 33F
‣ 更多 BNMAA 的文章
文章代碼(AID): #1BQbsui3 (Army-Sir)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 BNMAA 的文章
文章代碼(AID): #1BQbsui3 (Army-Sir)