[理工] 109 中央 資演選擇對答案

看板Grad-ProbAsk作者 (アーニャ寶)時間3年前 (2023/01/12 23:20), 3年前編輯推噓1(1推 0噓 26→)
留言27則, 2人參與, 3年前最新討論串1/1
板上好像沒有 或者是我找不到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://www.ptt.cc/bbs/Grad-ProbAsk/M.1673536834.A.E8E.html ※ 編輯: tinhanho (36.224.161.235 臺灣), 01/12/2023 23:21:15
→
01/13 10:13, 3年前 , 1F
4.ABCD
01/13 10:13, 1F
好像做錯了 ABCD沒錯 感謝~
→
01/13 10:15, 3年前 , 2F
兩個stack 一個由上往下另一個反之 判斷一下push時top
01/13 10:15, 2F
→
01/13 10:15, 3年前 , 3F
是否一樣為滿
01/13 10:15, 3F
→
01/13 10:17, 3年前 , 4F
第三題我想法是kruskal先找一個mst，然後找剩下的邊
01/13 10:17, 4F
→
01/13 10:18, 3年前 , 5F
最小的加入mst必會產生cycle,在cyle內閃掉最小邊得到
01/13 10:18, 5F
→
01/13 10:18, 3年前 , 6F
次小mst
01/13 10:18, 6F
※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 10:55:24
→
01/13 10:58, 3年前 , 7F
我不是用dfs求欸我用定義
01/13 10:58, 7F
→
01/13 10:58, 3年前 , 8F
在圖論中，由一個有向無環圖的頂點組成的序列
01/13 10:58, 8F
→
01/13 10:59, 3年前 , 9F
若且唯若滿足下列條件時，才能稱為該圖的一個拓撲排序
01/13 10:59, 9F
→
01/13 10:59, 3年前 , 10F
序列中包含每個頂點，且每個頂點只出現一次；
01/13 10:59, 10F
→
01/13 11:00, 3年前 , 11F
若A在序列中排在B的前面，則在圖中不存在從B到A的路徑
01/13 11:00, 11F
我用洪毅的indegree來寫 後來有寫出來~ 感謝 圖論的部分不太熟@@ 圖論真的蠻難的 ※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 11:02:18
→
01/13 11:19, 3年前 , 12F
第四題 想法大概是排序s成上升序列 用一個二維陣列c(
01/13 11:19, 12F
→
01/13 11:19, 3年前 , 13F
i,j)表示前i個和等於j的方法數 判斷i與j大小關係定義
01/13 11:19, 13F
→
01/13 11:19, 3年前 , 14F
遞迴
01/13 11:19, 14F
→
01/13 11:19, 3年前 , 15F
01/13 11:19, 15F
→
01/13 11:20, 3年前 , 16F
感覺有點像背包那樣吧 有錯請指教
01/13 11:20, 16F
→
01/13 11:22, 3年前 , 17F
不對 是元素個數才對
01/13 11:22, 17F
→
01/13 11:23, 3年前 , 18F
上面是錯的
01/13 11:23, 18F
→
01/13 11:48, 3年前 , 19F
01/13 11:48, 19F
→
01/13 12:02, 3年前 , 20F
T(i,j,a)才對 排序多餘的
01/13 12:02, 20F
→
01/13 13:06, 3年前 , 21F
拍謝Mst那題應該沒辦法是次小，我查geek上https://im
01/13 13:06, 21F
→
01/13 13:06, 3年前 , 22F
gur.com/ci9D3hu
01/13 13:06, 22F
推
01/13 13:53, 3年前 , 23F
申論2.填空我寫的是:
01/13 13:53, 23F
→
01/13 13:53, 3年前 , 24F
for(j=i;j<n;j++)
01/13 13:53, 24F
→
01/13 13:53, 3年前 , 25F
swap
01/13 13:53, 25F
→
01/13 13:53, 3年前 , 26F
perm(list, i+1, n);
01/13 13:53, 26F
→
01/13 13:53, 3年前 , 27F
swap
01/13 13:53, 27F
你是對的 但應該是<=n https://imgur.com/6KbVUrX
寫題目寫到有點累 摸一下程式 題外話 swap的地方搞有點久 我的指標還是一樣爛 qqqqqq ※ 編輯: tinhanho (36.224.128.72 臺灣), 01/13/2023 22:34:18
‣ 更多 tinhanho 的文章
文章代碼(AID): #1Zm2L2wE (Grad-ProbAsk)