數(shù)據(jù)結構課后習題答案1

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結構課后習題答案1習題1

1．解釋以下概念：規(guī)律結構，存儲結構，操作，數(shù)據(jù)結構，數(shù)據(jù)結構的表示，數(shù)據(jù)結構的實現(xiàn)，抽象數(shù)據(jù)類型，算法，算法的時間代價，算法的空間代價，大O表示法。

2．理解以下關系：算法與數(shù)據(jù)結構的關系；數(shù)據(jù)結構與抽象數(shù)據(jù)類型的關系；算法和數(shù)據(jù)結構與問題求解的關系。

3.寫出以下程序段的平均狀況下的時間代價O表示式。(1)a=b+c;d=a+e(2)sum=0;

for(i=0;i=(y+1)*(y+1))y++;(4)s=0;if(even(n))

for(i=0;i0){

if(x>lO0){x=x-10;n=n-1;}elsex=x+1;}

4．對于給定的n個元素，可以構造出有，，，四種。

規(guī)律結構

的5.按增長率由小到大的順序排列以下各函數(shù)：

33n2n4nn

2,(),(),(),n,n2,n!,n,log2n,n/log2n

233100

習題2

2.1已知L是無頭結點的單鏈表，且p結點既不是第一個結點，也不是最終一個結點，試從以下提供的語句中選出適合的語句序列：(1)在p結點之后插入s結點：(2)在p結點之前插入s結點：(3)在單鏈表L首插入s結點：(4)在單鏈表L后插入s結點：提供的語句：

①p->next＝s；②p->next＝p->next->next；③p->next=s->next；④s->next=p->next；⑤s->next＝L；⑥s->next=p；⑦s->next=NULL；⑧q＝p；

⑨while(p->next!=q)p=p->next；⑩while(p->next!=NULL)p=p->next；⑾p=q；⑿p=L；⒀L＝s；⒁L＝p；

2.2已知p結點是某雙向鏈表的中間結點，試從以下提供的語句中選出適合的語句序列。

(1)在p結點之后插入s結點：(2)在p結點之前插入s結點：(3)刪除p結點的直接后繼結點：(4)刪除p結點的直接前驅(qū)結點：提供的語句：

①p->next＝p->next->next；②p->prior=p->prior->prior；③p->next=s；④p->prior=s；⑤s->next=p；⑥s->prior＝p；

⑦s->next=p->next；⑧s->prior=p->prior；⑨p->prior->next=p->next；⑩p->prior->next＝p；⑾p->next->prior＝p；⑿p->next->prior＝s；

⒀p->prior->next=s；⒁p->next->prior=p->prior；⒂q=p->next；⒃q=p->prior；⒄free(p)；⒅free(q)；

2.3試編寫一個計算頭結點指針為L的單鏈表長度的算法。2.4試編寫一個將單循環(huán)鏈表逆置的算法。

2.5已知一順序表A，其元素值非遞減有序排列，編寫一個算法，刪除順序表中多余的值一致的元素。

習題3

3.1簡述棧和線性表的區(qū)別。簡述棧和隊列的一致點和不同點。

3.2假使進棧的數(shù)據(jù)元素序列為1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、3、5、4、2、6的出棧序列?并說明為什么得不到或如何得到。3.3利用兩個棧模擬一個隊列的入隊、出隊和判斷隊列空的運算。3.4寫一算法，將一個順序棧中的元素依次取出，并打印元素值。3.5寫一算法，將一個非負十進制整數(shù)轉換成二進制。

3.6寫一算法，將一個鏈式隊列中的元素依次取出，并打印元素值。

3.7設有編號為1、2、3、4的4輛車，順序進入一個棧式結構的站臺，試寫出這4輛車開出站臺的所有可能的順序。

3.8寫一個算法，借助于棧將一個單鏈表逆置。

習題4

4.1空串和空格串有什么區(qū)別?

4.2兩個字符串相等的充要條件是什么?4.3串的三種機內(nèi)表示方法是什么?

4.4設S＝'Iamastudent'，T＝'good'，Q＝'worker'。求：(1)StrLength(S)

(2)SubString(&Sub，S，8，7)(3)SubString(&Sub，T，2，1)(4)Index(S，'a'，1)(5)Index(S，T，1)

(6)Replace(&S，'Student'，Q)

(7)Concat(&N，SubString(&V，S，6，2)，Concat(&P，T，SubString(&W,S,7,8)))

4.5設A＝'This'，F(xiàn)＝'asample'，C＝'good'，D＝'ne'，B＝''，G＝'is'。求：

(1)Coneat(&S，A，Concat(&Z，SubString(&Y，F(xiàn)，2，7)，Concat(&X，B，SubString(A，3，2))))

(2)Concat(&U，SubString(&X，C，3，1)，D)(3)Replace(&F，SubString(&X，F(xiàn)，3，6)，C)(4)StrLength(S)(5)Index(V，G，1)(6)Index(U，G，1)

(7)Concat(&V，S，Concat(&Z，B，Concat(&Y，F(xiàn)，Concat(&X，B，U))))

4.6利用C的庫函數(shù)strlen、strcpy(或strcat)寫一個算法voidStrDelete(char*S,inti,intm)，刪除串S中從位置i開始連續(xù)的m個字符。若i≥strlen(S)，則沒有字符被刪除；若i+m≥strlen(S)，則S中從位置i開始直至末尾的字符均被刪去.。

4.7采用順序結構存儲串，編寫一個函數(shù)，求串s和串t的一個最長的公共子串。

提醒:需要采用三重循環(huán)來實現(xiàn)。

習題5

1.假設按行優(yōu)先存儲整數(shù)數(shù)組A[9][3][5][8]時，第一個元素的字節(jié)地址是100，每個整數(shù)占4個字節(jié)。問以下元素的存儲地址是什么?

(1)a0000(2)a1111(3)a3125(4)a82472.假設一個準對角矩陣

按以下方式存儲于一維數(shù)組B[4m]中：

寫出由一對下標(i,j)求k的轉換公式。3.現(xiàn)有如下的稀疏矩陣A，要求畫出三元組表示法。

習題6

10.假設用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10。試為這8個字母設計赫夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。

11．一棵度為2的樹與一棵二叉樹有何區(qū)別?樹與二叉樹之間有何區(qū)別?12．對于如下圖的樹，試給出：(1)雙親數(shù)組表示法示意圖；(2)孩子鏈表表示法示意圖；

(3)孩子兄弟鏈表表示法示意圖。

13．畫出下圖所示的森林經(jīng)轉換后所對應的二叉樹，并指出在二叉鏈表中某結點所對應的森林中結點為葉子結點的條件。

14．將如下圖的二叉樹轉換成相應的森林。

15．在具有n(n>1)個結點的各棵樹中，其中深度最小的那棵樹的深度是多少?它共有多少葉子和非葉子結點?其中深度最大的那棵樹的深度是多少?它共有多少葉子和非葉子結點?

16．畫出和以下已知序列對應的樹T：樹的先根訪問序列為：GFKDAIEBCHJ；樹的后根訪問序列為：DIAEKFCJHBG。17．畫出和以下已知序列對應的森林F：森林的先序訪問序列為：ABCDEFGHIJKL；森林的中序訪問序列為：CBEFDGAJIKLH。

18．對以孩子－兄弟鏈表表示的樹編寫計算樹的深度的算法。

習題7

1對于右圖所示的有向圖，試給出：(1)每個頂點的入度和出度。(2)鄰接矩陣。(3)鄰接表。(4)逆鄰接表。(5)強連通分量。

2設無向圖G如右圖所示，試給出：(1)該圖的鄰接矩陣。(2)該圖的鄰接表。(3)該圖的多重鄰接表。

(4)從v0出發(fā)的“深度優(yōu)先〞遍歷序列。(5)從v0出發(fā)的“廣度優(yōu)先〞遍歷序列。

3請對下邊的無向帶權圖，

(1)寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；(2)寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。

4對下圖所示的帶權有向圖G，試回復以下問題：

(1)求出G中從結點v1出發(fā)按深度優(yōu)先探尋遍歷G所得到結點序列；(2)求出G中從結點v1出發(fā)按廣度優(yōu)先探尋遍歷G所得的結點序列；

5對于下圖所示的帶權圖

(1)依照普里姆算法，