數(shù)據(jù)結(jié)構(gòu)試題精選（2）-算法設(shè)計題_跨考網(wǎng)

五、算法設(shè)計題

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

【北京大學(xué) 1998 三、1 （5分）】

類似本題的另外敘述有：

（1）設(shè)有兩個無頭結(jié)點的單鏈表,頭指針分別為ha,hb,鏈中有數(shù)據(jù)域data,鏈域next,兩鏈表的數(shù)據(jù)都按遞增序存放,現(xiàn)要求將hb表歸到ha表中,且歸并后ha仍遞增序,歸并中ha表中已有的數(shù)據(jù)若hb中也有,則hb中的數(shù)據(jù)不歸并到ha中,hb的鏈表在算法中不允許破壞。【南京理工大學(xué)1997 四、3（15分）】

PROCEDURE?? merge(ha,hb);

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

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

類似本題的另外敘述有：

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

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

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

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

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

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

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

3. 知L1、L2分別為兩循環(huán)單鏈表的頭結(jié)點指針，m,n分別為L1、L2表中數(shù)據(jù)結(jié)點個數(shù)。要求設(shè)計一算法，用最快速度將兩表合并成一個帶頭結(jié)點的循環(huán)單鏈表?！?a target="_blank">東北大學(xué)1996 二 (12分)】

類似本題的另外敘述有：

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

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

（2）設(shè)有兩個鏈表，ha為單向鏈表，hb為單向循環(huán)鏈表。編寫算法，將兩個鏈表合并成一個單向鏈表，要求算法所需時間與鏈表長度無關(guān)?！灸暇┖娇蘸教齑髮W(xué) 1997 四（8分）】

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

5. 已知不帶頭結(jié)點的線性鏈表list，鏈表中結(jié)點構(gòu)造為（data、link），其中data為數(shù)據(jù)域，link為指針域。請寫一算法，將該鏈表按結(jié)點數(shù)據(jù)域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結(jié)點空間?！?a target="_blank">北京航空航天大學(xué) 1998 五（15分）】

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

類似本題的另外敘述有：

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

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

類似本題的另外敘述有：

（1）設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點）。【北京理工大學(xué) 2000 四、2（4分）】

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

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

1) 寫出其類型定義：

2) 寫出算法。【山東大學(xué) 1998 九 (9分)】 【山東工業(yè)大學(xué) 2000 九（9分）】

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

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

類似本題的另外敘述有：

（1）設(shè)有一元素為整數(shù)的線性表L=(a1,a2,a3,…,an),存放在一維數(shù)組A[N]中,設(shè)計一個算法,以表中an作為參考元素,將該表分為左、右兩部分,其中左半部分每個元素小于等于an,右半部分每個元素都大于an, an位于分界位置上(要求結(jié)果仍存放在A[N]中)?！颈本├砉ご髮W(xué) 1999 八（6分）】

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

1）表B和C另外設(shè)置存儲空間;

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

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