2023年山東省資料總結要領

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

2、假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，若存在，則以頂點序列的方式輸出該迴路（找到一條即可）。（注：圖中不存在頂點到自己的弧）

有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完；已訪問且其鄰接點已訪問完。

下面用0，1，2表示這三種狀態。前面已提到，若dfs（v）結束前出現頂點u到v的回邊，則圖中必有包含頂點v和u的迴路。對應程式中v的狀態為1，而u是正訪問的頂點，若我們找出u的下一鄰接點的狀態為1，就可以輸出迴路了。

void print(int v,int start ) //輸出從頂點start開始的迴路。

//if

}//print

void dfs(int v)

//if

else

visited[v]=2;

}//dfs

void find_cycle() //判斷是否有迴路，有則輸出鄰接矩陣。visited陣列為全域性變數。

//find_cycle

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); }//是二部圖

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

4、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數pre（初值為null）和全域性變數flag，初值為true。若非二叉排序樹，則置flag為false。

#define true 1

#define false 0

typedef struct node

*btree;

void judgebst（btree t,int flag）

// 判斷二叉樹是否是二叉排序樹，本演算法結束後，在呼叫程式中由flag得出結論。

//不是完全二叉樹

judgebst （t->rlink,flag）；// 中序遍歷右子樹

}//judgebst演算法結束