1、本題應使用深度優先遍歷，從主調函式進入dfs(v)時，開始記數，若退出dfs()前，已訪問完有向圖的全部頂點（設為n個），則有向圖有根，v為根結點。將n個頂點從1到n編號，各呼叫一次dfs()過程，就可以求出全部的根結點。題中有向圖的鄰接表儲存結構、記頂點個數的變數、以及訪問標記陣列等均設計為全域性變數。
建立有向圖g的鄰接表儲存結構參見上面第2題，這裡只給出判斷有向圖是否有根的演算法。
int num=0， visited=0 //num記訪問頂點個數，訪問陣列visited初始化。
const n=使用者定義的頂點數;
adjlist g用鄰接表作儲存結構的有向圖g。
void dfs(v)
//if
p=g[v].firstarc;
while (p)
//while
visited[v]=0; num--; //恢復頂點v
}//dfs
void judgeroot()
//判斷有向圖是否有根，有根則輸出之。
}// judgeroot
演算法中列印根時，輸出頂點在鄰接表中的序號（下標），若要輸出頂點資訊，可使用g[i].vertex。
2、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。（20分）
3、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。
2023年江西省資料總結加強
1 設t是一棵滿二叉樹，編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。2 設一棵二叉樹的結點結構為 llink,info,rlink root為指向該二叉樹根結點的指標，p 和q分別為指向該二叉樹中任意兩個結點的指標，試編寫一演算法ancestor root，p,q,r 該演算法找到p和...
2023年江西省資料總結入門
1 矩陣中元素按行和按列都已排序，要求查詢時間複雜度為o m n 因此不能採用常規的二層迴圈的查詢。可以先從右上角 i a,j d 元素與x比較，只有三種情況 一是a i,j x，這情況下向j 小的方向繼續查詢 二是a i,j void search datatype a int a,b,c,d,d...
2023年江西省資料總結加強
1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是 區域性根 確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為 左根右 三部分。若左 右子樹均有，則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有...