2023年吉林省資料總結大綱

1、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。

void translation（float *matrix，int n）

//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。

//for i

for(i=0; i

sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.

}//if

}//for i

free(p); //釋放p陣列.

}// translation

[演算法分析] 演算法中使用選擇法排序,比較次數較多,但資料交換(移動)較少.若用其它排序方法,雖可減少比較次數,但資料移動會增多.演算法時間複雜度為o(n2).

2、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈，去掉圈上權最大的邊」，反覆執行這一步驟，直到沒有圈為止。請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法，並用程式實現你所給出的演算法。

注：圈就是迴路。

3、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。

4、設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹並給出構造過程。