Re: [理工] 中央DS101

[jordanforme (jordan)]

※ 引述《kiki86151 (白飯)》之銘言：
: 先分享一下我答案
: BBEAC    ?ABCB   EBDCB  DAC?B   E?BCB

幾題想問一下 答案跟我的不太一樣...

9.選b. X+83
column major 10X10
X indicates the memory address of A[0][0]
which of the following is the memory address of the element A[3][8]


10. 應該是e.
a.b.c的運算都正常吧 只是可能回應queue滿或 queue空
這樣應該不會造成什麼illegal opration

13. 我是選a  看討論後也有修正成a

16. e.
b跟b+ tree 看書畫的圖也都是把leaf同一層
要比平衡 應該也是B跟B+trees較為平衡
所以全部都算平衡吧？

23. c. bellman-ford
問shortest path one node to another in an arbitrayweighted graph with no
negative cycle?

dijkstra不能有負邊


其他應該就都一樣了















: 問一下幾題 打?是不確定Q_Q 其他題也歡迎提出討論
: 第6題 我會選E
: Which of following input is worst-case scenario (i.e requires the most
: number of comparisons) for the merge?
: The input numbers are
: a.in ascending order?
: b.descendind order
: c.almost sorted-only few are not in right position
: d.in random order
: e.The order of the input does not matter
: 這問題是問merge排序當輸入的資料 是怎樣的情況才會發生最糟情況
: 我覺得是merge最糟最佳和平均都是O(nlogn) 不論資料怎麼排都沒差吧...
: 他都會先分格子合併在排 基本上分隔子就執行基數為2的logn回合了 (每回合為O(n))
: 不知道對不對
: 第19題 Suppose there is a test file containing text composed only by the
: five letters{a,b,c,d,e} with the corresponding probability distribution{
: 0.05,0.10,0.12,0.13,0.60} Which of the following encoding will produce
: the shortest encoding of the original text?
: A.a=000,b=001,c=010,d=011,e=100;
: B.a=000,b=001,c=010,d=011,e=1;
: C.a=0  ,b=100,c=110,d=101,e=111;
: D.a=100,b=010,c= 10,d= 00,e=11;
: E.a=111,b=110,c=1  ,d=101,e=100
: 看不懂 這題是在問怎= = 答案是A還是B 還是其他Orz Why?有人知道嗎
: 第22題 The disjoint set can be implemented by array.Assume that Union by
: size and Find with path compression are used, given elements 1,2,3,4,5
: and 6, which of the following could be the context of the array after the
: following operations.
: Union(1,2);
: Union(3,4)
: Union(1,3)
: Find(4);
: A.[-4,1,1,1,-1,-1]    B.[0,1,1,1,0,0]    C.[2,-4,1,1,-1,-1]
: D.[2,3,4,3,0,0]   E.none of the above
: 不太知道這題要表達甚麼...問array的內容
: 有6個元素 分別放在Array[0,1,....5] 進行運算
: 知道Union是指把兩set合併成1個set(也就是聯集)
: 一開始是{1},{2},{3},{4},{5},{6}====>Array[0,1,2,3,4,5]
: 進行Union(1,2)代表Array[1]和Array[2]做聯集動作 也就是{2}和{3}
: 並從Array0到5找是否有{2} 有的話Array[2]的元素也就是{3}放進該{2}屬於的集合
: 有{2}集合就是Array[1]因此 Array[1]=3
: 所以變成[0,3,0,0,0,0] 其他Union按照上面做法來做
: 可是越做下去越覺得怪怪的= =不知道哪裡出問題...答案是D嗎?
: 還是我誤解題目的意思QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.124.143.199
推 A4P8T6X9:14. D radix跟bucket都是O(n)。
→ A4P8T6X9:18. 好像是B ，那個t =2 印象中是234 tree。
→ jordanforme:對 剛翻書查兩題應該都修正成你的答案 cormen都有寫到
→ kiki86151:@@那不是去年的文章嗎 那時我還很廢啊XD
→ kiki86151:日期2013/1/11==現在我早就全部重寫一份自己的答案了…
→ h56999:所以這一份考卷都是單選題嗎?