作者tinhanho (アーニャ寶)
看板Grad-ProbAsk
標題[理工] 109 中央 資演選擇對答案
時間Thu Jan 12 23:20:32 2023
板上好像沒有 或者是我找不到QQ
題目
https://rapid.lib.ncu.edu.tw/cexamn/exam/EC02_109_01.pdf
複選
1. ABD
2. C
3. A
4. CD
ABCD
5. A
6. C
是非
7. B
8. B
9. B
10. A
11. B
申論題不太會寫qq
第1題
想法是一個從頂端push 一個從底部push
第2題
▼錯的
for(j=1;j<=n;j++)
swap...;
perm(list[i], i+1, n);
swap...;
▼正確
for(j=i;j<=n;j++)
swap...;
perm(list, i+1, n);
swap...;
第3題
a Kruskal, time:O(ElogE)
b 不會寫 google的->
https://web.ntnu.edu.tw/~algo/SpanningTree2.html
第4題
看板上有一篇說用DP做
但我應該還是寫不出來
自己寫的答案 有錯煩請指正 感激不盡 祝大家金榜題名
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.161.235 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1673536834.A.E8E.html
※ 編輯: tinhanho (36.224.161.235 臺灣), 01/12/2023 23:21:15
1F：→ ping990579: 4.ABCD 01/13 10:13
好像做錯了 ABCD沒錯 感謝~
2F：→ ping990579: 兩個stack 一個由上往下另一個反之 判斷一下push時top 01/13 10:15
3F：→ ping990579: 是否一樣為滿 01/13 10:15
4F：→ ping990579: 第三題我想法是kruskal先找一個mst，然後找剩下的邊 01/13 10:17
5F：→ ping990579: 最小的加入mst必會產生cycle,在cyle內閃掉最小邊得到 01/13 10:18
6F：→ ping990579: 次小mst 01/13 10:18
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 10:55:24
7F：→ ping990579: 我不是用dfs求欸我用定義 01/13 10:58
8F：→ ping990579: 在圖論中，由一個有向無環圖的頂點組成的序列 01/13 10:58
9F：→ ping990579: 若且唯若滿足下列條件時，才能稱為該圖的一個拓撲排序 01/13 10:59
10F：→ ping990579: 序列中包含每個頂點，且每個頂點只出現一次； 01/13 10:59
11F：→ ping990579: 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑 01/13 11:00
我用洪毅的indegree來寫 後來有寫出來~ 感謝
圖論的部分不太熟@@ 圖論真的蠻難的
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 11:02:18
12F：→ ping990579: 第四題 想法大概是排序s成上升序列 用一個二維陣列c( 01/13 11:19
13F：→ ping990579: i,j)表示前i個和等於j的方法數 判斷i與j大小關係定義 01/13 11:19
14F：→ ping990579: 遞迴 01/13 11:19
16F：→ ping990579: 感覺有點像背包那樣吧 有錯請指教 01/13 11:20
17F：→ ping990579: 不對 是元素個數才對 01/13 11:22
18F：→ ping990579: 上面是錯的 01/13 11:23
20F：→ ping990579: T(i,j,a)才對 排序多餘的 01/13 12:02
21F：→ ping990579: 拍謝Mst那題應該沒辦法是次小，我查geek上https://im 01/13 13:06
22F：→ ping990579: gur.com/ci9D3hu 01/13 13:06
23F：推 jim881115: 申論2.填空我寫的是: 01/13 13:53
24F：→ jim881115: for(j=i;j<n;j++) 01/13 13:53
25F：→ jim881115: swap 01/13 13:53
26F：→ jim881115: perm(list, i+1, n); 01/13 13:53
27F：→ jim881115: swap 01/13 13:53
你是對的 但應該是<=n
https://imgur.com/6KbVUrX
寫題目寫到有點累 摸一下程式
題外話 swap的地方搞有點久 我的指標還是一樣爛 qqqqqq
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 22:34:18