1、本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a，取出a[i]（0<=ilinkedlist creat(elemtype a,int n)
//由含n個資料的陣列a生成迴圈鍊錶，要求鍊錶有序並且無值重複結點
//查詢a[i]的插入位置
if(p==h || p->data!=a[i重複資料不再輸入
}//for
return(h);
}演算法結束
2、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。
void translation（float *matrix，int n）
//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。
//for i
for(i=0; i
sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.
}//if
}//for i
free(p); //釋放p陣列.
}// translation
[演算法分析] 演算法中使用選擇法排序,比較次數較多,但資料交換(移動)較少.若用其它排序方法,雖可減少比較次數,但資料移動會增多.演算法時間複雜度為o(n2).
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、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
5、後序遍歷最後訪問根結點，即在遞迴演算法中，根是壓在棧底的。採用後序非遞迴演算法，棧中存放二叉樹結點的指標，當訪問到某結點時，棧中所有元素均為該結點的祖先。本題要找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
6、設t是給定的一棵二叉樹，下面的遞迴程式count(t)用於求得:二叉樹t中具有非空的左,右兩個兒子的結點個數n2;只有非空左兒子的個數nl;只有非空右兒子的結點個數nr和葉子結點個數n0。n2、nl、nr、n0都是全域性量，且在呼叫count(t)之前都置為0.
typedef struct node
node;
int n2,nl,nr,n0;
void count(node *t)
26.樹的先序非遞迴演算法。
void example(b)
btree *b;
if (p->lchild!=null)
(3)___; (4)__;
}}}}
7、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。
void pretopost(elemtype pre ,post,int l1,h1,l2,h2)
//將滿二叉樹的先序序列轉為後序序列，l1,h1,l2,h2是序列初始和最後結點的下標。
}//pretopost
32. .葉子結點只有在遍歷中才能知道，這裡使用中序遞迴遍歷。
設定前驅結點指標pre，初始為空。第乙個葉子結點由指標head指向，遍歷到葉子結點時，就將它前驅的rchild指標指向它，最後葉子結點的rchild為空。
linkedlist head,pre=null; //全域性變數
linkedlist inorder(bitree bt)
//中序遍歷二叉樹bt，將葉子結點從左到右鏈成乙個單鏈表，表頭指標為head
//處理第乙個葉子結點
else //將葉子結點鏈入鍊錶
inorder(bt->rchild中序遍歷左子樹
pre->rchild=null設定鍊錶尾
}return(head); } //inorder
時間複雜度為o(n),輔助變數使用head和pre,棧空間複雜度o(n)
8、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。
2023年吉林省資料總結加強
1 對一般二叉樹，僅根據乙個先序 中序 後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列 即任一遍歷序列均可確定一棵二叉樹 void pretopost elemtype pre post,int l1,h1,l2...
2023年吉林省資料總結加強
1 因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。void longestpath bitree bt 求二叉樹中的第一條最長...
2023年吉林省重要資料加強
1 設一棵樹t中邊的集合為，要求用孩子兄弟表示法 二叉鍊錶 表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。2 設一棵二叉樹的結點結構為 llink,info,rlink root為指向該二叉樹根結點的指標，p 和q分別為指向該二叉樹中任意兩個結點的指標，試編寫一演算法ancestor root，p...