※ 引述《RedJessy (Jessy)》之銘言：
: 請問這次高考的資料結構 有高手可以分享一下嗎 ?
: 第一題 不太會推..只有背他們的大小關係 就掰上去 不知道有沒有同情分數ˊˋ
n^2LOG(N!)<n^2(LOGN)!
=> log(n!)<(logn)!
=>log(1*2*3*...*n)<log1*log2*...*logn
=>log1+log2+...+logn<log1*log2*...*logn
: 第二題 是用數學歸納法嗎 ?
n=2 0--0 2個點分支度都為1得證
設n<k 至少2個點分支度都為1
當n=k 將節點為n的tree的內部節點和樹葉節點分兩個集合
得內部節點節點小於k且樹葉節點為獨立的1個點分支度為0
將內部節點和樹葉節點用1個邊連接起來，原來的樹葉節點
為分支度為1得證
(二)反證法
設每個節點分支度>=2，假設都為2則n個節點有總分支為2n
因為為無向圖所以每個節點的分支度皆算了2次所以 總分支度為2n/2=n
和(一)矛盾所以具有n個節點n>1恰好有n-1個邊
: 第三題 我是把Dijkstar演算法簡單的寫一寫
(一)假設每個邊權重都一樣，用dfs找最短路徑O(n)
(二)就Dijkstar寫給他
: 第四題和第五題沒想法...
第四題
用avl tree建m個值的avltree,再給比root大向右邊找比root小向左邊找的演算法
第五題
(一)用最壞的情況說(但回家想想好像會比n/2大)
(二)n分群分成m群找出中間值logn 再從這些值找中間值
: 還有程式語言最後一題 (智慧卡進出系統)
: 是要將3個class的內容都寫出來嗎 ? 然後順便改寫toString()?
這是我寫的是個人的想法請多多指教謝謝
--
: 請問這次高考的資料結構 有高手可以分享一下嗎 ?
: 第一題 不太會推..只有背他們的大小關係 就掰上去 不知道有沒有同情分數ˊˋ
n^2LOG(N!)<n^2(LOGN)!
=> log(n!)<(logn)!
=>log(1*2*3*...*n)<log1*log2*...*logn
=>log1+log2+...+logn<log1*log2*...*logn
: 第二題 是用數學歸納法嗎 ?
n=2 0--0 2個點分支度都為1得證
設n<k 至少2個點分支度都為1
當n=k 將節點為n的tree的內部節點和樹葉節點分兩個集合
得內部節點節點小於k且樹葉節點為獨立的1個點分支度為0
將內部節點和樹葉節點用1個邊連接起來，原來的樹葉節點
為分支度為1得證
(二)反證法
設每個節點分支度>=2，假設都為2則n個節點有總分支為2n
因為為無向圖所以每個節點的分支度皆算了2次所以 總分支度為2n/2=n
和(一)矛盾所以具有n個節點n>1恰好有n-1個邊
: 第三題 我是把Dijkstar演算法簡單的寫一寫
(一)假設每個邊權重都一樣，用dfs找最短路徑O(n)
(二)就Dijkstar寫給他
: 第四題和第五題沒想法...
第四題
用avl tree建m個值的avltree,再給比root大向右邊找比root小向左邊找的演算法
第五題
(一)用最壞的情況說(但回家想想好像會比n/2大)
(二)n分群分成m群找出中間值logn 再從這些值找中間值
: 還有程式語言最後一題 (智慧卡進出系統)
: 是要將3個class的內容都寫出來嗎 ? 然後順便改寫toString()?
這是我寫的是個人的想法請多多指教謝謝
--
All Comments