1、習(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è)在順序表a0,a1,an1中，每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的數(shù)目為4，且第0個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為100，則第7個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是（ D ）。A. 106 B. 107 C.124 D.1283. 在線(xiàn)性表中若經(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ǔ)

2、方式。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.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(

3、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. i B. n-i-1 C. n-i D. 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); p.getNext().setPrior(s); s.setPrior(p

4、); s.setNext(p.getNext();C. s.setPrior(p); s.setNext(p.getNext(); p.setNext(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小于1 B. 等于1 C. 大于1 D. 不能確定10. 對(duì)于圖2.29所示的單鏈表，下列表達(dá)式值為真的是（ D ）。ABCE headDP1P2圖2.29 單鏈表

5、head的存儲(chǔ)結(jié)構(gòu)圖A. head.getNext().getData()='C' B. head.getData()='B'C. P1.getData()=D D. P2.getNext()=null二、填空題1. 線(xiàn)性表是由n（n0）個(gè)數(shù)據(jù)元素所構(gòu)成的 有限序列 ，其中n為數(shù)據(jù)元素的個(gè)數(shù)，稱(chēng)為線(xiàn)性表的 長(zhǎng)度 ，n=0的線(xiàn)性表稱(chēng)為 空表 。2. 線(xiàn)性表中有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，除開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)之外，其它每一個(gè)數(shù)據(jù)元素有且僅有一個(gè) 前驅(qū) ，有且僅有一個(gè) 后繼 。3. 線(xiàn)性表通常采用 順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 兩種存儲(chǔ)結(jié)構(gòu)。若線(xiàn)性表的長(zhǎng)度確定或變化不大，

6、則適合采用 順序存儲(chǔ) 存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。4. 在順序表a0,a1,an-1中的第i(0in-1)個(gè)位置之前插入一個(gè)新的數(shù)據(jù)元素，會(huì)引起 n-i 個(gè)數(shù)據(jù)元素的移動(dòng)操作。5. 在線(xiàn)性表的單鏈表存儲(chǔ)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，用于存儲(chǔ)數(shù)據(jù)元素值本身，另一個(gè)是 指針域 ，用于存儲(chǔ)后繼結(jié)點(diǎn)的地址。6. 在線(xiàn)性表的順序存儲(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)鏈表中，訪(fǎng)問(wèn)第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（1） 。9.

7、在含有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. 編寫(xiě)一個(gè)順序表類(lèi)的成員函數(shù)，實(shí)現(xiàn)對(duì)順序表就地逆置的操作。所謂逆置，就是把（a1,a2,an）變成（an,an-1,a1）；所謂就地，就是指逆置后的數(shù)據(jù)元素仍存儲(chǔ)在原來(lái)順序表的存儲(chǔ)空間中，即不為逆置后的順序表另外分配存儲(chǔ)空間。參考答案:public void reverse() for (int i = 0,j=curLen-1; i < j; i+,

8、j-) Object temp = listElemi;listElemi = listElemj;listElemj = temp;2. 編寫(xiě)一個(gè)順序表類(lèi)的成員函數(shù)，實(shí)現(xiàn)對(duì)順序表循環(huán)右移k位的操作。即原來(lái)順序表為（a1,a2,an-k,an-k+1, an），循環(huán)向右移動(dòng)k位后變成（an-k+1, an ,a1,a2,an-k）。要求時(shí)間復(fù)雜度為O（n）。參考答案:public void shit(int k) int n=curLen,p=0,i,j,l; Object temp; for(i=1;i<=k;i+) if(n%i=0&&k%i=0) /求n和k的最大公

9、約數(shù)p p=i; for(i=0;i<p;i+) j=i; l=(i+n-k)%n; temp=listElemi; while(l!=i) listElemj=listEleml; j=l; l=(j+n-k)%n; / 循環(huán)右移一步 listElemj=temp; 分析： 要把數(shù)組listElem的元素循環(huán)右移k位,則listElem0移至listElemk, listElemk移至listElem2k.直到最終回到listElem0.然而這并沒(méi)有全部解決問(wèn)題,因?yàn)橛锌赡苡械脑卦诖诉^(guò)程中始終沒(méi)有被訪(fǎng)問(wèn)過(guò),而是被跳了過(guò)去.分析可知,當(dāng)n和k的最大公約數(shù)為p時(shí),只要分別以listEle

10、m0, listElem1,. listElemp-1為起點(diǎn)執(zhí)行上述算法,就可以保證每一個(gè)元素都被且僅被右移一次,從而滿(mǎn)足題目要求.也就是說(shuō),A的所有元素分別處在p個(gè)"循環(huán)鏈"上面.舉例如下:n=15,k=6,則p=3. 第一條鏈: listElem0->listElem6, listElem6->listElem12, listElem12-> listElem3, listElem3-> listElem9, listElem9-> listElem0. 第二條鏈: listElem1->listElem7, listElem7-&g

11、t;listElem13, listElem13-> listElem4, listElem4->listElem10, listElem10-> listElem1. 第三條鏈: listElem2-> listElem8, listElem8-> listElem14, listElem14->listElem5, listElem5->listElem11, listElem11->listElem2.恰好使所有元素都右移一次.雖然未經(jīng)數(shù)學(xué)證明,但相信上述規(guī)律應(yīng)該是正確的.3. 編寫(xiě)一個(gè)單鏈表類(lèi)的成員函數(shù)，實(shí)現(xiàn)在非遞減的有序單鏈表中插入一個(gè)

12、值為x的數(shù)據(jù)元素，并使單鏈表仍保持有序的操作。參考答案(方法一):public void insert(int x) Node p = head.getNext();/p指向首結(jié)點(diǎn)Node q = head;/ q用來(lái)記錄p的前驅(qū)結(jié)點(diǎn)int temp;while (p != null) temp = (Integer) p.getData().intValue();if (temp < x) q = p;p = p.getNext(); elsebreak;Node s = new Node(x); / 生成新結(jié)點(diǎn)s.setNext(p);/ 將s結(jié)點(diǎn)插入到單鏈表的q結(jié)點(diǎn)與p結(jié)點(diǎn)之間q.

13、setNext(s);參考答案(方法二):public void insert(int x) Node p = head.getNext(); /p指向首結(jié)點(diǎn)while (p.getNext()!= null&&(Integer) p.getNext().getData().intValue()<x) p = p.getNext();Node s = new Node(x); / 生成新結(jié)點(diǎn)s.setNext(p.getNext();/ 將s結(jié)點(diǎn)插入到單鏈表的q結(jié)點(diǎn)與p結(jié)點(diǎn)之間p.setNext(s);4. 編寫(xiě)一個(gè)單鏈表類(lèi)的成員函數(shù)，實(shí)現(xiàn)對(duì)帶頭結(jié)點(diǎn)的單鏈表就地逆置的操作

14、。所謂逆置，就是把（a1,a2,an）變成（an,an-1,a1）；所謂就地，就是指逆置后的結(jié)點(diǎn)仍存儲(chǔ)在原來(lái)單鏈表的存儲(chǔ)空間中，只不過(guò)通過(guò)修改鏈來(lái)改變單鏈表中每一個(gè)結(jié)點(diǎn)之間的邏輯位置關(guān)系。參考答案:public void reverse() /實(shí)現(xiàn)對(duì)單鏈表就地逆置(采用的是頭插法)Node p = head.getNext();head.setNext(null);Node q;while (p != null) q = p.getNext();p.setNext(head.getNext();head.setNext(p);p = q;5. 編寫(xiě)一個(gè)單鏈表類(lèi)的成員函數(shù)，實(shí)現(xiàn)刪除不帶頭結(jié)點(diǎn)的單

15、鏈表中數(shù)據(jù)域值等于x的第一個(gè)結(jié)點(diǎn)的操作。若刪除成功，則返回被刪除結(jié)點(diǎn)的位置；否則，返回-1。參考答案: public int remove(Object x) Node p = head;/ 初始化,p指向首結(jié)點(diǎn)Node q=null; /q用來(lái)記錄p的前驅(qū)結(jié)點(diǎn) int j = 0; /j為計(jì)數(shù)器/ 從單鏈表中的首結(jié)點(diǎn)元素開(kāi)始查找，直到p.getData()指向元素x或到達(dá)單鏈表的表尾while (p != null && !p.getData().equals(x) q=p; p = p.getNext();/ 指向下一個(gè)元素 +j;/ 計(jì)數(shù)器的值增1 if (p!=null

16、&&q=null) /刪除的是單鏈表中的首結(jié)點(diǎn) head=p.getNext(); else if (p != null) / 刪除的是單鏈表中的非首結(jié)點(diǎn) q.setNext(p.getNext(); else return -1;/值為x的結(jié)點(diǎn)在單鏈表中不存在 return j; 6. 編寫(xiě)一個(gè)單鏈表類(lèi)的成員函數(shù)，實(shí)現(xiàn)刪除帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于x的所有結(jié)點(diǎn)的操作。要求函數(shù)返回被刪除結(jié)點(diǎn)的個(gè)數(shù)。參考答案:public int removeAll(Object x) Node p = head.getNext();/ 初始化,p指向首結(jié)點(diǎn),j為計(jì)數(shù)器Node q = he

17、ad; / 用來(lái)記錄p的前驅(qū)結(jié)點(diǎn)int j = 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ù)器的值增1 elseq = p;p = p.getNext();/ 指向下一個(gè)元素return j;/ 返回被刪除結(jié)點(diǎn)的個(gè)數(shù)7. 編寫(xiě)一個(gè)多項(xiàng)式類(lèi)的成員函數(shù)，實(shí)現(xiàn)將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式的操作，并使兩個(gè)多項(xiàng)式中各自?xún)H含奇次項(xiàng)或偶次項(xiàng)。要求利用原來(lái)循環(huán)鏈表中的存儲(chǔ)空間構(gòu)成這兩個(gè)鏈表。參考答案:public

18、CircleLinkList separatePolyn(CircleLinkList cList) CircleLinkList cList1 = new CircleLinkList();/ 含奇次項(xiàng)的多項(xiàng)式Node p1 = cList1.getHead();/ p2指向奇次項(xiàng)多項(xiàng)式的頭結(jié)點(diǎn)CircleLinkList cList2 = new CircleLinkList();/ 含偶次項(xiàng)的多項(xiàng)式Node p2 = cList2.getHead();/ p2指向偶次項(xiàng)多項(xiàng)式的頭結(jié)點(diǎn)Node p = cList.getHead().getNext();/ 原多項(xiàng)式的首結(jié)點(diǎn)while (p!=cList.getHea