1、氣泡排序演算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的氣泡排序演算法。
48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）
2、我們用l代表最長平台的長度，用k指示最長平台在陣列b中的起始位置（下標）。用j記住區域性平台的起始位置，用i指示掃瞄b陣列的下標，i從0開始，依次和後續元素比較，若區域性平台長度（i-j）大於l時，則修改最長平台的長度k（l=i-j）和其在b中的起始位置（k=j），直到b陣列結束，l即為所求。
void platform (int b[ ], int n)
//求具有n個元素的整型陣列b中最長平台的長度。
//區域性最長平台
i++; j=i新平台起點
printf(「最長平台長度%d，在b陣列中起始下標為%d」，l，k)；
}// platform
3、在有向圖g中，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功能：
（1）．建立有向圖g的鄰接表儲存結構；
（2）．判斷有向圖g是否有根，若有，則列印出所有根結點的值。
4、假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，若存在，則以頂點序列的方式輸出該迴路（找到一條即可）。（注：圖中不存在頂點到自己的弧）
有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完；已訪問且其鄰接點已訪問完。
下面用0，1，2表示這三種狀態。前面已提到，若dfs（v）結束前出現頂點u到v的回邊，則圖中必有包含頂點v和u的迴路。對應程式中v的狀態為1，而u是正訪問的頂點，若我們找出u的下一鄰接點的狀態為1，就可以輸出迴路了。
void print(int v,int start ) //輸出從頂點start開始的迴路。
//if
void dfs(int v)
//if
else
visited[v]=2;
}//dfs
void find_cycle() //判斷是否有迴路，有則輸出鄰接矩陣。visited陣列為全域性變數。
//find_cycle
5、 將頂點放在兩個集合v1和v2。對每個頂點，檢查其
和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。
int bpgraph (adjmatrix g)
//判斷以鄰接矩陣表示的圖g是否是二部圖。
//初始化，各頂點未確定屬於那個集合
q[1]=1; r=1; s[1]=1;//頂點1放入集合s1
while(finfo=(1for((2rposllink=restore(ppos+1, (4)_______,k );
ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);
return ptr;
}postorder(tnode*ptr)
//結束similar
9、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
10、氣泡排序演算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的氣泡排序演算法。
48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）
11、假設以鄰接矩陣作為圖的儲存結構，編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路，若存在，則以頂點序列的方式輸出該迴路（找到一條即可）。（注：圖中不存在頂點到自己的弧）
有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。
下面用0，1，2表示這三種狀態。前面已提到，若dfs（v）結束前出現頂點u到v的回邊，則圖中必有包含頂點v和u的迴路。對應程式中v的狀態為1，而u是正訪問的頂點，若我們找出u的下一鄰接點的狀態為1，就可以輸出迴路了。
void print(int v,int start ) //輸出從頂點start開始的迴路。
//if
void dfs(int v)
//if
else
visited[v]=2;
}//dfs
void find_cycle() //判斷是否有迴路，有則輸出鄰接矩陣。visited陣列為全域性變數。
//find_cycle
12、二路插入排序是將待排關鍵字序列r[1..n]中關鍵字分二路分別按序插入到輔助向量d[1..n]前半部和後半部（注:
向量d可視為迴圈表），其原則為，先將r[l]賦給d[1]，再從r[2] 記錄開始分二路插入。編寫實現二路插入排序演算法。
13、4、 void linklist_reverse(linklist &l)
//鍊錶的就地逆置;為簡化演算法,假設表長大於2p=l->next;q=p->next;s=q->next;p->next=nullwhile(s->next)
q->next=p;s->next=q;l->next=s;
}//linklist_reverse
14、若第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)
15、二部圖（bipartite graph） g=（v，e）是乙個能將其結點集v分為兩不相交子集v 1和v2=v-v1的無向圖，使得：v1中的任何兩個結點在圖g中均不相鄰，v2中的任何結點在圖g中也均不相鄰。
（1）．請各舉乙個結點個數為5的二部圖和非二部圖的例子。
（2）．請用c或pascal編寫乙個函式bipartite判斷乙個連通無向圖g是否是二部圖，並分析程式的時間複雜度。設g用二維陣列a來表示，大小為n*n（n為結點個數）。請在程式中加必要的注釋。
若有必要可直接利用堆疊或佇列操作。【
16、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。
17、因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。
void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度
//沿左分枝向下
if(tag[top]==1) //當前結點的右分枝已遍歷
//保留當前最長路徑到l棧，記住最高棧頂指標，退棧
}else if(top>0) //沿右子分枝向下
}//while(p!=null||top>0)
}//結束longestpath
18、 連通圖的生成樹包括圖中的全部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++) //按邊上的權值大小，對邊進行逆序排序。
//測試下一條邊edge[k]，權值置0表示該邊被刪除
k++; //下條邊
}//while
}//演算法結束。
connect()是測試圖是否連通的函式，可用圖的遍歷實現，
19、設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。
20、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
21、4、 void linklist_reverse(linklist &l)
//鍊錶的就地逆置;為簡化演算法,假設表長大於2p=l->next;q=p->next;s=q->next;p->next=nullwhile(s->next)
q->next=p;s->next=q;l->next=s;
}//linklist_reverse
22、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
29. ① 試找出滿足下列條件的二叉樹
1）先序序列與後序序列相同 2）中序序列與後序序列相同
3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同
23、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。
2023年山西省資料總結高階
1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是 區域性根 確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為 左根右 三部分。若左 右子樹均有，則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有...
2023年山西省資料總結大綱
1 設t是給定的一棵二叉樹，下面的遞迴程式count t 用於求得 二叉樹t中具有非空的左，右兩個兒子的結點個數n2 只有非空左兒子的個數nl 只有非空右兒子的結點個數nr和葉子結點個數n0。n2 nl nr n0都是全域性量，且在呼叫count t 之前都置為0.typedef struct no...
2023年山西省資料總結大綱
1 設t是給定的一棵二叉樹，下面的遞迴程式count t 用於求得 二叉樹t中具有非空的左,右兩個兒子的結點個數n2 只有非空左兒子的個數nl 只有非空右兒子的結點個數nr和葉子結點個數n0。n2 nl nr n0都是全域性量，且在呼叫count t 之前都置為0.typedef struct no...