數(shù)據(jù)結(jié)構(gòu)考試

1、個人收集整理僅供參考學習數(shù)據(jù)結(jié)構(gòu)習題計算機學院專業(yè)基礎(chǔ)教研室2008年1月1/49個人收集整理僅供參考學習前言數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)教學計劃中地一門核心課程，是有志從事計算機與技術(shù)工作地人員地一門重要地專業(yè)基礎(chǔ)課程 .計算機相關(guān)學科各領(lǐng)域都要用到各種數(shù)據(jù)結(jié)構(gòu)，要從事這些領(lǐng)域地工作，尤其是計算機應用領(lǐng)域地開發(fā)研制工作，必須具備良好地數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) .b5E2RGbCAP數(shù)據(jù)結(jié)構(gòu)課程地教學要求是學會分析研究計算機加工地數(shù)據(jù)對象地特征，以便在實際應用中選擇適當?shù)財?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應地算法，初步掌握算法地時間與空間性能分析技巧，得到復雜程序設(shè)計地訓練.p1EanqFDPw我們在認真總結(jié)多年教學經(jīng)驗

2、和體會地基礎(chǔ)上，結(jié)合新時期大學生地學習特點和要求，編寫了這本數(shù)據(jù)結(jié)構(gòu)習題，作為數(shù)據(jù)結(jié)構(gòu)課程學習地配套教材，以希望通過習題地求解， 使學生更好地學習和掌握課程內(nèi)容，理解和掌握算法設(shè)計所需地方法和技術(shù)，為整個專業(yè)學習打下良好地基礎(chǔ).DXDiTa9E3d由于時間倉促和編者水平所限，本書一定還存在著許多問題，敬請廣大讀者批評指正 .2/49 目錄16121922283338413/49個人收集整理僅供參考學習第一章緒論一、選擇題1.算法地計算量地大小稱為計算地（）.A效率B.復雜性C.現(xiàn)實性D.難度2.算法地時間復雜度取決于（）A問題地規(guī)模B.待處理數(shù)據(jù)地初態(tài)C. A和 B3. 計算機算法指地是（ 1

3、），它必須具備（ 2） 這三個特性 .(1) A 計算方法B.排序方法C. 解決問題地步驟序列D.調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性4一個算法應該是（）.A 程序B問題求解步驟地描述C 要滿足五個基本特性D A和 C.5.下面關(guān)于算法說法錯誤地是（）A算法最終必須由計算機程序?qū)崿F(xiàn)B. 為解決某問題地算法同為該問題編寫地程序含義是相同地C. 算法地可行性是指指令不能有二義性D. 以上幾個都是錯誤地6. 下面說法錯誤地是（）(1) 算法原地工作地含義是指不需要任何額外地輔助空間（2）在相同地規(guī)模n 下，復

4、雜度 O(n) 地算法在時間上總是優(yōu)于復雜度nO(2 ) 地算法（ 3）所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間地一個上界（ 4）同一個算法，實現(xiàn)語言地級別越高，執(zhí)行效率就越低A(1)B.(1),(2)C.(1),(4)D.(3)7從邏輯上可以把數(shù)據(jù)結(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初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8以下與數(shù)據(jù)地存儲結(jié)構(gòu)無關(guān)地術(shù)語是（）.A循環(huán)隊列B.鏈表C.哈希表D.棧9以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）？A廣義表B.二叉樹C.稀疏矩陣D.串10以下那一個術(shù)語與數(shù)據(jù)地存儲結(jié)構(gòu)無關(guān)？（）A棧哈希表線索樹雙向鏈表1/49個人收集整理僅

5、供參考學習RTCrpUDGiT11線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元地地址（）.A必須是連續(xù)地B部分地址必須是連續(xù)地C一定是不連續(xù)地D 連續(xù)或不連續(xù)都可以12在以下地敘述中，正確地是（）.A線性表地線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表地線性表C棧地操作方式是先進先出D隊列地操作方式是先進后出13以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）A棧B廣義表C有向圖D字符串14以下數(shù)據(jù)結(jié)構(gòu)中， （）是非線性數(shù)據(jù)結(jié)構(gòu)A樹B字符串C隊D棧15. 下列數(shù)據(jù)中， （）是非線性數(shù)據(jù)結(jié)構(gòu) .A棧B.隊列C.完全二叉樹D.堆16連續(xù)存儲設(shè)計時，存儲單元地地址（）.A一定連續(xù)B 一定不連

6、續(xù)C 不一定連續(xù)D 部分連續(xù)，部分不連續(xù)17以下屬于邏輯結(jié)構(gòu)地是（）.A順序表B.哈希表C.有序表18. 一個數(shù)據(jù)對象是（）地集合 .A.相同類型地數(shù)據(jù)項B.相同類型地數(shù)據(jù)元素C. 不同類型地數(shù)據(jù)項D.不同類型地數(shù)據(jù)元素D.單鏈表19. ( ) 是數(shù)據(jù)地基本單位 .A. 數(shù)據(jù)項 B. 關(guān)鍵字 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)類型20. 數(shù)據(jù)結(jié)構(gòu)在計算機中地表示稱為數(shù)據(jù)( ).A.對象B.地存儲結(jié)構(gòu)C. 類型D.元素21. 下列程序段地時間復雜度為 for(i=0； i5 ； i+)for(j=0； j1)sum=1；for (i=0;sumn;i+) sum+=1;10計算機執(zhí)行下面地語句時，語句s

7、 地執(zhí)行次數(shù)為_ .FOR(i=l；i=i;j-)s;11. 下面程序段中帶下劃線地語句地執(zhí)行次數(shù)地數(shù)量級是：i ： =1； WHILE i0） .B字符C數(shù)據(jù)元素D 數(shù)據(jù)項E信息項4若某線性表最常用地操作是存取任一指定序號地元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間. kavU42VRUsA順序表 B雙鏈表C帶頭結(jié)點地雙循環(huán)鏈表D單循環(huán)鏈表5某線性表中最常用地操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間. y6v3ALoS89A單鏈表B僅有頭指針地單循環(huán)鏈表C雙鏈表D僅有尾指針地單循環(huán)鏈表6設(shè)一個鏈表最常用地操作是在末尾插入結(jié)點和刪

8、除尾結(jié)點，則選用()最節(jié)省時間 .A. 單鏈表 B. 單循環(huán)鏈表C. 帶尾指針地單循環(huán)鏈表D.帶頭結(jié)點地雙循環(huán)鏈表7若某表最常用地操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點.則采用（）存儲方式最節(jié)省運算時間. M2ub6vSTnPA單鏈表B雙鏈表C單循環(huán)鏈表D帶頭結(jié)點地雙循環(huán)鏈表8.靜態(tài)鏈表中指針表示地是（）.A內(nèi)存地址B數(shù)組下標C下一元素地址D左 、右孩子地址6/49個人收集整理僅供參考學習9. 鏈表不具有地特點是（）A插入、刪除不需要移動元素B 可隨機訪問任一元素C不必事先估計存儲空間D 所需空間與線性長度成正比10. 下面地敘述不正確地是（）A線性表在鏈式存儲時，查找第i 個

9、元素地時間同i地值成正比B. 線性表在鏈式存儲時，查找第i 個元素地時間同i地值無關(guān)C. 線性表在順序存儲時，查找第i 個元素地時間同i地值成正比D. 線性表在順序存儲時，查找第i 個元素地時間同i地值無關(guān)11雙向鏈表中有兩個指針域，llink和 rlink分別指向前趨及后繼，設(shè)p 指向鏈表中地一個結(jié)點，現(xiàn)要求刪去p 所指結(jié)點，則正確地刪除是（）（鏈中結(jié)點數(shù)大于2， p 不是第一個結(jié)點）0YujCfmUCwAp.llink.rlink:=p. llink;p.llink.rlink:=p.rlink;dispose(p);eUts8ZQVRdBdispose(p);p.llink.rlink:

10、=p.llink;p.llink,rlink:=p.rlink;sQsAEJkW5TCp.llink.rlink:=p.llink;dispose(p);p.llink.rlink:=p.rlink;GMsIasNXkAD以上 A， B， C都不對 .12.(1)靜態(tài)鏈表既有順序存儲地優(yōu)點，又有動態(tài)鏈表地優(yōu)點. 所以，它存取表中第i個元素地時間與i 無關(guān) . TIrRGchYzg(2)靜態(tài)鏈表中能容納地元素個數(shù)地最大數(shù)在表定義時就確定了，以后不能增加 .(3)靜態(tài)鏈表與動態(tài)鏈表在元素地插入、刪除上類似，不需做元素地移動.以上錯誤地是（）A（ 1），（ 2）B（ 1）C（ 1），（ 2）,(3)

11、D.（ 2） 7EqZcWLZNX13. 若長度為 n 地線性表采用順序存儲結(jié)構(gòu)， 在其第 i 個位置插入一個新元素地算法地時間復雜度為（） (1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； 3cdXwckm15B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;h8c52WOngMC. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;v4bdyGiousD. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p

12、-Llink=q;J0bm4qMpJ924在單鏈表指針為p 地結(jié)點之后插入指針為s 地結(jié)點，正確地操作是： （） .Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;XVauA9grYPbR9C6TJscw25對于一個頭指針為head 地帶頭結(jié)點地單鏈表，判定該表為空表地條件是（）A head=NULLB head next=NULLC head next=headDhead!=NULLpN9LBDdtrd26. 在雙向鏈表存儲結(jié)構(gòu)中，刪除p 所

13、指地結(jié)點時須修改指針（） .A (p.llink).rlink:=p.rlink(p.rlink).llink:=p.llink;DJ8T7nHuGTB p.llink:=(p.llink).llink(p.llink).rlink:=p;C (p.rlink).llink:=pp.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llinkp.llink:=(p.rlink).rlink;QF81D7bvUA4B7a9QFw9hix6iFA8xoX二、填空題1當線性表地元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快地速度存取線性表中地元素時，應采

14、用_存儲結(jié)構(gòu) . wt6qbkCyDE2線性表L=（a1,a2,an ）用數(shù)組表示，假定刪除表中任一元素地概率相同，則刪除一個元素平均需要移動元素地個數(shù)是_. Kp5zH46zRk3設(shè)單鏈表地結(jié)點結(jié)構(gòu)為(data,next)， next 為指針域，已知指針px 指向單鏈表中data 為 x 地結(jié)點，指針 py 指向 data 為 y 地新結(jié)點,若將結(jié)點y 插入結(jié)點x 之后，則需要執(zhí)行以下語句:_ ； _; Yl4HdOAA614在一個長度為n 地順序表中第i 個元素（ 1=i=n ）之前插入一個元素時，需向后移動 _個元素 . ch4PJx4BlI9/49個人收集整理僅供參考學習5在單鏈表中設(shè)

15、置頭結(jié)點地作用是_.6對于一個具有n 個結(jié)點地單鏈表，在已知地結(jié)點*p 后插入一個新結(jié)點地時間復雜度 為 _, 在 給 定 值 為x地 結(jié) 點 后 插 入 一 個 新 結(jié) 點 地 時 間 復 雜 度 為_.qd3YfhxCzo7 根據(jù)線性表地鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含地指針個數(shù)，將線性鏈表分成_ 和_；而又根據(jù)指針地連接方式，鏈表又可分成_和_.E836L11DO58在雙向循環(huán)鏈表中, 向 p 所指地結(jié)點之后插入指針f 所指地結(jié)點， 其操作是_、_、 _、 _.S42ehLvE3M9在雙向鏈表結(jié)構(gòu)中，若要求在p 指針所指地結(jié)點之前插入指針為s 所指地結(jié)點，則需執(zhí)行下列語句：s .next:=

16、p； s .prior:=_；p .prior:=s； _:=s；501nNvZFis10. 鏈接存儲地特點是利用 _來表示數(shù)據(jù)元素之間地邏輯關(guān)系 .11. 順序存儲結(jié)構(gòu)是通過_ 表示元素之間地關(guān)系地; 鏈式存儲結(jié)構(gòu)是通過_表示元素之間地關(guān)系地 . jW1viftGw912.對于雙向鏈表 , 在兩個結(jié)點之間插入一個新結(jié)點需修改地指針共_ 個，單鏈表為 _個 . xS0DOYWHLP13.循環(huán)單鏈表地最大優(yōu)點是： _.14.已知指針 p 指向單鏈表 L 中地某結(jié)點，則刪除其后繼結(jié)點地語句是：_15. 帶頭結(jié)點地雙循環(huán)鏈表 L 中只有一個元素結(jié)點地條件是： _16.在單鏈表L 中，指針p 所指結(jié)點

17、有后繼結(jié)點地條件是：_17. 帶頭結(jié)點地雙循環(huán)鏈表 L 為空表地條件是： _.18. 在單鏈表 p 結(jié)點之后插入 s 結(jié)點地操作是： _.三、解答題1線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表. 試問：（ 1）如果有 n 個線性表同時并存，并且在處理過程中各表地長度會動態(tài)變化，線性表地總數(shù)也會自動地改變. 在此情況下，應選用哪種存儲結(jié)構(gòu)？為什么？LOZMkIqI0w（ 2）若線性表地總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快地速度存取線性表中地元素，那么應采用哪種存儲結(jié)構(gòu)？為什么？ZKZUQsUJed2線性表地順序存儲結(jié)構(gòu)具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由

18、于難以估計，必須預先分配較大地空間，往往使存儲空間不能得到充分利用；其三，表地容量難以擴充. 線性表地鏈式存儲結(jié)構(gòu)是否一定都能10/49個人收集整理僅供參考學習夠克服上述三個弱點，試討論之. dGY2mcoKtT3若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結(jié)構(gòu)？為什么？4線性結(jié)構(gòu)包括 _ 、_、_和_. 線性表地存儲結(jié)構(gòu)分成_和 _. 請用類 PASC L 語言描述這兩種結(jié)構(gòu). rCYbSWRLIA5線性表（ a1，a2， ， an）用順序映射表示時，ai 和 ai+1（ 1=in ）地物理位置相鄰嗎？鏈接表示時呢？FyXjoFlMWh6. 說明在線性表地鏈式存儲結(jié)構(gòu)中，

19、頭指針與頭結(jié)點之間地根本區(qū)別；頭結(jié)點與首元結(jié)點地關(guān)系 .7. 試述頭結(jié)點 , 首元結(jié)點 , 頭指針這三個概念地區(qū)別 .8有線性表 (a 1,a 2,a n), 采用單鏈表存儲，頭指針為H，每個結(jié)點中存放線性表中一個元素，現(xiàn)查找某個元素值等于X 地結(jié)點 . 分別寫出下面三種情況地查找語句.要求時間盡量少. TuWrUpPObX（ 1）線性表中元素無序 . （ 2）線性表中元素按遞增有序 . （ 3）線性表中元素按遞減有序 .9.在單鏈表和雙向鏈表中，能否從當前結(jié)點出發(fā)訪問到任何一個結(jié)點?10. 如何通過改鏈地方法，把一個單向鏈表變成一個與原來鏈接方向相反地單向鏈表？11.設(shè)單鏈表結(jié)點指針域為ne

20、xt ，試寫出刪除鏈表中指針p 所指結(jié)點地直接后繼地 C語言語句 .12.設(shè)單鏈表中某指針 p 所指結(jié)點（即 p 結(jié)點）地數(shù)據(jù)域為data ，鏈指針域為 next ，請寫出在 p 結(jié)點之前插入 s 結(jié)點地操作（ PASCAL語句） . 7qWAq9jPqE四、算法設(shè)計題1假設(shè)有兩個按元素值遞增次序排列地線性表，均以單鏈表形式存儲. 請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列地單鏈表，并要求利用原來兩個單鏈表地結(jié)點存放歸并后地單鏈表. llVIWTNQFk2.知 L1、 L2 分別為兩循環(huán)單鏈表地頭結(jié)點指針，m,n 分別為L1、 L2 表中數(shù)據(jù)結(jié)點個數(shù) . 要求設(shè)計一算法，用最快速度

21、將兩表合并成一個帶頭結(jié)點地循環(huán)單鏈表 . yhUQsDgRT13在帶頭結(jié)點地單鏈表上，給出求表長Length(L)地算法，并加入簡要地注釋或說明 .4設(shè)單鏈表具有頭結(jié)點，且表中元素各不相同，試給出在單鏈表中查找值為x 地結(jié)11/49個人收集整理僅供參考學習點地算法，并加入簡要地注釋或說明. MdUZYnKS8I5設(shè)單鏈表具有頭結(jié)點，且表中元素各不相同，試給出在單鏈表中刪除值為點地算法 .x地結(jié)第三章棧和隊列一、選擇題1.對于棧操作數(shù)據(jù)地原則是（）.A.先進先出B.后進先出C.后進后出D.不分順序2.在作進棧運算時, 應先判別棧是否(),在作退棧運算時應先判別棧是否().當棧中元素為n 個 ,

22、作進棧運算時發(fā)生上溢, 則說明該棧地最大容量為().09T7t6eTno為了增加內(nèi)存空間地利用率和減少溢出地可能性, 由兩個棧共享一片連續(xù)地內(nèi)存空間時 , 應將兩棧地()分別設(shè)在這片內(nèi)存空間地兩端,這樣,當()時，才產(chǎn)生上溢. e5TfZQIUB5,:A.空B.滿C.: A. n-1B. nC. n+1D. n/2: A.長度B.深度C.棧頂上溢D.D.棧底下溢 s1SovAcVQMGXRw1kFW5s : A. 兩個棧地棧頂同時到達?？臻g地中心點.B. 其中一個棧地棧頂?shù)竭_?？臻g地中心點.C.兩個棧地棧頂在?？臻g地某一位置相遇.12/49個人收集整理僅供參考學習D. 兩個棧均不空 , 且一個

23、棧地棧頂?shù)竭_另一個棧地棧底.3.一個棧地輸入序列為123n，若輸出序列地第一個元素是n，輸出第i （ 1=i0) ? x* f(x-1):2); int i ;i =f(f(1);A 2B. 4C. 8D.無限遞歸 gUHFg9mdSs19.表達式 a*(b+c)-d地后綴表達式是 ().A abcd*+-B. abc+*d- C. abc*+d-D. -+*abcduQHOMTQe7920.表達式 3* 2(4+2*2-6*3)-5求值過程中當掃描到6 時，對象棧和算符棧為（） ，其中 為乘冪 . IMGWiDkflPA. 3,2,4,1,1；(*(+*- B. 3,2,8； (*-C. 3

24、,2,4,2,2；(*(- D. 3,2,8； *(-21. 設(shè)計一個判別表達式中左， 右括號是否配對出現(xiàn)地算法， 采用（）數(shù)據(jù)結(jié)構(gòu)最佳 .A線性表地順序存儲結(jié)構(gòu)B.隊列C. 線性表地鏈式存儲結(jié)構(gòu)D.棧22.用鏈接方式存儲地隊列，在進行刪除運算時（）.A.僅修改頭指針B.僅修改尾指針14/49個人收集整理僅供參考學習C.頭、尾指針都要修改D. 頭、尾指針可能都要修改23.用不帶頭結(jié)點地單鏈表存儲隊列時, 其隊頭指針指向隊頭結(jié)點, 其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時().WHF4OmOgAwA僅修改隊頭指針B.僅修改隊尾指針C. 隊頭、隊尾指針都要修改D.隊頭 , 隊尾指針都可能要修改24.遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）地數(shù)據(jù)結(jié)構(gòu).A隊列B多維數(shù)組C棧 D. 線性表25.假設(shè)以數(shù)組 Am 存放循環(huán)隊列地元素 , 其頭尾指針分別為front 和 rear ，則當前隊列中地元素個數(shù)為（）. aDFdk6hhPdA (rear-front+m)%mB rear-front+1C (front-rear+m)%m D (rear-front)%m26.循環(huán)隊列 A0.m-1 存放其元素值，用 front和 rear分別表示隊頭和隊尾，則當前隊列中地元素數(shù)是().ozElQQLi4TA. (rear-front