→ cansister:上篇有人問7(a)感覺是true我回答一下，因為如果unique 03/18 14:43
→ cansister:heaviest edge是圖中的bridge時，一定會被spanning tree 03/18 14:45
→ cansister:收集到的，所以還是可能會在MST中的。 03/18 14:45
推 SONGya168:格式請先修正唷 03/18 15:21
※ 引述《imnewlegend (努力準備考試)》之銘言：
http://140.115.130.224:8080/~arhui/cexamn/exam/EC02_97_01.pdf
1.
: if (find[i]= =find[j])
: 有cycle
: int find(int i)
: {
: for(;parent[i]>=0;i=parent[i]);
: return i;
: } 不是很懂題目的2個operation是什麼
我認為的答案是
if(find[u]!=find[v])
union(u,v);
這應該是要考disjiont吧 所以他要兩個operation應該是union和find
只是我不瞭解他要我們怎麼回答
2.
: ACEB
我的答案是ACEDB
3.
swap(root->left);
swap(root->right);
temp=(root->left);
root->left=root->right;
root->right=temp;
4.
(a)yes
(b)path=5 (過程使用Dijkstra's Algorithm)
其path為ABEFCD
: (c)
: dfs(A) ABCDHEF
: forward edge B->E
: back E->A ; F->C ; F->H
: cross A->G ; G->H ; G->E
dfs(A) ABCDHEFG
cross 我覺得(A,G)應該是true edge吧
5.
利用divide and conqure
對於矩陣中的每一行使用下列方法計算
對n/2和(n/2)+1比較
1.相異 {count=n/2;}
2.相同 a.都是O →對右半繼續上述的判斷
b.都是X →對左半繼續上述的判斷
所以時間為O(logn)
總時間O(logn)*n=O(nlogn)
6.
a. 用for跑一遍配對就行了
b. 不會請大大分享
: 7. FTTF
為什麼第四小題是F？？ 可以幫忙解釋一下嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.129.184