[理工] 清大102計科

[visual (米干)]

有幾題想要請教一下大家

1. 3(B)的(c) http://imgur.com/a/bPSjP

   題目中的priority queue並沒有說要delete max或min key
   所以是兩個結果都要寫嗎??

2. 4(B) http://imgur.com/a/OFcqU

   以下是我寫的過程: http://imgur.com/a/7fYej
   想請問一下我前面兩個小題這樣對嗎?
   然後第3小題我知道到每個leaf經過的black node長度一樣
   但是不知道要怎麼轉顏色@@

3. 6(A) http://imgur.com/a/gHo0F

   不是很懂這題要求什麼@@

4. 5(A)的(a) http://imgur.com/a/FlYfF

   我寫10240，不知道對不對?

PS 這幾天寫考古寫下來還是覺得自己好廢，不知道一個月之後要拿什麼去考試QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.8.102.151
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483958963.A.EB2.html
推 moooner: +1... 廢到沒自信..
→ gary19941208: 3(B)H就是第一小題的max heap，所以是delete max
推 yupog2003: 3b的c應該只要delete max就好，因為a說H是max heap了
→ gary19941208: 6(A)就是將A做LL^T分解
→ gary19941208: 5(A)是10240沒錯
→ gary19941208: 4(B)(a)30(b)5
→ gary19941208: n個node可形成的BT個數，Catalan number
→ gary19941208: 差在一個是BST順序固定一個是BT所以乘3!
→ yupog2003: 4(B)(c)你畫的只差root的左子點為黑色，這樣就對了
推 AllenPaul: 3b(c)我以為是從轉乘陣列後移除前兩個耶
→ visual: to gary大: 4(B)的BST個數我懂了，但是我想問一下我(b)
→ visual: 畫的BT，我查了一下3個node不同的BT畫法，發現我畫法中的
→ visual: 2跟4形狀重複，但因為他有不同key值，依照不同insert順序
→ visual: 雖然形狀一樣，但key值不一樣，還是算同一種BST嗎?
→ visual: sorry，前面兩行BST和BT打反了
→ visual: to yu大: 所以依照最基本判斷哪些是black node，之後看路
→ gary19941208: 你4畫錯了，1怎麼會在2的右子樹
→ yupog2003: 4(B)b的第四個畫錯囉！應該跟第三個一樣才對，這樣就是
→ visual: 啊!!我耍笨了XDDDD太感謝你了~~~~~
→ yupog2003: 5個了，我也是這樣解的
→ visual: 徑中的black node數有沒有相同，沒有的話再一個一個試把
→ visual: 哪個node畫成black嗎??
→ yupog2003: 同時也要注意不能有連續兩個紅node
→ visual: 了解，謝謝yu大~