2023年河北省資料總結大綱

1、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）

（1）a和d是合法序列，b和c 是非法序列。

（2）設被判定的操作序列已存入一維陣列a中。

int judge(char a)

//判斷字元陣列a中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。

}i++; //不論a[i]是『i』或『o』，指標i均後移。}

if(j!=k)

else

}//演算法結束。

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

}}}}

3、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。（20分）