[理工] 中央DS101

看板Grad-ProbAsk作者kiki86151 (白飯)時間13年前 (2013/01/11 20:08)推噓8(8推 0噓 9→)

留言17則, 5人參與討論串1/3 (看更多)

先分享一下我答案 BBEAC ?ABCB EBDCB DAC?B E?BCB 問一下幾題打?是不確定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: 140.115.213.99

推

BuliBuchi

01/11 20:44, , 1^F

01/11 20:44, 1^F

推

BuliBuchi

01/11 20:45, , 2^F

01/11 20:45, 2^F

→

kiki86151

01/11 21:27, , 3^F

01/11 21:27, 3^F