[理工] 中央104資結第1、2、5、6、7題

[kk8850tw (甘蔗)]

中央104資結第1題
http://imgur.com/rK3AdmA
我想第一題的解答無疑是B
但是有人能解釋為甚麼C和E是錯的嗎?


中央104資結第5、6、7題
http://imgur.com/LPSCDgC
第五題A、B是沒有疑問的，C我也在網路上也有查到可以(google Incident Matrix)，
我倒是沒看過只用linked list表示的，大都會用adjacent list，這算linked list的一
種嗎?
還是這邊的link list有甚麼特殊的呢?

第六題我的想法如下
A: 第一個除非是skew-BST，不然不會是
B: BST好像可以只有一個點?
C: 並沒有完全sorting好
D: 三個點的BST就不是2的次方數
E: 應該吧?

第七題
我覺得14和17都在正確的位置上了，所以都有可能第一輪是pivot，所以選A(不要管題目
紙上寫的D?)
不知道這樣對不對?


非常感謝各位~~~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.227.238
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484144224.A.670.html
推 Astar5566: 二分搜的前提是要排序好
  對耶，我竟然忘了這點，謝謝!
※ 編輯: kk8850tw (140.115.227.238), 01/11/2017 22:38:21
※ 編輯: kk8850tw (140.115.227.238), 01/11/2017 22:48:25
推 yupog2003: 第一題，C我的經驗告訴我，recursive在trace的時候有點
→ yupog2003: 麻煩，所以也不太好debug
→ yupog2003: (E)一段code越短其實對Compiler來說是越難找到可以優化
→ yupog2003: 的地方的，而recursive的程式碼通常蠻短的，而且我覺得
→ yupog2003: compiler優化loop遠比優化recursive強，我覺得拉...
→ yupog2003: 之前修compiler的直覺
→ yupog2003: 第五題，如果一個graph剛好是一個simple path也許就可
→ yupog2003: 以用link list表示？反正題目只是說can也沒說要can
→ gigayaya: 1.(E) 應該是只有尾端遞迴才好優化 一般遞迴無法優化
→ yupog2003: represent all，如果是我我會選E拉...
→ yupog2003: 第七題我的想法和你一模一樣
推 AllenPaul: 優化方面giga大說的是對的
→ w181496: 第六是問binary search的條件 不是問BST@@
  對耶，看錯了!!!
推 Transfat: 第七題跟你想的一樣
→ Transfat: 第五題graph還滿常用linked-list表示的呀
※ 編輯: kk8850tw (140.115.227.238), 01/15/2017 20:56:30