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

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

A:一對一

B:一對多

C:多對一

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

B:關(guān)系

C:操作

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

B:正確性和簡明性

C:可讀性和文檔性

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

B:不必相鄰

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

D:無要求5、下面兩個圖各表現(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)向一個長度為n的順序表的第i個元素（1<=i<=n）之前插入一個元素時，需向后移動__D__個元素。A:iB:n-iC:n-i-1D:n-i+17、在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(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、一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是_C___。

A:edcba

B:decba

C:dceab

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

A:(rear-front+m)%m

B:rear-front+1

C:rear-front-1

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

A:空格串就是空串

B:空格串是零個字符的串

C:空格串的長度為零

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

A:SA+140

B:SA+144

C:SA+222

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

A:n=h+m

B:h+m=2n

C:m=h-1

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

A:8

B:7

C:6

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

A:一定是完全

B:不一定是完全

C:不是

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

A:99

B:98

C:50

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

A:棧

B:隊列

C:鏈表

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

A:3

B:4

C:5

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

A:

B:

C:

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

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

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

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

D:包含有零元素的矩陣三、已知線性鏈表如下圖，頭指針為La，寫出語句序列使左圖中的指針指向改成右圖中的指針指向。答:p=La->next;La->next=p->next;p->next=La;La=p;四、在一個C語言程序中，有結(jié)構(gòu)類型STUDENT的定義和結(jié)構(gòu)數(shù)組allstudents的聲明如下：structSTUDENT{charname[8];intnumber;}STUDENTallstudents[10][50];allstudents是一個二維數(shù)組，它的每個元素都是包含name和number的結(jié)構(gòu)類型。已知在C語言中，二維數(shù)組使用以行序為主序的存儲結(jié)構(gòu)，char類型占用1字節(jié)，int類型占用4字節(jié)。假定allstudents在內(nèi)存中的起始存儲位置是2000，請寫出計算allstudents[i][j]的存儲位置的算式，并計算allstudents[3][5]的存儲位置。答:(1)allstudents[i][j]的存儲位置=2000+(i*50+j)*12(2)allstudents[3][5]的存儲位置=2000(3*50+5)*12=3860五、用下標(biāo)從0到4的一維數(shù)組存儲一個循環(huán)隊列，目前其中有兩個元素A、B，狀態(tài)如圖(a)。如果此后有17個數(shù)據(jù)元素C、D、……P、Q、R、S依次進(jìn)隊列，其間又有16個元素先后出隊列，請在圖(b)中填寫隊列最后的狀態(tài)，包括其中的元素和指針的位置。答:rear→RBfront→Qfront→Arear→S(a)(b)六、序列(a,b,c,d,e)已存在靜態(tài)鏈表如下圖a，頭指針指向1號結(jié)點。請完成：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七、已知一個稀疏矩陣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個結(jié)點的二叉樹，已知它有M個葉子結(jié)點。試證明非葉子結(jié)點中度數(shù)為2的有M-1個，其余的度數(shù)為1。證:設(shè)二叉樹中度為0的結(jié)點數(shù)為n0,度為1的結(jié)點數(shù)為n1，度為2的結(jié)點數(shù)為n2，二叉樹中分支數(shù)為B∵N=n0+n1+n2N=M+n1+n2又∵B=0+n1+2*n2(其中:0---度為0的結(jié)點的分支數(shù)(葉子結(jié)點),n1---度為1的結(jié)點的分支數(shù),2*n2---度為2的結(jié)點的分支數(shù).又∵N=B+1M+n1+n2=0+n1+2*n2+1M=n2+1∴n2=M-1證明：設(shè)度為1和2的結(jié)點數(shù)是n1和n2，則二叉樹結(jié)點數(shù)n為

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

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

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

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