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

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

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

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

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

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

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

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