數(shù)據(jù)結構與算法期中練習題答案

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

A:一對一

B:一對多

C:多對一

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

B:關系

C:操作

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

B:正確性和簡明性

C:可讀性和文檔性

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

B:不必相鄰

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

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

A:edcba

B:decba

C:dceab

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

A:(rear-front+m)%m

B:rear-front+1

C:rear-front-1

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

A:空格串就是空串

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

C:空格串的長度為零

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

A:SA+140

B:SA+144

C:SA+222

D:SA+225深度為4的二叉樹至多有__B__個結點。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個結點的完全二叉樹其深度為__B__。（根的層次號為1）

A:8

B:7

C:6

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

A:一定是完全

B:不一定是完全

C:不是

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

A:99

B:98

C:50

D:4817、將遞歸算法轉換成對應的非遞歸算法時，通常需要使用__A__。

A:棧

B:隊列

C:鏈表

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

A:3

B:4

C:5

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

A:

B:

C:

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

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

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

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

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

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

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

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

由（1）和（2），得n2=m-1。即n個結點的二叉樹，若葉子結點數(shù)是m，則非葉子結點中有（m-1）個度為2，其余度為1。九、寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表（a1,a2,…,an）逆置為（an,an-1,…,a1）。答:#defineListSize100//假定表空間大小為100typedefintDataType;//假定DataType的類型為int型typedefstruct{DataTypedata[ListSize];//向量data用于存放表結點intlength;//當前的表長度}Seqlist;//順序表結構定義同上題voidReverseList(Seqlist*L){DataTypetemp;//設置臨時空間用于存放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ù)的結點個數(shù)。答:單鏈表結點的類型定義如下:typedefintelemtype;//定義數(shù)據(jù)域的類型typedefstructLnode{//定