數(shù)據(jù)結構第二章線性表練習及答案

1、一、選擇題1、用單鏈表方式存儲的線性表，存儲每個結點需要兩個域，一個是數(shù)據(jù)域，另一個是（）A、當前結點所在的地址域B、指針域C、空指針域D、空閑域2、不帶頭結點的單鏈表head為空的判斷條件是（）A、head==NULLB、headnext==NULLC、headdata==NULLD、head!=NULL3、在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在p和q之間插入s結點，則執(zhí)行（）A、snext=pqnext=sB、p

2、next=snextsnext=pC、qnext=snextsnext=pD、pnext=ssnext=q4、在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是（）A、O（1）B、O（n）C、O（n2）D、O（nlog2n）5、一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行（）A、pnext=pnextnextB、p=pnextpnext=pnextnextC、pnext=pD、p=pnextnext6、已知一個順

3、序存儲的基本線性表，設每個結點需占m個存儲單元，若第一個結點的地址為d1，則第i個結點的地址為（）A、d1(i1)mB、d1imC、d1imD、d1(i1)m7、在n個結點的順序表中，算法的時間復雜度是O（1）的操作是（）A、訪問第i個結點(1next=pqpri=pprippri=qpprinext=qB、ppri=qqnext=ppprinext=qqpri=ppriC、qpri=ppriqnext=ppprinext=qppri=

4、qD、以上都不對9、在循環(huán)雙鏈表的p所指結點之后插入s所指結點的操作是（）A、pnext=sspri=ppnextpri=ssnext=pnextB、pnext=spnextpri=sspri=psnext=pnextC、spri=psnext=pnextpnext=spnextpri=sD、spri=ppnextpri=ssnext=pnextpnext=s10、從具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均

5、比較（）個結點。A、nB、n2C、(n1)2D、(n1)211、單鏈表的存儲空間利用率（）A、大于1B、等于1C、小于1D、不能確定12、在順序表中，有7個元素，設第1個元素的查找概率是14，第2個元素的查找概率是13，其余元素的查找概率相等，則整個順序表的平均查找次數(shù)是（）次。A、4412B、45160C、3612D、562413、順序表的長度是（）。A、表中的存儲空間數(shù)B、表中的數(shù)據(jù)元素個數(shù)C、存儲空間數(shù)減去數(shù)據(jù)元素個數(shù)D、存儲空間

6、數(shù)加數(shù)據(jù)元素個數(shù)14、在單鏈表中插入結點的時間復雜度是（）A、O（1）B、O（n）C、O（n2）D、O（log2n）二、填空題1、基本線性表有（順序）和（鏈式）兩種存儲形式。2、在雙鏈表中，每個結點有兩個指針域，一個指向（前驅結點），另一個指向（后繼結點）。3、按順序存儲方法存儲的基本線性表稱為（順序表），按鏈表存儲的基本線性表稱為（鏈表）。4、順序表相對于鏈表的優(yōu)點有（隨機存?。┖停ù鎯臻g利用率高）。5、鏈表相對于順序表的優(yōu)點有（存

7、儲空間動態(tài)分配）和（插入刪除操作效率高）。6、在n個結點的順序表中插入一個結點需平均移動（N2）個結點，具體的移動次數(shù)取決于（插入的位置）。7、在n個結點的順序表中刪除一個結點需平均移動（(N1)2）個結點，具體的移動次數(shù)取決于（刪除的位置）。8、在順序表中訪問任意一個結點的時間復雜度均為（1），因此，順序表也稱（隨機存取或直接存?。┑臄?shù)據(jù)結構。9、在單鏈表中設置頭結點的作用是（保護頭指針）。10、順序表中邏輯上相鄰的元素，物理位置（一

8、定）相鄰。11、當對一個基本線性表進行插入和刪除操作較頻繁時，線性表應采用（鏈式）存儲結構；當對線性表的操作不會引起它的變化時，線性應采用（順序）存儲結構。12、基本線性表的鏈式存儲中，根據(jù)鏈表指針的鏈接方向可分為（單向鏈表）、（雙向鏈表）和（循環(huán)鏈表）。13、在個結點的單鏈表中要刪除已知結點p，則需找到（P的前驅結點），其時間復雜度為（O(N)）。14、在雙向鏈表中要刪除已知結點p，其時間復雜度為（O(1)）。15、在循環(huán)鏈表中，可根