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

1、習(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è)在順序表a0a1……an－1中，每一個(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.帶

2、頭結(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.順序表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.se

3、tNext(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.要將一個(gè)順序表a0a1……an1中第i個(gè)數(shù)據(jù)元素ai(0≤i≤n1)刪除，需要移動(dòng)（B）個(gè)數(shù)據(jù)元素。A.iB.ni1C.niD.ni18.

4、在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中的p結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)s，其修改鏈的java語(yǔ)句序列是（D）。A.p.setNext(s)s.setPri(p)p.getNext().setPri(s)s.setNext(p.getPri())B.p.setNext(s)p.getNext().setPri(s)s.setPri(p)s.setNext(p.getNext())C.s.setPri(p)s.setNext(p.getNext())p.se

5、tNext(s)p.getNext().setPri(s)D.s.setNext(p.getNext())s.setPri(p)p.getNext().setPri(s)p.setNext(s)9.順序表的存儲(chǔ)密度是（B），而單鏈表的存儲(chǔ)密度是（A）。A小于1B.等于1C.大于1D.不能確定10.對(duì)于圖2.29所示的單鏈表，下列表達(dá)式值為真的是（D）。ABCEheadDP1P2圖2.29單鏈表單鏈表head的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)圖A.h

6、ead.getNext().getData()==CB.head.getData()==BC.P1.getData()==’D’D.P2.getNext()==null二、填空題二、填空題listElem[j]=temp分析：分析：要把數(shù)組listElem的元素循環(huán)右移k位則listElem[0]移至listElem[k]listElem[k]移至listElem[2k]......直到最終回到listElem[0].然而這并沒(méi)有全部解

7、決問(wèn)題因?yàn)橛锌赡苡械脑卦诖诉^(guò)程中始終沒(méi)有被訪問(wèn)過(guò)而是被跳了過(guò)去.分析可知當(dāng)n和k的最大公約數(shù)為p時(shí)只要分別以listElem[0]listElem[1]...listElem[p1]為起點(diǎn)執(zhí)行上述算法就可以保證每一個(gè)元素都被且僅被右移一次從而滿(mǎn)足題目要求.也就是說(shuō)A的所有元素分別處在p個(gè)“循環(huán)鏈“上面.舉例如下:n=15k=6則p=3.第一條鏈:listElem[0]listElem[6]listElem[6]listElem[12]

8、listElem[12]listElem[3]listElem[3]listElem[9]listElem[9]listElem[0].第二條鏈:listElem[1]listElem[7]listElem[7]listElem[13]listElem[13]listElem[4]listElem[4]listElem[10]listElem[10]listElem[1].第三條鏈:listElem[2]listElem[8]listE

9、lem[8]listElem[14]listElem[14]listElem[5]listElem[5]listElem[11]listElem[11]listElem[2].恰好使所有元素都右移一次.雖然未經(jīng)數(shù)學(xué)證明但相信上述規(guī)律應(yīng)該是正確的.3.編寫(xiě)一個(gè)單鏈表類(lèi)的成員函數(shù)，實(shí)現(xiàn)在非遞減的有序單鏈表中插入一個(gè)值為x的數(shù)據(jù)元素，并使單鏈表仍保持有序的操作。參考答案參考答案(方法一方法一):):publicvoid(intx)Nodep=

10、head.getNext()p指向首結(jié)點(diǎn)Nodeq=headq用來(lái)記錄p的前驅(qū)結(jié)點(diǎn)inttempwhile(p!=null)temp=((Integer)p.getData()).intValue()if(tempx)q=pp=p.getNext()elsebreakNodes=newNode(x)生成新結(jié)點(diǎn)s.setNext(p)將s結(jié)點(diǎn)插入到單鏈表的q結(jié)點(diǎn)與p結(jié)點(diǎn)之間q.setNext(s)參考答案參考答案(方法二方法二):):pu