1、後序遍歷最後訪問根結點，即在遞迴演算法中，根是壓在棧底的。採用後序非遞迴演算法，棧中存放二叉樹結點的指標，當訪問到某結點時，棧中所有元素均為該結點的祖先。本題要找p和q 的最近共同祖先結點r ,不失一般性，設p在q的左邊。
後序遍歷必然先遍歷到結點p，棧中元素均為p的祖先。將棧拷入另一輔助棧中。再繼續遍歷到結點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第乙個匹配（即相等）的元素就是結點p 和q的最近公共祖先。
typedef struct
stack;
stack s,s1;//棧，容量夠大
bitree ancestor(bitree root,p,q,r)//求二叉樹上結點p和q的最近的共同祖先結點r。
//沿左分枝向下
if(bt==p) //不失一般性，假定p在q的左側,遇結點p時，棧中元素均為p的祖先結點
//將棧s的元素轉入輔助棧s1 儲存
if(bt==q) //找到q 結點。
for(i=top;i>0;i--)//；將棧中元素的樹結點到s1去匹配
｝while(top!=0 && s[top].tag==1) top退棧
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍歷
}//結束while(bt!=null ||top>0)
return(null);//ｑ、p無公共祖先
｝//結束ancestor
2、(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
3、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
29. ① 試找出滿足下列條件的二叉樹
1）先序序列與後序序列相同 2）中序序列與後序序列相同
3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同
4、有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表(用陣列表示)進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某乙個記錄，統計出的計數值為c，那麼，這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法；
(3) (4分)對於有n個記錄的表，關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什麼?
5、矩陣中元素按行和按列都已排序，要求查詢時間複雜度為o（m+n），因此不能採用常規的二層迴圈的查詢。可以先從右上角（i=a,j=d）元素與x比較，只有三種情況：一是a[i,j]>x， 這情況下向j 小的方向繼續查詢；二是a[i,j]void search(datatype a[ ][ ], int a,b,c,d, datatype x)
//n*m矩陣a,行下標從a到b,列下標從c到d,本演算法查詢x是否在矩陣a中.
else if (a[i][j]>x) j--; else i++;
if(flag) printf(「a[%d][%d]=%d」,i,j,x假定x為整型.
else printf(「矩陣a中無%d 元素」，x)；
}演算法search結束。
[演算法討論]演算法中查詢x的路線從右上角開始，向下（當x>a[i,j]）或向左（當x6、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數pre（初值為null）和全域性變數flag，初值為true。若非二叉排序樹，則置flag為false。
#define true 1
#define false 0
typedef struct node
*btree;
void judgebst（btree t,int flag）
// 判斷二叉樹是否是二叉排序樹，本演算法結束後，在呼叫程式中由flag得出結論。
//不是完全二叉樹
judgebst （t->rlink,flag）；// 中序遍歷右子樹
}//judgebst演算法結束
2023年新疆維吾爾自治區資料總結綱要
1 連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n 1條邊，最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序，然後從大到小將邊刪除。每刪除一條當前權值最大的邊後，就去測試圖是否仍連通，若不再連通，則將該邊恢復。若仍連通，繼續向下刪 直到剩n 1條邊為止。void spnt...
2023年新疆維吾爾自治區資料總結要領
1 陣列a和b的元素分別有序，欲將兩陣列合併到c陣列，使c仍有序，應將a和b拷貝到c，只要注意a和b陣列指標的使用，以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。void union int a,b,c,m,n 整型陣列a和b各有m和n個元素，前者遞增有序，後者遞減有序，本演算法將a...
2023年新疆維吾爾自治區資料總結入門
1 設有兩個集合a和集合b，要求設計生成集合c a b的演算法，其中集合a b和c用鏈式儲存結構表示。typedef struct node lklist void intersection lklist ha,lklist hb,lklist hc 2 二部圖 bipartite graph g ...