1、有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表(用陣列表示)進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某乙個記錄，統計出的計數值為c，那麼，這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法；
(3) (4分)對於有n個記錄的表，關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什麼?
2、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是「區域性根」。確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標r，指向層次序列待處理元素。演算法中先處理根結點，將根結點和左右子女的資訊入佇列。
然後，在佇列不空的條件下，迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下：
typedef struct
qnode;
bitree creat(datatype in,level,int n)
//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數
qnode s,qq是元素為qnode型別的佇列，容量足夠大
init(q); int r=0; //r是層次序列指標，指向當前待處理的結點
bitree p=(bitree)malloc(sizeof(binode生成根結點
p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料
for (i=0; iif (in[i]==level[0]) break;
if (i==0) //根結點無左子樹，遍歷序列的1—n-1是右子樹
else if (i==n-1) //根結點無右子樹，遍歷序列的1—n-1是左子樹
else //根結點有左子樹和右子樹
while (!empty(q)) //當佇列不空，進行迴圈，構造二叉樹的左右子樹
else if (i==s.h)
else
}//結束while (!empty(q))
return(p);
}//演算法結束
3、給定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演算法構造其最小生成樹（每選取一條邊畫乙個圖）。
2023年山東省資料總結大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。void translation f...
2023年山東省資料總結大綱
1 題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。void translation f...
2023年山東省資料總結大綱
1 給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。20分 2 由...