2023年澳門特別行政區資料總結基礎

1、設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)__;

}}}}

2、假設k1，…，kn是n個關鍵詞，試解答：

試用二叉查詢樹的插入演算法建立一棵二叉查詢樹，即當關鍵詞的插入次序為k1，k2，…，kn時，用演算法建立一棵以llink / rlink 鏈結表示的二叉查詢樹。

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

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

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

4、我們用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