2023年山東省資料總結入門

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

2、給定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演算法構造其最小生成樹（每選取一條邊畫乙個圖）。

3、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）

（1）a和d是合法序列，b和c 是非法序列。

（2）設被判定的操作序列已存入一維陣列a中。

int judge(char a)

//判斷字元陣列a中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。

}i++; //不論a[i]是『i』或『o』，指標i均後移。}

if(j!=k)

else

}//演算法結束。

4、設一棵二叉樹的結點結構為 (llink,info,rlink),root為指向該二叉樹根結點的指標，p 和q分別為指向該二叉樹中任意兩個結點的指標，試編寫一演算法ancestor（root，p,q,r）,該演算法找到p和q的最近共同祖先結點r。