《數(shù)據(jù)結(jié)構(gòu)[第4版]習題和實驗答案數(shù)據(jù)結(jié)構(gòu)復習資料（完整版）[c語言版]》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)[第4版]習題和實驗答案數(shù)據(jù)結(jié)構(gòu)復習資料（完整版）[c語言版]（41頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

3、性表的存儲構(gòu)造包括順序存儲構(gòu)造和鏈式存儲構(gòu)造兩種。 2、表長為n的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均次數(shù)為〔 E 〕，刪除一個元素需要移動的元素的個數(shù)為〔 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、“線性表的邏輯順序與存儲順序總是一致的。〞這個結(jié)論是〔 B 〕 A、正確的 B、錯誤的 C、不一定，與具體的構(gòu)造有關(guān) 4、線性表采用鏈式存儲構(gòu)造時，要求內(nèi)存中可用存儲單元的地址〔

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

5、 A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度是〔 B 〕 A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一個單鏈表中，假設(shè)刪除p所指結(jié)點的后繼結(jié)點，則執(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、在一個單鏈表中，假設(shè)在p所指結(jié)點之后插入s所指結(jié)點，則執(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的前趨結(jié)點，假設(shè)在q和p之間插入結(jié)點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、在線性構(gòu)造中，第一個結(jié)點 沒有 前趨結(jié)點，其余每個結(jié)點有且只有 1 個前趨結(jié)點。 棧和隊列 1、在棧操作中，輸入序列為〔A，B，C，D〕，不可能得到的輸出數(shù)列是〔 D 〕 A、〔A，B，C，D〕 B、〔D，C，B，A〕 C、〔A，C，D，B〕 D、〔C，A，D，B〕 2、設(shè)棧ST用順序存儲構(gòu)造表示，則棧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結(jié)點時，執(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的鏈棧中刪除一個結(jié)點，用x保存被刪結(jié)點的值，則執(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、判定一個鏈隊列Ｑ〔最多元素個數(shù)為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、在鏈隊列Ｑ中，插入要所指結(jié)點需順序執(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中，刪除一個結(jié)點需要執(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、線性表、棧和隊列都是線性構(gòu)造，可以在線性表的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入元素和在隊首刪除元素。 串和數(shù)組 1、設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)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))的結(jié)果串是〔 D 〕 A、BCDEF B、BCDEF

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

13、 D、元素之間無聯(lián)系的數(shù)據(jù) 2、按照二叉樹的定義，具有3個結(jié)點的二叉樹有〔 C 〕種。 A、3 B、4 C、5 D、6 3、在一棵有n個結(jié)點的二叉樹中，假設(shè)度為2的結(jié)點數(shù)為n2，度為1的結(jié)點數(shù)為n1，度為0的結(jié)點數(shù)為n0，則樹的最大高度為〔 E 〕，其葉結(jié)點數(shù)為〔 G 〕；樹的最小高度為〔 B 〕，其葉結(jié)點數(shù)為〔 G 〕；假設(shè)采用鏈表存儲構(gòu)造，則有〔 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層的結(jié)點數(shù)最多為〔 B 〕?！布僭O(shè)根結(jié)點的層數(shù)為0〕 A、8 B、16 C、15 D、32 5、深度為5的二叉樹至多有〔 C 〕個結(jié)點。 A、16 B、32 C、31 D、10 6、在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊〔 A 〕 A、只有右子樹上的所有結(jié)點 B、只有右子樹上的局部結(jié)點 C、只有左子樹上的局部結(jié)點 D、只有左子樹

15、上的所有結(jié)點 7、一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI，則在先序遍歷中結(jié)點E的直接前趨為〔 D 〕，后序遍歷中結(jié)點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、在樹形構(gòu)造中，樹根結(jié)點沒有___前趨________結(jié)點，其余每個結(jié)點有且只有_______1______個前趨結(jié)點；葉子結(jié)點沒有___

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

17、前序遍歷序列為ABCDEFG，試問能不能惟一確定一棵二叉樹，假設(shè)能請畫出該二叉樹。假設(shè)給定前序遍歷序列和后序遍歷序列，能否惟一確定一棵二叉樹，說明理由。 答： ⑴由中序遍歷序列和前序遍歷序列或中序遍歷序列和后序遍歷序列可以惟一確定一棵二叉樹。 基本思想是前序〔后序〕定根，中序分左右。 對于給定的前序和中序序列?？纱_定根結(jié)點為A，以A為根的左子樹結(jié)點為B，C，D，右子樹結(jié)點為E，F(xiàn)，G。進一步可確定所有子樹的根結(jié)點，因而也就確定了整個二叉樹。對應的二叉樹如以以下圖： 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、設(shè)二叉樹bt的存儲構(gòu)造如下： 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為樹根結(jié)點指針，left，right分別為結(jié)點的左右孩子指針域，data為結(jié)點的數(shù)據(jù)域，請完成以下各題： ⑴畫出二叉樹

19、bt的邏輯構(gòu)造 ⑵寫出按前序、中序和后序遍歷二叉樹bt所得到的結(jié)點序列。 答： ⑴二叉樹bt的邏輯構(gòu)造如以以下圖： 12 a j i g h f d e c b ⑵前序遍歷：abcedfhgij 中序遍歷：ecbhfdjiga 后序遍歷：echfjigdba 13、給定一棵以二叉鏈表存儲構(gòu)造表示的二叉樹，其根結(jié)點指針為T，試寫出求二叉樹的葉子數(shù)目的算法。 int CountLeaf (BiTree T){ //返回指針T所指二叉樹中所有葉子結(jié)點個數(shù) 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、給定一棵以二叉鏈表存儲構(gòu)造表示的二叉樹，其根結(jié)點指針為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、存儲稀疏圖的數(shù)據(jù)構(gòu)造常用的是〔 C 〕 A、鄰接矩陣 B、三元組 C、鄰接表 D、十字鏈表 4、在有向圖的鄰接表存儲構(gòu)造中，頂點V在表結(jié)點中出現(xiàn)的次數(shù)是〔 C 〕 A、頂點V的度 B、頂點V的出度 C、頂點V的入度 D、依附于頂點V的邊數(shù) 5、用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時，打印出相應的頂點，則輸出的頂點序列是〔 A 〕 A、逆拓撲有序的 B、拓撲有序的 C、無序的 6、一個圖如以以下圖，假設(shè)從頂點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、在圖形構(gòu)造中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以___任意多個_______。 10、在AOE網(wǎng)中，從源點到匯點各活動時間總和最長的路徑稱為關(guān)鍵路徑。 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)先生成樹轉(zhuǎn)換為對應的二叉樹。 答： 〔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)先生成樹轉(zhuǎn)換成二叉樹如以以以下圖所示 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). 數(shù)據(jù) 關(guān)系 (2). 邏輯構(gòu)造 物理構(gòu)造 (3). 線性數(shù)據(jù)構(gòu)造 樹型構(gòu)造 圖構(gòu)造 (4). 順序存儲 鏈式存儲 索引存儲 散列表〔Hash〕存儲 (5). 變量的取值范圍 操作的類別 (6). 數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)元素存儲方式或者數(shù)據(jù)元素的物理關(guān)系 (7). 關(guān)系 網(wǎng)狀構(gòu)造 樹構(gòu)造 (8). 空間復雜度和時間復雜度 (9). 空間 時間 (10). Ο(n) 1.3名

27、詞解釋如下： 數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計算機程序加工和處理的對象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。 數(shù)據(jù)項：數(shù)據(jù)項指不可分割的、具有獨立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項有時也稱為字段或域。 數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的 基本單位，在計算機程序中通常作為一個整體進展考慮和處理，一個數(shù)據(jù)元素可由假設(shè)干個數(shù)據(jù)項組成。 數(shù)據(jù)邏輯構(gòu)造：數(shù)據(jù)的邏輯構(gòu)造就是指數(shù)據(jù)元素間的關(guān)系。 數(shù)據(jù)存儲構(gòu)造：數(shù)據(jù)的物理構(gòu)造表示數(shù)據(jù)元素的存儲方式或者數(shù)據(jù)元素的物理關(guān)系。 數(shù)據(jù)類型：是指變量的取值范圍和所能夠進展的操作的總和。 算法：是對特定問題求解步驟的一種描述，是指令的有限序列。 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). 數(shù)據(jù) 指針 (7). 前驅(qū) 后繼 (8). Ο(1)Ο(n) (9). s->next=p->next;

31、 p->next=s ; (10). s->next 2.3.解題思路：將順序表A中的元素輸入數(shù)組a，假設(shè)數(shù)組a中元素個數(shù)為n,將下標為0，1,2,…,〔n-1〕/2的元素依次與下標為n,n-1,…, 〔n-1〕/2的元素交換，輸出數(shù)組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 答：一般線性表使用數(shù)組來表示的 線性表一般有插入、刪除、讀取等對于任意元

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[]) //將十進制數(shù)轉(zhuǎn)換為2進制存放在a[]，并返回位數(shù) { 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; //假設(shè)棧元素為字符型 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） 所含字符均是空格，所含空格數(shù) （4） 10 （5） “helloboy〞 （6） 18 （7） 1066 （8） 由零個或多個任意字符組成的字符序列 （9） 串中所含不同字符的個數(shù) （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 葉子結(jié)點:C、F、G、L、I、M、K； 非終端結(jié)點：A、B、D、E、J； 各結(jié)點的度： 結(jié)點： 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) 先序序列和后序序列一樣：空樹或只有根結(jié)點的二叉樹。 5.8 這棵二叉樹為: 5.9 先根遍歷序列:ABFGLCDIEJMK 后根遍歷序列:FGLBCIDMJKEA

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

50、數(shù)為： n0 = n2 + 2n3 + …… + (m-1)nm + 1 5.11 由5.10結(jié)論得，n0 = (k-1)nk + 1 又由 n=n0 + nk，得nk= n-n0，代入上式，得 n0 = (k-1)〔n-n0〕+ 1 葉子結(jié)點數(shù)為：n0 = n (k-1) / k 5.12 int NodeCount(BiTree T) {//計算結(jié)點總數(shù) 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所指二叉樹中所有結(jié)點的左、右子樹相互交換 */ 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; /* 假設(shè)本次出隊列的是空指針時，則修改flag值為1。假設(shè)以后出隊列的指針存在非空，則可斷定不是完全二叉樹 */ else if (flag) return 0; /*斷定不是完全二叉樹 */ else {

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

54、 int parent; } NodeType; (1) 求樹中結(jié)點雙親的算法: 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) 求樹中結(jié)點雙親的算法: 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結(jié)點的雙親下標*/ }/* ParentL */ (2) 求樹中結(jié)點孩子的算法: 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，并設(shè)這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個鏈表中邊表結(jié)點數(shù)___ 〔10〕___第i個鏈表中邊表結(jié)點數(shù)___ 〔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 拓撲排序結(jié)果： V3à V1 à V4 à V5 à V2 à V6 6.9 〔1〕建設(shè)無向圖鄰接矩陣算法： 提示：參見算法6.1 因為無向圖的鄰接矩陣是對稱的，所以有 for (k=0; ke; k++) /*輸入e條邊，建設(shè)無向圖鄰接矩陣*/ { scanf