Re: [理工][DS]101 交大資聯

[Numbstu (noob)]

※ 引述《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
→ cutemiller:太感謝了,看來光是看懂基本型不懂延伸
→ cutemiller:考交大應該會很慘......嗚嗚
→ cutemiller:寫洪逸的題庫,似乎交大真的很有限....
→ cutemiller:考
→ Numbstu:有人想對台清101考題嗎?
→ luhui:可以請問(19)為何有(m-1)*5嗎?謝謝:)
→ luhui:喔我知道了謝謝ㄏㄏ