-線性表習(xí)題參考答案

1、第2章-線性表習(xí)題參考答案習(xí)題二參考答案一、選擇題1.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是(D)。A.便于隨機(jī)存取B.存儲(chǔ)密度高C.無(wú)需預(yù)分配空間D.便于進(jìn)行插入和刪除操作2 .假設(shè)在順序表ao,a1,an一i中，每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的數(shù)目為4,且第0個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為100,則第7個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是(D)。A.106B.107C.124D.1283.在線性表中若經(jīng)常要存取第i個(gè)數(shù)據(jù)元素及其前趨，則宜采用(A)存儲(chǔ)方式。A.順序表B.帶頭結(jié)點(diǎn)的單鏈表C.不帶頭結(jié)點(diǎn)的單鏈表D.循環(huán)單鏈表4 .在鏈表中若經(jīng)常要?jiǎng)h除表中最后一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則宜采用(C)存儲(chǔ)方式。A.

2、順序表B.用頭指針標(biāo)識(shí)的循環(huán)單鏈表C.用尾指針標(biāo)識(shí)的循環(huán)單鏈表D.雙向鏈表5 .在一個(gè)單鏈表中的p和q兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)，假設(shè)新結(jié)點(diǎn)為S,則修改鏈的java語(yǔ)句序列是(D)。A.s.setNext(p);q.setNext(s);B.p.setNext(s.getNext();s.setNext(p);C.q.setNext(s.getNext();s.setNext(p);D.p.setNext(s);s.setNext(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

3、.要將一個(gè)順序表a0,ai,an-i中第i個(gè)數(shù)據(jù)元素a(0wiwn-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語(yǔ)句序列是(D)。A. p.setNext(s);s.setPrior(p);p.getNext().setPrior(s);s.setNext(p.getPrior();B. p.setNext(s);s.setPrior(p);s.setNext(p.getNext();C. s.setPrior(p);s.setNext(p.getNext();p.setNext

4、(s);p.getNext().setPrior(s);D. s.setNext(p.getNext();s.setPrior(p);p.getNext().setPrior(s);p.setNext(s);9.順序表的存儲(chǔ)密度是(B),而單鏈表的存儲(chǔ)密度是(A)。A,小于1B.等于1C.大于1D.不p.getNext().setPrior(s);能確定10 .對(duì)于圖2.29所示的單鏈表，下列表達(dá)式值為真的是(D)。heMALrLBLrLQL!PI圖2.29單鏈表head的存儲(chǔ)結(jié)構(gòu)圖A.head.getNext().getData()=Chead.getData()=BC.P.getData(

5、)=DP2.getNext()=null二、填空題1.線性表是由n(n0)個(gè)數(shù)據(jù)元素所構(gòu)成的有限序列，其中n為數(shù)據(jù)元素的個(gè)數(shù)，稱為線性表的長(zhǎng)度.n=0的線性表稱為空表。2 .線性表中有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，除開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)之外， 其它每一個(gè)數(shù)據(jù)元素有且僅有一個(gè)前驅(qū)， 有且僅有一個(gè)后繼。3.線性表通常采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。若線性表的長(zhǎng)度確定或變化不大，則適合采用順序何存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。4.在順序表a,a1,，an-1中的第i(0in-1)個(gè)位置之前插入一個(gè)新的數(shù)據(jù)元素，會(huì)引起n-i個(gè)數(shù)據(jù)元素的移動(dòng)操作。5.在線性表的單鏈表存儲(chǔ)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，用

6、于存儲(chǔ)數(shù)據(jù)元素值本身，另一個(gè)是指B.D.針域.用于存儲(chǔ)后繼結(jié)點(diǎn)的地址。6 .在線性表的順序存儲(chǔ)結(jié)構(gòu)中可實(shí)現(xiàn)快速的隨機(jī)存取，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中則只能進(jìn)行順序存取。7.順序表中邏輯上相鄰的數(shù)據(jù)元素，其物理位置一定相鄰，而在單鏈表中邏輯上相鄰的數(shù)據(jù)元素，其物理位置不一定相鄰。8 .在僅設(shè)置了尾指針的循環(huán)鏈表中，訪問(wè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)的地址值，則這個(gè)鏈表就構(gòu)成了循環(huán)單鏈表。三、算法設(shè)計(jì)題1.編寫一個(gè)順序表類的成員函

7、數(shù)，實(shí)現(xiàn)對(duì)順序表就地逆置的操作。所謂逆置，就是把(ai,a2,，an)變成(an,an-i,ai);所謂就地，就是指逆置后的數(shù)據(jù)元素仍存儲(chǔ)在原來(lái)順序表的存儲(chǔ)空間中，即不為逆置后的順序表另外分配存儲(chǔ)空間參考答案：publicvoidreverse()for(inti=0,j=curLen-1;ij;i+,j-)Objecttemp=listElemi;listElemi=listElemj;listElemj=temp;編寫一個(gè)順序表類的成員函數(shù)，實(shí)現(xiàn)對(duì)順序表循環(huán)右位的操作。即原來(lái)順序表為(日?2,an-k,an-k+1,，an),循環(huán)向右移動(dòng)k位后變成(an-k+1,an,a1,a2,*,an

8、-k)o要求時(shí)間復(fù)雜度為O(n)。參考答案：publicvoidshit(intk)intn=curLen,p=0,i,j,l;Objecttemp;for(i=1;i=k;i+)if(n%i=0&k%i=0)公約數(shù)pp=i;for(i=0;ilistElem6,listElem6-listElem12,listElem12-listElem3,listElem3-listElem9,listElem9-listElem0.第二條鏈:listElem1-listElem7,listElem7-listElem13,listElem13-listElem4,listElem4-listE

9、lem10,listElem10-listElem1.第三條鏈：listElem2-listElem8,listElem8-listElem14,listElem14-listElem5,listElem5-listElem11,listElem11-listElem2.恰好使所有元素都右移一次.雖然未經(jīng)數(shù)學(xué)證明，但相信上述規(guī)律應(yīng)該是正確的.3.編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)現(xiàn)在非遞減的有序單鏈表中插入一個(gè)值為x的數(shù)據(jù)元素， 并使單鏈表仍保序的操作。參考答案(方法一):publicvoidinsert(intx)Nodep=head.getNext();/p指向首結(jié)點(diǎn)Nodeq=head;/q

10、inttemp;while(p!=null)tempp.getData().intValue();if(tempx)q=p;持有用來(lái)記錄p的前驅(qū)結(jié)點(diǎn)(Integer)p=p.getNext();elsebreak;Nodes=newNode(x);/生成新結(jié)點(diǎn)s.setNext(p);/將s結(jié)點(diǎn)插入到單鏈表的點(diǎn)與p結(jié)點(diǎn)之間q.setNext(s);參考答案(方法二):publicvoidinsert(intx)Nodep=head.getNext();/pwhile(p.getNext()!=null&(Integer)p.getNext().getData().intValue()x

11、)p=p.getNext();)Nodes=newNode(x);/s.setNext(p.getNext();/單鏈表的q結(jié)點(diǎn)與p結(jié)點(diǎn)之間p.setNext(s);)指向首結(jié)點(diǎn)生成新結(jié)點(diǎn)將s結(jié)點(diǎn)插入到4.編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)現(xiàn)對(duì)帶頭結(jié)點(diǎn)的單鏈表就地逆置的操作。所謂逆置，就是把(a1,a2,an)變成(an,an-i,ai);所謂就地)就是指逆置后的結(jié)點(diǎn)仍存儲(chǔ)在原來(lái)單鏈表的存儲(chǔ)空間中， 只不過(guò)通過(guò)修改鏈來(lái)改變單鏈表中每一個(gè)結(jié)點(diǎn)之間的邏輯位置關(guān)系。參考答案：publicvoidreverse()/實(shí)現(xiàn)對(duì)單鏈表就地逆置(采用的是頭插法)Nodep=head.getNext();head.

12、setNext(null);Nodeq;while(p!=null)q=p.getNext();p.setNext(head.getNext();head.setNext(p);p=q;5.編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)現(xiàn)刪除不帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于x的第一個(gè)結(jié)點(diǎn)的操作。若刪除成功，則返回被刪除結(jié)點(diǎn)的位置；否則，返回-1。參考答案：publicintremove(Objectx)Nodep=head;/初始化,p指向首結(jié)點(diǎn)Nodeq=null;/q用來(lái)記錄p的前驅(qū)結(jié)點(diǎn)intj=0;/j為計(jì)數(shù)器/從單鏈表中的首結(jié)點(diǎn)元素開(kāi)始查找，直到p.getData()指向元素x或到達(dá)單鏈表的表尾whi

13、le(p!=null&!p.getData().equals(x)q=p;p=p.getNext();/指向下一個(gè)元素+j;計(jì)數(shù)器的值增1if(p!=null&q=null)/刪除的是單鏈表中的首結(jié)點(diǎn)head=p.getNext();elseif(p!=null)/的非首結(jié)點(diǎn)q.setNext(p.getNext();elsereturn-1;/值為x的結(jié)點(diǎn)在單鏈表中不存在returnj;編寫一個(gè)單鏈表類的成員函數(shù)， 實(shí)現(xiàn)刪除帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于x的所有結(jié)點(diǎn)的操作。要求函數(shù)返回被刪除結(jié)點(diǎn)的個(gè)數(shù)。參考答案：publicintremoveAll(Objectx)Nodep

14、=head.getNext();/初始化,p指向首結(jié)點(diǎn),j為計(jì)數(shù)器刪除的是單鏈 表中Nodeq=head;/用來(lái)記錄p的前驅(qū)結(jié)點(diǎn)intj=0;/用來(lái)記錄被刪除結(jié)點(diǎn)的個(gè)數(shù)while(p!=null)/從單鏈表中的首結(jié)點(diǎn)開(kāi)始對(duì)整個(gè)鏈表遍歷一次if(p.getData().equals(x)q.setNext(p.getNext();+j;/計(jì)數(shù)器的值增1elseq=p;p=p.getNext();/指向下一個(gè)元素returnj;/返回被刪除結(jié)點(diǎn)的個(gè)數(shù)7.編寫一個(gè)多項(xiàng)式類的成員函數(shù)， 實(shí)現(xiàn)將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式的操作， 并使兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)。要求利用原來(lái)循

15、環(huán)鏈表中的存儲(chǔ)空間構(gòu)成這兩個(gè)鏈表。參考答案：publicCircleLinkList口separatePolyn(CircleLinkListcList)CircleLinkList();/含奇次項(xiàng)的多項(xiàng)式Nodep1=cList1.getHead();/p2指向奇次項(xiàng)多項(xiàng)式的頭結(jié)點(diǎn)CircleLinkList();/含偶次項(xiàng)的多項(xiàng)式Nodep2=cList2.getHead();/p2指向偶次項(xiàng)多項(xiàng)式的頭結(jié)點(diǎn)Nodep=cList.getHead().getNext();/原多項(xiàng)式的首結(jié)點(diǎn)while(p!=cList.getHead()PolynNodedata=(PolynNode)p.getData();intexpn=data.getExpn()