《數(shù)據(jù)結(jié)構(gòu)》呂云翔編著第2章線性表習(xí)題解答

1、數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題解答一、單選題     1在一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移 （B）  個(gè)元素。         A、n-i       B、n-i+1        C、n-i-1  &#

2、160;    D、i     2在一個(gè)長度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1in+1)時(shí)，需要從前向后依次前移 （A）個(gè)元素。         A、n-i       B、n-i+1        C、n-i-1   &

3、#160;   D、i 3. 在一個(gè)長度為n的線性表中順序查找值為x的元素時(shí)，在等概率情況下，查找成功時(shí) 的平均查找長度（即需要比較的元素個(gè)數(shù)）為( C )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4在一個(gè)長度為 n的線性表中，刪除值為x的元素時(shí)需要比較元素和移動(dòng)元素的總次 數(shù)為(C )。 A. (n+1)/2 B. n/2 C. n D. n+1 5. 在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)雜度為(B )。 A. O(n) B. O(1) C. O(n*n) D. O(log2n) 6.若一個(gè)結(jié)點(diǎn)的引用為p，它的前驅(qū)結(jié)點(diǎn)的

4、引用為q，則刪除p的后繼結(jié)點(diǎn)的操作為(B  )。    A. p=p.next.next             B. p.next=p.next.next    C. q.next=p.next            

5、    D. q.next=q.next.next 8. 假定一個(gè)多項(xiàng)式中x的最高次冪為n，則在保存所有系數(shù)項(xiàng)的線性表表示中，其線性 表長度為(A )。  A. n+1 B. n C. n-1 D. n+2 二、填空題 1對于當(dāng)前長度為n的線性表，共包含有_多個(gè)插入元素的位置，共包含有 _多個(gè)刪除元素的位置。（答案n+1 n） 2若經(jīng)常需要對線性表進(jìn)行表尾插入和刪除運(yùn)算，則最好采用_存儲(chǔ)結(jié)構(gòu)，若經(jīng) 常需要對線性表進(jìn)行表頭插入和刪除運(yùn)算，則最好采用_存儲(chǔ)結(jié)構(gòu)。

6、0;（答案：順序 鏈?zhǔn)剑?由n個(gè)元素生成一個(gè)順序表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè) 算法的時(shí)間復(fù)雜度為_，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法 的時(shí)間復(fù)雜度為_。 （答案： O（n） O（n）4由n個(gè)元素生成一個(gè)單鏈表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè) 算法的時(shí)間復(fù)雜度為_，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法 的時(shí)間復(fù)雜度為_。   （答案： O（1） O（1）5. 對于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_， 在

7、表尾插入元素的時(shí)間復(fù)雜度為_。 （答案：O（n），O（1）6. 對于一個(gè)單鏈接存儲(chǔ)的線性表，在表頭插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為_，在表尾插 入結(jié)點(diǎn)的時(shí)間復(fù)雜度為_。 （答案：O（1），O（1）7. 從一個(gè)順序表和單鏈表中訪問任一個(gè)給定位置序號的元素（結(jié)點(diǎn)）的時(shí)間復(fù)雜度分別 為_和_。（答案：O（1），O（n）三、 算法設(shè)計(jì)題1. 修改從順序存儲(chǔ)的集合中刪除元素的算法，要求當(dāng)刪除一個(gè)元素后檢查數(shù)組空間的大小，若空間利用率小于40%同時(shí)數(shù)組長度大于maxSize時(shí)則釋放數(shù)組的一半存儲(chǔ)空間。public void remove(int i) throws Excep

8、tionif(i<0|i>curLen-1)throw new Exception("刪除位置非法");for(int j=i;i<curLen-1;i+)listItemj=listItemj+1;curLen-;if(double)curLen/maxSize<0.4 && curLen>maxSize) maxSize=maxSize/2;listItem=new ObjectmaxSize; System.out.println(maxSize);2. 編寫順序存儲(chǔ)集合類sequenceSet中的構(gòu)造方法，它包含有一維數(shù)

9、組參數(shù)Object a，該方法中給setArray數(shù)組分配的長度是a數(shù)組長度的1.5倍，并且根據(jù)a數(shù)組中的所有不同的元素值建立一個(gè)集合。public sequenceSet(Object a) length=0; setArray=new Object(int)(a.length*1.5); for(int i=0; i<a.length; i+) int j; for(j=0; j<length; j+) if(setArrayj.equals(ai) break; if(j=length) setArraylength=ai; length+; 3. 編寫一個(gè)靜態(tài)成員方法，返回

10、一個(gè)順序存儲(chǔ)的集合set中所有元素的最大值，假定元素類型為Double。 public static Object maxValue(Set set) sequenceSet dset=(sequenceSet)set; if(dset.size()=0) return null; Double x=(Double)dset.value(1); for(int i=1; i<dset.size(); i+) Double y=(Double)dset.value(i+1); if(pareTo(x)>0) x=y; return x; 4. 編寫順序存儲(chǔ)集合類sequenceSet

11、中的復(fù)制構(gòu)造方法，它包含有一個(gè)參數(shù)為Set set，實(shí)現(xiàn)把set所指向的順序集合的內(nèi)容復(fù)制到當(dāng)前集合中的功能。 public sequenceSet(Set set) sequenceSet dset=(sequenceSet)set; setArray=new Objectdset.setArray.length; for(int i=0; i<dset.length; i+) setArrayi=dset.setArrayi; length=dset.length; 5. 編寫一個(gè)靜態(tài)成員方法，實(shí)現(xiàn)兩個(gè)順序存儲(chǔ)集合的差運(yùn)算，并返回所求得的差集。 public static Set d

12、ifference(Set set1, Set set2) sequenceSet dset2=(sequenceSet)set2; sequenceSet1 dset3=new sequenceSet(set1); for(int i=0; i<dset2.size(); i+) dset3.remove(dset2.value(i+1); return dset3; 6. 編寫一個(gè)靜態(tài)成員方法，實(shí)現(xiàn)兩個(gè)鏈接存儲(chǔ)集合的差運(yùn)算，并返回所求得的差集。 public static Set difference1(Set set1, Set set2) linkSet dset1=(linkS

13、et)set1; linkSet dset2=(linkSet)set2; linkSet dset3=new linkSet(); for(int i=0; i<dset1.size(); i+) dset3.add(dset1.value(i+1); for(int i=0; i<dset2.size(); i+) dset3.remove(dset2.value(i+1); return dset3; 7. 編寫一個(gè)帶有主函數(shù)的程序，其中包含兩個(gè)靜態(tài)成員方法，分別為使用順序和鏈接存儲(chǔ)的線性表解決約瑟夫（Josephus）問題。約瑟夫的問題是：設(shè)有n個(gè)人圍坐在一張圓桌周圍，現(xiàn)從

14、某個(gè)人開始從1報(bào)數(shù)，數(shù)到m的人出列（即離開坐位，不參加以后的報(bào)數(shù)），接著從出列的下一個(gè)人開始重新從1報(bào)數(shù)，數(shù)到m的人又出列，如此下去直到所有人都出列為止，試求出這n個(gè)人的出列次序。 例如，當(dāng)n=8,m=4時(shí)，若從第一個(gè)人開始報(bào)數(shù)，假定n個(gè)人對應(yīng)的編號依次為1、2、n，則得到的出列次序?yàn)椋?,8,5,2,1,3,7,6。 在每個(gè)解決約瑟夫問題的靜態(tài)成員方法中，要求以整型對象n、m和s作為參數(shù)，n表示開始參加報(bào)數(shù)的人數(shù)，m為下一次要出列的人所報(bào)出的數(shù)字序號，s為最開始報(bào)數(shù)的那個(gè)人的編號。 注意：人的座位是首位相接的，所以報(bào)數(shù)是循環(huán)進(jìn)行的，最后一個(gè)人報(bào)數(shù)后，接著是最前面的一個(gè)人報(bào)數(shù)。 參考程序如下：

15、 public class Chap3_15 static void seqJosephus(int n, int m, int s) /使用順序表解決約琵夫問題的算法，n為人數(shù)，每次報(bào)數(shù)到m出列 if(n<=0 | m<=0 | s<=0) System.out.println("參數(shù)值不合法，退出運(yùn)行！"); System.exit(1); sequenceList a=new sequenceList(n); /定義和創(chuàng)建一個(gè)線性表a int i,k; for(i=1; i<=n; i+) a.add(i,i); /插入n個(gè)元素，元素值依次為1

16、n k=s; /給k賦初值為s,開始從編號為s的人起報(bào)數(shù) for(i=1; i<n; i+) /循環(huán)n-1次，每次使一個(gè)人出列 k=(k+m-1)%a.size(); /計(jì)算出待出列的元素序號 if(k=0) k=a.size(); /若k的值為0則應(yīng)修改為表尾的序號 System.out.print(a.value(k)+", "); /輸出序號為k的元素值 a.remove(k); /從線性表中刪除序號為k的元素 System.out.println(a.value(1); /輸出最后剩余的一個(gè)元素的值 static void linkJosephus(int n

17、, int m, int s) /使用鏈表解決約琵夫問題的算法，n為人數(shù) if(n<=0 | m<=0 | s<=0) System.out.println("參數(shù)值不合法，退出運(yùn)行！"); System.exit(1); linkList a=new linkList(); /定義和創(chuàng)建一個(gè)空的線性鏈表a int i,k; for(i=n; i>=1; i-) a.add(i,1); /插入n個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)值依次為1n Node p=a.prior(), q=p.next, head=p; /q指向表頭結(jié)點(diǎn)，p為前驅(qū) k=1; /給k賦初值1 while(k<s) /循環(huán)結(jié)束后q結(jié)點(diǎn)為第s個(gè)結(jié)點(diǎn) p=q; q=q.next; if(q=head) p=q; q=q.next;/若q為附加表頭結(jié)點(diǎn)，則移到表頭 k+; for(i=1; i<n; i+) /循環(huán)n-1次，每次從1報(bào)數(shù)到m k=1; while(k<m) /每次循環(huán)結(jié)束，q指向要出列的結(jié)點(diǎn) p=q; q=q.next; if(q=head) p=q; q=q.next;/使指針跳過表頭附加結(jié)點(diǎn) k+;