數(shù)據(jù)結(jié)構(gòu)第二章線性表練習(xí)及答案

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

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

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

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

5、比較（）個結(jié)點。A、nB、n2C、(n1)2D、(n1)211、單鏈表的存儲空間利用率（）A、大于1B、等于1C、小于1D、不能確定12、在順序表中，有7個元素，設(shè)第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、在單鏈表中插入結(jié)點的時間復(fù)雜度是（）A、O（1）B、O（n）C、O（n2）D、O（log2n）二、填空題1、基本線性表有（順序）和（鏈?zhǔn)剑﹥煞N存儲形式。2、在雙鏈表中，每個結(jié)點有兩個指針域，一個指向（前驅(qū)結(jié)點），另一個指向（后繼結(jié)點）。3、按順序存儲方法存儲的基本線性表稱為（順序表），按鏈表存儲的基本線性表稱為（鏈表）。4、順序表相對于鏈表的優(yōu)點有（隨機存?。┖停ù鎯臻g利用率高）。5、鏈表相對于順序表的優(yōu)點有（存

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

8、定）相鄰。11、當(dāng)對一個基本線性表進行插入和刪除操作較頻繁時，線性表應(yīng)采用（鏈?zhǔn)剑┐鎯Y(jié)構(gòu)；當(dāng)對線性表的操作不會引起它的變化時，線性應(yīng)采用（順序）存儲結(jié)構(gòu)。12、基本線性表的鏈?zhǔn)酱鎯χ校鶕?jù)鏈表指針的鏈接方向可分為（單向鏈表）、（雙向鏈表）和（循環(huán)鏈表）。13、在個結(jié)點的單鏈表中要刪除已知結(jié)點p，則需找到（P的前驅(qū)結(jié)點），其時間復(fù)雜度為（O(N)）。14、在雙向鏈表中要刪除已知結(jié)點p，其時間復(fù)雜度為（O(1)）。15、在循環(huán)鏈表中，可根