[理工] 清大102計科

看板Grad-ProbAsk作者 (米干)時間9年前 (2017/01/09 18:49), 編輯推噓3(3021)
留言24則, 5人參與, 最新討論串1/1
有幾題想要請教一下大家 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

01/09 18:56, , 1F
+1... 廢到沒自信..
01/09 18:56, 1F

01/09 18:59, , 2F
3(B)H就是第一小題的max heap,所以是delete max
01/09 18:59, 2F

01/09 19:00, , 3F
3b的c應該只要delete max就好,因為a說H是max heap了
01/09 19:00, 3F

01/09 19:01, , 4F
6(A)就是將A做LL^T分解
01/09 19:01, 4F

01/09 19:02, , 5F
5(A)是10240沒錯
01/09 19:02, 5F

01/09 19:06, , 6F
4(B)(a)30(b)5
01/09 19:06, 6F

01/09 19:07, , 7F
n個node可形成的BT個數,Catalan number
01/09 19:07, 7F

01/09 19:08, , 8F
差在一個是BST順序固定一個是BT所以乘3!
01/09 19:08, 8F

01/09 19:41, , 9F
4(B)(c)你畫的只差root的左子點為黑色,這樣就對了
01/09 19:41, 9F

01/09 20:32, , 10F
3b(c)我以為是從轉乘陣列後移除前兩個耶
01/09 20:32, 10F

01/09 21:47, , 11F
to gary大: 4(B)的BST個數我懂了,但是我想問一下我(b)
01/09 21:47, 11F

01/09 21:48, , 12F
畫的BT,我查了一下3個node不同的BT畫法,發現我畫法中的
01/09 21:48, 12F

01/09 21:49, , 13F
2跟4形狀重複,但因為他有不同key值,依照不同insert順序
01/09 21:49, 13F

01/09 21:51, , 14F
雖然形狀一樣,但key值不一樣,還是算同一種BST嗎?
01/09 21:51, 14F

01/09 21:52, , 15F
sorry,前面兩行BST和BT打反了
01/09 21:52, 15F

01/09 21:54, , 16F
to yu大: 所以依照最基本判斷哪些是black node,之後看路
01/09 21:54, 16F

01/09 21:54, , 17F
你4畫錯了,1怎麼會在2的右子樹
01/09 21:54, 17F

01/09 21:56, , 18F
4(B)b的第四個畫錯囉!應該跟第三個一樣才對,這樣就是
01/09 21:56, 18F

01/09 21:56, , 19F
啊!!我耍笨了XDDDD太感謝你了~~~~~
01/09 21:56, 19F

01/09 21:56, , 20F
5個了,我也是這樣解的
01/09 21:56, 20F

01/09 21:57, , 21F
徑中的black node數有沒有相同,沒有的話再一個一個試把
01/09 21:57, 21F

01/09 21:57, , 22F
哪個node畫成black嗎??
01/09 21:57, 22F

01/09 22:08, , 23F
同時也要注意不能有連續兩個紅node
01/09 22:08, 23F

01/10 00:30, , 24F
了解,謝謝yu大~
01/10 00:30, 24F
文章代碼(AID): #1OSsgpwo (Grad-ProbAsk)