1、給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。
2、約瑟夫環問題（josephus問題）是指編號為1、2、，n的n（n>0）個人按順時針方向圍坐成一圈，現從第s個人開始按順時針方向報數，數到第m個人出列，然後從出列的下乙個人重新開始報數，數到第m的人又出列，，如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法，模擬此過程。
3、若第n件物品能放入揹包，則問題變為能否再從n-1件物品中選出若干件放入揹包（這時揹包可放入物品的重量變為s-w[n]）。若第n件物品不能放入揹包，則考慮從n-1件物品選若干件放入揹包（這時揹包可放入物品仍為s）。若最終s=0,則有一解；否則，若s<0或雖然s>0但物品數n<1,則無解。
（1）s-w[n],n-1 //knap(s-w[n],n-1)=true（2）s,n-1knap←knap(s,n-1)
4、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。當n=1時，只有乙個根結點，由中序序列和後序序列可以確定這棵二叉樹。設當n=m-1時結論成立，現證明當n=m時結論成立。
設中序序列為s1，s2，，sm,後序序列是p1,p2,，pm。因後序序列最後乙個元素pm是根，則在中序序列中可找到與pm相等的結點（設二叉樹中各結點互不相同）si(1≤i≤m)，因中序序列是由中序遍歷而得，所以si是根結點，s1，s2，，si-1是左子樹的中序序列，而si+1,si+2,,sm是右子樹的中序序列。
若i=1，則s1是根，這時二叉樹的左子樹為空，右子樹的結點數是m-1,則和可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則sm是根，這時二叉樹的右子樹為空，左子樹的結點數是m-1，則和唯一確定左子樹，從而也確定了二叉樹。
最後，當15、對二叉樹的某層上的結點進行運算，採用佇列結構按層次遍歷最適宜。
int leafklevel(bitree bt, int k) //求二叉樹bt的第k(k>1)層上葉子結點個數 //last移到指向下層最右一元素if(level>k) return (leaf層數大於k後退出執行
}//while }//結束leafklevel
6、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a，取出a[i]（0<=i//由含n個資料的陣列a生成迴圈鍊錶，要求鍊錶有序並且無值重複結點 //查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);}演算法結束7、設t是給定的一棵二叉樹，下面的遞迴程式count(t)用於求得:二叉樹t中具有非空的左,右兩個兒子的結點個數n2;只有非空左兒子的個數nl;只有非空右兒子的結點個數nr和葉子結點個數n0。n2、nl、nr、n0都是全域性量，且在呼叫count(t)之前都置為 struct node
node;int n2,nl,nr,n0;void count(node *t)
26.樹的先序非遞迴演算法。void example(b)btree *b;
if (p->lchild!=null)(3)___; (4)__;}}}}8、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈，去掉圈上權最大的邊」，反覆執行這一步驟，直到沒有圈為止。
請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法，並用程式實現你所給出的演算法。注：圈就是迴路。
9、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈，去掉圈上權最大的邊」，反覆執行這一步驟，直到沒有圈為止。請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法，並用程式實現你所給出的演算法。
注：圈就是迴路。
10、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。
void translation（float *matrix，int n）
//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。
sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.}//if}//for i
free(p); //釋放p陣列.}// translation
[演算法分析]演算法中使用選擇法排序,比較次數較多,但資料交換(移動)較少.若用其它排序方法,雖可減少比較次數,但資料移動會增多.演算法時間複雜度為o(n2).
11、請設計乙個演算法，要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表，表頭指標為head。二叉樹按二叉鍊錶方式儲存，鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。
12、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）
（1）下面所示的序列中哪些是合法的？
a. ioiioioo b. iooioiio c. iiioioio d. iiiooioo
（2）通過對（1）的分析，寫出乙個演算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維陣列中）。
13、設從鍵盤輸入一整數的序列：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（014、4、void linklist_reverse(linklist &l)
//鍊錶的就地逆置;為簡化演算法,假設表長大於2
q->next=p;s->next=q;l->next=s;}//linklist_reverse
15、將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。
int bpgraph (adjmatrix g)
//判斷以鄰接矩陣表示的圖g是否是二部圖。
//初始化，各頂點未確定屬於那個集合
q[1]=1; r=1; s[1]=1;//頂點1放入集合s1while(f //鄰接點入佇列else if (s[j]==s[v]) return(0);} //非二部圖}//if (!visited[v])}//while
return(1); }//是二部圖
[演算法討論]題目給的是連通無向圖，若非連通，則演算法要修改。
廣西壯族自治區概況
一 概況 廣西壯族自治區簡稱桂，地處祖國南疆，位於東經104 26 112 04 北緯20 54 26 24 之間，北回歸線橫貫全區中部。廣西區位優越，南臨北部灣，面向東南亞，西南與越南毗鄰，東鄰粵 港 澳，北連華中，背靠大西南。是西南地區最便捷的出海通道，也是中國西部資源型經濟與東南開放型經濟的結...
2023年廣西壯族自治區資料總結加強
1 給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。20分 2 題...
2023年廣西壯族自治區資料總結高階
1 設有兩個集合a和集合b，要求設計生成集合c a b的演算法，其中集合a b和c用鏈式儲存結構表示。typedef struct node lklist void intersection lklist ha,lklist hb,lklist hc 2 將頂點放在兩個集合v1和v2。對每個頂點，檢...