Re: [理工] 成大-資結 100年

[Byzantin (拜占庭)]

分享一下我的想法順便騙騙P幣

1-6 T

1-7 若G不為connected則必不為tree , F

2-2

(A) First in 不一定 First out , F

(B) 若tree有n個node，n = n0 + n1 + n2 (ni為degree為i的node數)

    n個node會有n+1個threads，n+1 = n0+n1+n2+1 = 2*n0 + n1 =/= 2*n0 , F

(C) LL 、 RR為single rotation , LR 、 RL 為double rotation ,

    所花時間只差1倍，time complexity同 , T

(D) T

(E) F



※ 引述《showyoulovex (NONO)》之銘言：
: 題目:http://ppt.cc/9Ag-
: 1-6 我寫答案是T 不知道對不對
: 1-7 曾經好像有看過相關觀念 我寫T
:     但一時書又找不到在哪，想問是否有誤
: 2-2 1)Queue 是FIFO 可是他考優先Queue  還是FIFO嗎?
:     2)書上root會自己連到自己 所以是 2*n0+1嗎?
:     3)感覺應該不會一樣 不知是否正確
:     4)我認為是正確的 不知是否有誤
: 請各位高手 幫我看一下 是否正確  感謝
: 歡迎有想要考 成大電通 想一起討論歷年答案的人寄站內信給我
: 我跟朋友 應該至少會寫到95年

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 180.177.5.100
→ gskman:我個人認為B就是要考你知不知道single double rotation,
→ gskman:所以time complexity我會覺得有差
→ showyoulovex:感謝大大回覆，1-7 我是覺得應該是針對 連通進行討論
→ showyoulovex:如果不連通，DFS和BFS都無法走到不是媽?
→ gskman:我也會選t 但我不確定dfs跟bfs怎麼走不連通XD
推 SiriusCloud:那A 他是說資料結構型態~ 仍是FIFO 不然就不較佇列了?
推 da0910cc:製作priority queue的資料結構應該是HEAP?
推 kiwidoit:Leftist tree應該也可以
推 SiriusCloud:題目最後只是提到有FIFO特性 ~