數(shù)據(jù)結(jié)構(gòu)習(xí)題答案習(xí)題

第1章解答

一、選擇題

1-5：DABBC6-10：DCCBC

二、填空題

1、數(shù)據(jù)元素，關(guān)系2、邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，運(yùn)算

3、線性結(jié)構(gòu)，非線性結(jié)構(gòu)4、一對(duì)一，一對(duì)多

5、前驅(qū)，1,后續(xù)，16、前驅(qū)，1,后續(xù)，任意多個(gè)

7、任意多個(gè)8、順序、鏈?zhǔn)健⑺饕?、散?/p>

9、插入、刪除、修改、查找、排序10、時(shí)間，效率

三、綜合題

1、答：(1)是線性結(jié)構(gòu)，(2)是樹形結(jié)構(gòu)，(3)圖結(jié)構(gòu)。

2、答：(a)是線性結(jié)構(gòu)，(b)是樹形結(jié)構(gòu)，(c)是有向圖。

3、答：(a)O(mxn),(b)O(n2),(c)O(log2n)

4、答：(1)優(yōu)點(diǎn)：根據(jù)exit報(bào)告值，可以知道錯(cuò)誤發(fā)生處。

缺點(diǎn)：每運(yùn)行一次程序，至多能發(fā)現(xiàn)一個(gè)錯(cuò)誤。

(2)優(yōu)點(diǎn)：利用函數(shù)返回值來提供錯(cuò)誤發(fā)生情況，可以根據(jù)嚴(yán)重程度作相應(yīng)的處理。

缺點(diǎn)：增加編程難度。

(3)優(yōu)點(diǎn)：利用函數(shù)參數(shù)來提供錯(cuò)誤發(fā)生情況，可以根據(jù)嚴(yán)重程度作相應(yīng)的處理。

缺點(diǎn)：增加編程難度并增加函數(shù)的參數(shù)資源.

5、答：(1)優(yōu)點(diǎn)：直接與外設(shè)建立聯(lián)系，可以減少存儲(chǔ)空間。

缺點(diǎn)：由于輸入輸出需要時(shí)間，程序運(yùn)行效率下降。

(2)優(yōu)點(diǎn)：傳遞速度快。缺點(diǎn)：增加存放數(shù)據(jù)的空間，增加棧的操作量。

(3)優(yōu)點(diǎn)：傳遞速度快。缺點(diǎn)：增加存放數(shù)據(jù)的空間，影響局部化。

第2章解答

一、選擇題

1~5：CADCA6~10：ACCAD

二、填空題

1、L->prior==L->next==L2、head->next==NULL

3、q->next4、O(n)

5、1006、n-i+1

7、n-i8、head->next==NULL

9、q->next=s;s->next=p;10、p->next=p->next->next;

三、判斷題

1?5：x/xxx6-10：乂x///

第3章解答

一、選擇題

1~5：CCDBA6~10：ABCCC11-15：DDAAD

二、填空題

1、32、(rear-front+M)%M3、n-14、615、15

6、線性，任何，棧頂，隊(duì)尾，隊(duì)首7、棧頂，棧底8、隊(duì)列

9、移動(dòng)棧頂指針10、移動(dòng)隊(duì)首指針

三、判斷題

1-5：，x/x/6~10：x//xx

四、綜合題

1：(1)123,132,213,231,321

(2)不能產(chǎn)生435612,可以產(chǎn)生135426

因?yàn)镾1S2S3S4X4X3S5X5S6X6X2X1,只能產(chǎn)生435621

S1X1S2S3X3S4S5X5X4X2S6X6,可以產(chǎn)生135426

2：若進(jìn)棧序列為a,b,c,d,全部可能的出棧序列是：

abed,abdc,aebd,aedb,adeb,bacd,badc,bead,beda,

bdca,cbad,cbda,edba,deba。

不可能的：adbe.bdac,edab,cadb,cadb>dabc,dacb.dbac,dbea,dcab。

3：由于隊(duì)列中操作遵循的原則是先進(jìn)先出，出隊(duì)元素的順序是bdefea,故元素進(jìn)隊(duì)的順序

也是bdefea,元素進(jìn)隊(duì)的順序與元素出棧的順序相同，在棧中存取數(shù)據(jù)遵循的原則是后進(jìn)先

出，要得到出棧序列bdefea,棧的容量至少是應(yīng)該存放3個(gè)元素的空間。

4：3425615+-/8*+

5：abc+*d-

第4章解答

一、選擇題

1~5：CACAB6~10：ABBBD

二、填空題

1、模式匹配2、143、對(duì)應(yīng)位置字符相同

4、不包含任何字符(長(zhǎng)度為0)的串；由一個(gè)或多個(gè)空格(僅由空格符)組成的串

5、20,36、被匹配的主串，子串7、6

8、(n-m+l)*m9、兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相同

10、“goodmoming","nin”,4,"goto"

三、應(yīng)用題

1：T=concat(concat(concat(substr(S,l,2),substr(S,6,l)),substr(S,4,2)),

concat(substr(S,7,1),substr(S,3,1)))

2：串S的長(zhǎng)度為n,其中的字符各不相同，所以S="(x+z)*y”中含1個(gè)字符的子串有n個(gè),

2個(gè)字符的子串有n-l個(gè)....含n-2個(gè)字符的子串有3個(gè)，含n-1個(gè)字符的子串有2個(gè),

共有非平凡子串的個(gè)數(shù)是n(n+l)/2-l?

3：串T的next和nextval函數(shù)值見下表：

下標(biāo)j1234567891011

串Tabcaaccbaca

next[j]01112211121

nextval[j]01102211020

第5章解答

一、選擇題

1~5：CBBDB6~10：ABCDB

二、判斷題

1~5：xx/x/6~10：x/x//

三、填空題

1、Loc(A[0][0])+(i*n+j)*k2、(x,y,z)3、按行優(yōu)先和按列優(yōu)先

4、三元數(shù)組，十字鏈表5、288B,1282,1072,12766、8950

7、行下標(biāo)，列下標(biāo)，元素值8、(a,b),(c,d),b,(d)

9、子表10、((b),((c,(d))))

四、綜合題

2、特殊矩陣是指具有相同值的矩陣元素或零元素的分布具有一定規(guī)律，可以將其壓縮存儲(chǔ)

在一維數(shù)組中，矩陣元素a”的下標(biāo)i和j與其在一維數(shù)中存放的下標(biāo)k之間存在一一對(duì)應(yīng)關(guān)

系，故不會(huì)失去隨機(jī)存取功能。

稀疏矩陣中零元素的分布沒有一定規(guī)律，可以將非零元素存于三元組表中，非零元素

au在三元組中的存放位置與i、j沒有對(duì)應(yīng)關(guān)系，故失去隨機(jī)存取功能。

3、n階對(duì)稱矩陣A中，2產(chǎn)細(xì)，可以僅存放下三角元素(或上三角元素)。

設(shè)r=max(i,j),c=min(i,j),

k=r(r-l)/2+c-l;

例如，4階對(duì)稱矩陣A,按行優(yōu)先順序存于一維數(shù)組F[10]中，

0123456789

alla21a22a31a32a33a41a42a43a44

當(dāng)i=3,j=2時(shí)，k=3*2/2+2-l=4;

當(dāng)i=2,j=3時(shí)>k=4

(2)當(dāng)對(duì)稱矩陣A按列優(yōu)先順序壓縮存放，若僅存放上三角元素，則有:

k=r(r-l)/2+c-l

例如，4階對(duì)稱矩陣A,按列優(yōu)先順序存于一維數(shù)組F[10]中，

0123456789

allal2a22al3a23a33al4a24a34a44

當(dāng)i=l,j=3時(shí)，k=3*2/2+Ll=3；當(dāng)i=3,j=l時(shí),k=3

第6章解答

一、選擇題

1?5：CBBDB6-10：CBABB11-15：DACDC

二、判斷題

1?5：/乂/乂乂6-10：xxxZZ11-15：///X/

三、填空題

1、Llog2nJ+l2、最小3、n2+l4、最大值5、5

6、517、988、2k-l9、3110、不能

四、綜合題

1：

(1)根結(jié)點(diǎn)：a(2)葉子結(jié)點(diǎn)：b,d,f,h,i,j,k

(3)k的祖先：a,c,g(4)j的兄弟:i(5)樹的深度為5

2：二叉樹形態(tài)3：答

A000

B101

C10000

D1001

EII

F10001

G01

H001

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

6：(1)樹形態(tài):7：答A

32

(2)帶權(quán)路徑長(zhǎng)度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79

8：(1)樹形態(tài):10答a：Oil,b：10,c：00,d：010,e：11

(2)帶權(quán)路徑長(zhǎng)度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129

9答:

11答：先序：FDBACEGIHJ,中序：ABCDEFGH1J,后序：ACBEDHJIGF

12答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。

即，在一般樹中若某結(jié)點(diǎn)只有一個(gè)孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個(gè)

孩子也有左右之分。

13答：(1)前序遍歷序列是：ABCDEFGH,(2)中序遍歷序列是：CBDEAGHF

(3)后序遍歷序列是：CEDBHGFA

第7章解答

一、選擇題

1~5：BBABB6~10：BACBB11-15：AAABD16-20：BCDDB

21-25：CABCA26-30：DBBBB

二、填空題

1、n-1條2、極小連通子圖3、鄰接矩陣4、深度優(yōu)先搜索

5、16、拓?fù)渑判?、圖的鄰接矩陣第i列中非零元素的個(gè)數(shù)

8、n-19、圖的鄰接矩陣第i行全置零10、出度

三、判斷題

1?5：xx/xx6~10：xxxxZ

四、綜合題

1答案：1,5,2,3,6,41,5,6,2,3,45,1,2,3,6,4

5,1,6,2,3,45,6,1,2,3,4

2答案：(1)最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間:(2)關(guān)鍵路徑:

(2)關(guān)鍵路徑

事件123456789

Ve064577161418

VI0668710161418

4答案:(1)是強(qiáng)連通圖(2)鄰接矩陣和鄰接表為:

0101V1—v2v4|

0010v2Tv3|

1000v3Avl

0010v4

5答案:

終點(diǎn)最短路徑求解

b6(a,b)5(a,c,b)

c3(a,c)

d006(a,c,d)6(a,c,d)

e007(a,c,e)7(a,c,e)7(a,c,e)

fco00009(a,c,d,D9(a,c,d,D

vjcbdef

s{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f}

第9章解答

一、選擇題

1?5：ADDAA6?10：CBCCC

二、填空題

1、散列地址空間大小2、23、沖突4、中序5、大，小

6>47、28、m,「m/2],m-1,9、m,「m72〕10>63

三、判斷題

1~5：又//x/

四、綜合題

I答案：(1)表形態(tài)：

012345678910

22014613304153

1112311

(2)ASL：ASL(7)=(1*5+2*1+3*1)/7=(5+2+3)/7=10/7

2答案：(1)表形態(tài)：

9123￡678^9101112

14276855192084231011

1212113122

(2)平均查找長(zhǎng)度：ASL(10)=(1*5+2*4+3*1)/10=1.6

3答案：

ASL：ASL(9)=(1*1+2*2+3*3+3*4)/9=26/9

4答案：(1)表形態(tài)：

0I2345678910II1213141516171K

27I1455688419201023II77

312123II3111

(2)ASL：ASL(12)=(1*7+2*2+3*3)/7=(7+4+9)/12=5/3

5答案：表形態(tài)：

下標(biāo)0123456789101112

數(shù)組R132624518911

比較次數(shù)12111211

(2)ASL：ASL(8)=(l*6+2*2)/7=(6+4)/8=5/4

第10章解答

一、選擇題1~5：CCBDC6~10：BCDBD

二、填空題

1、遞增排列，遞減排列2、希爾排序、選擇排序、快速排序、堆排序

3、84,79,56,38,40,464、冒泡排序5、選擇排序

6、希爾、快速、堆、歸并7、歸并8、40,30,50,80,70,609、選擇10、3

三、判斷題1-5：/XX//

四、綜合題

1答案:初始：54,23,89,48,64,,50,,25,90,34

1：(23,54),89,48,64,50,25,90,34

2：(23,54,89),48,64,50,