線性表習(xí)題參考

1、習(xí)題二參照答案一、選擇題鏈?zhǔn)絻?chǔ)存構(gòu)造的最大長(zhǎng)處是（D）。A.便于隨機(jī)存取B.儲(chǔ)存密度高C.無需預(yù)分派空間D.便于進(jìn)行插入和刪除操作2.假定在次序表a,a,a中，每一個(gè)數(shù)據(jù)元素所占的儲(chǔ)存單元的數(shù)量為4，且第0個(gè)數(shù)據(jù)元素的儲(chǔ)存地01n1址為100，則第7個(gè)數(shù)據(jù)元素的儲(chǔ)存地點(diǎn)是（D）。A.106B.107C.1243.在線性表中若常常要存取第i個(gè)數(shù)據(jù)元素及其前趨，則宜采納（A）儲(chǔ)存方式。A.次序表B.帶頭結(jié)點(diǎn)的單鏈表C.不帶頭結(jié)點(diǎn)的單鏈表D.循環(huán)單鏈表4.在鏈表中若常常要?jiǎng)h除表中最后一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)以后插入一個(gè)新結(jié)點(diǎn)，則宜采納（C）儲(chǔ)存方式。A.次序表B.用頭指針表記的循環(huán)單鏈表C.用尾指針

2、表記的循環(huán)單鏈表D.雙向鏈表5.在一個(gè)單鏈表中的p和q兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)，假定新結(jié)點(diǎn)為S,則改正鏈的java語句序列是（D）。A.(p);(s);B.();(p);C.();(p);D.(s);(q);6.在一個(gè)含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍舊保擁有序的算法的時(shí)間復(fù)雜度是（C）。A.O(1)B.O(log2n)C.O(n)D.O(n2)7.要將一個(gè)次序表a0,a1,an-1中第i個(gè)數(shù)據(jù)元素ai(0in-1)刪除，需要挪動(dòng)（B）個(gè)數(shù)據(jù)元素。A.iB.n-i-1C.n-iD.n-i+18.在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中的p結(jié)點(diǎn)以后插入一個(gè)新結(jié)點(diǎn)s，其改正鏈的java語句序

3、列是（D）。(s);(p);().setPrior(s);();(s);().setPrior(s);(p);();(p);();(s);().setPrior(s);D.();(p);().setPrior(s);(s);9.次序表的儲(chǔ)存密度是（B），而單鏈表的儲(chǔ)存密度是（A）。A小于1B.等于1C.大于1D.不可以確立關(guān)于圖所示的單鏈表，以下表達(dá)式值為真的是（D）。headABCDEP1P2圖單鏈表head的儲(chǔ)存構(gòu)造圖A.().getData()=CB.()=BC.()=DD.()=null二、填空題1.線性表是由n（n0）個(gè)數(shù)據(jù)元素所組成的n=0的線性表稱為空表。有限序列，此中n為數(shù)據(jù)元

4、素的個(gè)數(shù)，稱為線性表的長(zhǎng)度，線性表中有且僅有一個(gè)開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，除開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外，其余每一個(gè)數(shù)據(jù)元素有且僅有一個(gè)前驅(qū)，有且僅有一個(gè)后繼。3.線性表往常采納次序儲(chǔ)存和鏈?zhǔn)絻?chǔ)存兩種儲(chǔ)存構(gòu)造。若線性表的長(zhǎng)度確立或變化不大，則合適采納次序儲(chǔ)存藏儲(chǔ)構(gòu)造進(jìn)行儲(chǔ)存。4.在次序表a0,a1,an-1中的第i(0in-1)個(gè)地點(diǎn)以前插入一個(gè)新的數(shù)據(jù)元素，會(huì)惹起n-i個(gè)數(shù)據(jù)元素的挪動(dòng)操作。在線性表的單鏈表儲(chǔ)存構(gòu)造中，每一個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，用于儲(chǔ)存數(shù)據(jù)元素值自己，另一個(gè)是指針域，用于儲(chǔ)存后繼結(jié)點(diǎn)的地點(diǎn)。在線性表的次序儲(chǔ)存構(gòu)造中可實(shí)現(xiàn)迅速的隨機(jī)存取，而在鏈?zhǔn)絻?chǔ)存構(gòu)造中則只好進(jìn)行次序存取。7.次

5、序表中邏輯上相鄰的數(shù)據(jù)元素，其物理地點(diǎn)必定相鄰，而在單鏈表中邏輯上相鄰的數(shù)據(jù)元素，其物理位置不必定相鄰。8.在僅設(shè)置了尾指針的循環(huán)鏈表中，接見第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是O（1）。9.在含有n個(gè)結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除一個(gè)指定的結(jié)點(diǎn)p，則第一一定找到指定結(jié)點(diǎn)p的前驅(qū)，其時(shí)間復(fù)雜度為O（n）。10.若將單鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域值改為單鏈表中頭結(jié)點(diǎn)的地點(diǎn)值，則這個(gè)鏈表就組成了循環(huán)單鏈表。三、算法設(shè)計(jì)題1.編寫一個(gè)次序表類的成員函數(shù)，實(shí)現(xiàn)對(duì)次序表就地逆置的操作。所謂逆置，就是把（a1,a2,an）變?yōu)椋╝n,an-1,a1）；所謂就地，就是指逆置后的數(shù)據(jù)元素仍儲(chǔ)存在本來次序表的儲(chǔ)存空間中，即不為逆

6、置后的順序表此外分派儲(chǔ)存空間。參照答案:publicvoidreverse()for(inti=0,j=curLen-1;ij;i+,j-)Objecttemp=listElemi;listElemi=listElemj;listElemj=temp;2.編寫一個(gè)次序表類的成員函數(shù)，實(shí)現(xiàn)對(duì)次序表循環(huán)右移12n-k,an-k+1n），k位的操作。即本來次序表為（a,a,a,a循環(huán)向右挪動(dòng)k位后變?yōu)椋╝n-k+1,an,a1,a2,an-k）。要求時(shí)間復(fù)雜度為O（n）。參照答案:publicvoidshit(intk)intn=curLen,p=0,i,j,l;Objecttemp;for(i=1

7、;ilistElem6,listElem6-listElem12,listElem12-listElem3,listElem3-listElem9,listElem9-listElem0.第二條鏈:listElem1-listElem7,listElem7-listElem13,listElem13-listElem4,listElem4-listElem10,listElem10-listElem1.第三條鏈:listElem2-listElem8,listElem8-listElem14,listElem14-listElem5,listElem5-listElem11,listElem1

8、1-listElem2.恰巧使所有元素都右移一次.固然未經(jīng)數(shù)學(xué)證明,但相信上述規(guī)律應(yīng)當(dāng)是正確的.3.編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)此刻非遞減的有序單鏈表中插入一個(gè)值為擁有序的操作。參照答案(方法一):publicvoidinsert(intx)Nodep=();ntValue();if(tempx)q=p;p=();elsebreak;x的數(shù)據(jù)元素，并使單鏈表仍保Nodes=newNode(x);etData().intValue()x)p=();Nodes=newNode(x);quals(x)q=p;p=();quals(x)();+j;etNext();/原多項(xiàng)式的首結(jié)點(diǎn)while(p!=()PolynNodedata=(PolynNode