# ㄐㄉㄗㄧ
# 104交大
Ans:C
A:這邊priority是指加減乘除預設的priority,不是他在式子priority
Ans:B
B:唯一MST不保證唯一邊
C:唯一邊保證唯一MST
Ans:B
n/k+2n/k+3n/k+...+kn/k=n/k(1+2+..+k$^2$)=O(nk)
# 105交大
Ans:D
b:因為random access所以一樣
Ans:A
b:space:$\theta(m)$
c:O(n)time,因為不能random access
Ans:E
a:failure function應該是自己對自己
Ans:B
b:O(n)
Ans:C
a:O(n)
b:true,右子最多O(logn)
Ans:D
c:因為他inplace sort,所以不用merge
Ans:A
a:透過secondary key可以知道先後順序,就可以知道要不要換
c:應該是less or equal than key
Ans:C
b:題目在問merge會執行幾次,並非其時間複雜度,1+2+4+...+n/2=2$^n$-1
Ans:E
a:BFS找連通,disjoint set用union/find找同集合
b:DFS和BFS皆O(V+E)
c:disjoint set最好,space是O(n),其次是DFS,space是O(m),接著是BFS,space是O(m)
Ans:C
a:最多n個set,所以最多n個
b:每個邊做一次find,所以最多m個
Ans:E
b:log*n代表n幾次會變成2,所以極小
c:n^$\alpha$>nlogn>nlog*n
Ans:C
a:amortized cost和quick sort沒關係
b:Ture,accounting method用來算攤提成本,且要確保正數
Ans:D
Fibnoacci除了delete min,delete node的amortized cost是O(logn)外,其他皆O(1)
Ans:C
2/m*(1/(m-1))
Ans:B
可以這樣想,是$\alpha$已經滿格的,所以1-$\alpha$是沒滿的,所以1/(1-$\alpha$)
Ans:B
選同一格
# 106交大
對L1..Lm建立一個minimun priority queue Q,有m個元素,分別是n1...nm,ni代表第i個list的元素,每次挑Q中最小兩Q做merge,再放回Q,不斷重複直到剩一個sorted list
# 108交大
Ans:A
(((4+4)+8)+((5+4)+(3+5)))=>91
Ans:D
Ans:D
可以看成是一種OBST的算法,因為同樣會讓剛剛加過的再加一次
Knuth's Optimal Binary Search tree可以在O(n^2)解決
Ans:ABC
D:做BFS,O(V+E)
E:找所可走的path,做E次BFS,E(V+E)
Ans:D
K是2^logc,且k每次除2,相當於2^(logc-1),所以跑logc次,每次做E次BFS,O((E(V+E))logc) = O((E^2)logc)
Ans:ACDE
line3 extract min,所以array要O(n),binary和fibonacci heap O(logn)
line5做decrease key,binary heap O(logn), fibonacci heap O(1)
Ans:A
因為皆1,所以全部加起來了不起才n,背包可全裝
Ans:A
因為皆1or2,所以全部加起來了不起才2n,背包可全裝
Ans:B
因為不存在連續的xyz
Ans:BC
由於沒有xy,所以要讓xyz連續必然走x>z>y or y>z>x,所以在x,y分別增加a,b兩點確保一定要走z,接著要使這個圖連通,所以a,b走完要走回z,所以z要加a,b
Ans:ABC
根據剛剛的想法,由於z也可以當頭尾,所以xy要加上ab
# 109交大
Ans:B
Ans:BC
l1連a1,a2確保開頭一定走a1或a2
Ans:ABCD
l2負責與a1,a2,x1,x2,x3連,用來確保HC
Ans:CD
l3確保x1,x2連通,用來確保HC
Ans:BCD
l4與x1,x2,x3連通,確保HC
Ans:CE
A:2t-1 or 2t
B:B-tree leaf要同一層
C:True, root node
D:root>=1
E:可以把他想為binary tree,所以左邊的式子代表在高度h的節點總數,後面是整棵樹的節點總數,或直接帶最少節點公式
Ans:CD
A:如果插入的是full node的中間,會跑到parent
先得出MST,隨機選一邊刪除,看看他要用哪個邊來補會形成最大,應該做O(V+E)可做完
Ans:(18)B(19)D(20)A
18:將較小rank的tree指向較大rank的tree,這樣就不會增加rank
19:透過路徑壓縮可以扁平化disjoint set
20:將小的接大的,相同就隨機,是根據權值啟發的概念
Ans:ACE
C:要考慮當前的值是否是最尾點,或是不納入他
D:D(n, sum of A)
E:表格大小,最多可以到n * 6an
Ans:ADE
A:先花O(1)定位,預期每個key存a個,所在在花O(a)搜尋,O(1+a)
B:他是heap,非balanced BST,所以要O(n),除非是找最大或最小之類的
Ans:ACD
可以用maximum flow去解
s,t分別為p1,p2,中間的點是task,s連到task的weigth對應ai,t連到task的weight對應bi,task間再根據communication cost去建邊,因為叫小cost的邊會先被吃掉,在哪個邊滿,就代表他在哪個處理器上運作,接著考慮communication cost,可以發現若commuication cost加上去,那個task到t沒滿,就代表他們兩個間就算加上communicaton cost還是比待在原來好,這樣就可知道task分別在哪,可得P1:2,4 P2:1,3
X=4+17+3=24
Ans:ABDE
A:每個皆可選可不選,所以2^n
B:如上面構建的一樣
C:p1 p2分別在兩邊的min cut
Ans:A
第二行可知y可能是x的右子最小,四五行可知若x是y的左子才會停,且他是從原本的地方一路我左走上來,所以是要找successor
# 110交大
Ans:ACE
A:等價於漢米爾頓路徑
B:皆一可以用BFS,不同用floyd
C:等價漢米爾頓迴圈
D:用bellman-ford
E:有負cycle,無解
Ans:BD
每個點必帶兩個小孩
Ans:BD
A:排序過不能亂加,所以要先找再加
C:O(n)search
D:因為要搜尋node
Ans:BCE
A:maximum flow才是polynomial time
C:邊可以亂走亂流,反正最大一樣就好
D:雖然可以不同cut,但最後的capacity仍要一樣
E:因問最小切的容量和最大流一樣,所以必是偶數
Ans:ABE
A:必存在一條可使其為最短路徑
B:路徑可形成樹
C:但不一定是最小樹,他只保證到點最小
D:都說是最小了,怎麼可能比他小
Ans:BCE
先建立一個MST,然後加入剛剛沒加入的邊,刪除與他值最接近的邊,可得另外一個ST,透過這方法可找第二小
Ans:CD
4+b-a=c
c+d=24
20+1-b=d
Ans:AB
A:T(n)=4T(n/4)+O(n)
B:T(n)=2T(n/2)+O(n^2)
C:T(n)=2T(n/2)+O(nlogn)
D:明顯錯,最快都要O(nlogn),但卻只要O(nloglogn),T(n)=n/logn(T(logn)) + O(nlogn)
Ans:ABD
B:會要兩倍大的
C:存n個資料,所以空間n
D:問amortized是O(1),這邊是考慮到可能要搬東西到新位址才有可能O(n)
Ans:BCD
除leaf node外,其他degree皆為3
degree不足3的最多兩個,因為可以結合
Ans:BC
要盡量讓區間大，所以選最早結束或最晚開始,這樣重疊的最小
Ans:AD
log*n代表作幾次log會使n為1,會是一個極小的數
Ans:BC
A:T(n)=T(n/3)+T(3n/4)+O(n) 所以不為O(n)
D:下限是O(n),跟heap sort沒關係

# 111交大
Ans:DE
B:search看高度,O(logn)
C:一樣使用BFSorDFS,O(n)
E:AVL比紅黑樹嚴格,通常比紅黑樹矮,所以更快
Ans:D
這是Dijkstra
A:用adjacnecy matrix O(V^2),用adjacnecy lits O(V^2),binary heap O((V+E)logV),fibonacci O(E+VlogV)
B:shortest path Dijkstra
Ans:AC
C:用array做queue要保證資料形態相同,用linked list不用
Ans:CE
B:用merge,O(nlogn)
C:因為要走到最後再指回來,O(n)
D:O(n),將小的最後指到大的開頭
E:因為有最後的pointer,所以O(1)
Ans:AB
A:刪除要搜尋,O(n)
B:因為排序過,所以每次找值比較第一個元素就好,O(n)
C:通常linked list都用merge O(nlogn)
D:同上
E:要在O(n)建立BST,要確保linked list sort過,否則O(n^2)
Ans:D
A:一樣
B:array快一點,可以random access
C:一樣,都不能前後移動
D:doubly linked list快,因為可以前後移動
E:doubly linked list快一點,Binary tree沒辦法往前
Ans:ABCE
A:doubly linked list有雙向的特性,大於往後,小於往前
B:最差O(n^2),用類似quick sort的方式去想,因為要確保node前皆比其小,node後比其大,所以最差O(n^2)
C:如同quick sort
D:BST avg search O(logn),因為avg hight是logn
E:skew tree,O(n)
Ans:ADE
A:因為相同value會走到同一個位子,所以不會有相同value,不同node
BC:題目是說any子樹,沒限定是不是root的
E:平均BST樹高logn
Ans:ABCD
D:最多就叫n次
E:logn~n
Ans:ABC
A:最差就是整個hash table找過
B:將table的值sort過一遍,O(nlogn)
C:proper selction,所以O(1)
Ans:ACD
A:light edge必為某MST的一邊
B:有可能同weight
C:若邊唯一,則MST唯一,反過來不會對
D:因為最大在cycle
E:錯在every MST,應該是some MST,因為light edge不唯一
Ans:ACE
除s,t外,流出等於流入
x+1=2,x=3
4=2+z,z=2
y+3=2+z,y=1
c=6+1,c=7
2+b=3,b=1
a+3+3=c,a=1
Ans:ABCDE
verification algorithm就是非確定性解
所以只要屬於NP皆可
Ans:ABC
mincut可用Edmonds krap或Ford Fulkerson,所以P
C:co-NP為NP的補集,和NP交集於P
Ans:BCDE
vertex-cover是NPC問題
Ans:A
(1)1
(2)4
(3)3
(4)2,在interval,每次挑最小degree
(5)3
(6)3
(7)1
(8)2
(9)2
(10)3
x=2,y=3,z=4,w=1
Ans:BCD
(1)NPH,相當於漢米爾頓路徑
(2)NPH,有負回圈
(3)P,Bellman ford
(4)P,DFSorBFS
(5)NPH,相當於漢米爾頓cycle
(6)P,BFS
(7)NPH,找最大割
(8)P,最小割,Ford Fulkerson
(9)P,在interval 用greedy,一般圖是NPH
(10)P,3-CNF NPH
# 112交大
Ans:B
A:kruskal每次挑最短邊,所以關注點在邊
B:kruskal List:O(ElogE),Heap:O(ElogV),Prims list:O((V+E)logV),Binary Heap:O((V+E)logV),Fib Heap:O(E+VlogV),因為kruskal關注邊,所以邊多的時候不划算,prim關注點,所以點多不划算
C:MST可以允許負邊
Ans:BC
BC差在stable,B因為有等於,所以如果一樣會先放前面,stable
Ans:BD
最大高度是2 * log(n+1)
A:可以全黑,且路徑長一半至少為黑,所以應該是0~n/2
B:因為每條路徑上,黑節點至少為路徑的一半長,所以可知黑節點是ceil(n/2)~n
C:可以最大高度為最小高度的兩倍,最小全黑,最高紅黑交錯
D:因為root是黑,所以必定要刪除root
Ans:A
A:因為高度為0開始,節點最多為2^(h+1)-1
B:要刪除3個level,最多需要(2^(h+1)-1)-(2^(h-3+1)-1),很明顯,當h足夠大時,2^G肯定不夠
C:因為是第二小的,節點總數又為2^(h+1) -1,所以要2^(h+1)
D:H是插入15個節點的高度,所以要讓他跟h差距最大,則要插入h=2的樹,所以差距最多就是2
Ans:AB
A:觀察序列可以看到,令x為值,若x為odd,則pop時間為x+1,若x為enen,pop時間是2n-x+1,可得x+1=n,x=n-1 or 2n-x+1=n,x=n+1
B:XY中間只有一個要pop,所以差距為2
C:明顯錯,odd越大,pop時間越晚,even相反
D:根據A可知n-1和n+1其中一個會在n出現,又n-1+n+1=2n,所以s or t在n次pop會出現
Ans:任何邊在matching中,必有一端點會在vertex cover中,且在matching中,不存在兩邊共享同一個點,也就是說每個邊最多只能使用一個vertex cover的點,所以matching必不超過vertex cover
Ans:7,5
Ans:用二分搜尋的概念
1.設定left=0,right=n
2.mid=(left+right) / 2
3.若a[mid]>a[mid+1],則right=mid,否則left=mid+1
4.若left>=right,則輸出a[mid],否則跳回第二步
# 113交大
Ans:AE
A:因為S,S'會把s,t分開,所以聯集後依然可以把s,t分開
B:f1+f2的flow可能會超過edge capacity的
C:total capacity最大
D:Bellman-ford shortest path
E:Ford-fulkerson 可修改為BFS變成Edmonds Karp,O(VE$^2$)
Ans:C
sum是用來算每個bit數相加,所以跟digit sum有關,看他return可以看到他回傳的是n*y-x,所以是得出加n會成target
Ans:ACD
A:bj是做加k個ai,所以O(k)
B:A都可以做,klonp更大一定可做
C:有p個bj,所以O(kp)
D:
所以可以得一Vandermonde matrix,Vandermonde matrix行列式不為0即為獨立,1-1
E:p>k,所以無法any,非onto
Ans:ABCDE
A:因為1-1,所以一定不同
B:因為在有限域,所以最多k-1可組成另外一個
C:線性運算
D:因為1-1
E:線性運算
Ans:

構建一個從後面做到前面的LIS,稱其為R,則P(i)=min(T(i),R(i))-1,先算最小的升序和降序,再扣掉1,因為最後一個值重複