Re: [考題] 100年高考三級 資料結構

[onlyu0402 (我在故我唱)]

※ 引述《pinky94 (pinky)》之銘言：
:     [考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
: 出處:如題
: 六.已知二元樹可以用一維陣列來儲請依此概念設計一方法，儲以下三元樹於如下之一維陣
: 列中
: 參考補習班解答,為什麼一維陣列需要13個??
: 七.將數字25,5,75,0,60,10,55,15,45,15依序入一維陣列如下，以heap sort方式進行
: 由小到大的排序請顯示其在第一次執行完initial heap步驟後的一維陣列內容
: 參考補習班的解答為什麼是
: index 0  1  2  3  4  5  6  7  8  9
: data 75  60 55 45 15 10 25 15 0  5
: 酗ㄛ由尹鴗的排朱?

針對第七題:(不好意思，讓這題又浮出來
因為這題小弟也有一樣的困惑(高X、公X王，甚至是鼎X的書答案都一致)
參考了原文幾位回覆的大大，更篤定由小到大排序是用min-heap作答

欲在此提供個人解答如下-

min-heap:
                            0
                          /   \
                         5     10
                        / \   /  \
                      15  15 75  55
                     /  \ /
                    25 45 60

對照上圖，得一維陣列內容為
index 0 1  2  3  4  5  6  7  8  9
 data 0 5 10 15 15 75 55 25 45 60

以上若有誤還勞煩各位大大指教Orz

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.68.158.243
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1478007061.A.012.html
推 jachin: 我沒去查原題是什麼，不過原則上是沒錯的，但請注意min-he
→ jachin: ap的output方式是由陣列尾與陣列頭swap，再取出陣列尾，he
→ jachin: ap重新整理
→ onlyu0402: 好的~謝謝jachin大補充說明
推 jimmy12332: 其實是使用max heap沒錯的 因為其實每次把root跟最後
→ jimmy12332: 一個元素交換 就是把最大的元素放到陣列的最後了(heap
→ jimmy12332: 通常都是用陣列)如果你使用min heap 那是不是又要多一
→ jimmy12332: 個陣列來存你的output?