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

1、1 假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點存放歸并后的單鏈表?！颈本┐髮W(xué) 1998 三、1 （5分）】linkedlist union(linkedlist la,lb) pa=la-next; pb=lb-next; la-next=null; while(pa!=null & pb!=null) 當(dāng)兩鏈表均不為空時作if(pa-datadata) r=pa-next; pa-next=la-next; 將pa結(jié)點鏈于結(jié)果表中，同時逆置。la-next=pa;pa=r; elser

2、=pb-next; pb-next=la-next; 將pb結(jié)點鏈于結(jié)果表中，同時逆置。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è)有兩個無頭結(jié)點的單鏈表,頭指針分別為ha,hb,鏈中有數(shù)據(jù)域data,鏈域next,兩鏈表的數(shù)據(jù)都按遞增序存放,現(xiàn)要求將hb表歸到ha表中,且歸并后ha仍遞增序,歸并中ha表中已有的數(shù)據(jù)若

3、hb中也有,則hb中的數(shù)據(jù)不歸并到ha中,hb的鏈表在算法中不允許破壞?！灸暇├砉ご髮W(xué)1997 四、3（15分）】linkedlist union(linkedlist ha, hb) ha和hb是兩個無頭結(jié)點的數(shù)據(jù)域值遞增有序的單鏈表，本算法將hb中并不出現(xiàn)在ha中的數(shù)據(jù)合并到ha中，合并中不能破壞hb鏈表。 linkedlist la;la=(linkedlist)malloc(sizeof(lnode);la-next=ha; pa=ha; pb=hb; pre=la; while(pa&pb)if(pa-datadata) 處理ha中數(shù)據(jù)pre-next=pa;pre=pa;pa=pa

4、-next;else if(pa-datapb-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é)點數(shù)據(jù)相等時，只將ha的數(shù)據(jù)鏈入。pb=pb-next; if(pa!=null)pre-next=pa; 將兩鏈表中剩余部分鏈入結(jié)果鏈表。else pre-next=pb;free(la); 2）已知頭指針分別為la和lb 的帶頭結(jié)點的單鏈

5、表中，結(jié)點按元素值非遞減有序排列。寫出將la 和 lb兩鏈表歸并成一個結(jié)點按元素值非遞減有序排列的單鏈表（其頭指針為 lc），并計算算法的時間復(fù)雜度?！狙嗌酱髮W(xué) 1998 五 （20分）】pa=la-next;pb=hb-next;lc=(linkedlist )malloc(sizeof(lnode);pc=lc; pc是結(jié)果鏈表中當(dāng)前結(jié)點的前驅(qū)while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;if(pa)pc-next=pa; else pc-next=pb;fre

6、e(la);free(lb); 釋放原來兩鏈表的頭結(jié)點。2. 設(shè)帶頭結(jié)點且頭指針為ha和hb的兩線性表a和b 分別表示兩個集合。兩表中的元素皆為遞增有序。請寫一算法求a和b的并集aub。要求該并集中的元素仍保持遞增有序。且要利用a和b的原有結(jié)點空間。【北京郵電大學(xué) 1992 二 （15分）】linkedlist union(linkedlist ha,hb) pa=ha-next; pb=hb-next;設(shè)工作指針pa和pb。pc=ha;pc為結(jié)果鏈表當(dāng)前結(jié)點的前驅(qū)指針。while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else if

7、(pa-datapb-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é)果表。else pc-next=pb; 若hb表未空，則鏈入結(jié)果表。free(hb); return(ha);1）已知遞增有序的兩個單鏈表a，b分別了一個集合。設(shè)計算法實現(xiàn)求兩個集合的并集的運算a:=ab【合肥工業(yè)大學(xué) 1999 五、1（8分）】解答完全同上22）已知兩個鏈表a和b分別表示兩個集合，

8、其元素遞增排列。編一函數(shù)，求a與b的交集，并存放于a鏈表中?！灸暇┖娇蘸教齑髮W(xué) 2001 六（10分）】pa=la-next;pb=lb-next; pc=la; 結(jié)果表中當(dāng)前合并結(jié)點的前驅(qū)的指針。while(pa&pb)if(pa-data=pb-data) 交集并入結(jié)果表中。pc-next=pa; pc=pa; pa=pa-next; u=pb; pb=pb-next; free(u);else if(pa-datadata) u=pa;pa=pa-next; free(u);else u=pb; pb=pb-next; free(u);while(pa) u=pa; pa=pa-next

9、; free(u); while(pb) u=pb; pb=pb-next; free(u); pc-next=null; free(lb); 注： 本算法中也可對b表不作釋放空間的處理3）設(shè)有兩個從小到大排序的帶頭結(jié)點的有序鏈表。試編寫求這兩個鏈表交運算的算法（即l1l2）。要求結(jié)果鏈表仍是從小到大排序，但無重復(fù)元素?！灸暇┖娇蘸教齑髮W(xué) （10分）】pa=l1-next;pb=l2-next; pa、pb是兩鏈表的工作指針。pc=l1;l1作結(jié)果鏈表的頭指針。while(pa&pb)if(pa-datadata) u=pa;pa=pa-next;free(u); 刪除l1表多余元素else

10、if (pa-datapb-data) pb=pb-next; pb指針后移else 處理交集元素if(pc=l1) pc-next=pa;pc=pa;pa=pa-next; 處理第一個相等的元素。else if(pc-data=pa-data) u=pa;pa=pa-next;free(u); 重復(fù)元素不進入l1表。else pc-next=pa;pc=pa;pa=pa-next; 交集元素并入結(jié)果表。 whilewhile(pa) u=pa;pa=pa-next;free(u); 刪l1表剩余元素pc-next=null; 置結(jié)果鏈表尾5）已知遞增有序的單鏈表a,b和c分別存儲了一個集合，

11、設(shè)計算法實現(xiàn)a：=a（bc），并使求解結(jié)構(gòu)a仍保持遞增。要求算法的時間復(fù)雜度為o(|a|+|b|+|c|)。其中,|a|為集合a的元素個數(shù)?！竞戏使I(yè)大學(xué) 2000 五、1（8分）】linkedlist union(linkedlist a,b,c)pa=a-next;pb=b-next;pc=c-next; 設(shè)置三個工作指針。pre=a; pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點的前驅(qū)。if(pa-datadata|pa-datadata) a中第一個元素為結(jié)果表的第一元素。pre-next=pa;pre=pa;pa=pa-next;elsewhile(pb&pc) 找b表和c表中第一個公共元素。

12、if(pb-datadata)pb=pb-next;else if(pb-datapc-data)pc=pc-next;else break; 找到b表和c表的共同元素就退出while循環(huán)。if(pb&pc) 因共同元素而非b表或c表空而退出上面while循環(huán)。if(pa-datapb-data) a表當(dāng)前元素值大于b表和c表的公共元素，先將b表元素鏈入。pre-next=pb;pre=pb;pb=pb-next;pc=pc-next; b，c公共元素為結(jié)果表第一元素。 結(jié)束了結(jié)果表中第一元素的確定while(pa&pb&pc)while(pb&pc)if(pb-datadata) pb=pb

13、-next;else if(pb-datapc-data) pc=pc-next;else break; b表和c表有公共元素。if(pb&pc)while(pa&pa-datadata) 先將a中小于b，c公共元素部分鏈入。pre-next=pa;pre=pa;pa=pa-next;if(pre-data!=pb-data)pre-next=pb;pre=pb;pb=pb-next;pc=pc-next;elsepb=pb-next;pc=pc-next; 若a中已有b，c公共元素，則不再存入結(jié)果表。 while(pa&pb&pc)if(pa) pre-next=pa; 當(dāng)b，c無公共元素（

14、即一個表已空），將a中剩余鏈入。3. 知l1、l2分別為兩循環(huán)單鏈表的頭結(jié)點指針，m,n分別為l1、l2表中數(shù)據(jù)結(jié)點個數(shù)。要求設(shè)計一算法，用最快速度將兩表合并成一個帶頭結(jié)點的循環(huán)單鏈表?！緰|北大學(xué)1996 二 (12分)】linkedlist union(linkedlist l1,l2;int m,n)l1和l2分別是兩循環(huán)單鏈表的頭結(jié)點的指針，m和n分別是l1和l2的長度。本算法用最快速度將l1和l2合并成一個循環(huán)單鏈表。if(m0|n0) printf(“表長輸入錯誤n”)；exit(0);if(mn) 若mnext!=l1) p=p-next; 查最后一個元素結(jié)點。p-next=l2-

15、next; 將l1循環(huán)單鏈表的元素結(jié)點插入到l2的第一元素結(jié)點前。l2-next=l1-next;free(l1); 釋放無用頭結(jié)點。處理完mnext!=l2) p=p-next; 查最后元素結(jié)點。p-next=l1-next; 將l2的元素結(jié)點插入到l1循環(huán)單鏈表的第一元素結(jié)點前。l1-next=l2-next;free(l2); 釋放無用頭結(jié)點。1）試用類pascal語言編寫過程proc join（var la：link； lb：link） 實現(xiàn)連接線性表la和lb(lb在后)的算法，要求其時間復(fù)雜度為0（1）， 占用輔助空間盡量小。描述所用結(jié)構(gòu)?！颈本┕I(yè)大學(xué) 1997 一、1 (8分)

16、】linkedlist union(linkedlist la,lb)la和lb是兩個無頭結(jié)點的循環(huán)單鏈表的尾指針，本算法將lb接在la后，成為一個單循環(huán)鏈表。 q=la-next; q指向la的第一個元素結(jié)點。la-next=lb-next; 將lb的最后元素結(jié)點接到lb的第一元素。lb-next=q; 將lb指向la的第一元素結(jié)點，實現(xiàn)了lb接在la后。return(lb); 返回結(jié)果單循環(huán)鏈表的尾指針lb。2）設(shè)有兩個鏈表，ha為單向鏈表，hb為單向循環(huán)鏈表。編寫算法，將兩個鏈表合并成一個單向鏈表，要求算法所需時間與鏈表長度無關(guān)?！灸暇┖娇蘸教齑髮W(xué) 1997 四（8分）】若循環(huán)單鏈表帶有

17、頭結(jié)點，則相應(yīng)算法片段如下：q=lb-next; q指向lb的頭結(jié)點；lb-next=la-next; lb的后繼結(jié)點為la的頭結(jié)點。la-next=q-next; la的后繼結(jié)點為lb的第一元素結(jié)點。free(q); 釋放lb的頭結(jié)點return(lb); 返回結(jié)果單循環(huán)鏈表的尾指針lb。其核心算法片段如下（設(shè)兩鏈表均有頭結(jié)點）q=hb-next; 單向循環(huán)鏈表的表頭指針hb-next=ha-next; 將循環(huán)單鏈表最后元素結(jié)點接在ha第一元素前。ha-next=q-next; 將指向原單鏈表第一元素的指針指向循環(huán)單鏈表第一結(jié)點free(q); 釋放循環(huán)鏈表頭結(jié)點。若兩鏈表均不帶頭結(jié)點，則算法片段如下：q=hb-next; q指向hb首元結(jié)點。hb-next=ha; hb尾結(jié)點的后繼是ha第一元素結(jié)點。ha=q; 頭指針指向hb的首元結(jié)點。4. 順序結(jié)構(gòu)線性表la與lb的結(jié)點關(guān)鍵字為整數(shù)。la與lb的元素按非遞減有序，線性表空間足夠大。試用類pascal語言給出一種高效算法，將lb中元素合到la中，使新的la的元素仍保持非遞減有序。高效指最大限度的避免移動元素。【北京工業(yè)大學(xué) 1997 一、2 (12分)】proc union(var la:seqlist;lb:seqlist)la和lb是順序存儲的非遞減有序線性表，本算法將lb合并到la中，元素