[理工] [資演] 105-台大-資工-資演 對答案

看板Grad-ProbAsk作者 (呱)時間9年前 (2017/01/20 13:29), 9年前編輯推噓14(14推 0噓 54→)
留言68則, 12人參與, 最新討論串1/2 (看更多)
抱歉，又是我 <(_ _)> 想來對一下105 台大資工資演答案 http://imgur.com/a/84y4L a. D b. G c. C d. C B e. C f. H http://imgur.com/a/OA6Xt a.θ(n^(log_8(3)) b.O(lglgn) c.O(n^3 / M^(1/2)) http://imgur.com/a/pjoyK a.O(log(n/m)) b. O(m) = n c. 0 1 2 3 4 5 6 28 8 16 nil 22 nil 11 http://imgur.com/a/F9MXj a. 1. 找到G中最小值 2. Inorder search(G.the-left-node); b. int catalan(int n) { if (n==0 || n==1) return 1; int sum = 0; for(int i=1;i<n-1;i++) sum += catalan(i)*catalan(n-i); return sum; } c. ○ ╱ ╲ ● ○ ╱╲ ╱ ○ ○● ╱ ● http://imgur.com/a/S9GPk a. A-> D -> E -> G -> H 27# b. 44 32 http://imgur.com/a/5WAlu Define Φ(H_i) =kΣ H_i(x) x∈H_i Insertion: c'i ＝ ci + Φ(H_i)- Φ(H_i-1) ≦ klog(n_i) + kΣ H_i(x) - kΣ H_i-1(x) ＝ klog(n_i) + klog(n_i + 1) ＝ O(log_n) Exact min c'i ＝ ci + Φ(H_i)- Φ(H_i-1) ≦ klog(n_i) + kΣ H_i(x) - kΣ H_i-1(x) ＝ klog(n_i) - klog(n_i + 1) ＝ O(1) http://imgur.com/a/RCPMe [ 0 , if i = j+1 [ 1 , if i = j L(i,j) =[ L(i+1,j-1) +2 , if i < j and s[i] == s[j] [ max{L(i,j-1) , L(i+1,j) , ,otherwise CABDAACBADFA C111133556667 A011133346667 B 01112244555 D 0112223555 A 012223333 A 01111113 C 0111113 B 011113 A 01113 D 0111 F 011 A 01 取ADAA ADAAADA# 考試快到了，大家加油QQ~ -- 　　有一個香錦囊，是從一個神話般的守軍的血屍頂上剝下的。那一次我們部隊遭受從未 有過的頑強抵抗，我們犧牲了三個艦隊，一個裝甲師和無以數計小組推進的敢死排，才摧 毀了那處隘口的碉堡。但是竟然發現，使我們遭受如此慘烈傷亡的守軍，總數只有一人。 　　士兵們起鬨地在他胸前發現這枚香袋，大家都相信這是一枚具有神奇力量的護身符。 我們把他的頭顱砍斷，取下香袋，剝開， 　　裡面一張被血浸紅的宣紙竟用漢字娟娟秀秀四個整齊的楷書寫著－「盼君早歸。」 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.10.229 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484890170.A.435.html ※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 13:30:52
→
01/20 13:33, , 1F
1.d是B吧
01/20 13:33, 1F
感謝w大，你說的沒錯
→
01/20 13:34, , 2F
題目是說worst case吧@@?
01/20 13:34, 2F
→
01/20 13:36, , 3F
哦哦哦哦 我看錯了
01/20 13:36, 3F
推
01/20 13:37, , 4F
5.(b)是32噢
01/20 13:37, 4F
我找到32了，剛剛少畫一條3 感謝HUT大~ ※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 13:48:09
→
01/20 14:18, , 5F
2.a) n^log_8 3, n^1/2=n^log_8 √8,√8小於3
01/20 14:18, 5F
感謝A大指正，如你所說的沒錯
→
01/20 14:24, , 6F
3.c最後一格是11吧
01/20 14:24, 6F
我打錯了QQQ~~~ 感謝 ※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 14:27:46 ※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 14:33:19
→
01/20 15:34, , 7F
第4.b)我覺得應該是要求n個node可以形成幾種相異BST?
01/20 15:34, 7F
沒錯，我看錯題目意思了@_@
推
01/20 15:34, , 8F
4b我有不同的答案：
01/20 15:34, 8F
→
01/20 15:35, , 9F
num_BST(i,j){
01/20 15:35, 9F
→
01/20 15:35, , 10F
if i < j
01/20 15:35, 10F
→
01/20 15:35, , 11F
count=0
01/20 15:35, 11F
→
01/20 15:36, , 12F
for x = i to j
01/20 15:36, 12F
→
01/20 15:37, , 13F
count = count + num_BST(i,x-1)*num_BST(x+1,j)
01/20 15:37, 13F
→
01/20 15:37, , 14F
return count
01/20 15:37, 14F
→
01/20 15:37, , 15F
else
01/20 15:37, 15F
※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 15:37:56
→
01/20 15:37, , 16F
return 1
01/20 15:37, 16F
→
01/20 15:37, , 17F
}
01/20 15:37, 17F
→
01/20 15:38, , 18F
呼叫方式:num_BST(1,n)
01/20 15:38, 18F
這題思考一下應該是使用Random Binary Search tree 將值隨機插入 最高達 n! 排列組合 ※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 15:45:36
推
01/20 15:51, , 19F
是說實際打成程式碼之後num_BST會回傳Catalan number
01/20 15:51, 19F
→
01/20 15:51, , 20F
也許題目就是想算Catalan number ?
01/20 15:51, 20F
→
01/20 15:54, , 21F
結果是卡特蘭數沒錯 ，只能朝這個方向著手了QQ
01/20 15:54, 21F
推
01/22 15:06, , 22F
請問一下為何第一題d是O(n)而不是O(nlogn)
01/22 15:06, 22F
→
01/22 16:15, , 23F
01/22 16:15, 23F
推
01/23 17:17, , 24F
第六題是不是要設計一個potential 可是你沒設計
01/23 17:17, 24F
→
01/23 17:17, , 25F
就蹦出來了
01/23 17:17, 25F
沒有要設計呀@@ 解釋它怎麼運作就行了
推
01/23 17:23, , 26F
4.b 算出來的總數回傳是不是catalan number才對?
01/23 17:23, 26F
是，但我之前懶得改QQQ
→
01/23 17:24, , 27F
4.a 他是不是只問bst性質 可是看到你有寫color
01/23 17:24, 27F
→
01/23 17:26, , 28F
可能是小弟我頭昏了 再麻煩指點一下
01/23 17:26, 28F
題目是指要求找到最小AVL tree 的node 數且滿足 紅黑樹的性質 ※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 20:47:45 ※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 20:59:32
推
01/23 21:25, , 29F
沒設計出potential function 怎麼能運作 我覺得怪怪的
01/23 21:25, 29F
你可能需要看一下 amorized 的章節，當題目已經給 Φ 的時候，我已經認定 出題教授很明白地讓我們用該符號去做potential function 的運算來表達 為何insertion & Extraction 為 amortized O(logn) & O(1) 就行了 不用再去額外設計potential function ，因為Φ本身就是potential function 至於內部細節 Φ = i log(i) 等之類的可以被預減 因此被我省略
→
01/23 21:38, , 30F
4.a.就只有問bst性質而已吧
01/23 21:38, 30F
首先，AVL 與 RB tree 是不同的，它並非詢問 RB tree 的 balance Draw a smallest AVL tree of height 3 (number of edges from the root to the leaves ) 畫一顆高度為3的最小 AVL tree (高度判定為: 從root到葉的邊數) and then label its node with B(black) or R(red) 且標註它的 黑 與 紅 node to make it satisfy the RB-tree property. 來滿足它的紅黑樹特性 這是我對於這題敘述的理解，有錯可以指正一下 感謝 <(_ _)> ※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 21:58:25
→
01/23 22:00, , 31F
你說到的可能是4.c我說的是4.a喔 不是畫圖那題
01/23 22:00, 31F
原來是在指這題的問題 QQ .. 抱歉 我還認真回一串 我這題使用color 的想法是避免重複取到同一個 node
→
01/23 22:01, , 32F
potential function是cormen的習題
01/23 22:01, 32F
我知道這題是cormen 的習題~ ※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:05:00
→
01/23 22:05, , 33F
01/23 22:05, 33F
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:08:05
→
01/23 22:07, , 34F
我在看cormen的時候 他每一個potentialfunction 都有
01/23 22:07, 34F
→
01/23 22:08, , 35F
先定義出來 不然無法算每個operation的cost才對呀
01/23 22:08, 35F
→
01/23 22:09, , 36F
就像是fib heap他如果沒有想到那個設計也無法O(1)吧
01/23 22:09, 36F
如as大所說它會先定義c' = c_i + Φ(D_i)-Φ(D) 而上面 po 的這一篇我之前也有反覆參考過 我上述的寫法的確投機了一點，只不過那是我在當下遇到這題的解法 抱歉<(_ _)> ※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:25:04
→
01/23 22:33, , 37F
我是覺得沒先定義是什麼可能會被扣分 提醒一下 ^^
01/23 22:33, 37F
好的，我會這麼寫就代表在考這張考卷的時候就有覺悟了 XDD 還是感謝AS大 的提醒 另外4.a as大有其他的看法嗎?? ※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:34:59
→
01/23 22:41, , 38F
說真的我很廢 我寫不出來 但我有找到別人寫的 哈
01/23 22:41, 38F
→
01/23 22:41, , 39F
01/23 22:41, 39F
→
01/23 22:42, , 40F
我不確定你的code對不對 但是你可以去leetcode驗證
01/23 22:42, 40F
→
01/23 22:43, , 41F
01/23 22:43, 41F
→
01/23 23:07, , 42F
想偷問一下ken大 你怎麼在這畫出binary tee的
01/23 23:07, 42F
→
01/23 23:07, , 43F
還有一些很怪的數學符號
01/23 23:07, 43F
綜估時間來說算是倉促的，所以有些都是我自己假設 但到時候考試我還是會將假設的東西寫清楚，像是題目一定要給我們一個 input，以及一個 G(V,E) 且既然題目是要我們求BST的性質，那一定得給我們BT 否則我們也可以自行在code 內判定 是否有 adj[V].color = white 的 node 點 是否有超過 兩個 (不包含 V.parent.color = black ) 寫這種 code 不太可能真的拿去測試 XDD , 除非照著官方的演算法，自己想的 code 絕對 bug 一堆 且像是我 code 內的連續 < 這在 C 等語言上面光是 compiler 就不會過了 只能盡可能的表達自己的想法在 code 上~ 有哪些符號不懂得嗎@@? != 是不等於 ※ 編輯: ken52011219 (36.224.18.42), 01/24/2017 09:31:28
推
01/24 09:49, , 44F
可以詳細下2c嗎？
01/24 09:49, 44F
沒問題 https://goo.gl/FgtW6R ※ 編輯: ken52011219 (36.224.18.42), 01/24/2017 10:00:50
推
01/24 10:01, , 45F
感謝ken大討論這麼多 想問2能不能直接套master theor
01/24 10:01, 45F
→
01/24 10:01, , 46F
em
01/24 10:01, 46F
→
01/24 10:03, , 47F
另外我上面想問的是你怎麼在ptt上畫出一棵樹的 還有
01/24 10:03, 47F
→
01/24 10:03, , 48F
打出那些數學符號
01/24 10:03, 48F
https://goo.gl/vVewm6 請詳閱~ 我是從這裡學的 關於根號 我想應該只能用 subsutation (其實我大部分都是用這個方法去解) 另外符號的部分，你看你PTT (PC版) 上面那排工具列，有一個鎖的圖像 它左邊就是 符號表了 ※ 編輯: ken52011219 (36.224.18.42), 01/24/2017 10:14:06
推
01/24 10:23, , 49F
感謝詳細(消化ing) 祝考試時鉛筆芯不斷 原子筆不斷水
01/24 10:23, 49F
→
01/24 10:45, , 50F
根號系列應該是用n=2^2^k代入？
01/24 10:45, 50F
→
01/24 10:46, , 51F
強化板master theorem的case 2&3，應該是log_b(a)?
01/24 10:46, 51F
→
01/24 10:47, , 52F
不過應該不會有人搞錯這個部份就是了，其他都很實用
01/24 10:47, 52F
推
01/25 00:14, , 53F
第2大題的C小題的M的次方應該為1.5
01/25 00:14, 53F
→
01/25 02:28, , 54F
上面忽略，爬文才發現我講錯......
01/25 02:28, 54F
推
01/25 12:17, , 55F
可以請問第三題A 的題目敘述 第二段對答案有影響嗎，另
01/25 12:17, 55F
不會有差別，除非為insertion
→
01/25 12:17, , 56F
外想請問slot and bucket的差別 ，從第三題A來看 如果他
01/25 12:17, 56F
→
01/25 12:17, , 57F
所為slot 就是bucket的話，那用AVL tree儲存並搜尋的時
01/25 12:17, 57F
→
01/25 12:17, , 58F
間複雜度，就是每個SLOT平均會有(n/m)個資料，再套用AVL
01/25 12:17, 58F
→
01/25 12:17, , 59F
TREE的的搜尋時間log(n)，所以最後答案就是log(1+log(n/
01/25 12:17, 59F
→
01/25 12:17, , 60F
m))這樣想是對的嗎
01/25 12:17, 60F
ii another hash table H' is used to hash all the elements with the same hash value in H.Collisions in H' are resolved recursively. Assume that each H' also has m slot 這段敘述在這裡最大的功用是 「 避免有 unstable 」的情況發生，若有相同 的 Value 時，它必須能夠使 AVL tree 能正確地把 「最後到達」 的 相同值 歸類在 AVL tree 的相同值的右邊 ( PS: 這樣講好像有點 bug ，當該相同值多到又重新繞回來原相同值的前後面 好像就悲劇了QQ 感覺比較像 1 ..... m ┌─┬─┬─┐ │　│..│　│ └┬┴─┴─┘ ○ 1 ...... m ╱ ╲ ┌─┬─┬─┐ ○ ｘ┤ｘ│..│x'│ └─┴─┴─┘ ) 基本上來說，我是在這邊假設它為 linear probing 只不過不影響它的時間複雜 度 為 worst case O(m) 但這邊要注意的是，此為insertion的情況。而題目是要search，並非insert 以要 search 某值 的情況下， 某值先經過 mod 後找到其 slot( or bucket)值 後藉著 (i)chaining (time Complexity: O(1)) 找到對應的AVL tree 注意的是，題目有給「uniform hashing」，代表意義為每個 slot(or bucket) 的值皆為平均相等，意思是 AVL tree 中 共有 n/m 個 node 接著search AVL tree 找到該值，只需利用該值與node上的值判斷大小即可 直到該AVL tree 的 leaf 為 nil ，則回傳未找到 (time Complexity: O(log(n/m)) 相乘即為所求 ※ 編輯: ken52011219 (36.224.17.160), 01/25/2017 13:19:54 ※ 編輯: ken52011219 (36.224.17.160), 01/25/2017 13:25:00
推
01/25 14:32, , 61F
因為我在其他講義看過bucket and slot 不是一樣的東西
01/25 14:32, 61F
→
01/25 14:32, , 62F
而是類似二維的儲存資料空間 一個TABLE下有N個BUCKET 每
01/25 14:32, 62F
→
01/25 14:32, , 63F
個BUCKET下又有M個SLOT，類似這種敘述，所以題目是指有M
01/25 14:32, 63F
→
01/25 14:32, , 64F
個BUCKET嗎
01/25 14:32, 64F
剛剛那個是水球嗎@_@ 我不太會用 嚴格來說slot 的確與 bucket 不太一樣，但大部分來說是指同一個分類方法 slot 專指 「欄」,一種類似 entry 的概念，而 這裡 bucket 指的是hash 對於 index 的區別 我是覺得大部分的時間是一樣的啦@@~，除非題目有特別敘述說其為不一樣才會 考慮有其他的闡述方法 因為wiki上面 是寫「bucket or slot」 皆可
→
02/03 10:19, , 65F
4.a的作法?
02/03 10:19, 65F
→
02/03 10:21, , 66F
看到有人回一篇了XD
02/03 10:21, 66F
※ 編輯: ken52011219 (36.224.3.46), 02/05/2017 17:07:30
推
01/14 20:18, , 67F
RBTree的leave不是一定要是黑的?
01/14 20:18, 67F
→
01/14 20:22, , 68F
nil不算高度@@
01/14 20:22, 68F
‣ 更多 ken52011219 的文章
文章代碼(AID): #1OWQ0wGr (Grad-ProbAsk)
‣ 更多 ken52011219 的文章
文章代碼(AID): #1OWQ0wGr (Grad-ProbAsk)