數(shù)據(jù)結(jié)構(gòu)與算法期中練習(xí)題答案

《數(shù)據(jù)結(jié)構(gòu)與算法》期中練習(xí)題寫出以下各詞語的對(duì)應(yīng)中文queue隊(duì)列singlylinkedlists單鏈表storgestructure存儲(chǔ)結(jié)構(gòu)timecomplexity時(shí)間復(fù)雜度AbstractDataType(ADT)抽象數(shù)據(jù)類型選擇題1、在數(shù)據(jù)結(jié)構(gòu)中，線性結(jié)構(gòu)中元素之間存在__A__關(guān)系。

A:一對(duì)一

B:一對(duì)多

C:多對(duì)一

D:多對(duì)多2、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的B___和運(yùn)算等的學(xué)科。A:結(jié)構(gòu)

B:關(guān)系

C:操作

D:算法3、算法分析的兩個(gè)主要方面是__A__。A:空間復(fù)雜度和時(shí)間復(fù)雜度

B:正確性和簡明性

C:可讀性和文檔性

D:數(shù)據(jù)復(fù)雜性和程序復(fù)雜性4、順序表中邏輯上相鄰的節(jié)點(diǎn)其物理位置也___A_。A:一定相鄰

B:不必相鄰

C:按某種規(guī)律排列

D:無要求5、下面兩個(gè)圖各表現(xiàn)一批數(shù)據(jù)的結(jié)構(gòu)，其中C。A:左邊表現(xiàn)的是邏輯結(jié)構(gòu)，右邊表現(xiàn)的是物理結(jié)構(gòu)B:右邊表現(xiàn)的是邏輯結(jié)構(gòu)，左邊表現(xiàn)的是物理結(jié)構(gòu)C:兩者表現(xiàn)的都是邏輯結(jié)構(gòu)D:兩者表現(xiàn)的都是物理結(jié)構(gòu)向一個(gè)長度為n的順序表的第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)__D__個(gè)元素。A:iB:n-iC:n-i-1D:n-i+17、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(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;8、一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是_C___。

A:edcba

B:decba

C:dceab

D:abcde9、循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是__A__。

A:(rear-front+m)%m

B:rear-front+1

C:rear-front-1

D:rear-front10、關(guān)于空格串，下列說法中正確的有__D__。

A:空格串就是空串

B:空格串是零個(gè)字符的串

C:空格串的長度為零

D:空格串的長度就是其包含的空格個(gè)數(shù)11、數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為__C__。

A:SA+140

B:SA+144

C:SA+222

D:SA+225深度為4的二叉樹至多有__B__個(gè)結(jié)點(diǎn)。A：14B：15C：16D：1713、對(duì)于一棵滿二叉樹，m個(gè)樹葉，n個(gè)節(jié)點(diǎn)，深度為h，則__D__。

A:n=h+m

B:h+m=2n

C:m=h-1

D:n=2h-114、具有65個(gè)結(jié)點(diǎn)的完全二叉樹其深度為__B__。（根的層次號(hào)為1）

A:8

B:7

C:6

D:515、滿二叉樹__A__二叉樹。

A:一定是完全

B:不一定是完全

C:不是

D:不是完全16、將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的節(jié)點(diǎn)的左孩子編號(hào)為__B__。

A:99

B:98

C:50

D:4817、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用__A__。

A:棧

B:隊(duì)列

C:鏈表

D:樹18、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有__C__種。

A:3

B:4

C:5

D:619、如圖所示的4棵二叉樹中，_C___不是完全二叉樹。

A:

B:

C:

D:20、所謂稀疏矩陣指的是__C__。

A:零元素個(gè)數(shù)較多的矩陣

B:零元素個(gè)數(shù)占矩陣元素總個(gè)數(shù)一半的矩陣

C:零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于非零元素個(gè)數(shù)且分布沒有規(guī)律的矩陣

D:包含有零元素的矩陣三、已知線性鏈表如下圖，頭指針為La，寫出語句序列使左圖中的指針指向改成右圖中的指針指向。答:p=La->next;La->next=p->next;p->next=La;La=p;四、在一個(gè)C語言程序中，有結(jié)構(gòu)類型STUDENT的定義和結(jié)構(gòu)數(shù)組allstudents的聲明如下：structSTUDENT{charname[8];intnumber;}STUDENTallstudents[10][50];allstudents是一個(gè)二維數(shù)組，它的每個(gè)元素都是包含name和number的結(jié)構(gòu)類型。已知在C語言中，二維數(shù)組使用以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)，char類型占用1字節(jié)，int類型占用4字節(jié)。假定allstudents在內(nèi)存中的起始存儲(chǔ)位置是2000，請(qǐng)寫出計(jì)算allstudents[i][j]的存儲(chǔ)位置的算式，并計(jì)算allstudents[3][5]的存儲(chǔ)位置。答:(1)allstudents[i][j]的存儲(chǔ)位置=2000+(i*50+j)*12(2)allstudents[3][5]的存儲(chǔ)位置=2000(3*50+5)*12=3860五、用下標(biāo)從0到4的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，目前其中有兩個(gè)元素A、B，狀態(tài)如圖(a)。如果此后有17個(gè)數(shù)據(jù)元素C、D、……P、Q、R、S依次進(jìn)隊(duì)列，其間又有16個(gè)元素先后出隊(duì)列，請(qǐng)?jiān)趫D(b)中填寫隊(duì)列最后的狀態(tài)，包括其中的元素和指針的位置。答:rear→RBfront→Qfront→Arear→S(a)(b)六、序列(a,b,c,d,e)已存在靜態(tài)鏈表如下圖a，頭指針指向1號(hào)結(jié)點(diǎn)。請(qǐng)完成：1．在靜態(tài)鏈表中標(biāo)出此序列的邏輯關(guān)系。2．畫出依次執(zhí)行了b前插入f，刪除e，c后插入g操作后的新的靜態(tài)鏈表圖b。答:14刪除e，c后插入g操作后142c52c33e∧3g54a64a75d35d∧6b26b277f6圖a圖b插入”f”后142c53e∧4a75d36b27f6圖b七、已知一個(gè)稀疏矩陣A如下，填寫下表1．給出它的三元組順序表表示2．給出它的轉(zhuǎn)置矩陣B的三元組順序表表示0 2 0 0 0 01 0 0 0 0 00 3 0 0 0 00 0 0 0 4 00 5 0 0 0 6答:ijv轉(zhuǎn)置后(排序)ijv122121211212323233454255525544566656A.dataB.dataA.mu5B.mu6A.nu6B.nu5A.tu6B.tu6轉(zhuǎn)置后(未排序)ijv212121233544255656八、任意一棵有N個(gè)結(jié)點(diǎn)的二叉樹，已知它有M個(gè)葉子結(jié)點(diǎn)。試證明非葉子結(jié)點(diǎn)中度數(shù)為2的有M-1個(gè)，其余的度數(shù)為1。證:設(shè)二叉樹中度為0的結(jié)點(diǎn)數(shù)為n0,度為1的結(jié)點(diǎn)數(shù)為n1，度為2的結(jié)點(diǎn)數(shù)為n2，二叉樹中分支數(shù)為B∵N=n0+n1+n2N=M+n1+n2又∵B=0+n1+2*n2(其中:0---度為0的結(jié)點(diǎn)的分支數(shù)(葉子結(jié)點(diǎn)),n1---度為1的結(jié)點(diǎn)的分支數(shù),2*n2---度為2的結(jié)點(diǎn)的分支數(shù).又∵N=B+1M+n1+n2=0+n1+2*n2+1M=n2+1∴n2=M-1證明：設(shè)度為1和2的結(jié)點(diǎn)數(shù)是n1和n2，則二叉樹結(jié)點(diǎn)數(shù)n為

n=m+n1+n2…………(1)

由于二叉樹根結(jié)點(diǎn)沒有分枝所指，度為1和2的結(jié)點(diǎn)各有1個(gè)和2個(gè)分枝，度為0的結(jié)點(diǎn)沒有分枝，故二叉樹的結(jié)點(diǎn)數(shù)n與分枝數(shù)B有如下關(guān)系

n=B+1=n1+2*n2+1……….(2)

由（1）和（2），得n2=m-1。即n個(gè)結(jié)點(diǎn)的二叉樹，若葉子結(jié)點(diǎn)數(shù)是m，則非葉子結(jié)點(diǎn)中有（m-1）個(gè)度為2，其余度為1。九、寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表（a1,a2,…,an）逆置為（an,an-1,…,a1）。答:#defineListSize100//假定表空間大小為100typedefintDataType;//假定DataType的類型為int型typedefstruct{DataTypedata[ListSize];//向量data用于存放表結(jié)點(diǎn)intlength;//當(dāng)前的表長度}Seqlist;//順序表結(jié)構(gòu)定義同上題voidReverseList(Seqlist*L){DataTypetemp;//設(shè)置臨時(shí)空間用于存放datainti;for(i=0;i<=L->length/2;i++)//L->length/2為整除運(yùn)算{temp=L->data[i];//交換數(shù)據(jù)L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}十、寫一算法，實(shí)現(xiàn)統(tǒng)計(jì)帶表頭的單鏈表中元素值為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)。答:單鏈表結(jié)點(diǎn)的類型定義如下:typedefintelemtype;//定義數(shù)據(jù)域的類型typedefstructLnode{//定