2019山西省資料結構分析深入

1、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。

2、設有乙個陣列中存放了乙個無序的關鍵序列k1、k2、…、kn。現要求將kn放在將元素排序後的正確位置上，試編寫實現該功能的演算法，要求比較關鍵字的次數不超過n。

51. 借助於快速排序的演算法思想，在一組無序的記錄中查詢給定關鍵字值等於key的記錄。設此組記錄存放於陣列r[l..

h]中。若查詢成功，則輸出該記錄在r陣列中的位置及其值，否則顯示「not find」資訊。請編寫出演算法並簡要說明演算法思想。

3、請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法，設二叉樹用llink-rlink法儲存。

4、程式設計實現單鏈表的就地逆置。

23．在陣列 a[1..n]中有n個資料，試建立乙個帶有頭結點的迴圈鍊錶，頭指標為h，要求鏈中資料從小到大排列，重複的資料在鏈中只儲存乙個.

5、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。

29. ① 試找出滿足下列條件的二叉樹

1）先序序列與後序序列相同 2）中序序列與後序序列相同

3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同

6、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈，去掉圈上權最大的邊」，反覆執行這一步驟，直到沒有圈為止。請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法，並用程式實現你所給出的演算法。

注：圈就是迴路。

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