[理工] 100成大資工 DS＆Algo(資結)

[genius945 (添財)]

http://0rz.tw/SkLcE  題目


看板上好像只有去年考完有人討論...

一堆都不會...整個亂寫

答案 PO上來請各位幫忙修正&指導 = =


1.

(a)AVL  感謝版友
(b)B tree of order 3 (2-3 tree)
(c)Max Heap(binary)

2.

(a) 不會...瞎寫了一個code後來發覺不是O(lgn)

所以(b)也甭提了...


3.

這題好難,我幾乎沒一個是確定的都亂矇

a-6
b-2
c-9
d-1(版友指正XD)
e-4
f-3


4.θ(nloglogn)

5.

這題應該會有不同答案吧
給左右給0或1或是合併次序

我做的是
a:01
b:0000
c:001
d:101
e:11
f:0001
g:100


6.
不會

一開始看到複雜度想說先做kruskal's algo O(V^2logV)

再搭個BFS之類的

但後來想想有邊在MST並不能保證此邊是這兩點的最短距離= =

我就掰了 Orz


7.

我的想法是

step1.做類似counting sort的動作,計算1~k各有幾個

假設這n個int存在int[n]
建count[k],初值皆為0

for i = 1 to n
count[int[i]]++

O(n)

step2.建立一個sum[k],存count[1]+....+count[i]之sum

sum[1]=count[1]
for i = 2 to k
sum[i]=sum[i-1]+count[i]

O(k)


時間複雜度為O(n+k)



若要知道多少個int在range a~b

則只要 return (sum[b]-sum[a-1])即可  故為O(1)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.192.163
推 FY4:第四題為什麼是θ(nloglogn) 他不是n/logn嗎
→ genius945:就...用展開代入法做囉
※ 編輯: genius945       來自: 218.173.192.163      (01/12 22:07)
※ 編輯: genius945       來自: 218.173.192.163      (01/12 22:08)
推 pikachu123:下面那個我覺得用radix用hashnig去做 他分bucket
→ pikachu123:只要O(1)
推 wei12f8158: 2019感恩推