2023年內蒙古自治區資料總結入門

1、設t是一棵滿二叉樹，編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。

2、若第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)

3、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數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演算法結束

4、設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹並給出構造過程。