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

1、李春葆編著：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言篇）――習(xí)題與解析（修訂版）清華大學(xué)出版社一、緒論選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。1A.數(shù)據(jù)元素B.計(jì)算方法C.邏輯存儲(chǔ)D.數(shù)據(jù)映像2A.結(jié)構(gòu)B.關(guān)系C.運(yùn)算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.存儲(chǔ)D.關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)

2、結(jié)構(gòu)分成。A.動(dòng)態(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)的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取5.算法分析的目的是，算法分析的兩個(gè)主要方面是。1A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性2A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)單性C

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

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

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

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

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

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

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

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