數(shù)據(jù)結(jié)構(gòu)練習(xí)題含答案

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題習(xí)題習(xí)題1緒論緒論1.11.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算法Ｂ數(shù)據(jù)元素Ｃ數(shù)據(jù)操作Ｄ數(shù)據(jù)對象②A操作Ｂ映象Ｃ存儲

2、Ｄ關(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ù)雜性5.計算機算法指的是①，它必具備輸入、輸出和②等五

3、個特性。①A.計算方法B.排序方法C.解決問題的有限運算序列D.調(diào)度方法②A.可行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性1.21.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é)點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有個

4、后續(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)系。6.算法的五個重要特性是____________________。7.分析下面算法（程序段），給出最大語句頻度，該算法的時間復(fù)雜度是____。f(i=0inext=

5、=headD.head!=NULL8.帶頭結(jié)點的單鏈表head為空的判定條件是____。A.head==NULLB.headnext==NULLC.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=s

6、sleft=pprightleft=ssright=prightB.pright=sprightleft=ssleft=psright=prightC.sleft=psright=prightpright=sprightleft=sD.sleft=psright=prightprightleft=spright=s11.在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行____。A.snext=pne

7、xtpnext=sB.pnext=snextsnext=pB.qnext=ssnext=pC.pnext=ssnext=q12.在一個單鏈表中，若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=pnextn

8、ext；B.p=pnextpnext=pnextnext；C.pnext=pnextD.p=pnextnext；14.從一個具有n個結(jié)點的單鏈表中查找其值等于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個元素的向量，建立一個有

9、序單鏈表的時間復(fù)雜度是____。A.O(1)）B.O(n)C.O(n2)D.O(nlog2n)2.22.2填空題（將正確的答案填在相應(yīng)的空中）填空題（將正確的答案填在相應(yīng)的空中）1.單鏈表可以做____的鏈接存儲表示。2.在雙鏈表中，每個結(jié)點有兩個指針域，一個指向______，另一個指向_____。3.在一個單鏈表中p所指結(jié)點之前插入一個s(值為e)所指結(jié)點時，可執(zhí)行如下操作：q=headwhile(qnext!=p)q=qnexts=

10、newnewNodesdata=eqnext=填空snext=填空4.在一個單鏈表中刪除p所指結(jié)點的后繼結(jié)點時，應(yīng)執(zhí)行以下操作：q=pnextpnext=____填空填空5.在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行snext=____和pnext=____的操作。6.對于一個具有n個結(jié)點的單鏈表，在已知p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是____；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是____。2.32.3