《數(shù)據(jù)結(jié)構(gòu)》第二章線性表習(xí)題

1、《數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)》第二章第二章線性表性表習(xí)題習(xí)題一、單項選擇題一、單項選擇題1.線性表是________。A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空2.在一個長度為n的順序表中刪除第i個元素(0next=sspri=ppnextpri=ssnext=pnextBspri=psnext=pnextpnext=spnextpri=sCpnext=spnextpri=sspri=psne

2、xt=pnextDspri=psnext=pnextpnextpri=spnext=s6.設(shè)單鏈表中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指針的操作為________。Apnext=pnextnextBp=pnextCp=pnextnextDpnext=p7.在一個長度為n的順序表中向第i個元素(0next=pnextpnext=sBqnext=ssnext=pCpnext=snextsnext=pDpnext=ss

3、next=q9.以下關(guān)于線性表的說法不正確的是______。A線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。7.當(dāng)對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進行的是插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。8.順

4、序表中邏輯上相鄰的元素，物理位置____相鄰，單鏈表中邏輯上相鄰的元素，物理位置____相鄰。9.線性表、棧和隊列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置插入和刪除元素；對于隊列只能在_______位置插入元素和在_______位置刪除元素。10.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為_

5、_______和_________。11.在單鏈表中設(shè)置頭結(jié)點的作用是________。12.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_______。13.對于一個棧作進棧運算時，應(yīng)先判別棧是否為_______，作退棧運算時，應(yīng)先判別棧是否為_______，當(dāng)棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_______。為了增

6、加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時才產(chǎn)生上溢。14.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過pushpushpoppushpoppushpush后，輸出序列是_________。15.無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，進行插入或刪除運算的時間復(fù)雜度均相同為__________。三、簡答題三、簡答題1.

7、描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。2.線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？3.對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？4.對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。5.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置