ds第二章課后習(xí)題答案

1、第二章線性表2.1填空題(1)一半插入或刪除的位置(2)靜態(tài)動(dòng)態(tài)(3)一定不一定(4)頭指針頭結(jié)點(diǎn)的next前一個(gè)元素的next2.2選擇題(1)A(2)DAGKHDAELIAFIFA(IDA)(3)D(4)D(5)D2.3頭指針：在帶頭結(jié)點(diǎn)的鏈表中，頭指針存儲(chǔ)頭結(jié)點(diǎn)的地址；在不帶頭結(jié)點(diǎn)的鏈表中，頭指針存放第一個(gè)元素結(jié)點(diǎn)的地址；頭結(jié)點(diǎn)：為了操作方便，在第一個(gè)元素結(jié)點(diǎn)前申請(qǐng)一個(gè)結(jié)點(diǎn)，其指針域存放第一個(gè)元素結(jié)點(diǎn)的地址，數(shù)據(jù)域可以什么都不放；

2、首元素結(jié)點(diǎn)：第一個(gè)元素的結(jié)點(diǎn)。2.4已知順序表L遞增有序，寫一算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。voidInserList(SeqListLElemTypex)inti=Llastif(Llast=MAXSIZE1)returnFALSE順序表已滿while(i=0iLelem[i1]=xLlast2.5刪除順序表中從i開(kāi)始的k個(gè)元素intDelList(SeqListLintiintk)intjlif(iLla

3、st)printf(“TheInitialPositionisErr!“)return0if(k=Llast)Llast=LlastkmodifythelengthijLlast=i12.7編寫算法，在一非遞減的順序表L中，刪除所有值相等的多余元素。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。voidRepeatItem(SeqListL)inti=0j=1while(jlast)if(Lelem[i]==Lelem[j])jels

4、eLelem[i1]==Lelem[j]ijLlast=i2.8已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度。voidDelData(LinkListLElemTypeminkElemTypemaxk)Nodep=Lnextpre=Lwhile(!pwhile(p)if(pdatamaxk)breakels