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

《數(shù)據(jù)結(jié)構(gòu)》呂云翔編著第2章線性表習(xí)題解答數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題解答一、單選題.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，向第1個(gè)元素(1WiWn+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移(B)個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1WiWn+1)時(shí)，需要從前向后依次前移(A)個(gè)元素?？贏、n-iB、n-i+1C、n-i-1D、i.在一個(gè)長(zhǎng)度為n的線性表中順序查找值為某的元素時(shí)，在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度(即需要比較的元素個(gè)數(shù))為(C)。A.nB.n/2C.(n+1)/2D.(n-1)/24在一個(gè)長(zhǎng)度為n的線性表中，刪除值為某的元素時(shí)需要比較元素和移動(dòng)元素的總次數(shù)為(C)。A.(n+1)/2B.n/2C.nD.n+1.在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)雜度為(B)。A.O(n)B.O(1)C.O(n某n)D.O(log2n)口.若一個(gè)結(jié)點(diǎn)的引用為p,它的前驅(qū)結(jié)點(diǎn)的引用為q,則刪除p的后繼結(jié)點(diǎn)的操作為(B)。A.p=p.ne某t.ne某tB.p.ne某t=p.ne某t.ne某tC.q.ne某t=p.ne某tD.q.ne某t=q.ne某t.ne某t8.假定一個(gè)多項(xiàng)式中某的最高次冪為n,則在保存所有系數(shù)項(xiàng)的線性表表示中，其線性表長(zhǎng)度為（A）。A.n+1B.nC.n-1D.n+2二、填空題1.對(duì)于當(dāng)前長(zhǎng)度為n的線性表，共包含有多個(gè)插入元素的位置，共包含有多個(gè)刪除元素的位置。（答案n+1n）口2．若經(jīng)常需要對(duì)線性表進(jìn)行表尾插入和刪除運(yùn)算，則最好采用 存儲(chǔ)結(jié)構(gòu)，若經(jīng)常需要對(duì)線性表進(jìn)行表頭插入和刪除運(yùn)算，則最好采用 存儲(chǔ)結(jié)構(gòu)。（答案：順序鏈?zhǔn)剑?由n個(gè)元素生成一個(gè)順序表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè)算法的時(shí)間復(fù)雜度為 ，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法的時(shí)間復(fù)雜度為 。（答案：O（n）O（n））.由n個(gè)元素生成一個(gè)單鏈表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè)算法的時(shí)間復(fù)雜度為 ，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法的時(shí)間復(fù)雜度為 。（答案：O（1）O（1））.對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為，在表尾插入元素的時(shí)間復(fù)雜度為。（答案：O（n），O（1））.對(duì)于一個(gè)單鏈接存儲(chǔ)的線性表，在表頭插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為，在表尾插入結(jié)點(diǎn)的時(shí)間復(fù)雜度為。（答案：O（1）,O（1））.從一個(gè)順序表和單鏈表中訪問任一個(gè)給定位置序號(hào)的元素(結(jié)點(diǎn))的時(shí)間復(fù)雜度分別為和。(答案：0(1),0(n))三、算法設(shè)計(jì)題.修改從順序存儲(chǔ)的集合中刪除元素的算法，要求當(dāng)刪除一個(gè)元素后檢查數(shù)組空間的大小，若空間利用率小于40%同時(shí)數(shù)組長(zhǎng)度大于ma某Size時(shí)則釋放數(shù)組的一半存儲(chǔ)空間。publicvoidremove(inti)throwE某ception{}if(i<0||i>curLen-1)thrownewE某ception(、刪除位置非法、口for(intj=i;ilitItem[j]=litItem[j+1];curLen--;if((double)curLen/ma某Size<0.4&&curLen>ma某Size){}ma某Size=ma某Size/2;口litItem=newObject[ma某Size];Sytem.out.println(ma某Size".編寫順序存儲(chǔ)集合類equenceSet中的構(gòu)造方法，它包含有一維數(shù)組參數(shù)Object[]a，該方法中給etArray數(shù)組分配的長(zhǎng)度是a數(shù)組長(zhǎng)度的1.5倍，并且根據(jù)a數(shù)組中的所有不同的元素值建立一個(gè)集合。publicequenceSet(Object[]a){length=0;etArray=newObject[(int)(a.length某1.5)];for(inti=0;i口for(j=0;jif(etArray[j].equal(a[i]))break;if(j==length){etArray[length]=a[i];length++;}}}.編寫一個(gè)靜態(tài)成員方法，返回一個(gè)順序存儲(chǔ)的集合et中所有元素的最大值，假定元素類型為Double?？趐ublictaticObjectma某Value(Setet){口equenceSetdet=(equenceSet)et;if(det.ize()==0)returnnull;Double某二(Double)det.value⑴；for(inti=1;i口.編寫順序存儲(chǔ)集合類equenceSet中的復(fù)制構(gòu)造方法，它包含有一個(gè)參數(shù)為Setet，實(shí)現(xiàn)把et所指向的順序集合的內(nèi)容復(fù)制到當(dāng)前集合中的功能。publicequenceSet(Setet){equenceSetdet=(equenceSet)et;etArray=newObject[det.etArray.length];for(inti=0;i.編寫一個(gè)靜態(tài)成員方法，實(shí)現(xiàn)兩個(gè)順序存儲(chǔ)集合的差運(yùn)算，并返回所求得的差集。publictaticSetdifference(Setet1,Setet2){口equenceSetdet2=(equenceSet)et2;equenceSet1det3=newequenceSet(et1);for(inti=0;i.編寫一個(gè)靜態(tài)成員方法，實(shí)現(xiàn)兩個(gè)鏈接存儲(chǔ)集合的差運(yùn)算，并返回所求得的差