1、給定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演算法構造其最小生成樹（每選取一條邊畫乙個圖）。
2、編寫乙個過程，對乙個n×n矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。
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、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
29. ① 試找出滿足下列條件的二叉樹
1）先序序列與後序序列相同 2）中序序列與後序序列相同
3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同
5、程式設計實現單鏈表的就地逆置。
23．在陣列 a[1..n]中有n個資料，試建立乙個帶有頭結點的迴圈鍊錶，頭指標為h，要求鏈中資料從小到大排列，重複的資料在鏈中只儲存乙個.
6、有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表(用陣列表示)進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某乙個記錄，統計出的計數值為c，那麼，這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法；
(3) (4分)對於有n個記錄的表，關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什麼?
7、 連通圖的生成樹包括圖中的全部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()是測試圖是否連通的函式，可用圖的遍歷實現，
8、設從鍵盤輸入一整數的序列：a1, a2, a3，…，an,試編寫演算法實現：用棧結構儲存輸入的整數，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數並出棧。
演算法應對異常情況（入棧滿等）給出相應的資訊。
設有乙個揹包可以放入的物品重量為s，現有n件物品，重量分別為w1，w2，...，wn。問能否從這n件物品中選擇若干件放入揹包，使得放入的重量之和正好是s。
設布林函式knap(s，n)表示揹包問題的解，wi(i=1,2,...，n)均為正整數，並已順序儲存地在陣列w中。請在下列演算法的下劃線處填空，使其正確求解揹包問題。
knap(s，n)
若s=0
則knap←true
否則若（s<0）或(s>0且n<1)
則knap←false
否則若knap(1) , _=true
則print(w[n])；knap ←true
否則 knap←knap(2
設有乙個順序棧s，元素s1, s2, s3, s4, s5, s6依次進棧，如果6個元素的出棧順序為s2, s3, s4, s6, s5, s1，則順序棧的容量至少應為多少？畫出具體進棧、出棧過程。
假定採用帶頭結點的單鏈表儲存單詞，當兩個單詞有相同的字尾時，則可共享相同的字尾儲存空間。例如：
設str1和str2是分別指向兩個單詞的頭結點，請設計乙個盡可能的高效演算法，找出兩個單詞共同字尾的起始位置，分析演算法時間複雜度。
將n(n>1)個整數存放到一維陣列r中。設計乙個盡可能高效（時間、空間）的算
法，將r中儲存的序列迴圈左移p（09、約瑟夫環問題（josephus問題）是指編號為1、2、…，n的n（n>0）個人按順時針方向圍坐成一圈，現從第s個人開始按順時針方向報數，數到第m個人出列，然後從出列的下乙個人重新開始報數，數到第m的人又出列，…，如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法，模擬此過程。
#include<>
typedef int datatype;
typedef struct node
listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
while(k1->next!=k1) /*當迴圈鍊錶中的結點個數大於1時*/
pre->next=p->next; /*輸出該結點，並刪除該結點*/
printf("%4d",p->data);
free(p);
k1=pre->next新的報數起點*/
} printf("%4d",k1->data); /*輸出最後乙個結點*/
free(k1);
}main()
{linklist head,p,r;
2023年山東省資料總結高階
1 因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。void longestpath bitree bt 求二叉樹中的第一條最長...
2023年山東省資料總結高階
1 因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。void longestpath bitree bt 求二叉樹中的第一條最長...
2023年山東省資料總結高階
r i x 3 兩棵空二叉樹或僅有根結點的二叉樹相似 對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。int similar bitree p,q 判斷二叉樹p和q是否相似 結束similar 4 在有向圖g中，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功...