[理工] 中央DS101

[kiki86151 (白飯)]

來回覆一下好了

8.12是觀念題
然後14題
洪逸的書 沒講bucket sort= = 然後不小心把基數複雜度想成O(nlogk)-  -
所以應該我錯Orz

推 wjungle:第8題聽說洪逸在課堂是選E                                01/13 22:05
→ wjungle:第10題在別的討論串中是選C                               01/13 22:06
推 wjungle:第12題有關於JAVA的是C，題庫班有這題                     01/13 22:11
推 wjungle:第13題看DS課本感覺像B，討論一下                         01/13 22:19
→ wjungle:第14題 我選D 理由是都是O(n)吧？                         01/13 22:23

剩下回答其他題一起討論一下

再來第10題 這題感覺有一點盲點 其實我也不確定 看板上有人寫C也有人寫B
我是選B 不知道對不對 看討論串 都有一點模糊 最近讀書頭有點很昏QQ
個人想法是 所謂不合法的我想應該是指
在queue full時候硬要插data進去 或是empty時拿data出來 這兩種情況發生吧?

enq代表在尾端將資料放進去
deq從前端取資料出來
一開始front和rear是設定NULL的 也就是-1

每跑enq時候rear會+1 這代表 有資料放進去的 此時front應該不會有怎麼變動 就是-1
如果rear=front=-1當然整個queue應該是empty的也沒拿東西出來
deq則是每跑一次front就+1 對到rear代表就把該資料拿出來


http://epaper.gotop.com.tw/pdf/AEE032400.pdf
看這第3頁code和圖 感覺滿清楚的

所以C要rear=n-1才會不合法吧...
至於B的front=rear 代表queue已經empty了 根本data可以拿出來阿QQ
想法不知道對不對


13題的話 他問優先權queue用array的原因是什麼
我覺得可以參考Heap sorting或是Heap tree和比較array和link list優缺點吧
仔細看一下 這答案好像是A=  =不是D我應該寫錯QQ
A:array的確找父點 左右點 較容易
B:想像成Heap tree  deq就是刪除 enq就是插入 都花費O(log N)
C:array比link list 浪費記憶體空間 所以不是原因
D:Sequential效率最不好才對 不管資料有沒有先排序
接題目又說for a particular value所以我想應該是用Hashing Search比較快
所以是A(?)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.115.213.99
推 BuliBuchi:13的C 其實是節省啦 因為heap是complete BT
→ BuliBuchi:A則是search.swap快=效率好 so我想效率好應該>省空間吧~
推 cutemiller:我覺得13是A...c的話如果一開始heap滿後來被刪光光
→ cutemiller:array不就花的mem比 linklist多了
→ cutemiller:第10我覺得A,原因n-1格的array
→ kiki86151:事實上我也覺得第13題是A阿@@(本來寫D Orz)只是w大問的
→ kiki86151:才發現 寫錯了QQ然後第10題 討論上都是再說不是B就是C耶
→ kiki86151:cutemiller大說的 n-1格的array 你能說明一下嗎@@
→ kiki86151:我覺得C要 rear=n-1才會不合法(原因是equeue已經空了
→ kiki86151:但卻取資料出來)
→ cutemiller:我是想 n-1 格 用 n 格的例子
→ cutemiller:illegal 我覺得是發出 trap 通知os才算illegal
→ kiki86151:題目前題不是說已經給你n格array來利用-  -
→ cutemiller:rear 等於 front 不就是 return " q 空"
→ cutemiller:我是這樣猜,不然我就會寫 e ,因為我覺得他用詞很模糊
推 bin272max:可以請問一下第2、12、20題嗎?
→ kiki86151:12是觀念題 不知道如何解釋...去查書或上網找比較準
→ kiki86151:至於第2題 也是觀念題 洪捷書好像有說 但可以用證的吧
→ kiki86151:第20題是matrix chain ((A1A2)A3)=10*100*5+10*5*50
推 bin272max:謝謝： )