2023年新疆維吾爾自治區資料總結入門

1、設t是一棵滿二叉樹，編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。

2、在有向圖g中，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功能：

（1）．建立有向圖g的鄰接表儲存結構；

（2）．判斷有向圖g是否有根，若有，則列印出所有根結點的值。

3、 將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。

int bpgraph (adjmatrix g)

判斷以鄰接矩陣表示的圖g是否是二部圖。

//初始化，各頂點未確定屬於那個集合

q[1]=1; r=1; s[1]=1;//頂點1放入集合s1

while(f //鄰接點入佇列

else if (s[j]==s[v]) return(0);} //非二部圖

}//if (!visited[v])

}//while

return(1); }//是二部圖

[演算法討論] 題目給的是連通無向圖，若非連通，則演算法要修改。

2023年新疆維吾爾自治區資料總結綱要

1 連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n 1條邊，最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序，然後從大到小將邊刪除。每刪除一條當前權值最大的邊後，就去測試圖是否仍連通，若不再連通，則將該邊恢復。若仍連通，繼續向下刪 直到剩n 1條邊為止。void spnt...

2023年新疆維吾爾自治區資料總結要領

1 陣列a和b的元素分別有序，欲將兩陣列合併到c陣列，使c仍有序，應將a和b拷貝到c，只要注意a和b陣列指標的使用，以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。void union int a,b,c,m,n 整型陣列a和b各有m和n個元素，前者遞增有序，後者遞減有序，本演算法將a...

2023年新疆維吾爾自治區資料總結入門

1 設有兩個集合a和集合b，要求設計生成集合c a b的演算法，其中集合a b和c用鏈式儲存結構表示。typedef struct node lklist void intersection lklist ha,lklist hb,lklist hc 2 二部圖 bipartite graph g ...