翻舊文來跟大家對對答案XD
※ 引述《ai305428d (可愛小小羅)》之銘言：
: 一.Data Structures
: 1.
: (a) -20
: (b) 6
: 2.
: 我選abc
: (a)我比較傾向把d視為常數
: (c)考慮到undirected,應該是T
: (d)錯的理由是考慮可能存在loop
這邊我答案是只有b是T
這幾題好像前幾年考古都有
: 3.
: (a) yes
: pseudo code不會寫.....強烈徵求
: (b) 不會
這題....完全不懂
有人能解釋一下嗎= =
#1DKoZ-Cg有但還是不懂...Orz
: 二.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
這題我的解法差不多
只不過我是畫無向圖QQ
: 7.用Bellman-ford檢驗
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.192.163
※ 編輯: genius945 來自: 218.173.192.163 (01/12 21:11)