【正文】 f( rear=NULL) { rear=s。 else rearnext=snext。⑶14⑷模式匹配(5)由空格字符（ASCII值32）所組成的字符串，空格個數(shù)(6)該串所包含的的字符的個數(shù)(7) a. 21 b. 1 c. DataBase Structure Coursed. Data Course e. Structure Base Course2. 簡答題（1） 不含任何字符的串稱為空串，其長度為0。子串在主串中第一次出現(xiàn)時的第一個字符的位置稱子串在主串中的位置。}⑵從后向前刪除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。算法如下： include iostream include string void main() { int strbegin,strend。 while (strbegin strend) { tmp = str[strbegin]。從左到右掃描字符串，初次碰到數(shù)字字符時，作為一個整數(shù)的開始。 ch=’9’) /*是數(shù)字字符*/ ｛num=０。 ｝ else scanf（“%c”，amp。i=1。 while(j!=0) {i++。⑸21 根據二叉樹性質3的證明過程，有n0=n2+2n3+3n4+1（n0、nnn4分別為葉子結點、度為度為3和度為4的結點的個數(shù)）。(11)C 因為有n+1個空鏈域來作為線索(12)B(13)D(14)D(15)D 因為這些分支結點共有N1+2*N2+…+m*Nm個指針域，其中有N1+N2+…+Nm 1個指針指向分支結點，所以余下的指針指向的是葉子結點。 n++。 printleaf(rootlchild)。注意和前序遍歷的區(qū)別，具體算法如下：void PostPrder(BiNode *root){ if (root) { printf(“%d “,rootdata)。 } } ⑹對二叉鏈表進行遍歷，在遍歷的過程中查找結點a并記載其雙親，然后將結點x的雙親結點中指向結點x的指針置空。bool ComBiTree(BiNode *root){ front=rear=1。 if (prchild) b=0。 else /*右子樹非空*/ { if(pltag==0) /*左子樹非空，左孩子就是后繼*/ q=plchild； if(pltag==1) /*左子樹為空，右孩子就是后繼*/ q=prchild。⑵鄰接矩陣，鄰接表 這是最常用的兩種存儲結構，此外，還有十字鏈表、鄰接多重表等。⑵對。⑹錯。（2）鄰接矩陣表示如下：鄰接表表示如下： 各頂點的度：TD(v1)=3 TD(v2)=4 TD(v3)=2 TD(v4)=4 TD(v5)=3 TD(v6)=2深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5（3）按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：（4）拓撲序列為：v0 v1 v5 v2 v3 v6 v v0 v1 v5 v2 v6 v3 v v0 v1 v5 v6 v2 v3 vv0 v5 v1 v2 v3 v6 v v0 v5 v1 v2 v6 v3 vv0 v5 v1 v6 v2 v3 v v1 v0 v5 v2 v3 v6 vv1 v0 v5 v2 v6 v3 v v1 v0 v5 v6 v2 v3 vv1 v5 v0 v2 v3 v6 v v1 v5 v0 v2 v6 v3 v v1 v5 v0 v6 v2 v3 vv5 v0 v1 v2 v3 v6 vv5 v0 v1 v2 v6 v3 vv5 v0 v1 v6 v2 v3 vv5 v1 v0 v2 v3 v6 v v5 v1 v0 v2 v6 v3 v v5 v1 v0 v6 v2 v3 v4（5）所有事件的最早發(fā)生時間ve[k]： ve (1)=0 ve (2)=3 ve (3)= max{ve(1)+2,ve(2)+6,ve(4)+2}=9 ve (4)=5 ve (5)=max{ve(2)+5,ve(3)+8}=17 ve (6)= max{ve(3)+4,ve(4)+8}=13 ve (7)=max{ve(3)+9,ve(5)+8,ve(6)+7}=25 所有事件的最晚發(fā)生時間vl[k]： vl (7)= ve(7) =25 vl (6)= vl (7)7=18 vl (5)= vl (7) 8=17 vl (4)= min{ vl (3)2, vl (6)8}=7 vl (3)=min{ vl (7)9, vl (5)8, vl (6)4}=9 vl (2)=min{ vl (5)5, vl (3)6}=3 vl (1)= min{ vl (4)5, vl (3)2, vl (2)3}=0 所有活動ai的最早開始時間e[i]和最晚開始時間l[i]： 活動a1 e (1)=ve (1)=0 l (1)=vl (2) 3 =0 活動a2 e (2)=ve (1)=0 l (2)=vl (3) 2=7 活動a3 e (3)=ve (2)=0 l (3)=vl (4) 5=2 活動a4 e (4)=ve (2)=3 l (4)=vl (5) 5=12 活動a5 e (5)=ve (3)=3 l (5)=vl (3) 6=3 活動a6 e (6)=ve (3)=5 l (6)=vl (3) 2=7 活動a7 e (7)=ve (4)=5 l (7)=vl (6) 8=10 活動a8 e (8)=ve (5)=9 l (8)=vl (5) 8=9 活動a9 e (9)=ve (5)=9 l (9)=vl (7) 9=16 活動a10 e (10)=ve (6)=9 l (10)=vl (6) 4=14 活動a11 e (11)=ve (7)=17 l (11)=vl (7) 8=17 活動a12 e (12)=ve (8)=13 l (12)=vl (7) 7=18 最后，比較e[i]和l[i]的值可判斷出a1,a5,a8,a11這些活動的e[i]和l[i]的值相等，沒有時間余量，所以它們是關鍵活動，關鍵路徑如下圖所示。鄰接表存儲結構定義如下：const int MaxSize=10。int vertexNum, arcNum。 i++)[i].firstedge=NULL。 [i].firstedge=p。 i 。 a[i][j]=1。 i++) { flag=0。因此，當某列非零元素的個數(shù)為零時，則對應頂點的入度為零。 j++) if (arcs[j][i]!=0) { flag=1。for (i=0。 p2adjlist=I。b．di =12，12，22，22，… ，177。4 （1）.散列地址0123456789關鍵字140192384275520比較次數(shù)1112 3 412平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關鍵字27為例：H（27）=27%7=6（沖突） H1=（6+1）%10=7（沖突） H2=（6+22）%10=0（沖突） H3=（6+32）%10=5 所以比較了4次。該方法不易產生“聚集”，但增加了計算時間。 } } }習題八解答填空題（1）主關鍵字（2）3（4）(1)哈希函數(shù)(2)解決沖突的方法 (3)選擇好的哈希函數(shù) (4)處理沖突的方法 (5)均勻(6)簡單（5）AVL樹（高度平衡樹，高度平衡的二叉排序樹），或為空二叉樹，或二叉樹中任意結點左子樹高度與右子樹高度差的絕對值小于等于1。i。}(5)在有向圖中，若鄰接表中頂點vi有鄰接點vj，在逆鄰接表中vj一定有鄰接點