2023年澳門特別行政區資料總結大綱

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

若仍連通，繼續向下刪；直到剩n-1條邊為止。

void spntree (adjlist g)

//用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。

node; //設頂點資訊就是頂點編號，權是整型數

node edge;

scanf( "%d%d",&e,&n) ; //輸入邊數和頂點數。

for (i=1;i<=e;i輸入e條邊：頂點，權值。

scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

for (i=2;i<=e;i++) //按邊上的權值大小，對邊進行逆序排序。

//for

k=1; eg=e;

while (eg>=n破圈，直到邊數e=n-1.

if (connect(k)) //刪除第k條邊若仍連通。

edge[k].w=0; eg--; }//測試下一條邊edge[k]，權值置0表示該邊被刪除

k++; //下條邊

while

}//演算法結束。

connect()是測試圖是否連通的函式，可用圖的遍歷實現，

2、我們用l代表最長平台的長度，用k指示最長平台在陣列b中的起始位置（下標）。用j記住區域性平台的起始位置，用i指示掃瞄b陣列的下標，i從0開始，依次和後續元素比較，若區域性平台長度（i-j）大於l時，則修改最長平台的長度k（l=i-j）和其在b中的起始位置（k=j），直到b陣列結束，l即為所求。

void platform (int b[ ], int n)

//求具有n個元素的整型陣列b中最長平台的長度。

//區域性最長平台

i++; j=i新平台起點

printf(「最長平台長度%d，在b陣列中起始下標為%d」，l，k)；

}// platform

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