數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法試題

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法試題1．假設(shè)有兩個(gè)按元素值遞增次序羅列的線性表，均以單鏈表形式存儲(chǔ)。請(qǐng)編寫算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序羅列的單鏈表，并要求利用本來兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。【北京高校1998三、1（5分）】

LinkedListUnion(LinkedListla,lb)

{pa=la->next;pb=lb->next;

la->next=null;

while(pa!=null

pa->next=la->next;∥將pa結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。

la->next=pa;

pa=r;

}

else

{r=pb->next;

pb->next=la->next;∥將pb結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。

la->next=pb;

pb=r;

}

while(pa!=null)∥將la表的剩余部分鏈入結(jié)果表，并逆置。

{r=pa->next;pa->next=la->next;la->next=pa;pa=r;}

while(pb!=null)

{r=pb->next;pb->next=la->next;la->next=pb;pb=r;}

}

1）設(shè)有兩個(gè)無頭結(jié)點(diǎn)的單鏈表,頭指針分離為ha,hb,鏈中有數(shù)據(jù)域data,鏈域next,兩鏈表的數(shù)據(jù)都按遞增序存放,現(xiàn)要求將hb表歸到ha表中,且歸并后ha仍遞增序,歸并中ha表中已有的數(shù)據(jù)若hb中也有,則hb中的數(shù)據(jù)不歸并到ha中,hb的鏈表在算法中不允許破壞?！灸暇├砉じ咝?997四、3（15分）】

LinkedListUnion(LinkedListha,hb)∥ha和hb是兩個(gè)無頭結(jié)點(diǎn)的數(shù)據(jù)域值遞增有序的單鏈

｛LinkedList表，本算法將hb中并不浮現(xiàn)在ha中的數(shù)據(jù)合并到ha中，合并中不能破壞hb鏈表。

la;

la=(LinkedList)malloc(sizeof(LNode));

la->next=ha;

pa=ha;

pb=hb;

pre=la;

while(papre=pa;pa=pa->next;}

elseif(pa->data>pb->data)∥處理hb中數(shù)據(jù)。

{r=(LinkedList)malloc(sizeof(LNode));

r->data=pb->data;pre->next=r;

pre=r;

pb=pb->next;}

Else∥處理pa->data=pb->data;

{pre->next=pa;pre=pa;

pa=pa->next;∥兩結(jié)點(diǎn)數(shù)據(jù)相等時(shí)，只將ha的數(shù)據(jù)鏈入。

pb=pb->next;

}

if(pa!=null)pre->next=pa;∥將兩鏈表中剩余部分鏈入結(jié)果鏈表。

elsepre->next=pb;

free(la);

}

2）已知頭指針分離為la和lb的帶頭結(jié)點(diǎn)的單鏈表中，結(jié)點(diǎn)按元素值非遞減有序羅列。寫出將la和lb兩鏈表歸并成一個(gè)結(jié)點(diǎn)按元素值非遞減有序羅列的單鏈表（其頭指針為lc），并計(jì)算算法的時(shí)光復(fù)雜度?！狙嗌礁咝?998五（20分）】

pa=la->next;pb=hb->next;

lc=(LinkedList)malloc(sizeof(LNode));

pc=lc;∥pc是結(jié)果鏈表中當(dāng)前結(jié)點(diǎn)的前驅(qū)

while(papc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next;}

if(pa)pc->next=pa;elsepc->next=pb;

free(la);free(lb);∥釋放本來兩鏈表的頭結(jié)點(diǎn)。

2.設(shè)帶頭結(jié)點(diǎn)且頭指針為ha和hb的兩線性表A和B分離表示兩個(gè)集合。兩表中的元素皆為遞增有序。請(qǐng)寫一算法求A和B的并集AUB。要求該并集中的元素仍保持遞增有序。且要利用A和B的原有結(jié)點(diǎn)空間?！颈本┼]電高校1992二（15分）】

LinkedListUnion(LinkedListha,hb)

{pa=ha->next;pb=hb->next;∥設(shè)工作指針pa和pb。

pc=ha;∥pc為結(jié)果鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)指針。

while(papc=pa;pa=pa->next;}

elseif(pa->data>pb->data)

{pc->next=pb;pc=pb;pb=pb->next;}

Else{pc->next=pa;pc=pa;pa=pa->next;∥處理pa->data=pb->data.

u=pb;pb=pb->next;free(u);}

if(pa)pc->next=pa;∥若ha表未空，則鏈入結(jié)果表。

elsepc->next=pb;∥若hb表未空，則鏈入結(jié)果表。

free(hb);return(ha);

}

1）已知遞增有序的兩個(gè)單鏈表A，B分離存儲(chǔ)了一個(gè)集合。設(shè)計(jì)算法實(shí)現(xiàn)求兩個(gè)集合的并集的運(yùn)算A:=A∪B【合肥工業(yè)高校1999五、1（8分）】解答徹低同上2

2）已知兩個(gè)鏈表A和B分離表示兩個(gè)集合，其元素遞增羅列。編一函數(shù)，求A與B的交集，并存放于A鏈表中。【南京航空航天高校2022六（10分）】

pa=la->next;pb=lb->next;

pc=la;∥結(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(qū)的指針。

while(papc=pa;pa=pa->next;u=pb;pb=pb->next;free(u);}

elseif(pa->datadata){u=pa;pa=pa->next;free(u);}

else{u=pb;pb=pb->next;free(u);}

while(pa){u=pa;pa=pa->next;free(u);}

while(pb){u=pb;pb=pb->next;free(u);}

pc->next=null;

free(lb);∥注：本算法中也可對(duì)B表不作釋放空間的處理

3）設(shè)有兩個(gè)從小到大排序的帶頭結(jié)點(diǎn)的有序鏈表。試編寫求這兩個(gè)鏈表交運(yùn)算的算法（即L1∩L2）。要求結(jié)果鏈表仍是從小到大排序，但無重復(fù)元素?！灸暇┖娇蘸教旄咝＃?0分）】pa=L1->next;pb=L2->next;∥pa、pb是兩鏈表的工作指針。

pc=L1;∥L1作結(jié)果鏈表的頭指針。

while(papa=pa->next;free(u);}∥刪除L1表多余元素

elseif(pa->data>pb->data)pb=pb->next;∥pb指針后移

else∥處理交集元素

{if(pc==L1){pc->next=pa;pc=pa;pa=pa->next;}∥處理第一個(gè)相等的元素。

elseif(pc->data==pa->data){u=pa;pa=pa->next;free(u);}∥重復(fù)元素不進(jìn)入L1表。

else{pc->next=pa;pc=pa;pa=pa->next;}∥交集元素并入結(jié)果表。

}∥while

while(pa){u=pa;pa=pa->next;free(u);}∥刪L1表剩余元素

pc->next=null;∥置結(jié)果鏈表尾

5）已知遞增有序的單鏈表A,B和C分離存儲(chǔ)了一個(gè)集合，設(shè)計(jì)算法實(shí)現(xiàn)A：=A∪（B∩C），并使求解結(jié)構(gòu)A仍保持遞增。要求算法的時(shí)光復(fù)雜度為O(|A|+|B|+|C|)。其中,|A|為集合A的元素個(gè)數(shù)?！竞戏使I(yè)高校2000五、1（8分）】

LinkedListunion(LinkedListA,B,C)

{pa=A->next;pb=B->next;pc=C->next;∥設(shè)置三個(gè)工作指針。

pre=A;∥pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。

if(pa->datadata||pa->datadata)∥A中第一個(gè)元素為結(jié)果表的第一元素。

{pre->next=pa;pre=pa;pa=pa->next;}

else{while(pb

elseif(pb->data>pc->data)pc=pc->next;

elsebreak;∥找到B表和C表的共同元素就退出while循環(huán)。

if(pbpre=pb;pb=pb->next;pc=pc->next;}∥B，C公共元素為結(jié)果表第一元素。

}∥結(jié)束了結(jié)果表中第一元素確實(shí)定

while(pa

elseif(pb->data>pc->data)pc=pc->next;

elsebreak;∥B表和C表有公共元素。

if(pbpre=pa;pa=pa->next;}

if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}

else{pb=pb->next;pc=pc->next;}∥若A中已有B，C公共元素，則不再存入結(jié)果表。

}

}∥while(pa∥當(dāng)B，C無公共元素（即一個(gè)表已空），將A中剩余鏈入。

}

3.知L1、L2分離為兩循環(huán)單鏈表的頭結(jié)點(diǎn)指針，m,n分離為L1、L2表中數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù)。要求設(shè)計(jì)一算法，用最迅速度將兩表合并成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表。【東北高校1996二(12分)】

LinkedListUnion(LinkedListL1,L2;intm,n)

∥L1和L2分離是兩循環(huán)單鏈表的頭結(jié)點(diǎn)的指針，m和n分離是L1和L2的長度。

∥本算法用最迅速度將L1和L2合并成一個(gè)循環(huán)單鏈表。

{if(mnext!=L1)p=p->next;∥查最后一個(gè)元素結(jié)點(diǎn)。

p->next=L2->next;∥將L1循環(huán)單鏈表的元素結(jié)點(diǎn)插入到L2的第一元素結(jié)點(diǎn)前。

L2->next=L1->next;

free(L1);∥釋放無用頭結(jié)點(diǎn)。

}

}∥處理完mnext!=L2)p=p->next;∥查最后元素結(jié)點(diǎn)。

p->next=L1->next;∥將L2的元素結(jié)點(diǎn)插入到L1循環(huán)單鏈表的第一元素結(jié)點(diǎn)前。

L1->next=L2->next;

free(L2);∥釋放無用頭結(jié)點(diǎn)。

}

}

1）試用類Pascal語言編寫過程PROCjoin（VARla：link；lb：link）實(shí)現(xiàn)銜接線性表la和lb(lb在后)的算法，要求其時(shí)光復(fù)雜度為0（1），占用輔助空間盡量小。描述所用結(jié)構(gòu)?！颈本┕I(yè)高校1997一、1(8分)】

LinkedListUnion(LinkedListla,lb)

∥la和lb是兩個(gè)無頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，本算法將lb接在la后，成為一個(gè)單循環(huán)鏈表。

{q=la->next;∥q指向la的第一個(gè)元素結(jié)點(diǎn)。

la->next=lb->next;∥將lb的最后元素結(jié)點(diǎn)接到lb的第一元素。

lb->next=q;∥將lb指向la的第一元素結(jié)點(diǎn)，實(shí)現(xiàn)了lb接在la后。

return(lb);∥返回結(jié)果單循環(huán)鏈表的尾指針lb。

}

2）設(shè)有兩個(gè)鏈表，ha為單向鏈表，hb為單向循環(huán)鏈表。編寫算法，將兩個(gè)鏈表合并成一個(gè)單向鏈表，要求算法所需時(shí)光與鏈表長度無關(guān)。【南京航空航天高校1997四（8分）】

若循環(huán)單鏈表帶有頭結(jié)點(diǎn)，則相應(yīng)算法片段如下：

q=lb->next;∥q指向lb的頭結(jié)點(diǎn)；

lb->next=la->next;∥lb的后繼結(jié)點(diǎn)為la的頭結(jié)點(diǎn)。

la->next=q->next;∥la的后繼結(jié)點(diǎn)為lb的第一元素結(jié)點(diǎn)。

free(q);∥釋放lb的頭結(jié)點(diǎn)

return(lb);∥返回結(jié)果單循環(huán)鏈表的尾指針lb。

其核心算法片段如下（設(shè)兩鏈表均有頭結(jié)點(diǎn)）

q=hb->next;∥單向循環(huán)鏈表的表頭指針

hb->next=ha->next;∥將循環(huán)單鏈表最后元素結(jié)點(diǎn)接在ha第一元素前。

ha->next=q->next;∥將指向原單鏈表第一元素的指針指向循環(huán)單鏈表第一結(jié)點(diǎn)

free(q);∥釋放循環(huán)鏈表頭結(jié)點(diǎn)。

若兩鏈表均不帶頭結(jié)點(diǎn)，則算法片段如下：

q=hb->next;∥q指向hb首元結(jié)點(diǎn)。

hb->next=ha;∥hb尾結(jié)點(diǎn)的后繼是ha第一元素結(jié)點(diǎn)。

ha=q;∥頭指針指向hb