數(shù)據(jù)結(jié)構(gòu)復(fù)習題目

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習題數(shù)據(jù)結(jié)構(gòu)復(fù)習題（打星號內(nèi)容可以不考慮）（打星號內(nèi)容可以不考慮）習題習題1緒論緒論1.1單項選擇題單項選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的課程，它研究程序設(shè)計問題中數(shù)據(jù)元素的①、數(shù)據(jù)信息在計算機中的②以及一組相關(guān)的運算等的課程。①A操作對象Ｂ計算方法Ｃ邏輯結(jié)構(gòu)Ｄ數(shù)據(jù)映象②A存儲結(jié)構(gòu)Ｂ關(guān)系Ｃ運算Ｄ算法2.數(shù)據(jù)結(jié)構(gòu)DS(DataStruct)可以被形式地定義為DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。①A

2、算法Ｂ數(shù)據(jù)元素Ｃ數(shù)據(jù)操作Ｄ數(shù)據(jù)對象②A操作Ｂ映象Ｃ存儲Ｄ關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)Ｂ緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)Ｃ線性結(jié)構(gòu)和非線性結(jié)構(gòu)Ｄ內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.算法分析的目的是①，算法分析的兩個主要方面是②。①A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性②A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)

3、雜性5.計算機算法指的是①，它必具備輸入、輸出和②等五個特性。①A.計算方法B.排序方法C.解決問題的有限運算序列D.調(diào)度方法②A.可行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性1.2填空題（將正確的答案填在相應(yīng)的空中）填空題（將正確的答案填在相應(yīng)的空中）1.數(shù)據(jù)邏輯結(jié)構(gòu)包括、和三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為。2.在線性結(jié)構(gòu)中，第一個結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)

4、點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有個后續(xù)結(jié)點。3.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點有且只有個直接前驅(qū)結(jié)點，葉子結(jié)點沒有結(jié)點，其余每個結(jié)點的直接后續(xù)結(jié)點可以。4.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以。5.線性結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B.線性表的順序存儲結(jié)構(gòu)適用于頻繁插入刪除數(shù)據(jù)元素的情況C.線性表的鏈表存儲

5、結(jié)構(gòu)適用于頻繁插入刪除數(shù)據(jù)元素的情況D.線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)6.每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找，這種說法___。A.正確B.不正確7.不帶頭結(jié)點的單鏈表head為空的判定條件是____。A.head==NULLB.headnext==NULLC.headnext==headD.head!=NULL8.帶頭結(jié)點的單鏈表head為空的判定條件是____。A.head==NULLB.headnext==NUL

6、LC.headnext==headD.head!=NULL9.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足____。A.pnext==NULLB.p==NULLC.pnext==headD.p==head10.在雙向循環(huán)鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是____。A.pright=ssleft=pprightleft=ssright=prightB.pright=sprightleft=ssleft=psright=pri

7、ghtC.sleft=psright=prightpright=sprightleft=sD.sleft=psright=prightprightleft=spright=s11.在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行____。A.snext=pnextpnext=sB.pnext=snextsnext=pC.qnext=ssnext=pD.pnext=ssnext=q12.在一個單鏈表中

8、，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行____。A.snext=ppnext=sB.snext=pnextpnext=sC.snext=pnextp=sC.pnext=ssnext=p13.在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行____。A.pnext=pnextnext；B.p=pnextpnext=pnextnext；C.p=pnextD.p=pnextnext；14.從一個具有n個結(jié)點的單鏈表中查找

9、其值等于x結(jié)點時，在查找成功的情況下，需平均比較____個結(jié)點。A.nB.n2C.(n1)2D.(n1)215.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)16.給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是____。A.O(1)）B.O(n)C.O(n2)D.O(nlog2n)2.2填空題（將正確的答案填在相應(yīng)的空中）填空題（將正確