作者BNMAA (o,o,o)
看板Army-Sir
标题[问题] 99计概第34题
时间Thu Feb 4 13:40:05 2010
按照题目所给的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
1F：→ DragonDeath:这题完全不懂啊 02/04 13:42
2F：推 topractise:之前修资结的印象 都从左边先走...一次走到底 02/04 13:42
3F：→ Liroy:洪兔没教你说字母前面的先走起吗XD 02/04 13:43
4F：推 b90738:没说是中序？後序？前序？ 所以我把它当中序＝＝！ 02/04 13:46
5F：→ BNMAA:2F: 树习惯是这样 但这题不是树 02/04 13:47
6F：→ BNMAA:3F: DFS没有这种规定 端看邻居的list怎麽maintain 02/04 13:48
7F：推 RoyalWalker:这题是真的不会，算此次的难题之一吧 02/04 14:06
8F：推 cjcat2266:这题我就BC二猜一，然後猜错了 = = 02/04 14:15
9F：→ cjcat2266:我还是觉得两种都是合法的DFS啊 02/04 14:16
10F：推 lcd0507:这有两个答案吧 02/04 14:18
11F：推 RoyalWalker:跟树无关喔，这不是树的走访，有篇文我看了就觉得没错 02/04 14:32
13F：→ RoyalWalker:虽然也写错了，当作学到一件事好了... 02/04 14:34
14F：→ RoyalWalker:6F_BNMAA:文中说「DFS通常也会有着循序、渐增的特质」 02/04 14:36
15F：推 topractise:(原来我是赛对的) 02/04 14:38
16F：推 tulian:赛对+1 02/04 14:42
17F：推 tcf:就理论上来说DFS是不会唯一,但是这是考试不得已还是选B好 02/04 14:43
18F：推 lcd0507:如果用阵列来实作或许会符合循序渐增 02/04 15:50
19F：→ lcd0507:用adjacent list 就要看node摆的位置不一定按照顺序吧?? 02/04 15:51
20F：→ lcd0507:如果照书上演算法写的定义应该bc都对吧 02/04 15:52
21F：推 jeff30133:就把英文字母当做优先顺序 不然ㄧ开始从A干嘛 02/04 16:04
22F：→ BNMAA:to R:那是nonsense 我回圈也可以从後面跑回来 02/04 16:14
23F：推 chieher:j大胡扯 = = A是因为他是root 02/04 16:14
24F：→ BNMAA:for (i = |N(v)| - 1; i >= 0; i--) dfs_visit(N(v)[i]); 02/04 16:15
25F：→ BNMAA:这题根本就没人规定提取邻居的priority如何决定 02/04 16:15
26F：→ BNMAA:怎麽能说DFS出来的序列是唯一？ 02/04 16:15
27F：→ BNMAA:我的看法同lcd0507 02/04 16:18
※ 编辑: BNMAA 来自: 123.240.242.207 (02/04 16:18)
28F：推 bnsblue:graph没有root.tree才有 从A来是因为他四个选项都是A先= = 02/04 16:29
29F：推 frouscy:纯推香蕉 真的是眉头一皱 XD 02/04 17:31
30F：推 chevalierxd:我猜B耶~~这题有问题啦(敲碗) 02/04 22:15
31F：推 tchuangtom:这题B或C都可给对,但不该送分,因题目没有问题 02/05 00:44
32F：推 Leeng:BC都可以吧 02/05 00:55