2023年福建省資料總結摘要

1、設一棵二叉樹的結點結構為 (llink,info,rlink),root為指向該二叉樹根結點的指標，p和q分別為指向該二叉樹中任意兩個結點的指標，試編寫一演算法ancestor（root，p,q,r）,該演算法找到p和q的最近共同祖先結點r。

2、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數pre（初值為null）和全域性變數flag，初值為true。若非二叉排序樹，則置flag為false。

define true 1

define false 0

typedef struct node

datatype data; struct node *llink,*rlink;} *btree;

void judgebst（btree t,int flag）

判斷二叉樹是否是二叉排序樹，本演算法結束後，在呼叫程式中由flag得出結論。 //不是完全二叉樹

judgebst （t->rlink,flag）；// 中序遍歷右子樹

judgebst演算法結束

3、4、 void linklist_reverse(linklist &l)

鍊錶的就地逆置;為簡化演算法,假設表長大於2

p=l->next;q=p->next;s=q->next;p->next=null;

while(s->next)

q->next=p;p=q;

q=s;s=s->next; //把l的元素逐個插入新表表頭

q->next=p;s->next=q;l->next=s;

linklist_reverse

4、矩陣中元素按行和按列都已排序，要求查詢時間複雜度為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中.

i=a; j=d; flag=0; //flag是成功查到x的標誌

while(i<=b && j>=c)

if(a[i][j]==x)

else if (a[i][j]>x) j--; else i++;

if(flag) printf(「a[%d][%d]=%d」,i,j,x假定x為整型.