Re: [理工][DS]101 交大資聯
※ 引述《cutemiller (cutemiller)》之銘言：
: 大家好,
: 剛寫了考古題竟然大爆炸,101的跟之前的比難度明顯提升許多
: (以前的無腦題都不見了=_=!!,我99年的寫完還沾沾自喜)
: ,補習班上課的code都背了幫助也有限,有好多不會想請大大幫忙!謝謝!
: 問題:
: 題目連結:http://ppt.cc/sW9I
: 請問這些問題是HOROWITZ及CORMEN裡面的嗎?我有大概翻一下書沒有看到相關的說明
: B 1.(3)請問複雜度是怎麼分析的?
: B 2.(6)同上
: D 4.(11)請問這max heap 的 code 嗎?我算26選(e)答案錯
: C 7.(19)不知該如何算
: B (20)
: D (21)
1.每個節點走訪並交換O(N)
4.main function那邊的i...QQ;然後n=10代表index從0開始;8被排擠不會排
7.(19)(m-1)*5+m*7=512
可得m=43.xxxxx(然後浪費一點點block空間)
m=43
其中m-1為key值,m為指標數
(20)題目要最多key值:所以node要滿的;然後每個block都要有m-1個key值
h個層,初始為1,thus:第一層 1個node
第二層 m個 一值到第h層 m^(h-1)
總共節點數有(m^h-1)/m-1
然後每個block中有m-1個key值;所以((m^h-1)/m-1)*(m-1)=m^h-1 為最大
(21)當下想到two way balanced search tree 所以直接logmN
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.218.103.140
→
12/03 08:51, , 1F
12/03 08:51, 1F
→
12/03 08:51, , 2F
12/03 08:51, 2F
→
12/03 08:52, , 3F
12/03 08:52, 3F
→
12/03 08:53, , 4F
12/03 08:53, 4F
→
12/03 13:59, , 5F
12/03 13:59, 5F
→
01/24 13:02, , 6F
01/24 13:02, 6F
→
01/24 13:13, , 7F
01/24 13:13, 7F