數(shù)據(jù)結(jié)構(gòu)[第4版]習(xí)題和實(shí)驗(yàn)答案數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料（完整版）[c語(yǔ)言版]

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

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

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

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

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

5、 A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是〔 B 〕 A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一個(gè)單鏈表中，假設(shè)刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(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、在一個(gè)單鏈表中，假設(shè)在p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)，則執(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、在一個(gè)單鏈表中，q是p的前趨結(jié)點(diǎn)，假設(shè)在q和p之間插入結(jié)點(diǎn)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)造中，第一個(gè)結(jié)點(diǎn) 沒(méi)有 前趨結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前趨結(jié)點(diǎn)。 棧和隊(duì)列 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用順序存儲(chǔ)構(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、向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，執(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、從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪結(jié)點(diǎn)的值，則執(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、用單鏈表表示的鏈?zhǔn)娟?duì)列的隊(duì)頭在鏈表的〔 A 〕位置。 A、鏈頭 B、鏈尾 C、鏈中 6、判定一個(gè)鏈隊(duì)列Ｑ〔最多元素個(gè)數(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、在鏈隊(duì)列Ｑ中，插入要所指結(jié)點(diǎn)需順序執(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、在一個(gè)鏈隊(duì)列Q中，刪除一個(gè)結(jié)點(diǎn)需要執(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、棧和隊(duì)列的共同點(diǎn)〔 C 〕 A、都是先進(jìn)后出 B、都是先進(jìn)先出 C、只允許在端點(diǎn)處插入和刪除元素 D、沒(méi)有共同點(diǎn) 10

11、、棧的特點(diǎn)是_先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出 11、線性表、棧和隊(duì)列都是線性構(gòu)造，可以在線性表的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入元素和在隊(duì)首刪除元素。 串和數(shù)組 1、設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)Concat(x,y)返回x和y串的連接串，Substr(s,I,j)返回串s從序號(hào)i開(kāi)場(chǎng)的j個(gè)字符組成的子串，length(s)返回串s的長(zhǎng)度，則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á)在〔 D 〕 A、可以順序存儲(chǔ) B、數(shù)據(jù)元素是一個(gè)字符 C、可以鏈接存儲(chǔ) D、數(shù)據(jù)元素可以是多個(gè)字符 3、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作〔 B 〕 A、連接 B、模式匹配 C、求子串聯(lián) D、求串長(zhǎng) 4、串的兩種最 基本的存儲(chǔ)方式是順序存儲(chǔ)方式和鏈接存儲(chǔ)方式。 樹(shù)和二叉樹(shù) 1、樹(shù)最適宜用來(lái)表示〔 B 〕 A、有序數(shù)據(jù)元素 B、元素之間具有分支層次關(guān)系的數(shù)據(jù) C、無(wú)序數(shù)據(jù)元素

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

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

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

17、前序遍歷序列為ABCDEFG，試問(wèn)能不能惟一確定一棵二叉樹(shù)，假設(shè)能請(qǐng)畫(huà)出該二叉樹(shù)。假設(shè)給定前序遍歷序列和后序遍歷序列，能否惟一確定一棵二叉樹(shù)，說(shuō)明理由。 答： ⑴由中序遍歷序列和前序遍歷序列或中序遍歷序列和后序遍歷序列可以惟一確定一棵二叉樹(shù)。 基本思想是前序〔后序〕定根，中序分左右。 對(duì)于給定的前序和中序序列?？纱_定根結(jié)點(diǎn)為A，以A為根的左子樹(shù)結(jié)點(diǎn)為B，C，D，右子樹(shù)結(jié)點(diǎn)為E，F(xiàn)，G。進(jìn)一步可確定所有子樹(shù)的根結(jié)點(diǎn)，因而也就確定了整個(gè)二叉樹(shù)。對(duì)應(yīng)的二叉樹(shù)如以以下圖： F A D G F E C B ⑵由前序遍歷和后序遍歷序列不能惟一確定一棵二叉樹(shù)。如以以下圖為4棵不

18、同的二叉樹(shù)，它們的前序遍歷序列都是ABC，而后序遍歷序列都是CBA。 A C B C B A A C B A C B 12、設(shè)二叉樹(shù)bt的存儲(chǔ)構(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為樹(shù)根結(jié)點(diǎn)指針，left，right分別為結(jié)點(diǎn)的左右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域，請(qǐng)完成以下各題： ⑴畫(huà)出二叉樹(shù)

19、bt的邏輯構(gòu)造 ⑵寫(xiě)出按前序、中序和后序遍歷二叉樹(shù)bt所得到的結(jié)點(diǎn)序列。 答： ⑴二叉樹(shù)bt的邏輯構(gòu)造如以以下圖： 12 a j i g h f d e c b ⑵前序遍歷：abcedfhgij 中序遍歷：ecbhfdjiga 后序遍歷：echfjigdba 13、給定一棵以二叉鏈表存儲(chǔ)構(gòu)造表示的二叉樹(shù)，其根結(jié)點(diǎn)指針為T(mén)，試寫(xiě)出求二叉樹(shù)的葉子數(shù)目的算法。 int CountLeaf (BiTree T){ //返回指針T所指二叉樹(shù)中所有葉子結(jié)點(diǎn)個(gè)數(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、給定一棵以二叉鏈表存儲(chǔ)構(gòu)造表示的二叉樹(shù)，其根結(jié)點(diǎn)指針為T(mén)，試寫(xiě)出求二叉樹(shù)的深度的算法。 int Depth (BiTree T ){ // 返回二叉樹(shù)的深度 if ( !T ) depthval = 0; else { depthLeft = Depth

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

22、 C、7 D、8 3、存儲(chǔ)稀疏圖的數(shù)據(jù)構(gòu)造常用的是〔 C 〕 A、鄰接矩陣 B、三元組 C、鄰接表 D、十字鏈表 4、在有向圖的鄰接表存儲(chǔ)構(gòu)造中，頂點(diǎn)V在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)是〔 C 〕 A、頂點(diǎn)V的度 B、頂點(diǎn)V的出度 C、頂點(diǎn)V的入度 D、依附于頂點(diǎn)V的邊數(shù) 5、用DFS遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS算法退棧返回時(shí)，打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是〔 A 〕 A、逆拓?fù)溆行虻? B、拓?fù)溆行虻? C、無(wú)序的 6、一個(gè)圖如以以下圖，假設(shè)從頂點(diǎn)a出

23、發(fā)按深度優(yōu)先搜索法進(jìn)展遍歷，則可能得到的一種頂點(diǎn)序列為〔 D 〕，按廣度優(yōu)先搜索法進(jìn)展遍歷，則可能得到的一種頂點(diǎn)序列為〔 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、采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先搜索遍歷算法類似于二叉樹(shù)的〔 D 〕 A、中序遍歷 B、先序遍歷 C、后序遍歷 D、按層遍歷 8、一個(gè)圖如以以下圖，則由該圖得到的一種拓?fù)湫蛄袨?/p>

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)造中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以___任意多個(gè)_______。 10、在AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)各活動(dòng)時(shí)間總和最長(zhǎng)的路徑稱為關(guān)鍵路徑。 11、給出圖G，如以以下圖： 1 11 10 9 8 7 6 5 4 3 2 〔1〕給出圖G的鄰接表〔畫(huà)圖即可〕 〔2〕在你給出的鄰接表的情況下，以頂點(diǎn)V4為根，畫(huà)出

25、圖G的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。 〔3〕將你畫(huà)出的廣度優(yōu)先生成樹(shù)轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)。 答： 〔1〕圖的鄰接表如以以以下圖所示：略 〔2〕以頂點(diǎn)V4為根的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)如以以下圖 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)先生成樹(shù)轉(zhuǎn)換成二叉樹(shù)如以以以下圖所示 1 1 10 9 11 7 8 6 3 4 5 2 附錄 習(xí)題及實(shí)驗(yàn)參考答案 習(xí)題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)造 樹(shù)型構(gòu)造 圖構(gòu)造 (4). 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 索引存儲(chǔ) 散列表〔Hash〕存儲(chǔ) (5). 變量的取值范圍 操作的類別 (6). 數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系 (7). 關(guān)系 網(wǎng)狀構(gòu)造 樹(shù)構(gòu)造 (8). 空間復(fù)雜度和時(shí)間復(fù)雜度 (9). 空間 時(shí)間 (10). Ο(n) 1.3名

27、詞解釋如下： 數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計(jì)算機(jī)程序加工和處理的對(duì)象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)指不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段或域。 數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的 基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)展考慮和處理，一個(gè)數(shù)據(jù)元素可由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成。 數(shù)據(jù)邏輯構(gòu)造：數(shù)據(jù)的邏輯構(gòu)造就是指數(shù)據(jù)元素間的關(guān)系。 數(shù)據(jù)存儲(chǔ)構(gòu)造：數(shù)據(jù)的物理構(gòu)造表示數(shù)據(jù)元素的存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。 數(shù)據(jù)類型：是指變量的取值范圍和所能夠進(jìn)展的操作的總和。 算法：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。 1.4語(yǔ)句的時(shí)間復(fù)雜度為： (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)’ } 習(xí)題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). 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) (3). Ｏ(n)O(n) (4). n-i+1 n-i (5). 鏈?zhǔn)? (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中元素個(gè)數(shù)為n,將下標(biāo)為0，1,2,…,〔n-1〕/2的元素依次與下標(biāo)為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--) // 移動(dòng)線性表中元素，然后插入元素x a[k+1]=a[k]; a[i]=x; for(i=0;i<=n;i++) // 依次輸出線性表中的元素 printf(“%f〞,a[i]); } 2.6算法思路：依次掃描A和B的元素，對(duì)

35、比A、B當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個(gè)線性表掃描完畢，最后將未掃描完順序表中的余下局部賦給C即可。C的容量要能夠容納A、B兩個(gè)線性表相加的長(zhǎng)度。 有序表的合并算法： 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的元素對(duì)比，將值相等的元素賦給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； } 習(xí)題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ù)組來(lái)表示的 線性表一般有插入、刪除、讀取等對(duì)于任意元

39、素的操作 而棧只是一種特殊的線性表 棧只能在線性表的一端插入〔稱為入棧,push〕或者讀取棧頂元素或者稱為“彈出、出棧〞(pop)。 3.4 答：一樣點(diǎn)：棧和隊(duì)列都是特殊的線性表，只在端點(diǎn)處進(jìn)展插入，刪除操作。 不同點(diǎn)：棧只在一端〔棧頂〕進(jìn)展插入，刪除操作；隊(duì)列在一端〔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，按如下方式進(jìn)展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[]) //將十進(jìn)制數(shù)轉(zhuǎn)換為2進(jìn)制存放在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); //打印 } } 習(xí)題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） 串長(zhǎng)相等且對(duì)應(yīng)位置字符相等 （2） 不含任何元素的串，0 （3） 所含字符均是空格，所含空格數(shù) （4） 10 （5） “helloboy〞 （6） 18 （7） 1066 （8） 由零個(gè)或多個(gè)任意字符組成的字符序列 （9） 串中所含不同字符的個(gè)數(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í)行過(guò)程中只能引用不能改變；串變量的值在程序執(zhí)行過(guò)程中是可以改變和重新賦值的 主串與子串：子串是主串的一個(gè)子集 串變量的名字與串變量的值:串變量的名字表示串值的標(biāo)識(shí)符 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 矩陣的三元組表 習(xí)題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樹(shù) 〔9〕其第一個(gè)孩子; 下一個(gè)兄弟 〔10〕先序遍

47、歷；中序遍歷 5.3 葉子結(jié)點(diǎn):C、F、G、L、I、M、K； 非終端結(jié)點(diǎn)：A、B、D、E、J； 各結(jié)點(diǎn)的度： 結(jié)點(diǎn)： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0 樹(shù)深：4 5.4 無(wú)序樹(shù)形態(tài)如下： 二叉樹(shù)形態(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) 先序序列和中序序列一樣：空樹(shù)或缺左子樹(shù)的單支樹(shù)； (2) 后序序列和中序序列一樣：空樹(shù)或缺右子樹(shù)的單支樹(shù)； (3) 先序序列和后序序列一樣：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。 5.8 這棵二叉樹(shù)為: 5.9 先根遍歷序列:ABFGLCDIEJMK 后根遍歷序列:FGLBCIDMJKEA

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

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é)點(diǎn)數(shù)為：n0 = n (k-1) / k 5.12 int NodeCount(BiTree T) {//計(jì)算結(jié)點(diǎn)總數(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所指二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)相互交換 */ 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); /* 初始化隊(duì)列*/ flag=0; In_Queue(Q，T); /* 根指針入隊(duì)列 ，按層次遍歷*/ while(!Empty_Queue (Q)) { Out_Queue(Q,p); if(!p) flag=1; /* 假設(shè)本次出隊(duì)列的是空指針時(shí)，則修改flag值為1。假設(shè)以后出隊(duì)列的指針存在非空，則可斷定不是完全二叉樹(shù) */ else if (flag) return 0; /*斷定不是完全二叉樹(shù) */ else {

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

54、 int parent; } NodeType; (1) 求樹(shù)中結(jié)點(diǎn)雙親的算法: int Parent(NodeType t[], elemtype x){ /* x不存在時(shí)返回-2,否則返回x雙親的下標(biāo)(根的雙親為-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無(wú)孩子\n〞); } }/*Children*/ 5.18 typedef char elemtype; typedef struct ChildNode { int childcode; struct ChildNode *nextchild; } typedef struct { elemtype data; struct ChildNode *firstchild; } NodeType; (1) 求樹(shù)中結(jié)點(diǎn)雙親的算法: int ParentCL(NodeType t[], elemtype

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

58、rn i; /*返回x結(jié)點(diǎn)的雙親下標(biāo)*/ }/* ParentL */ (2) 求樹(shù)中結(jié)點(diǎn)孩子的算法: 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無(wú)孩子\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); /* 初始化隊(duì)列 */ 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(“無(wú)孩子\n〞); else { printf(“x的第%i個(gè)孩子:%c\n〞,++count, p->data);/*輸出第一個(gè)孩子*/ p=p->nextsibli

61、ng; /*沿右分支*/ while(p){ printf(“x的第%i個(gè)孩子:%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、樹(shù)為: 69 28 16 9 41 19 22 10 5 12 7 4 3 (2) 在上述哈夫曼樹(shù)的每個(gè)左分支上標(biāo)以1，右分支上標(biāo)以0，并設(shè)這7個(gè)字母分別為A、B、C、D、E、F和H，如以以以下圖所示： 則它們的哈夫曼樹(shù)為分別為: A：1100 B：1101 C：10 D：011 E：00 F：010 H：111 習(xí)題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對(duì)多 ; 多對(duì)多 〔3〕 n-1 ; n 〔4〕 0_ 〔5〕 有向圖 〔6〕 1 〔7〕 一半 〔8〕 一半 〔9〕___第i個(gè)鏈表中邊表結(jié)點(diǎn)數(shù)___ 〔10〕___第i個(gè)鏈表中邊表結(jié)點(diǎn)數(shù)___ 〔11〕深度優(yōu)先遍歷；廣度優(yōu)先遍歷 〔12〕O〔n2〕 〔13〕___無(wú)回路 6.3 〔1〕鄰接矩陣: 〔2〕鄰接鏈表： 〔3〕每個(gè)頂點(diǎn)的度： 頂點(diǎn) 度 V1 3 V2 3 V3

64、 2 V4 3 V53 6.4 〔1〕鄰接鏈表： 〔2〕逆鄰接鏈表： 〔3〕頂點(diǎn)入度出度 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 有兩個(gè)連通分量： 6.7 頂點(diǎn) 〔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) } 最小生成樹(shù)的示意圖如下： 6.8 拓?fù)渑判蚪Y(jié)果： V3à V1 à V4 à V5 à V2 à V6 6.9 〔1〕建設(shè)無(wú)向圖鄰接矩陣算法： 提示：參見(jiàn)算法6.1 因?yàn)闊o(wú)向圖的鄰接矩陣是對(duì)稱的，所以有 for (k=0; ke; k++) /*輸入e條邊，建設(shè)無(wú)向圖鄰接矩陣*/ { scanf