Re: [理工] 104台大電機丙資演對答案

[tzutengweng (神奇的湯姆)]

※ 引述《yaxauw (yaxauw)》之銘言：
: : 是非:
: : 1.F(沒特別說要怎麼著色  應該False吧?)
: 寫F 但我的理由是 它取omega 所以k取大一點的話 就不滿足了
: : 2.F
: : 3.F
: : 4.F(Fixed size讓我有點猶豫...)
: : 5.F
: 是因為寫rarely called才選F嗎 我選T
: : 6.??
: 我選T誒 感覺跟林立宇老師講的Tree上找diameter有點像
: 等下再問問她
: : 7.F
: 感謝dddm49幫助釐清觀點
: B-tree的External Nodes必須在同一level所以它寫can be less than or "equal to 1"
: 是錯的
: : 8.T
: : 9.T(嗎??)
: 感謝dddm49的解釋
: Kn圖至少要砍n-1個邊才會不連通
查了一下cut-set定義

The cut-set of a cut  C=(S,T) is the set
{(u,v)in E| u in S,v in T} of
edges that have one endpoint in S and the other endpoint in T.

所以如果今天是Kn,  cut set 最小就是只cut出一個點，剩下n-1個點在另外一邊
所以cardinality>=n-1

感謝 exile大大指點迷津




: : 10.Top-Down 2-3-4ok  但是2-3就不是很確定  希望高手畫一下  囧
: T
: 感謝jerry031181、odanaga解釋
: 畫法照level-order是 7、35、9、12、4、6、8、10
: *2-node 3-node指的是external node數
: : 複選:
: : 11.
: : BCDE
: 感謝jerry031181解釋
: : 12.
: : CE
: A DS說O(1) Algo說O(logn) =""= 我看了一下wiki後決定選了
: D 就是Merge 2個BinomialTree 我有選
: : 13.
: : BC
: : 不熟c++的寫法
: : t+=(str[i]<<(i*2))
: : 等於
: : str[i] = 2*i
: : t+=str[i]
: : 嗎?
: E說的沒錯吧 就新增加的100-199slot不會用到
: 其他不太確定orz
: : 14.
: : CE
: : D應該是False吧?
: D我有選誒 假如到leaf的path有長有短 那就是取max 求高手解釋
: : 15.
: : CE
: : A:好像大於O(2^n)?
: : D:因為黑白建期望為logn高度  所以反過來看應該也是50%而不會greter than?
: A看不懂..
: C是錯的 h=4時才會是7
: E是錯的吧 level-order建樹 黑黑紅紅紅黑黑 不會是2*r+1
: 因此我有選D.. 但不會證
: : 16.
: : DE
: : B:不太清楚,是八個嗎?
: : E:感覺要用reduce 但是不知道怎麼設計
: D覺得寫exponential怪怪的不敢選誒 求解釋

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.250.78.196
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483409314.A.CD0.html
推 exilelast: 它說 no less then n-1耶
→ exilelast: 所以4 no less than n-1,這沒有錯啊
→ tzutengweng: 對對~~歹勢  所以應該是true
※ 編輯: tzutengweng (59.125.97.119), 01/03/2017 21:54:58
※ 編輯: tzutengweng (59.125.97.119), 01/03/2017 21:55:17