資訊處理已哭 - 高考

By Linda
at 2015-07-16T21:59
at 2015-07-16T21:59
Table of Contents
※ 引述《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()?
這是我寫的是個人的想法請多多指教謝謝
--
Tags:
高考
All Comments

By Zenobia
at 2015-07-21T21:30
at 2015-07-21T21:30

By Tristan Cohan
at 2015-07-26T02:31
at 2015-07-26T02:31

By Zora
at 2015-07-30T11:35
at 2015-07-30T11:35

By Valerie
at 2015-08-03T01:38
at 2015-08-03T01:38

By Odelette
at 2015-08-05T22:04
at 2015-08-05T22:04

By Franklin
at 2015-08-10T10:28
at 2015-08-10T10:28

By Eden
at 2015-08-13T23:24
at 2015-08-13T23:24

By Edwina
at 2015-08-17T06:46
at 2015-08-17T06:46

By Kristin
at 2015-08-20T18:17
at 2015-08-20T18:17

By Eden
at 2015-08-25T08:29
at 2015-08-25T08:29

By Faithe
at 2015-08-26T04:47
at 2015-08-26T04:47

By Dora
at 2015-08-30T18:21
at 2015-08-30T18:21

By Ida
at 2015-09-01T11:06
at 2015-09-01T11:06

By Zanna
at 2015-09-06T10:27
at 2015-09-06T10:27

By Brianna
at 2015-09-06T12:20
at 2015-09-06T12:20

By Quintina
at 2015-09-07T17:35
at 2015-09-07T17:35

By Lauren
at 2015-09-08T09:18
at 2015-09-08T09:18

By Dorothy
at 2015-09-11T07:34
at 2015-09-11T07:34

By Hardy
at 2015-09-14T23:35
at 2015-09-14T23:35

By Delia
at 2015-09-17T21:54
at 2015-09-17T21:54

By Damian
at 2015-09-21T02:24
at 2015-09-21T02:24

By Hedwig
at 2015-09-23T22:04
at 2015-09-23T22:04

By Ingrid
at 2015-09-28T13:10
at 2015-09-28T13:10

By Elvira
at 2015-10-01T05:48
at 2015-10-01T05:48

By Frederic
at 2015-10-04T15:41
at 2015-10-04T15:41

By Ula
at 2015-10-05T18:10
at 2015-10-05T18:10

By Steve
at 2015-10-06T08:44
at 2015-10-06T08:44

By Oliver
at 2015-10-09T16:24
at 2015-10-09T16:24

By Audriana
at 2015-10-11T15:00
at 2015-10-11T15:00

By Thomas
at 2015-10-12T23:19
at 2015-10-12T23:19

By Franklin
at 2015-10-15T09:20
at 2015-10-15T09:20

By Andrew
at 2015-10-18T07:47
at 2015-10-18T07:47

By Delia
at 2015-10-20T11:12
at 2015-10-20T11:12

By Kristin
at 2015-10-23T14:07
at 2015-10-23T14:07

By Hazel
at 2015-10-26T09:49
at 2015-10-26T09:49

By Hamiltion
at 2015-10-26T11:52
at 2015-10-26T11:52

By Bennie
at 2015-10-26T18:27
at 2015-10-26T18:27

By Mary
at 2015-10-28T10:41
at 2015-10-28T10:41

By Joe
at 2015-10-29T07:53
at 2015-10-29T07:53

By Kelly
at 2015-10-31T08:10
at 2015-10-31T08:10

By Michael
at 2015-11-02T05:21
at 2015-11-02T05:21

By Caitlin
at 2015-11-03T05:51
at 2015-11-03T05:51

By Elizabeth
at 2015-11-07T05:56
at 2015-11-07T05:56

By Yuri
at 2015-11-07T13:15
at 2015-11-07T13:15

By Rae
at 2015-11-10T03:45
at 2015-11-10T03:45

By Charlotte
at 2015-11-13T04:41
at 2015-11-13T04:41

By Agatha
at 2015-11-13T14:55
at 2015-11-13T14:55

By Jacky
at 2015-11-14T08:14
at 2015-11-14T08:14

By Lydia
at 2015-11-17T20:40
at 2015-11-17T20:40

By Madame
at 2015-11-18T21:14
at 2015-11-18T21:14

By Kyle
at 2015-11-23T05:51
at 2015-11-23T05:51

By Michael
at 2015-11-23T14:50
at 2015-11-23T14:50

By Belly
at 2015-11-27T04:56
at 2015-11-27T04:56

By Enid
at 2015-11-29T12:07
at 2015-11-29T12:07

By Olivia
at 2015-12-03T13:11
at 2015-12-03T13:11

By Mary
at 2015-12-07T15:12
at 2015-12-07T15:12

By Liam
at 2015-12-10T17:23
at 2015-12-10T17:23

By Annie
at 2015-12-14T14:21
at 2015-12-14T14:21

By Kumar
at 2015-12-15T03:33
at 2015-12-15T03:33

By Anonymous
at 2015-12-18T12:20
at 2015-12-18T12:20
Related Posts
高考行政法第6題

By Christine
at 2015-07-16T21:32
at 2015-07-16T21:32
臺北市政府秘書處徵職代(約聘分析師)

By Mia
at 2015-07-16T21:20
at 2015-07-16T21:20
資訊處理已哭

By Edwina
at 2015-07-16T20:23
at 2015-07-16T20:23
高考體育行政

By Dinah
at 2015-07-16T17:23
at 2015-07-16T17:23
104年高級三級行政學題目不一樣

By Eden
at 2015-07-16T14:39
at 2015-07-16T14:39