2023年內蒙古自治區資料總結大綱

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

注：圈就是迴路。

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、(1)p->rchild (2)p->lchild (3)p->lchild (4)addq(q,p->lchild) (5)addq(q,p->rchild)

25. (1)t->rchild!=null (2)t->rchild!=null (3)n0++ (4)count(t->lchild) (5)count(t->rchild)

26. .(1)top2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild

27. (1)*ppos // 根結點（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

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

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

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

5、將頂點放在兩個集合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); }//是二部圖

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

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

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