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

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

2、頭結(jié)點的單鏈表C.不帶頭結(jié)點的單鏈表D.循環(huán)單鏈表4.在鏈表中若經(jīng)常要刪除表中最后一個結(jié)點或在最后一個結(jié)點之后插入一個新結(jié)點，則宜采用（C）存儲方式。A.順序表B.用頭指針標(biāo)識的循環(huán)單鏈表C.用尾指針標(biāo)識的循環(huán)單鏈表D.雙向鏈表5.在一個單鏈表中的p和q兩個結(jié)點之間插入一個新結(jié)點，假設(shè)新結(jié)點為S則修改鏈的java語句序列是（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.在一個含有n個結(jié)點的有序單鏈表中插入一個新結(jié)點，使單鏈表仍然保持有序的算法的時間復(fù)雜度是（C）。A.O(1)B.O(log2n)C.O(n)D.O(n2)7.要將一個順序表a0a1……an1中第i個數(shù)據(jù)元素ai(0≤i≤n1)刪除，需要移動（B）個數(shù)據(jù)元素。A.iB.ni1C.niD.ni18.

4、在帶頭結(jié)點的雙向循環(huán)鏈表中的p結(jié)點之后插入一個新結(jié)點s，其修改鏈的java語句序列是（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.順序表的存儲密度是（B），而單鏈表的存儲密度是（A）。A小于1B.等于1C.大于1D.不能確定10.對于圖2.29所示的單鏈表，下列表達(dá)式值為真的是（D）。ABCEheadDP1P2圖2.29單鏈表單鏈表head的存儲結(jié)構(gòu)圖的存儲結(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].然而這并沒有全部解

7、決問題因為有可能有的元素在此過程中始終沒有被訪問過而是被跳了過去.分析可知當(dāng)n和k的最大公約數(shù)為p時只要分別以listElem[0]listElem[1]...listElem[p1]為起點執(zhí)行上述算法就可以保證每一個元素都被且僅被右移一次從而滿足題目要求.也就是說A的所有元素分別處在p個“循環(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.編寫一個單鏈表類的成員函數(shù)，實現(xiàn)在非遞減的有序單鏈表中插入一個值為x的數(shù)據(jù)元素，并使單鏈表仍保持有序的操作。參考答案參考答案(方法一方法一):):publicvoid(intx)Nodep=

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