[理工] 100台大電機DS 對答案

[cocoyan (摳摳厭)]

1.E
2.A
3.A
                  　　p*O(n)+(1-p)*O(log(n))
amortized runtime　=　─────────── ≒ O(log(n))
　　　　　　　　　　　　　　　　1
應該和Ｋ沒關係，Ｋ次input代表run Ｋ次

4.B
5.D
6.如果答案有13的話我就想選XD

7.CD
(E)如果k=n就不行，也沒說是常數啊( ￣ c￣)y▂ξ

8.BCD
已更正！
9.BE
(B)的爭議點在於它說的leaf node(external node)到底是不是null pointer

10.CDE

11.ABDE
(C)無向ＯＫ但有向就會錯，而且(D)選項給undirected graph做對比
(E)看了前面的討論串還是不太懂為什麼不選，有人可以詳細說明嗎？

12.AE
13.E
14.ABCD
15.ABE
16.B
(C)應該是5


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.163.229
推 WashFreeID:可以問一下16題C是啥咪意思嗎
http://zh.wikipedia.org/wiki/分團覆蓋問題
其實我是猜的:P
※ 編輯: cocoyan         來自: 1.161.163.229        (02/24 23:24)
推 jjjjj4445:想問一下16(c)他是說最少是3cliques的子圖?
→ jjjjj4445:還是16-3最少有3個cliques?
推 johnny87901:3我問學校老師說應該要選B 他說其實題目超的有問題==
→ johnny87901:8D是可以做到的 9B他的意思就是外部點 11D樹都是無向
第三題既然題目怪怪那就跳過
第八題已更正
第九題已更正
十一題以下是我的看法：
　　　在圖論中樹為無向
      在資料結構中為有向
推 jjjjj4445:你的16(5) 是指可以分成5個3-clique嗎?
對的，不過說真的我只是猜猜
→ ken1325:第7題的E，如果不選的話，那102年第5題也是False囉？
嗯，我那一題也選False
※ 編輯: cocoyan         來自: 1.161.168.127        (02/26 11:09)
推 jimmylin1024: 10的A選項為什麼是錯的呢？紅黑樹insertion rotatio
→ jimmylin1024: n是O(1), deletion有可能color change到root 但是ro
→ jimmylin1024: tation也會是O(1)所以A選項說O(logn)根據定義就會是
→ jimmylin1024: 對的
→ jimmylin1024: 11題的C是對的喔～ 根據tree的定義 tree是無向的（
→ jimmylin1024: 子嘉離散第七章）