資訊處理已哭 - 高考

Linda avatar
By Linda
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()?
這是我寫的是個人的想法請多多指教謝謝

--
Tags: 高考

All Comments

Zenobia avatar
By Zenobia
at 2015-07-21T21:30
第三的第二是求任兩點 是用Johnson 之類的吧
Tristan Cohan avatar
By Tristan Cohan
at 2015-07-26T02:31
第四題我想的是從陣列第1元素開始比，若x比較大就和
Zora avatar
By Zora
at 2015-07-30T11:35
題目有說可以參考dijkstar但不用和dijkstar一樣詳細
Valerie avatar
By Valerie
at 2015-08-03T01:38
第2、4、8、16、32個元素比，直到x<陣列的元素在用Bin
Odelette avatar
By Odelette
at 2015-08-05T22:04
ary search搜尋~不知此想法是否符合題目要求
Franklin avatar
By Franklin
at 2015-08-10T10:28
因為我是看到題目說大部分x的值會出現在前面m個值，就用
Eden avatar
By Eden
at 2015-08-13T23:24
avl tree
Edwina avatar
By Edwina
at 2015-08-17T06:46
第一小題(logn)! 是這樣拆解的嗎？我以為是logn*((logn
)-1)*((logn)-2)....求解
Kristin avatar
By Kristin
at 2015-08-20T18:17
看老師接不接受了
Eden avatar
By Eden
at 2015-08-25T08:29
我也是認為(logn)!是樓樓上說的那樣
logn算出來如果是10 那不就是10! 答案跟原po寫的會不一樣
Faithe avatar
By Faithe
at 2015-08-26T04:47
johnson就是把所有的點做一次dijkstra
Dora avatar
By Dora
at 2015-08-30T18:21
第四題我寫的跟2F一樣 但感覺時間複雜度會超過
Ida avatar
By Ida
at 2015-09-01T11:06
但也想不出其他了 只好瞎掰
Zanna avatar
By Zanna
at 2015-09-06T10:27
題目有說明可以參考Dijkstra代表說這是唯一關鍵，我覺得用
其他解法只會越描越黑而已
Brianna avatar
By Brianna
at 2015-09-06T12:20
這也是個人考生看法...有更完整的打臉推文，接受打臉^^"
Quintina avatar
By Quintina
at 2015-09-07T17:35
第一小題想想好像L大的才對哈哈網路上又找不到哈
Lauren avatar
By Lauren
at 2015-09-08T09:18
又看了一次題目 好像真的寫dijkstra就好了 我以為是要
算出所有點的最短距離。。囧
Dorothy avatar
By Dorothy
at 2015-09-11T07:34
S到其他點的最短路徑阿
Hardy avatar
By Hardy
at 2015-09-14T23:35
大家都好強 我只能瞎掰
Delia avatar
By Delia
at 2015-09-17T21:54
@@..第一題不是可以推 (logn)! = O(n^loglogn)
Damian avatar
By Damian
at 2015-09-21T02:24
如果第一題寫B比較好 但是 推論有推出來 還是一樣會很低
分嗎??
Hedwig avatar
By Hedwig
at 2015-09-23T22:04
log(n!)=O(nlogn) 看是要用stirling還是展開求都可以
令 x = (logn)!
Ingrid avatar
By Ingrid
at 2015-09-28T13:10
logx = log((logn)!)
Elvira avatar
By Elvira
at 2015-10-01T05:48
右邊那串 跟 log(n!) 一樣 只是n變成logn
so~ => O( (logn) * (log ( logn ) ) )
Frederic avatar
By Frederic
at 2015-10-04T15:41
stirling會牽扯到定積分，根本不適合拿來解此題
Ula avatar
By Ula
at 2015-10-05T18:10
所以用展開求呀~
Steve avatar
By Steve
at 2015-10-06T08:44
看來我寫根據stirling可知O(nlogn)錯了 忽略我的解法
Oliver avatar
By Oliver
at 2015-10-09T16:24
求神人解（logn）！
Audriana avatar
By Audriana
at 2015-10-11T15:00
裡面那串前後交換 => O( (log(logn)) * (logn) )
Thomas avatar
By Thomas
at 2015-10-12T23:19
把前面那個搬上去
=> O(logn ^ loglogn)
Franklin avatar
By Franklin
at 2015-10-15T09:20
寫清楚一點 => O(log (n ^ loglogn) )
Andrew avatar
By Andrew
at 2015-10-18T07:47
logx = O(log(n ^ loglogn))
Delia avatar
By Delia
at 2015-10-20T11:12
x => O(n ^ loglogn) , x = (logn)!
Kristin avatar
By Kristin
at 2015-10-23T14:07
所以 (logn)! = O(n ^ loglogn) ...
Hazel avatar
By Hazel
at 2015-10-26T09:49
然後各自把前面的n^2乘進來
Hamiltion avatar
By Hamiltion
at 2015-10-26T11:52
一個會是 (n^3)*logn
Bennie avatar
By Bennie
at 2015-10-26T18:27
另一個是 n^2 * n^loglogn = n^(2+loglogn)
Mary avatar
By Mary
at 2015-10-28T10:41
在n很大的時候 n^(2+loglogn)會遠遠大於(n^3)*logn
Joe avatar
By Joe
at 2015-10-29T07:53
不過我把log(n!) = O(nlogn)是用stirling代過..
所以可能不太行吧..qq
Kelly avatar
By Kelly
at 2015-10-31T08:10
e大好強阿 上面也有很多神人 小弟都不知道在寫甚麼
Michael avatar
By Michael
at 2015-11-02T05:21
小弟國考路已走到盡頭 只能祈禱這次會有奇蹟出現了
Caitlin avatar
By Caitlin
at 2015-11-03T05:51
@@我專案管理可能0分呢XD 真是悲劇~
Elizabeth avatar
By Elizabeth
at 2015-11-07T05:56
我後來仔細看內聚力他要從差寫到好 我寫反了XDDD
Yuri avatar
By Yuri
at 2015-11-07T13:15
我也就內聚力那題好像可以寫些東西 其它都不會..@@
Rae avatar
By Rae
at 2015-11-10T03:45
8月沒考專案管理 所以我也都沒念~_~
Charlotte avatar
By Charlotte
at 2015-11-13T04:41
不會啦 我覺得你很有機會會上 不要太擔心
Agatha avatar
By Agatha
at 2015-11-13T14:55
我需要奇蹟才可能會上 只能先做好心理建設
Jacky avatar
By Jacky
at 2015-11-14T08:14
哀我也希望八月能考上 順利的話一定回來回報各位~_~
Lydia avatar
By Lydia
at 2015-11-17T20:40
o大你別想太多@@ 放鬆心情等放榜吧!! 搞不好會上 :)
Madame avatar
By Madame
at 2015-11-18T21:14
(logN)! N=10^X 代入 是不是能看出來cc ?
Kyle avatar
By Kyle
at 2015-11-23T05:51
另一邊應該小於log(N^N) = N*logN 也用 N=10^X 代入
Michael avatar
By Michael
at 2015-11-23T14:50
所以e大也是謝a>b嗎
Belly avatar
By Belly
at 2015-11-27T04:56
錯是a<b
Enid avatar
By Enid
at 2015-11-29T12:07
手殘要寫a<bㄧ直沒用好
Olivia avatar
By Olivia
at 2015-12-03T13:11
不是我沒寫好ptt會吃小於b
Mary avatar
By Mary
at 2015-12-07T15:12
恩A < B , 所以應該選A演算法
Liam avatar
By Liam
at 2015-12-10T17:23
謝謝e大
Annie avatar
By Annie
at 2015-12-14T14:21
內聚力那題看程式碼可以推得出 只是要花時間
Kumar avatar
By Kumar
at 2015-12-15T03:33
時程壓縮和CMMI都是申論形式分數難講
Anonymous avatar
By Anonymous
at 2015-12-18T12:20
我也只把定義寫出來再畫圖推 V MODEL定義很簡單但忘了

高考行政法第6題

Christine avatar
By Christine
at 2015-07-16T21:32
高考行政法選擇只錯這題... 第6題 關於公有公共設施音設置或管理有欠缺，致人民受損害之國家賠償責任， 下列敘述何者錯誤？ 答案給A A.供公眾使用之道路、橋梁、公園等，在施工建造中亦屬公共設施 我現在翻課本 上面有肯定說和否定說 否定說(林三欽、董保城、李惠宗) 驗收僅是承攬工作業者與委託機關 ...

臺北市政府秘書處徵職代(約聘分析師)

Mia avatar
By Mia
at 2015-07-16T21:20
各位剛剛跟高考奮戰完的大大水水你們好、大家好、苔軋厚~ 如果你今年是考資訊職系的麻煩照過來~照過來~ 臺北市政府秘書處現在在資訊分析師的職代 不管你是一直讀書累了，想找個短期的約聘工作賺生活費 或是你感覺今年很有把握了，想要利用時間先上班學習一下 還是你對這個工作很有興趣，想要來嘗試看看 以下是臺北市 ...

資訊處理已哭

Edwina avatar
By Edwina
at 2015-07-16T20:23
請問這次高考的資料結構 有高手可以分享一下嗎 ? 第一題 不太會推..只有背他們的大小關係　就掰上去 不知道有沒有同情分數ˊˋ 第二題 是用數學歸納法嗎 ? 第三題 我是把Dijkstar演算法簡單的寫一寫 第四題和第五題沒想法... 還有程式語言最後一題 (智慧卡進出系統) 是要 ...

高考體育行政

Dinah avatar
By Dinah
at 2015-07-16T17:23
各位前輩大家好： 今年第一次考高考 ， 科目是體育行政 ， 請問這次的難度比起往年 ， 是平均值還是比較難呢 ？ 如果有前輩也是考這科的 ， 希望不吝賜教 ！ 謝謝 ！ 手機發文請見諒 ！ ----- Sent from JPTT on my Sony D6653. - ...

104年高級三級行政學題目不一樣

Eden avatar
By Eden
at 2015-07-16T14:39
[問題] 應考資格、各種國考疑難雜症等，以有正確作法、答案者為主 (不包括書裡的疑問)。若問題如人生規劃、讀書計畫等，無一 定作法、答案者，請用閒聊選項。 由於本人有考104年高考三級一般行政，所以有拿到行政學的考卷， 本人也下載了考選部網站上放的題目 ...