數(shù)據(jù)結(jié)構(gòu)(李春葆)習(xí)題與解析

1、李春葆編著：數(shù)據(jù)結(jié)構(gòu)（C語言篇）――習(xí)題與解析（修訂版）清華大學(xué)出版社一、緒論選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題計算機的以及它們之間的和運算等的學(xué)科。1A.數(shù)據(jù)元素B.計算方法C.邏輯存儲D.數(shù)據(jù)映像2A.結(jié)構(gòu)B.關(guān)系C.運算D.算法2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(KR)，其中K是的有限集，R是K上的有限集。1A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)2A.操作B.映像C.存儲D.關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)

2、結(jié)構(gòu)分成。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種的存儲結(jié)構(gòu)。A.隨機存取B.順序存取C.索引存取D.散列存取5.算法分析的目的是，算法分析的兩個主要方面是。1A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性2A.空間復(fù)雜度和時間復(fù)雜度B.正確性和簡單性C

3、.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6.計算機算法指的是，它必須具備輸入、輸出和等5個特性。1A.計算方法B.排序方法C.解決問題的有限運算序列D.調(diào)度方法2A.可執(zhí)行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性7.線性表的邏輯順序與存儲順序總是一致的，這種說法。A.正確B.不正確8線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址。A.必須連續(xù)的B.部分地址必須連續(xù)的

4、C.一定是不續(xù)的D連續(xù)不連續(xù)都可以9.以下的敘述中，正確的是。A.線性表的存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊列的操作方式是先進(jìn)后出10.每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找，這種說法。A.正確B.不正確填空題1.數(shù)據(jù)邏輯結(jié)構(gòu)包括三種類型、和，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為。2.在線性結(jié)構(gòu)中，第一個結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；最后一個結(jié)點后續(xù)結(jié)點，其余每

5、個結(jié)點有且只有個后續(xù)結(jié)點。3.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；葉子結(jié)點沒有結(jié)點，其余每個結(jié)點的后續(xù)可以。4.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以。A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、19.判斷一個隊列QU(最多元素為m)為空的條件是。A.QUrear－QUfront==mB.QUrear－QUfront－1==mC.QUfront==QUrearD.QUfr

6、ont－QUrear110.判斷一個隊列QU(最多元素為m)為滿隊列的條件是。A.QUrear－QUfront==mB.QUrear－QUfront－1==mC.QUfront==QUrearD.QUfront－QUrear111.判斷一個循環(huán)隊列QU(最多元素為m)為空的條件是。A.QUfront==QUrearB.QUfront!=QUrearC.QUfront==(QUrear1)%mD.QUfront!=(QUrear1)%m1

7、2.判斷一個循環(huán)隊列QU(最多元素為m)為滿隊列的條件是。A.QUfront==QUrearB.QUfront!=QUrearC.QUfront==(QUrear1)%mD.QUfront!=(QUrear1)%m13循環(huán)隊列用數(shù)組A[0m1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊列中的元素個數(shù)是。A.(rear－frontm)%mB.rear－front1C.rear－front－1D.rear－front1

8、4.棧和隊列的共同點是。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點處插入、刪除元素D.沒有共同點填空題1.向量、棧和隊列都是結(jié)構(gòu)，可以在向量的位置插入和刪除元素；對于棧只能在插入和刪除元素；對于隊列只能在插入元素和刪除元素。2.在一個長度為n的向量中的第i個元素(1≤i≤n)之前插入一個元素時，需向后移動個元素。3.在一個長度為n的向量中的刪除第i個元素(1≤i≤n)時，需要向前移動個元素。4.向棧中壓入元素的操作是。5.對棧進(jìn)行

9、退棧時的操作是。6.在一個循環(huán)隊列中，隊首指針指向隊首元素的。7.從循環(huán)隊列中刪除一個元素時，其操作是。8.在具有n個單元的循環(huán)隊列中，隊滿時共有個元素的。9.一個棧的輸入序列是12345，則棧的輸出序列43512是。10.一個棧的輸入序列是12345，則棧的輸出序列12345是。三、鏈表單項選擇題1.不帶頭結(jié)點的單鏈表head為空的判定條件是。A.head==NULLB.headnxt==NULLC.headnext==headD.h

10、ead!=NULL2.帶頭結(jié)點的單鏈表head為空的判定條件是。A.head==NULLB.headnxt==NULLC.headnext==headD.head!=NULL3.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足。A.pnext==NULLB.p==NULLC.pnext==headD.p==head4.在循環(huán)雙鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是。A.pright=ssleft=pprightleft=ssrig