[理工] 中央DS101

[kiki86151 (白飯)]

先分享一下我答案
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:19就huffman algo
推 BuliBuchi:22.array裡存的是root的編號
→ kiki86151:感謝樓上! 第19題會了 答案是b 第22題還在想Orz
推 BuliBuchi:Find with path compression會把找到的點改接到root
→ BuliBuchi:4原本的parent應該是3 find(4)後parent變1了
→ kiki86151:感謝BuliBuchi我懂了原來是這樣QQ Union(1,3)3的父也變1
→ kiki86151:運算完Union(1,2)=>010000 (3,4)=>010300 (1,3)=>011300
→ kiki86151:最後find(4)=>011100
推 ab170926:我記得root要存 負的#集合
推 martin77:第16題我選E耶，B+ tree不也是平衡的嗎？
→ kiki86151:那題好像問利用2元搜尋來重新平衡 B+樹不需要吧..
→ martin77:我理解錯了XD
推 wjungle:第8題聽說洪逸在課堂是選E
→ wjungle:第10題在別的討論串中是選C
推 wjungle:第12題有關於JAVA的是C，題庫班有這題
推 wjungle:第13題看DS課本感覺像B，討論一下
→ wjungle:第14題 我選D 理由是都是O(n)吧？