線性表習題參考

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

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

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

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

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

6、置后的順序表此外分派儲存空間。參照答案:publicvoidreverse()for(inti=0,j=curLen-1;ij;i+,j-)Objecttemp=listElemi;listElemi=listElemj;listElemj=temp;2.編寫一個次序表類的成員函數(shù)，實現(xiàn)對次序表循環(huán)右移12n-k,an-k+1n），k位的操作。即本來次序表為（a,a,a,a循環(huán)向右挪動k位后變?yōu)椋╝n-k+1,an,a1,a2,an-k）。要求時間復雜度為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ù)學證明,但相信上述規(guī)律應當是正確的.3.編寫一個單鏈表類的成員函數(shù)，實此刻非遞減的有序單鏈表中插入一個值為擁有序的操作。參照答案(方法一):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();/原多項式的首結點while(p!=()PolynNodedata=(PolynNode