2023年黑龍江省資料總結大綱

1、對二叉樹的某層上的結點進行運算，採用佇列結構按層次遍歷最適宜。

int leafklevel(bitree bt, int k) //求二叉樹bt 的第k(k>1) 層上葉子結點個數

//last移到指向下層最右一元素

if(level>k) return (leaf層數大於k 後退出執行

}//while }//結束leafklevel

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、已知有向圖g=(v,e)，其中v=，e=

寫出g的拓撲排序的結果。

g拓撲排序的結果是：v1、v2、v4、v3、v5、v6、v7

4、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。

int similar(bitree p,q) //判斷二叉樹p和q是否相似

//結束similar

5、陣列a和b的元素分別有序，欲將兩陣列合併到c陣列，使c仍有序，應將a和b拷貝到c，只要注意a和b陣列指標的使用，以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。

void union(int a,b,c,m,n)

//整型陣列a和b各有m和n個元素，前者遞增有序，後者遞減有序，本演算法將a和b歸併為遞增有序的陣列c。

演算法結束

4、要求二叉樹按二叉鍊錶形式儲存。15分

（1）寫乙個建立二叉樹的演算法。（2）寫乙個判別給定的二叉樹是否是完全二叉樹的演算法。

bitree creat建立二叉樹的二叉鍊錶形式的儲存結構

else error(「輸入錯誤」)；

return(bt);

}//結束 bitree

int judgecomplete(bitree bt) //判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0

//while

return 1; } //judgecomplete

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

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

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

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

7、二部圖（bipartite graph） g=（v，e）是乙個能將其結點集v分為兩不相交子集v 1和v2=v-v1的無向圖，使得：v1中的任何兩個結點在圖g中均不相鄰，v2中的任何結點在圖g中也均不相鄰。

（1）．請各舉乙個結點個數為5的二部圖和非二部圖的例子。

（2）．請用c或pascal編寫乙個函式bipartite判斷乙個連通無向圖g是否是二部圖，並分析程式的時間複雜度。設g用二維陣列a來表示，大小為n*n（n為結點個數）。請在程式中加必要的注釋。

若有必要可直接利用堆疊或佇列操作。【