《數據結構[第4版]習題和實驗答案數據結構復習資料（完整版）[c語言版]》由會員分享，可在線閱讀，更多相關《數據結構[第4版]習題和實驗答案數據結構復習資料（完整版）[c語言版]（41頁珍藏版）》請在裝配圖網上搜索。

1、 ...wd... 數據構造根基及深入及考試 復習資料 習題及實驗參考答案見附錄 結論 1、數據的邏輯構造是指數據元素之間的邏輯關系。即從邏輯關系上描述數據，它與數據的存儲無關，是獨立于計算機的。 2、數據的物理構造亦稱存儲構造，是數據的邏輯構造在計算機存儲器內的表示〔或映像〕。它依賴于計算機。存儲構造可分為4大類：順序、鏈式、索引、散列 3、抽象數據類型：由用戶定義，用以表示應用問題的數據模型。它由 基本的數據類型構成，并包括一組

2、相關的服務〔或稱操作〕。它與數據類型實質上是一個概念，但其特征是使用與實現別離，實行封裝和信息隱蔽〔獨立于計算機〕。 4、算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉換為輸出的計算步驟。 5、在數據構造中，從邏輯上可以把數據構造分成〔 C 〕 A、動態(tài)構造和表態(tài)構造 B、緊湊構造和非緊湊構造 C、線性構造和非線性構造 D、內部構造和外部構造 6、算法的時間復雜度取決于〔 A 〕 A、問題的規(guī)模 B、待處理數據的初態(tài) C、問題的規(guī)模和待處理數據的初態(tài) 線性表 1、線

3、性表的存儲構造包括順序存儲構造和鏈式存儲構造兩種。 2、表長為n的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均次數為〔 E 〕，刪除一個元素需要移動的元素的個數為〔 A 〕。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“線性表的邏輯順序與存儲順序總是一致的。〞這個結論是〔 B 〕 A、正確的 B、錯誤的 C、不一定，與具體的構造有關 4、線性表采用鏈式存儲構造時，要求內存中可用存儲單元的地址〔

4、 D 〕 A、必須是連續(xù)的 B、局部地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)或不連續(xù)都可以 5、帶頭結點的單鏈表為 空的判定條件是〔 B 〕 A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不帶頭結點的單鏈表head為空的判定條件是〔 A 〕 A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循環(huán)單鏈表head的尾結點P滿足〔 C 〕

5、 A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是〔 B 〕 A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一個單鏈表中，假設刪除p所指結點的后繼結點，則執(zhí)行〔 A 〕 A、p->next=p->next->next; B、p=p->next;p->next=p->next->next; C、p->next=p->next; D、p= p->next->next;

6、 10、在一個單鏈表中，假設在p所指結點之后插入s所指結點，則執(zhí)行〔 B 〕 A、s->next=p;p->next=s; B、s->next=p->next;p->next=s; C、s->next=p->next;p=s; D、p->next=s;s->next=p; 11、在一個單鏈表中，q是p的前趨結點，假設在q和p之間插入結點s，則執(zhí)行〔 C 〕 A、s->next=p->next;p->next=s; B、p->next=s->next;s->next=p; C、q->next=s;s->next=p; D、p->next=s;s->next=q;

7、 12、在線性構造中，第一個結點 沒有 前趨結點，其余每個結點有且只有 1 個前趨結點。 棧和隊列 1、在棧操作中，輸入序列為〔A，B，C，D〕，不可能得到的輸出數列是〔 D 〕 A、〔A，B，C，D〕 B、〔D，C，B，A〕 C、〔A，C，D，B〕 D、〔C，A，D，B〕 2、設棧ST用順序存儲構造表示，則棧ST為空的條件〔 B 〕 A、ST.top=ST.base<>0 B、ST.top=ST.base==0 C、ST.top=ST.base<>n D、S

8、T.top=ST.base==n 3、向一個棧頂指針為HS的鏈棧中插入一個s結點時，執(zhí)行〔 C 〕 A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=S; D、s->next=HS;HS=HS->next; 4、從一個棧頂指針為HS的鏈棧中刪除一個結點，用x保存被刪結點的值，則執(zhí)行〔 C 〕 A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data; C、x=HS->data;HS=HS->next;

9、D、s->next=HS;HS=HS->next; 5、用單鏈表表示的鏈示隊列的隊頭在鏈表的〔 A 〕位置。 A、鏈頭 B、鏈尾 C、鏈中 6、判定一個鏈隊列Ｑ〔最多元素個數為n〕為空的條件是〔　　　A　　〕 Ａ、Ｑ.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 7、在鏈隊列Ｑ中，插入要所指結點需順序執(zhí)行的指令是〔　B　　〕 A、Q.front->next=s;f=s; B、Q.rear->next=s;Q.rear=s

10、; C、s->next=Q.rear;Q.rear=s; D、s->next=Q.front;Q.front=s; 8、在一個鏈隊列Q中，刪除一個結點需要執(zhí)行的指令是〔 C 〕 A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 9、棧和隊列的共同點〔 C 〕 A、都是先進后出 B、都是先進先出 C、只允許在端點處插入和刪除元素 D、沒有共同點 10

11、、棧的特點是_先進后出，隊列的特點是先進先出 11、線性表、棧和隊列都是線性構造，可以在線性表的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入元素和在隊首刪除元素。 串和數組 1、設串s1=’ABCDEFG’，s2=’PQRST’，函數Concat(x,y)返回x和y串的連接串，Substr(s,I,j)返回串s從序號i開場的j個字符組成的子串，length(s)返回串s的長度，則Concat(Substr(s1,2, length(s2), Substr(s1,length(s2),2))的結果串是〔 D 〕 A、BCDEF B、BCDEF

12、G C、BCPQRST D、BCDEFEF 2、串是一種特殊的線性表，其特殊性表達在〔 D 〕 A、可以順序存儲 B、數據元素是一個字符 C、可以鏈接存儲 D、數據元素可以是多個字符 3、設有兩個串p和q，求q在p中首次出現的位置的運算稱作〔 B 〕 A、連接 B、模式匹配 C、求子串聯 D、求串長 4、串的兩種最 基本的存儲方式是順序存儲方式和鏈接存儲方式。 樹和二叉樹 1、樹最適宜用來表示〔 B 〕 A、有序數據元素 B、元素之間具有分支層次關系的數據 C、無序數據元素

13、 D、元素之間無聯系的數據 2、按照二叉樹的定義，具有3個結點的二叉樹有〔 C 〕種。 A、3 B、4 C、5 D、6 3、在一棵有n個結點的二叉樹中，假設度為2的結點數為n2，度為1的結點數為n1，度為0的結點數為n0，則樹的最大高度為〔 E 〕，其葉結點數為〔 G 〕；樹的最小高度為〔 B 〕，其葉結點數為〔 G 〕；假設采用鏈表存儲構造，則有〔 I 〕個空鏈域。 A、n/2 B、[log2n]+1 C、log2n D、n E、n0 + n1 + n2

14、 F、n1 + n2 G、n2 +1 H、1 I、n+1 J、n1 K、n2 L、n1 +1 4、在一棵二叉樹上第5層的結點數最多為〔 B 〕?！布僭O根結點的層數為0〕 A、8 B、16 C、15 D、32 5、深度為5的二叉樹至多有〔 C 〕個結點。 A、16 B、32 C、31 D、10 6、在一非空二叉樹的中序遍歷序列中，根結點的右邊〔 A 〕 A、只有右子樹上的所有結點 B、只有右子樹上的局部結點 C、只有左子樹上的局部結點 D、只有左子樹

15、上的所有結點 7、一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI，則在先序遍歷中結點E的直接前趨為〔 D 〕，后序遍歷中結點B的直接后繼是〔 E 〕。 A、B B、D C、A D、I E、F F、C 8、某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是〔 D 〕 A、acbed B、decab C、deabc D、cedba 9、在樹形構造中，樹根結點沒有___前趨________結點，其余每個結點有且只有_______1______個前趨結點；葉子結點沒有___

16、___后繼___________結點，其余每個結點的后繼結點可以__任意多個____。 10、有一棵樹如以以下圖，答復下面的問題： K1 K7 K6 K5 K2 K3 K4 這棵樹的根結點是____K1_______，這棵樹的葉子結點是__K2，K5，K7，K4______；結點k3的度是____2________;這棵樹的度為___3_______；這棵樹的深度是_____4_________；結點k3的子女是______K5，K6_____；結點k3的父結點是_____K1_________. 11、一棵二叉樹的中序遍歷序列為CDBAEGF，

17、前序遍歷序列為ABCDEFG，試問能不能惟一確定一棵二叉樹，假設能請畫出該二叉樹。假設給定前序遍歷序列和后序遍歷序列，能否惟一確定一棵二叉樹，說明理由。 答： ⑴由中序遍歷序列和前序遍歷序列或中序遍歷序列和后序遍歷序列可以惟一確定一棵二叉樹。 基本思想是前序〔后序〕定根，中序分左右。 對于給定的前序和中序序列。可確定根結點為A，以A為根的左子樹結點為B，C，D，右子樹結點為E，F，G。進一步可確定所有子樹的根結點，因而也就確定了整個二叉樹。對應的二叉樹如以以下圖： F A D G F E C B ⑵由前序遍歷和后序遍歷序列不能惟一確定一棵二叉樹。如以以下圖為4棵不

18、同的二叉樹，它們的前序遍歷序列都是ABC，而后序遍歷序列都是CBA。 A C B C B A A C B A C B 12、設二叉樹bt的存儲構造如下： 1 2 3 4 5 6 7 8 9 10 left 0 0 2 3 7 5 8 0 10 1 data j h f d b a c e g i right 0 0 0 9 4 0 0 0 0 0 其中bt為樹根結點指針，left，right分別為結點的左右孩子指針域，data為結點的數據域，請完成以下各題： ⑴畫出二叉樹

19、bt的邏輯構造 ⑵寫出按前序、中序和后序遍歷二叉樹bt所得到的結點序列。 答： ⑴二叉樹bt的邏輯構造如以以下圖： 12 a j i g h f d e c b ⑵前序遍歷：abcedfhgij 中序遍歷：ecbhfdjiga 后序遍歷：echfjigdba 13、給定一棵以二叉鏈表存儲構造表示的二叉樹，其根結點指針為T，試寫出求二叉樹的葉子數目的算法。 int CountLeaf (BiTree T){ //返回指針T所指二叉樹中所有葉子結點個數 if (!T ) return 0; if (!T->lchild && !T->rch

20、ild) return 1; else{ m = CountLeaf( T->lchild); n = CountLeaf( T->rchild); return (m+n); } //else } // CountLeaf 14、給定一棵以二叉鏈表存儲構造表示的二叉樹，其根結點指針為T，試寫出求二叉樹的深度的算法。 int Depth (BiTree T ){ // 返回二叉樹的深度 if ( !T ) depthval = 0; else { depthLeft = Depth

21、( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval; } 圖 1、一個有n個頂點的無向圖最多有〔 C 〕條邊。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有6個頂點的無向圖至少應有〔 A 〕條邊才能確保是一個連通圖。 A、5 B、6

22、 C、7 D、8 3、存儲稀疏圖的數據構造常用的是〔 C 〕 A、鄰接矩陣 B、三元組 C、鄰接表 D、十字鏈表 4、在有向圖的鄰接表存儲構造中，頂點V在表結點中出現的次數是〔 C 〕 A、頂點V的度 B、頂點V的出度 C、頂點V的入度 D、依附于頂點V的邊數 5、用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時，打印出相應的頂點，則輸出的頂點序列是〔 A 〕 A、逆拓撲有序的 B、拓撲有序的 C、無序的 6、一個圖如以以下圖，假設從頂點a出

23、發(fā)按深度優(yōu)先搜索法進展遍歷，則可能得到的一種頂點序列為〔 D 〕，按廣度優(yōu)先搜索法進展遍歷，則可能得到的一種頂點序列為〔 B 〕。 ⑴A、abecdf B、acfebd C、acebfd D、acfdeb ⑵A、abcedf B、abcefd C、abedfc D、acfdeb C a c f d e b 7、采用鄰接表存儲的圖的廣度優(yōu)先搜索遍歷算法類似于二叉樹的〔 D 〕 A、中序遍歷 B、先序遍歷 C、后序遍歷 D、按層遍歷 8、一個圖如以以下圖，則由該圖得到的一種拓撲序列為

24、〔 A 〕 1 6 5 4 3 2 A、V1，V4，V6，V2，V5，V3 B、V1，V2，V3，V4，V5，V6 C、V1，V4，V2，V3，V6，V5 D、V1，V2，V4，V6，V3，V5 9、在圖形構造中，每個結點的前趨結點數和后續(xù)結點數可以___任意多個_______。 10、在AOE網中，從源點到匯點各活動時間總和最長的路徑稱為關鍵路徑。 11、給出圖G，如以以下圖： 1 11 10 9 8 7 6 5 4 3 2 〔1〕給出圖G的鄰接表〔畫圖即可〕 〔2〕在你給出的鄰接表的情況下，以頂點V4為根，畫出

25、圖G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。 〔3〕將你畫出的廣度優(yōu)先生成樹轉換為對應的二叉樹。 答： 〔1〕圖的鄰接表如以以以下圖所示：略 〔2〕以頂點V4為根的深度優(yōu)先生成樹和廣度優(yōu)先生成樹如以以下圖 1 11 10 9 8 7 6 5 4 3 2 d 1 11 10 9 8 7 6 5 4 3 2 〔3〕廣度優(yōu)先生成樹轉換成二叉樹如以以以下圖所示 1 1 10 9 11 7 8 6 3 4 5 2 附錄 習題及實驗參考答案 習題1參考答案 1.1.選擇題 (1). A. (2). A. (3)

26、. A. (4). B.,C. (5). A. (6). A. (7). C. (8). C. (9). B. (10.) A. 1.2.填空題 (1). 數據 關系 (2). 邏輯構造 物理構造 (3). 線性數據構造 樹型構造 圖構造 (4). 順序存儲 鏈式存儲 索引存儲 散列表〔Hash〕存儲 (5). 變量的取值范圍 操作的類別 (6). 數據元素間的邏輯關系數據元素存儲方式或者數據元素的物理關系 (7). 關系 網狀構造 樹構造 (8). 空間復雜度和時間復雜度 (9). 空間 時間 (10). Ο(n) 1.3名

27、詞解釋如下： 數據：數據是信息的載體，是計算機程序加工和處理的對象，包括數值數據和非數值數據。 數據項：數據項指不可分割的、具有獨立意義的最小數據單位，數據項有時也稱為字段或域。 數據元素：數據元素是數據的 基本單位，在計算機程序中通常作為一個整體進展考慮和處理，一個數據元素可由假設干個數據項組成。 數據邏輯構造：數據的邏輯構造就是指數據元素間的關系。 數據存儲構造：數據的物理構造表示數據元素的存儲方式或者數據元素的物理關系。 數據類型：是指變量的取值范圍和所能夠進展的操作的總和。 算法：是對特定問題求解步驟的一種描述，是指令的有限序列。 1.4語句的時間復雜度為： (1)

28、 Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 參考程序： main() { int X,Y,Z； scanf(“%d, %d, %d〞,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d〞,X,Y,Z);} else { printf(“%d, %d, %d〞,X,Z,Y);} else { printf(“%d, %d, %d〞,Z,X,Y);} else if(Z>=X) if (Y>=Z)

29、 { printf(“%d, %d, %d〞,Y,Z,X);} else { printf(“%d, %d, %d〞,Z,Y,X);} else { printf(“%d, %d, %d〞,Y,X,Z);} } 1.6 參考程序： main() { int i,n; float x,a[],p; printf(“\nn=〞);scanf(“%f〞,&n); printf(“\nx=〞);scanf(“%f〞,&x); for(i=0;i<=n;i++) scanf(“%f 〞,&a[i]); p=a[0]; for(i=1;i<=n;i++) { p

30、=p+a[i]*x; x=x*x;} printf(“%f〞,p)’ } 習題2參考答案 2.1選擇題 (1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D. 2.2.填空題 (1). 有限序列 (2). 順序存儲和鏈式存儲 (3). Ｏ(n)O(n) (4). n-i+1 n-i (5). 鏈式 (6). 數據 指針 (7). 前驅 后繼 (8). Ο(1)Ο(n) (9). s->next=p->next;

31、 p->next=s ; (10). s->next 2.3.解題思路：將順序表A中的元素輸入數組a，假設數組a中元素個數為n,將下標為0，1,2,…,〔n-1〕/2的元素依次與下標為n,n-1,…, 〔n-1〕/2的元素交換，輸出數組a的元素。 參考程序如下： main() { int i,n; float t,a[]; printf(“\nn=〞);scanf(“%f〞,&n); for(i=0;i<=n-1;i++) scanf(“%f 〞,&a[i]); for(i=0;i<=(n-1)/2;i++) { t=a[i]; a[i] =a[n-1-i

32、]; a[n-1-i]=t;} for(i=0;i<=n-1;i++) printf(“%f〞,a[i]); } 2.4算法與程序： main() { int i,n; float t,a[]; printf(“\nn=〞);scanf(“%f〞,&n); for(i=0;ia[0] { t=a[i]; a[i] =a[0]; a[0]=t;} printf(“%f〞,a[0]); for(i=2;i

33、i]>a[1] { t=a[i]; a[i] =a[1]; a[1]=t;} printf(“%f〞,a[0]); } 2.5 算法與程序： main() { int i,j,k,n; float x,t,a[]; printf(“\nx=〞);scanf(“%f〞,&x); printf(“\nn=〞);scanf(“%f〞,&n); for(i=0;i

34、 jj) {t=a[i];a[i]=a[k];a[k]=t;} } for(i=0;ix) break; for(k=n-1;k>=i;i--) // 移動線性表中元素，然后插入元素x a[k+1]=a[k]; a[i]=x; for(i=0;i<=n;i++) // 依次輸出線性表中的元素 printf(“%f〞,a[i]); } 2.6算法思路：依次掃描A和B的元素，對

35、比A、B當前的元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，最后將未掃描完順序表中的余下局部賦給C即可。C的容量要能夠容納A、B兩個線性表相加的長度。 有序表的合并算法： void merge (SeqList A, SeqList B, SeqList *C) { int i，j，k； i=0；j=0；k=0； while ( i<=A.last && j<=B.last ) if (A.data[i]<=B.data[j]) C->data[k++]=A.data[i++]； else

36、 C->data[k++]=B.data[j++]； while (i<=A.last ) C->data[k++]= A.data[i++]； while (j<=B.last ) C->data[k++]=B.data[j++]； C->last=k-1； } 2.7 算法思路：依次將A中的元素和B的元素對比，將值相等的元素賦給C，如此直到線性表掃描完畢，線性表C就是所求遞增有序線性表。 算法： void merge (SeqList A, SeqList B, SeqList *C) { int i，j，k；

37、 i=0；j=0；k=0； while ( i<=A.last) while〔j<=B.last ) if (A.data[i]=B.data[j]) C->data[k++]=A.data[i++]； C->last=k-1； } 習題3參考答案 3.1.選擇題 (1). D (2). C (3).D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C(15). C (16). D(17). B (18). C (

38、19). C (20). C 3.2.填空題 （1） FILO, FIFO （2） -1, 3 4 X * + 2 Y * 3 / - （3） stack.top++, stack.s[stack.top]=x （4） p>llink->rlink=p->rlink, p->rlink->llink=p->rlink （5） (R-F+M)%M （6） top1+1=top2 （7） F==R （8） front==rear （9） front==(rear+1)%n （10） N-1 3.3 答：一般線性表使用數組來表示的 線性表一般有插入、刪除、讀取等對于任意元

39、素的操作 而棧只是一種特殊的線性表 棧只能在線性表的一端插入〔稱為入棧,push〕或者讀取棧頂元素或者稱為“彈出、出棧〞(pop)。 3.4 答：一樣點：棧和隊列都是特殊的線性表，只在端點處進展插入，刪除操作。 不同點：棧只在一端〔棧頂〕進展插入，刪除操作；隊列在一端〔top〕刪除，一端(rear)插入。 3.5 答：可能序列有14種：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。 3.6 答：不能得到4，3，5，6，1，2，最先出棧的是4,則按321的方式出，不可能得到1在2前的序

40、列，可以得到1，3，5，4，2，6，按如下方式進展push(1),pop(),push(2),push(3),pop(),push(4),push(5),pop(),pop(),pop(), push(6), pop()。 3.7 答：stack 3.8 非遞歸: int vonvert (int no,int a[]) //將十進制數轉換為2進制存放在a[]，并返回位數 { int r; SeStack s,*p; P=&s; Init_stack(p); while(no) { push(p,no%2); no/=1

41、0; } r=0; while(!empty_stack(p)) { pop(p,a+r); r++; } return r; } 遞歸算法: void convert(int no) { if(no/2>0) { Convert(no/2); Printf(“%d〞,no%2); } else printf(“%d〞,no); } 3.9 參考程序： void view(SeStack s) { SeStack *p; //假設棧元素為字符型 char c;

42、 p=&s; while(!empty_stack(p)) { c=pop(p); printf(“%c〞,c); } printf(〞\n〞); } 3.10 答：char 3.11參考程序： void out(linkqueue q) { int e; while(q.rear !=q.front ) { dequeue(q,e); print(e); //打印 } } 習題4參考答案 4.1 選擇題： (1). A (2). D (3). C (4

43、). C (5). B (6). B (7). D (8). A (9). B (10). D 4.2 填空題： （1） 串長相等且對應位置字符相等 （2） 不含任何元素的串，0 （3） 所含字符均是空格，所含空格數 （4） 10 （5） “helloboy〞 （6） 18 （7） 1066 （8） 由零個或多個任意字符組成的字符序列 （9） 串中所含不同字符的個數 （10） 36 4.3 StrLength (s)=14, StrLength (t)=4, SubStr( s，8，7)=〞 STUDENT〞, SubStr(t，2，1)=〞O〞, St

44、rIndex(s,“A〞)=3, StrIndex (s，t)=0, StrRep(s，“STUDENT〞，q)=〞 I AM A WORKER〞, 4.4 StrRep(s,〞Y〞,〞+〞);StrRep(s,〞+*〞,〞*Y〞); 4.5 空串：不含任何字符；空格串：所含字符都是空格 串變量和串常量:串常量在程序的執(zhí)行過程中只能引用不能改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值的 主串與子串：子串是主串的一個子集 串變量的名字與串變量的值:串變量的名字表示串值的標識符 4.6 int EQUAl(S,T) { char *p,*q; p=&S

45、; q=&T; while(*p&&*q) { if(*p!=*q) return *p-*q; p++; q++; } return *p-*q; } 4.7 (1)6*8*6=288 (2)1000+47*6=1282 (3)1000+(8+4)*6=1072 (4)1000+(6*7+4)*6=1276 4.8 i j v 1 1 2 1 2 1 5 -1 3 2 1 4 4 3 4 7 5

46、 4 2 6 6 5 1 8 7 5 3 9 矩陣的三元組表 習題5參考答案 5.1 選擇 〔1〕C〔2〕B〔3〕C〔4〕B〔5〕C〔6〕D〔7〕C〔8〕C〔9〕B〔10〕C 〔11〕B〔12〕C〔13〕C〔14〕C〔15〕C 5.2 填空 〔1〕1 〔2〕1036；1040 〔3〕2i 〔4〕 1 ； n ; n-1 ; 2 〔5〕2k-1；2k-1 〔6〕ACDBGJKIHFE 〔7〕p!=NULL 〔8〕Huffman樹 〔9〕其第一個孩子; 下一個兄弟 〔10〕先序遍

47、歷；中序遍歷 5.3 葉子結點:C、F、G、L、I、M、K； 非終端結點：A、B、D、E、J； 各結點的度： 結點： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0 樹深：4 5.4 無序樹形態(tài)如下： 二叉樹形態(tài)如下： 5.5 二叉鏈表如下: A B C ∧ D ∧ E ∧ F ∧ G ∧ ∧ H ∧ ∧ I ∧ ∧ J ∧ 三叉鏈表如下: ∧ A C

48、B F ∧ ∧ G ∧ ∧ D ∧ E J ∧ ∧ I ∧ ∧ H ∧ 5.6 先序遍歷序列:ABDEHICFJG 中序遍歷序列:DBHEIAFJCG 后序遍歷序列:DHIEBJFGCA 5.7 (1) 先序序列和中序序列一樣：空樹或缺左子樹的單支樹； (2) 后序序列和中序序列一樣：空樹或缺右子樹的單支樹； (3) 先序序列和后序序列一樣：空樹或只有根結點的二叉樹。 5.8 這棵二叉樹為: 5.9 先根遍歷序列:ABFGLCDIEJMK 后根遍歷序列:FGLBCIDMJKEA

49、 層次遍歷序列:ABCDEFGLIJKM 5.10 證明：設樹中結點總數為n，葉子結點數為n0，則 n=n0 + n1 + …… + nm 〔1〕 再設樹中分支數目為B，則 B=n1 + 2n2 + 3n3 + …… + m nm 〔2〕 因為除根結點外，每個結點均對應一個進入它的分支，所以有 n= B + 1 〔3〕 將〔1〕和〔2〕代入〔3〕，得 n0 + n1 + …… + nm = n1 + 2n2 + 3n3 + …… + m nm + 1 從而可得葉子結點

50、數為： n0 = n2 + 2n3 + …… + (m-1)nm + 1 5.11 由5.10結論得，n0 = (k-1)nk + 1 又由 n=n0 + nk，得nk= n-n0，代入上式，得 n0 = (k-1)〔n-n0〕+ 1 葉子結點數為：n0 = n (k-1) / k 5.12 int NodeCount(BiTree T) {//計算結點總數 if(T) if (T-> lchild==NULL )&&( T --> rchild==NULL ) return 1; else return NodeCount(T-> lchil

51、d ) +Node ( T --> rchild )+1; else return 0; } 5.13 void ExchangeLR(Bitree bt){ /* 將bt所指二叉樹中所有結點的左、右子樹相互交換 */ if (bt && (bt->lchild || bt->rchild)) { bt->lchild<->bt->rchild; Exchange-lr(bt->lchild); Exchange-lr(bt->rchild); } }/* ExchangeLR */ 5.14 int IsFullBitree(Bit

52、ree T) {/* 是則返回1，否則返回0。*/ Init_Queue(Q); /* 初始化隊列*/ flag=0; In_Queue(Q，T); /* 根指針入隊列 ，按層次遍歷*/ while(!Empty_Queue (Q)) { Out_Queue(Q,p); if(!p) flag=1; /* 假設本次出隊列的是空指針時，則修改flag值為1。假設以后出隊列的指針存在非空，則可斷定不是完全二叉樹 */ else if (flag) return 0; /*斷定不是完全二叉樹 */ else {

53、 In_Queue(Q，p->lchild); In_Queue(Q，p->rchild); /* 不管孩子是否為空，都入隊列。*/ } }/* while */ return 1; /* 只有從某個孩子指針開場，之后所有孩子指針都為空，才可斷定為完全二叉樹*/ }/* IsFullBitree */ 5.15 轉換的二叉樹為： 5.16 對應的森林分別為： C 5.17 typedef char elemtype; typedef struct { elemtype data;

54、 int parent; } NodeType; (1) 求樹中結點雙親的算法: int Parent(NodeType t[], elemtype x){ /* x不存在時返回-2,否則返回x雙親的下標(根的雙親為-1 */ for(i=0;i

55、ypex){ for(i=0;i=MAXNODE) printf(“x不存在\n〞); else { flag=0; for(j=0;j

56、tf(“x無孩子\n〞); } }/*Children*/ 5.18 typedef char elemtype; typedef struct ChildNode { int childcode; struct ChildNode *nextchild; } typedef struct { elemtype data; struct ChildNode *firstchild; } NodeType; (1) 求樹中結點雙親的算法: int ParentCL(NodeType t[], elemtype

57、 x){ /* x不存在時返回-2, 否則返回x雙親的下標 */ for(i=0;i=MAXNODE) return -2; /* x不存在 */ /*搜索x的雙親*/ for(i=0;inextchild) if(loc==p->childcode) retu

58、rn i; /*返回x結點的雙親下標*/ }/* ParentL */ (2) 求樹中結點孩子的算法: void ChildrenCL(NodeType t[], elemtypex){ for(i=0;inextchild) { printf(“x的孩子:%c\n〞,t[p-> childcode].data); flag=1; } if(flag==0) prin

59、tf(“x無孩子\n〞); return; }/*if*/ printf(“x不存在\n〞); return; }/* ChildrenL */ 5.19 typedef char elemtype; typedef struct TreeNode { elemtype data; struct TreeNode *firstchild; struct TreeNode *nextsibling; } NodeType; void ChildrenCSL

60、(NodeType *t, elemtypex){ /* 層次遍歷方法 */ Init_Queue(Q); /* 初始化隊列 */ In_Queue(Q,t); count=0; while(!Empty_Queue (Q)){ Out_Queue(Q,p); if(p->data==x) { /*輸出x的孩子*/ p=p->firstchild; if(!p) printf(“無孩子\n〞); else { printf(“x的第%i個孩子:%c\n〞,++count, p->data);/*輸出第一個孩子*/ p=p->nextsibli

61、ng; /*沿右分支*/ while(p){ printf(“x的第%i個孩子:%c\n〞, ++count, p->data); p=p-> nextsibling; } } return; } if(p-> firstchild) In_Queue(Q,p-> firstchild); if(p-> nextsibling) In_Queue(Q,p-> nextsibling); } }/* ChildrenCSL */ 5.20 (1) 哈夫曼

62、樹為: 69 28 16 9 41 19 22 10 5 12 7 4 3 (2) 在上述哈夫曼樹的每個左分支上標以1，右分支上標以0，并設這7個字母分別為A、B、C、D、E、F和H，如以以以下圖所示： 則它們的哈夫曼樹為分別為: A：1100 B：1101 C：10 D：011 E：00 F：010 H：111 習題6參考答案 6.1 選擇題 〔1〕C 〔2〕A 〔3〕B〔4〕C〔5〕B______條邊?！?〕B〔7〕A〔8〕A〔9〕B〔10〕A 〔11〕A〔12〕A〔13〕B〔14〕A〔15〕B〔16〕A〔17〕C 6.2 填空

63、〔1〕 4 〔2〕 1對多 ; 多對多 〔3〕 n-1 ; n 〔4〕 0_ 〔5〕 有向圖 〔6〕 1 〔7〕 一半 〔8〕 一半 〔9〕___第i個鏈表中邊表結點數___ 〔10〕___第i個鏈表中邊表結點數___ 〔11〕深度優(yōu)先遍歷；廣度優(yōu)先遍歷 〔12〕O〔n2〕 〔13〕___無回路 6.3 〔1〕鄰接矩陣: 〔2〕鄰接鏈表： 〔3〕每個頂點的度： 頂點 度 V1 3 V2 3 V3

64、 2 V4 3 V53 6.4 〔1〕鄰接鏈表： 〔2〕逆鄰接鏈表： 〔3〕頂點入度出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 3 6.5 〔1〕深度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2 〔1〕廣度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3

65、V2 V5 6.6 有兩個連通分量： 6.7 頂點 〔1〕 〔2〕 〔3〕 〔4〕 〔5〕 Low Close Cost Vex Low Close Cost Vex Low Close Cost Vex Low Close Cost Vex Low Close Cost Vex V1 0 1 0 1 0 1 0 1 0 1 V2 1 1 0 1 0 1 1 0 1 0 1 V3 1 1 1

66、 1 0 1 0 1 0 1 V4 3 1 2 2 2 2 0 2 0 2 V5 ∞ 1 5 2 3 3 2 4 0 4 U {v1} {v1,v2} {v1,v2,v3} {v1, v2, v3, v4} {v1, v2, v3, v4, v5} T {} { (v1,v2) } {(v1,v2), (v1,v3) } {(v1,v2), (v1,v3), (v2,v4) } {(v1,v2), (v1,v3), (v2,v4), (v4,v5) } 最小生成樹的示意圖如下： 6.8 拓撲排序結果： V3à V1 à V4 à V5 à V2 à V6 6.9 〔1〕建設無向圖鄰接矩陣算法： 提示：參見算法6.1 因為無向圖的鄰接矩陣是對稱的，所以有 for (k=0; ke; k++) /*輸入e條邊，建設無向圖鄰接矩陣*/ { scanf