[理工] [ds][algo] [核對]-成大99-資工所

[ai305428d (可愛小小羅)]

一.Data Structures

1.

(a) -20

(b) 6

2.

我選abc

(a)我比較傾向把d視為常數
(c)考慮到undirected,應該是T
(d)錯的理由是考慮可能存在loop

3.

(a) yes

    pseudo code不會寫.....強烈徵求

(b) 不會


二.Algorithms

4.Θ(nlgn)

5.用Dag-shortest-path

  (先用DFS算出各個node的finishing time 做拓僕排序

  再依據這個order對每個相鄰的node做relax)

6.例證法

    q ---------------- > r
   ^  <----------------   ^
   | |                  | |
   | |                  | |
   | |                  | |
   | |                  | |
   | |                  | |
     v                  v
      <---------------
   s   -------------->   t

   從圖上知道q到t的最長path是q-r-t

   但q-r並不是q到r的最長path (應該是q-s-t-r)

   而r-t也不是r到t的最長path (應該是r-q-s-t)


   所以不具有optimal structure

7.用Bellman-ford檢驗



有錯請指認 謝謝~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.255.9.225
推 iamjustakid:先用DFS算出各個node的finishing time是做啥用的
→ iamjustakid:不太懂...可以幫忙解答一下嗎
→ billyking:第二題我是選全部
→ billyking:(d)每一個dfs所生成樹皆至少大於一點
→ billyking:我是把vertex x那邊看成所有點（除了起終點）都有inedge
→ billyking:和outedge所以在dfs時每一個tree至少包含起點+本身+終點
→ billyking: 3點所以為true
→ billyking:98有相同題目不確定這樣對不對
推 billyking:finishing time 是拿來做topological sort用