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

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

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

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

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

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

6、數(shù)加數(shù)據(jù)元素個(gè)數(shù)14、在單鏈表中插入結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）A、O（1）B、O（n）C、O（n2）D、O（log2n）二、填空題1、基本線性表有（順序）和（鏈?zhǔn)剑﹥煞N存儲(chǔ)形式。2、在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向（前驅(qū)結(jié)點(diǎn)），另一個(gè)指向（后繼結(jié)點(diǎn)）。3、按順序存儲(chǔ)方法存儲(chǔ)的基本線性表稱為（順序表），按鏈表存儲(chǔ)的基本線性表稱為（鏈表）。4、順序表相對(duì)于鏈表的優(yōu)點(diǎn)有（隨機(jī)存取）和（存儲(chǔ)空間利用率高）。5、鏈表相對(duì)于順序表的優(yōu)點(diǎn)有（存

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

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