2023年廣東省資料總結摘要

1、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。

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

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).

3、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。20分

void hospital(adjmatrix w,int n)

//在以鄰接帶權矩陣表示的n個村莊中，求醫院建在何處，使離醫院最遠的村莊到醫院的路徑最短。

//在最長路徑中，取最短的一條。m記最長路徑，k記出發頂點的下標。

printf(「醫院應建在%d村莊，到醫院距離為%d\n」,i,m);

}//for

}//演算法結束

對以上例項模擬的過程略。各行中最大數依次是9，9，6，7，9，9。這幾個最大數中最小者為6，故醫院應建在第三個村莊中,離醫院最遠的村莊到醫院的距離是6。

1、對圖1所示的連通網g，請用prim演算法構造其最小生成樹（每選取一條邊畫乙個圖）。

4、氣泡排序演算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的氣泡排序演算法。

48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）