【正文】 Delete_Between(LinkList *L,int mink,int maxk){ p=*L。 　　free(hb)。 　++。 t=pdata。 pprior=q。第2章 　選擇題1．對(duì)于線性表最常用的操作是查找指定序號(hào)的元素和在末尾插入元素，則選擇（ ）最節(jié)省時(shí)間 A）順序表 B）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 C）單鏈表 D）帶尾結(jié)點(diǎn)的單循環(huán)鏈表 【答案】A 2．若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法時(shí)間復(fù)雜度為（　?。?1≤i≤n+1)。 qprior=pprior。 pnext=s。 　[i+1]=x。 　 pnext=hbnext。 【算法分析】 1）查找最后一個(gè)不大于mink的元素結(jié)點(diǎn)，由指針p指向； 2）如果還有比mink更大的元素，查找第一個(gè)不小于maxk的元素，由指針q指向； 3）pnext=q，即刪除表中所有值大于 mink且小于 maxk的元素。 　　　　　　　　　} 　　　　　　　　pnext=q。Lnext=s。 【算法分析】按從小到大的順序依次把A和B的元素插入新表的頭部pc處，最后處理A或B的剩余元素。 /*構(gòu)造新表頭*/}/*reverse_merge*/10．已知A，B和C為三個(gè)遞增有序的線性表，現(xiàn)要求對(duì)A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。 /*j和k后移到新的元素*/ while(i(*A).lengthamp。amp。pnextpre=ppre。 pc=Cnext。 pcdatapadata) pc=pcnext。 /*置A表表尾標(biāo)記*/ while(pa!=NULL) /*刪除原A表剩余元素。p=s。} }/*結(jié)束奇數(shù)鏈結(jié)點(diǎn)*/ s=r。 /*暫存s的后繼*/ if(sdata%2==0) /*處理偶數(shù)*/ if (p==NULL) {p=s。}/*將新結(jié)點(diǎn)鏈入A表 */ pb=pbnext。 else if (pa amp。 【算法分析】留下三個(gè)鏈表中公共數(shù)據(jù)，首先查找兩表A和B中公共數(shù)據(jù)，再去C中找有無(wú)該數(shù)據(jù)。p!= (*L)) p=pnext。 /*p指向第一結(jié)點(diǎn)的后繼*/ lanextnext=NULL。 else if([j][k]) k++。pb=q。 qnext=s。 　　　q=s。 q=pnext?！next=new。試設(shè)計(jì)一個(gè)算法將這兩個(gè)鏈表連接在一起（即令其中一個(gè)表的首元結(jié)點(diǎn)連在另一個(gè)表的最后一個(gè)結(jié)點(diǎn)之后），假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。xamp。 【答案】（1）O(1) （2）O(n) 7. 對(duì)于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共_____________個(gè)，單鏈表為_(kāi)____________個(gè)。 ppriornext=q。 qprior=pprior。 【答案】A 9．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其元素地址（　?。?A）必須是連續(xù)的 B）一定是不連續(xù)的 C）部分地址是連續(xù)的 D）連續(xù)與否均可 【答案】D 　填空題1．線性表L=（a1，a2，…，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_____________。 【答案】144 11．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是_____________。i=amp。 　new=(LinkList*)malloc(sizeof(LNode))。 /*q是第一個(gè)不小于maxk的元素*/ 　　　　pnext=q。 【算法源代碼】 void LinkList_reverse(LinkList L){ if(!Lnext||!Lnextnext) return?！　=Bnext。 　while(pa||pb) 　　{ if(padatapbdata||!pb) /*將A的元素插入新表*/ 　　　　{ pc=pa。 k=0。(*A).elem==same) i++。}12．設(shè)有一個(gè)雙向循環(huán)鏈表，每個(gè)結(jié)點(diǎn)中除有 prior，data和 next三個(gè)域外，還增設(shè)了一個(gè)訪問(wèn)頻度域freq。 /*查找插入位置*/ if(q!=ppre) /*將x結(jié)點(diǎn)插入*/ { qnextpre=p。amp。pre=pa。編一函數(shù)，將 head鏈中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈，分別由p，q指向，每個(gè)鏈中的數(shù)據(jù)按由小到大排列。qnext=NULL。 if (predatasdata) {snext=pre。 【算法分析】本題要求將一個(gè)鏈表分解成兩個(gè)鏈表，兩個(gè)鏈表都要有序，兩鏈表建立過(guò)程中不得使用malloc申請(qǐng)空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。pa=panext。amp。 qnext=p。試編寫(xiě)符合上述要求的 LOCATE操作的算法。 /*A的剩余元素重新存儲(chǔ)*/