數據結構試題精選（2）-算法設計題_跨考網

五、算法設計題

1． 假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。

【北京大學 1998 三、1 （5分）】

類似本題的另外敘述有：

（1）設有兩個無頭結點的單鏈表,頭指針分別為ha,hb,鏈中有數據域data,鏈域next,兩鏈表的數據都按遞增序存放,現要求將hb表歸到ha表中,且歸并后ha仍遞增序,歸并中ha表中已有的數據若hb中也有,則hb中的數據不歸并到ha中,hb的鏈表在算法中不允許破壞?！?a target="_blank">南京理工大學1997 四、3（15分）】

PROCEDURE?? merge(ha,hb);

（2）已知頭指針分別為la和lb 的帶頭結點的單鏈表中，結點按元素值非遞減有序排列。寫出將la 和 lb兩鏈表歸并成一個結點按元素值非遞減有序排列的單鏈表（其頭指針為 lc），并計算算法的時間復雜度?！?a target="_blank">燕山大學 1998 五 （20分）】

2. 圖（編者略）中帶頭結點且頭指針為ha和hb的兩線性表A和B 分別表示兩個集合。兩表中的元素皆為遞增有序。請寫一算法求A和B的并集AUB。要求該并集中的元素仍保持遞增有序。且要利用A和B的原有結點空間?！?a target="_blank">北京郵電大學 1992 二 （15分）】

類似本題的另外敘述有：

(1) 已知遞增有序的兩個單鏈表A，B分別存儲了一個集合。設計算法實現求兩個集合的并集的運算A:=A∪B【合肥工業(yè)大學 1999 五、1（8分）】

（2）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。編一函數，求A與B的交集，并存放于A鏈表中?！?a target="_blank">南京航空航天大學 2001 六（10分）】

（3）設有兩個從小到大排序的帶頭結點的有序鏈表。試編寫求這兩個鏈表交運算的算法（即L1∩L2）。要求結果鏈表仍是從小到大排序，但無重復元素?！灸暇┖娇蘸教齑髮W 1996 十一（10分）】

（4）己知兩個線性表A ，B均以帶頭結點的單鏈表作存儲結構，且表中元素按值遞增有序排列。設計算法求出A與B的交集C，要求C另開辟存儲空間，要求C同樣以元素值的遞增序的單鏈表形式存貯。

【西北大學 2000 五 ( 8分)】

（5）已知遞增有序的單鏈表A,B和C分別存儲了一個集合，設計算法實現A：=A∪（B∩C），并使求解結構A仍保持遞增。要求算法的時間復雜度為O(|A|+|B|+|C|)。其中,|A|為集合A的元素個數。

【合肥工業(yè)大學 2000 五、1（8分）】

3. 知L1、L2分別為兩循環(huán)單鏈表的頭結點指針，m,n分別為L1、L2表中數據結點個數。要求設計一算法，用最快速度將兩表合并成一個帶頭結點的循環(huán)單鏈表。【東北大學1996 二 (12分)】

類似本題的另外敘述有：

（1）試用類Pascal語言編寫過程PROC join（VAR la：link； lb：link）???? 實現連接線性表la和lb(lb在后)的算法，要求其時間復雜度為0（1）， 占用輔助空間盡量小。描述所用結構。

【北京工業(yè)大學 1997 一、1? (8分)】

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

4. 順序結構線性表LA與LB的結點關鍵字為整數。LA與LB的元素按非遞減有序，線性表空間足夠大。試用類PASCAL語言給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避免移動元素?！颈本┕I(yè)大學 1997 一、2? (12分)】

5. 已知不帶頭結點的線性鏈表list，鏈表中結點構造為（data、link），其中data為數據域，link為指針域。請寫一算法，將該鏈表按結點數據域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結點空間。【北京航空航天大學 1998 五（15分）】

6. 設L為單鏈表的頭結點地址，其數據結點的數據都是正整數且無相同的，試設計利用直接插入的原則把該鏈表整理成數據遞增的有序單鏈表的算法。【東北大學 1996 六 (14分)】

類似本題的另外敘述有：

（1）設一單向鏈表的頭指針為head,鏈表的記錄中包含著整數類型的key域,試設計算法,將此鏈表的記錄按照key遞增的次序進行就地排序.【中科院計算所 1999 五、1（10分）】

7. 設 Listhead為一單鏈表的頭指針，單鏈表的每個結點由一個整數域DATA和指針域NEXT組成，整數在單鏈表中是無序的。編一PASCAL過程，將 Listhead鏈中結點分成一個奇數鏈和一個偶數鏈，分別由P,Q指向，每個鏈中的數據按由小到大排列。程序中不得使用 NEW過程申請空間?！?a target="_blank">山東大學1993六( 15分)】

類似本題的另外敘述有：

（1）設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A的元素類型為整型，要求B、C表利用A表的結點）?！?a target="_blank">北京理工大學 2000 四、2（4分）】

(2) 設L為一單鏈表的頭指針，單鏈表的每個結點由一個整數域 data和指針域NEXT組成，整數在單鏈表中是無序的。設計算法，將鏈表中結點分成一個奇數鏈和一個偶數鏈，分別由P，Q指向，每個鏈中的數據按由小到大排列，算法中不得申請新的結點空間?！厩鄭u海洋大學 1999 三（12分）】

(3) 將一個帶頭結點的單鏈表A分解為兩個帶頭結點的單鏈表A和B，使得A表中含有原表中序號為奇數的元素，而B表中含有原表中序號為偶數的元素，且保持其相對順序不變。

1) 寫出其類型定義：

2) 寫出算法?！旧綎|大學 1998 九 (9分)】 【山東工業(yè)大學 2000 九（9分）】

8. 已知線性表（a1 a2 a3 …an）按順序存于內存，每個元素都是整數，試設計用最少時間把所有值為負數的元素移到全部正數值元素前邊的算法：例：（x,-x,-x,x,x,-x …x）變?yōu)椋?x,-x,-x…x,x,x）。

【東北大學 1998 二 (15分)】

類似本題的另外敘述有：

（1）設有一元素為整數的線性表L=(a1,a2,a3,…,an),存放在一維數組A[N]中,設計一個算法,以表中an作為參考元素,將該表分為左、右兩部分,其中左半部分每個元素小于等于an,右半部分每個元素都大于an, an位于分界位置上(要求結果仍存放在A[N]中)。【北京理工大學 1999 八（6分）】

（2）順序存儲的線性表A,其數據元素為整型,試編寫一算法,將A拆成B和C兩個表,使A中元素值大于等于0的元素放入B,小于0的放入C中.. 要求:

1）表B和C另外設置存儲空間;

2）表B和C不另外設置,而利用A的空間.【山東大學 2001 九、1 (12分)】

（3）知線性表（a1, a2,a3,…,an）按順序存儲，且每個元素都是整數均不相同，設計把所有奇數移到所有偶數前邊的算法。（要求時間最少，輔助空間最少）【東北大學 1997 三 (15分)】