[理工] 105交大資演 第6題 關於array

[defsrisars (阿轉)]

因為找不到沒有答案，再加上三題都很不確定
所以想要問看看大家

16.
https://imgur.com/3blBUjt

這題我覺得ac是對的
但是不是很確定
我想說a應該是對的沒錯
b的話我想說addrA+1跟+1000花的時間嚴格來說應該不一樣？
但又感覺好像小到幾乎可以說是一樣的？
c的話我也不確定，但我覺得是對的，只是有些data structure用array可能效能會很差？

所以我會選D

17.
https://imgur.com/rh3Sj3d

這題我也不太確定時間複雜度要如何思考
我的想法是a是錯的，因為向量維度如果不是一維，時間應該不會是O(n)
然後bc是對的 選E

18.
https://imgur.com/gr0kh8e

這題我會選D，但也不是很確定@@

謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.52.157
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1514026909.A.6B6.html
推 jerry900287: 關於16提應該是 E
推 winiel559: 17a是對的吧
→ jerry900287: 等等我想一下XD
→ jerry900287: 改一下 應該是D才對 Array任何位置存取 應該都是O(1)
→ jerry900287: 關於16的c 他是說Array是基本的資料結構
→ jerry900287: 可以用在任何的資料結構 我想應該是沒有甚麼瑕疵才對
→ jerry900287: 只是影響解決問題的效能差異而已 基本上都可拿來應用
推 winiel559: 看錯17a的敘述了，length=n的話應該是錯的
推 FRAXIS: 18a failure function 只依賴 pat 所以這到底是算對還是
→ FRAXIS: 算錯? 用 pat 和 text 當然也算的出 failure function..
推 FRAXIS: 17 題 對於 sparse 的情況 空間複雜度應該是 O(m)?
推 sarsman: 我覺得17a可選，如果是常數維度就都還在theta(n)的範圍內
→ sarsman: 18a應該是錯的
→ sarsman: 應該是pat or text
推 winiel559: 二維就直接跳到n^2了耶 幾維就幾次方r
推 sarsman: 後來想想的確是w大所說的那樣@@
→ sarsman: 不過題目說是vector的話就只會有一維吧
推 kssdpp222: 向量是1*n 怎麼會變二維
推 winiel559: 因為強調是線代的向量所以一定是一維嗎？
推 olen0622: 猜DAE
推 andy6666: 這題交大給DAE
→ andy6666:  16 array支援random access 所以時間是一樣的
推 andy6666: 17 這題我是認為因為你還得去找跟你相符合的相加  所以
→ andy6666: 是O(mn)
→ andy6666: 18 a錯在and 要改or 然後其餘兩個林立宇kmp有寫  必看
→ andy6666:   網上爬文應該有考古題有到105的
推 yaya517: 網路上找了很久 可以請問樓上大大哪裡找到交大給的解答嗎
推 andy6666: https://drive.google.com/file/d/0B6Q2JDfTvQ9-dlF3TEJ
→ andy6666: GX2x3Mmc/view?usp=drivesdk
→ andy6666: https://drive.google.com/file/d/0B6Q2JDfTvQ9-eUdNS1I
→ andy6666: 2cE9TRTg/view?usp=drivesdk
→ andy6666: 兩份載下來放到同個資料夾解壓縮  有些沒有有些有
推 yaya517: 謝謝樓上大大 這份好多～