數(shù)據(jù)結(jié)構(gòu)線性表有關(guān)題目及答案

仝人收集整理—僅供參生學(xué)且仝人收集整理—僅供參生學(xué)且#/24p=L->next;q=p->next;r=q->next；while（q!=L）{while（p!=L）&&（p->data>q->data）p=p->prior；q->prior->next=r；（1；q->next=p->next；q->prior=p；（2）；X3;q=r；p=q—>prior；⑷；}}【北京理工大學(xué)1999第二部分數(shù)據(jù)結(jié)構(gòu)[7]（8分）】五、算法設(shè)計題．假設(shè)有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結(jié)點存放歸并后的單鏈表。文檔來自于網(wǎng)絡(luò)搜索【北京大學(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中,他的鏈表在算法中不允許破壞?！灸暇├砉ご髮W(xué)1997四、3（15分）】文檔來自于網(wǎng)絡(luò)搜索PROCEDUREmerge（ha,hb）;（2）已知頭指針分別為la和lb的帶頭結(jié)點的單鏈表中，結(jié)點按元素值非遞減有序排列。寫出將la和lb兩鏈表歸并成一個結(jié)點按元素值非遞減有序排列的單鏈表（其頭指針為lc），并計算算法的時間復(fù)雜度?！狙嗌酱髮W(xué)1998五（20分）】文檔來自于網(wǎng)絡(luò)搜索.圖（編者略）中帶頭結(jié)點且頭指針為ha和hb的兩線性表A和B分別表示兩個集合。兩表中的元素皆為遞增有序。請寫一算法求A和B的并集AUB。要求該并集中的元素仍保持遞增有序。且要利用A和B的原有結(jié)點空間?！颈本┼]電大學(xué)1992二（15分）】文檔來自于網(wǎng)絡(luò)搜索類似本題的另外敘述有:（1）已知遞增有序的兩個單鏈表A,B分別存儲了一個集合。設(shè)計算法實現(xiàn)求兩個集合的并集的運算A：=AUB【合肥工業(yè)大學(xué)1999五、1（8分）】文檔來自于網(wǎng)絡(luò)搜索mH（2）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。編一函數(shù)，求A與B的交集，并存放于A鏈表中?！灸暇┖娇蘸教齑髮W(xué)2001六（10分）】文檔來自于網(wǎng)絡(luò)搜索（3）設(shè)有兩個從小到大排序的帶頭結(jié)點的有序鏈表。試編寫求這兩個鏈表交運算的算法（即L1HL2）。要求結(jié)果鏈表仍是從小到大排序，但無重復(fù)元素?！灸暇┖娇蘸教齑髮W(xué)1996十一（10分）】文檔來自于網(wǎng)絡(luò)搜索（4）己知兩個線性表A,B均以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)，且表中元素按值遞增有序排列。設(shè)計算法求出A與B的交集C,要求C另開辟存儲空間，要求C同樣以元素值的遞增序的單鏈表形式存貯。文檔來自于網(wǎng)絡(luò)搜索【西北大學(xué)2000五（8分）】（5）已知遞增有序的單鏈表A,B和C分別存儲了一個集合，設(shè)計算法實現(xiàn)A：=AU（BHC）,并使求解結(jié)構(gòu)A仍保持遞增。要求算法的時間復(fù)雜度為O（|A|+|B|+|C|）。其中，|A|為集合A的元素個數(shù)。文檔來自于網(wǎng)絡(luò)搜索【合肥工業(yè)大學(xué)2000五、1（8分）】.知L1、L2分別為兩循環(huán)單鏈表的頭結(jié)點指針，m,n分別為L1、L2表中數(shù)據(jù)結(jié)點個數(shù)。要求設(shè)計一算法，用最快速度將兩表合并成一個帶頭結(jié)點的循環(huán)單鏈表?！緰|北大學(xué)1996二（12分）】文檔來自于網(wǎng)絡(luò)搜索類似本題的另外敘述有:（1）試用類Pascal語言編寫過程PROCjoin（VARla：link；lb：link）實現(xiàn)連接線性表la和lb（lb在后）的算法，要求其時間復(fù)雜度為0（1），占用輔助空間盡量小。描述所用結(jié)構(gòu)。文檔來自于網(wǎng)絡(luò)搜索【北京工業(yè)大學(xué)1997一、1（8分）】（2）設(shè)有兩個鏈表，ha為單向鏈表，hb為單向循環(huán)鏈表。編寫算法，將兩個鏈表合并成一個單向鏈表，要求算法所需時間與鏈表長度無關(guān)?！灸暇┖娇蘸教齑髮W(xué)1997四（8分）】文檔來自于網(wǎng)絡(luò)搜索.順序結(jié)構(gòu)線性表LA與LB的結(jié)點關(guān)鍵字為整數(shù)。LA與LB的元素按非遞減有序，線性表空間足夠大。試用類PASCAL語言給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避免移動元素?！颈本┕I(yè)大學(xué)1997一、2（12分）】文檔來自于網(wǎng)絡(luò)搜索.已知不帶頭結(jié)點的線性鏈表list，鏈表中結(jié)點構(gòu)造為（data、link），其中data為數(shù)據(jù)域，link為指針域。請寫一算法，將該鏈表按結(jié)點數(shù)據(jù)域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結(jié)點空間?！颈本┖娇蘸教齑髮W(xué)1998五（15分）】文檔來自于網(wǎng)絡(luò)搜索.設(shè)L為單鏈表的頭結(jié)點地址，其數(shù)據(jù)結(jié)點的數(shù)據(jù)都是正整數(shù)且無相同的，試設(shè)計利用直接插入的原則把該鏈表整理成數(shù)據(jù)遞增的有序單鏈表的算法?！緰|北大學(xué)1996六（14分）】文檔來自于網(wǎng)絡(luò)搜索類似本題的另外敘述有:（1）設(shè)一單向鏈表的頭指針為head,鏈表的記錄中包含著整數(shù)類型的key域,試設(shè)計算法,將此鏈表的記錄按照key遞增的次序進行就地排序.【中科院計算所1999五、1（10分）】文檔來自于網(wǎng)絡(luò)搜索.設(shè)Listhead為一單鏈表的頭指針，單鏈表的每個結(jié)點由一個整數(shù)域DATA和指針域NEXT組成，整數(shù)在單鏈表中是無序的。編一PASCAL過程，將Listhead鏈中結(jié)點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由P,Q指向，每個鏈中的數(shù)據(jù)按由小到大排列。程序中不得使用NEW過程申請空間。【山東大學(xué)1993六（15分）】文檔來自于網(wǎng)絡(luò)搜索類似本題的另外敘述有:（1）設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點）?！颈本├砉ご髮W(xué)2000四、2（4分）】文檔來自于網(wǎng)絡(luò)搜索（2）設(shè)L為一單鏈表的頭指針，單鏈表的每個結(jié)點由一個整數(shù)域data和指針域NEXT組成，整數(shù)在單鏈表中是無序的。設(shè)計算法，將鏈表中結(jié)點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由P，Q指向，每個鏈中的數(shù)據(jù)按由小到大排列，算法中不得申請新的結(jié)點空間?！厩鄭u海洋大學(xué)1999三（12分）】文檔來自于網(wǎng)絡(luò)搜索（3）將一個帶頭結(jié)點的單鏈表A分解為兩個帶頭結(jié)點的單鏈表A和B，使得A表中含有原表中序號為奇數(shù)的元素，而B表中含有原表中序號為偶數(shù)的元素，且保持其相對順序不變。文檔來自于網(wǎng)絡(luò)搜索寫出其類型定義：寫出算法?！旧綎|大學(xué)1998九（9分）】【山東工業(yè)大學(xué)2000九（9分）】.已知線性表（a1a2a3…an）按順序存于內(nèi)存，每個元素都是整數(shù)，試設(shè)計用最少時間把所有值為負數(shù)的元素移到全部正數(shù)值元素前邊的算法：例：（x,-x,-x,x,x,-x…乂）變?yōu)椋?x,-x,-x…x,x,x）。文檔來自于網(wǎng)絡(luò)搜索【東北大學(xué)1998二（15分）】類似本題的另外敘述有:（1）設(shè)有一元素為整數(shù)的線性表L=（a/a2,a3,…,an）,存放在一維數(shù)組A[N]中,設(shè)計一個算法，以表中an作為參考元素，將該表分為左、右兩部分，其中左半部分每個元素小于等于an,右半部分每個元素都大于an,an位于分界位置上（要求結(jié)果仍存放在A[N]中）?！颈本├砉ご髮W(xué)1999八（6分）】文檔來自于網(wǎng)絡(luò)搜索（2）順序存儲的線性表A,其數(shù)據(jù)元素為整型,試編寫一算法,將A拆成B和C兩個表,使A中元素值大于等于0的元素放入B/小于0的放入C中..要求:文檔來自于網(wǎng)絡(luò)搜索^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分）】文檔來自于網(wǎng)絡(luò)搜索（4）編寫函數(shù)將一整數(shù)序列中所有負數(shù)移到所有正數(shù)之前，要求時間復(fù)雜度為O（n）【南京航空航天大學(xué)2001八（10分）】（5）已知一個由n（設(shè)n=1000）個整數(shù)組成的線性表，試設(shè)計該線性表的一種存儲結(jié)構(gòu)，并用標準pascal語言描述算法，實現(xiàn)將n個元素中所有大于等于19的整數(shù)放在所有小于19的整數(shù)之后。要求算法的時間復(fù)雜度為O（n）,空間復(fù)雜度O（1）。【西安交通大學(xué)1996六（11分）】文檔來自于網(wǎng)絡(luò)搜索.試編寫在帶頭結(jié)點的單鏈表中刪除（一個）最小值結(jié)點的（高效）算法。voiddelete（Linklist&L）文檔來自于網(wǎng)絡(luò)搜索【北京理工大學(xué)2001九、3（8分）】.已知非空線性鏈表由list指出，鏈結(jié)點的構(gòu)造為（data,link）.請寫一算法，將鏈表中數(shù)據(jù)域值最小的那個鏈結(jié)點移到鏈表的最前面。要求:不得額外申請新的鏈結(jié)點。【北京航空航天大學(xué)2001四（10分）】文檔來自于網(wǎng)絡(luò)搜索.已知p指向雙向循環(huán)鏈表中的一個結(jié)點，其結(jié)點結(jié)構(gòu)為data、llink、rlink三個域，寫出算法change（p）,交換p所指向的結(jié)點和它的前綴結(jié)點的順序?！臼锥冀?jīng)貿(mào)大學(xué)1997二、2（15分）】文檔來自于網(wǎng)絡(luò)搜索.線性表（a1,a2，a3,…,an）中元素遞增有序且按順序存儲于計算機內(nèi)。要求設(shè)計一算法完成:文檔來自于網(wǎng)絡(luò)搜索（1）用最少時間在表中查找數(shù)值為x的元素。若找到將其與后繼元素位置相交換。若找不到將其插入表中并使表中元素仍遞增有序。【東北大學(xué)1996三（12分）】13.設(shè)單鏈表的表頭指針為h,結(jié)點結(jié)構(gòu)由data和next兩個域構(gòu)成，其中data域為字符型。寫出算法dc（h,n）,判斷該鏈表的前n個字符是否中心對稱。例如xyx,xyyx都是中心對稱?！臼锥冀?jīng)貿(mào)大學(xué)1998三、9（15分）】文檔來自于網(wǎng)絡(luò)搜索.已知兩個單鏈表A和B,其頭指針分別為heada和headb,編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。文檔來自于網(wǎng)絡(luò)搜索【中國礦業(yè)大學(xué)2000三（10分）】類似本題的另外敘述有:（1）h1、h2為兩個鏈表的表頭指針，結(jié)點結(jié)構(gòu)為data和link兩個域組成。寫出算法inde（h1,h2,i,j,l）,將鏈表hl從第i個結(jié)點起的l個結(jié)點刪除，并插入到h2表的第j個結(jié)點之前。文檔來自于網(wǎng)絡(luò)搜索【首都經(jīng)貿(mào)大學(xué)1998三、10（20分）】.設(shè)線性表存于A[1..size]的前num各分量中，且遞增有序。請設(shè)計一個算法，將x插入到線性表的適當位置上，以保持線性表的有序性，并在設(shè)計前說明設(shè)計思想，最后說明所設(shè)計算法的時間復(fù)雜度。文檔來自于網(wǎng)絡(luò)搜索【西安電子科技大學(xué)1999計應(yīng)用1997二（10分）】類似本題的另外敘述有:（1）試編制在線性表L={12,13,21,24,28,30,42,}中插入數(shù)據(jù)元素26的程序。（要求該程序用turboPascal語言編制并能在計算機上運行，結(jié)點類型為鏈式結(jié)構(gòu)）【大連海事大學(xué)1996二、1（16分）】文檔來自于網(wǎng)絡(luò)搜索.假設(shè)一個單循環(huán)鏈表，其結(jié)點含有三個域pre、data、link。其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針（NIL）；link為指針域，它指向后繼結(jié)點。請設(shè)計算法，將此表改成雙向循環(huán)鏈表。文檔來自于網(wǎng)絡(luò)搜索【西安電子科技大學(xué)1999軟件五（10分）】.已知遞增有序的單鏈表A,B分別存儲了一個集合，請設(shè)計算法以求出兩個集合A和B的差集A-B（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。文檔來自于網(wǎng)絡(luò)搜索【西安電子科技大學(xué)2000計應(yīng)用1997二（10分）】.已知一個單鏈表中每個結(jié)點存放一個整數(shù)，并且結(jié)點數(shù)不少于2，請設(shè)計算法以判斷該鏈表中第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)的值，若滿足則返回ture，否則返回false.文檔來自于網(wǎng)絡(luò)搜索【西安電子科技大學(xué)2000軟件1997二（10分）】.兩個整數(shù)序列A=a1,a2,a3,…，am和B=b1,b2,b3,…，bn已經(jīng)存入兩個單鏈表中，設(shè)計一個算法，判斷序列B是否是序列A的子序列?！緰|北大學(xué)1999二（10分）】文檔來自于網(wǎng)絡(luò)搜.L1與L2分別為兩單鏈表頭結(jié)點地址指針，且兩表中數(shù)據(jù)結(jié)點的數(shù)據(jù)域均為一個字母。設(shè)計把L1中與L2中數(shù)據(jù)相同的連續(xù)結(jié)點順序完全倒置的算法。【東北大學(xué)1997四（15分）】文檔來自于網(wǎng)絡(luò)搜索例：到第例：到第m個結(jié)點構(gòu)成一個循環(huán)部分鏈表，設(shè)計將這部分循環(huán)鏈表中所有結(jié)點順序完全倒置的算法。21.請寫一個算法將順序存儲結(jié)構(gòu)的線性表（a1...an）逆置為（an...a1）。【大連海事大學(xué)1996文檔來自于網(wǎng)絡(luò)搜索111111111^^^^^11111^^11^1111類似本題的另外敘述有:設(shè)有一帶頭結(jié)點的單鏈表,編程將鏈表顛倒過來.要求不用另外的數(shù)組或結(jié)點完成.【南京航空航天大學(xué)1999八（10分）】設(shè)有一個帶頭結(jié)點的單向鏈表，數(shù)據(jù)項遞減有序。寫一算法，重新排列鏈表，使數(shù)據(jù)項遞增有序，要求算法時間復(fù)雜度為O（n）。（注：用程序?qū)崿F(xiàn)）【南京航空航天大學(xué)1997七（12分）】文檔來自于網(wǎng)絡(luò)搜索試編寫求倒排循環(huán)鏈表元素的算法?！灸暇┖娇蘸教齑髮W(xué)1995十二（10分）】請設(shè)計算法將不帶頭結(jié)點的單鏈表就地逆置?！颈狈浇煌ù髮W(xué)2001三（12分）】試編寫算法，將不設(shè)表頭結(jié)點的、不循環(huán)的單向鏈表就地逆轉(zhuǎn)?！颈狈浇煌ù髮W(xué)1997五（10分）】文檔來自于網(wǎng)絡(luò)搜索（6）有一個單鏈表L（至少有1個結(jié)點），其頭結(jié)點指針為head,編寫一個過程將L逆置，即最后一個結(jié)點變成第一個結(jié)點，原來倒數(shù)第二個結(jié)點變成第二個結(jié)點，如此等等?！狙嗌酱髮W(xué)2001四、2（8分）】文檔來自于網(wǎng)絡(luò)搜索22．設(shè)有一個由正整數(shù)組成的無序（向后）單鏈表,編寫完成下列功能的算法：（1）找出最小值結(jié)點,且打印該數(shù)值；（2）若該數(shù)值是奇數(shù),則將其與直接后繼結(jié)點的數(shù)值交換；（3）若該數(shù)值是偶數(shù),則將其直接后繼結(jié)點刪除【東北大學(xué)2000二（15分）】.已知L為沒有頭結(jié)點的的單鏈表中第一個結(jié)點的指針，每個結(jié)點數(shù)據(jù)域存放一個字符，該字符可能是英文字母字符或數(shù)字字符或其它字符,編寫算法構(gòu)造三個以帶頭結(jié)點的單循環(huán)鏈表表示的線性表,使每個表中只含同一類字符。（要求用最少的時間和最少的空間）【東北大學(xué)2002三（15分）】文檔來自于網(wǎng)絡(luò)搜索.在一個遞增有序的線性表中,有數(shù)值相同的元素存在。若存儲方式為單鏈表,設(shè)計算法去掉數(shù)值相同的元素,使表中不再有重復(fù)的元素。例如：（7,10,10,21,30,42,42,42,51,70）將變作（7,10,21,30,42,51,70）,分析算法的時間復(fù)雜度?！颈本┕I(yè)大學(xué)1996三（15分）】文檔來自于網(wǎng)絡(luò)搜索.在輸入數(shù)據(jù)無序的情況下，建立一個數(shù)據(jù)值為整型的遞增有序的順序存儲線性表L,且要求當輸入相同數(shù)據(jù)值時,線性表中不能存在數(shù)據(jù)值相同的數(shù)據(jù)元素,試寫出其算法。文檔來自于網(wǎng)絡(luò)搜索順序存儲結(jié)構(gòu)的線性表描述為：CONSTmaxlen=｛線性表可能達到的最大長度｝；TYPEsqlisttp=RECORDelem:array[1..maxlen]ofinteger;last:0..maxlenEND;VARL:sqlisttp;【同濟大學(xué)1998二（12分）】.設(shè)有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序,且允許有相等的整數(shù)存在）,試編寫能實現(xiàn)下列功能的算法：（要求用最少的時間和最小的空間）文檔來自于網(wǎng)絡(luò)搜索（1）確定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計算一次,如序列｛20,20,17,16,15,15,11,10,8,7,7,5,4｝中比10大的數(shù)有5個）；文檔來自于網(wǎng)絡(luò)搜索（2）在單鏈表將比正整數(shù)x小的數(shù)按遞減次序排列；（3）將正整數(shù)（比）x大的偶數(shù)從單鏈表中刪除?！緰|北大學(xué)2001二（17分）】.編寫一個算法來交換單鏈表中指針P所指結(jié)點與其后繼結(jié)點，HEAD是該鏈表的頭指針，p指向該鏈表中某一結(jié)點?！炯执髮W(xué)2001二、1（7分）】文檔來自于網(wǎng)絡(luò)搜索類似本題的另外敘述有:（1）已知非空線性鏈表第一個結(jié)點由List指出，請寫一算法，交換p所指的結(jié)點與其下一個結(jié)點在鏈表中的位置（設(shè)p指向的不是鏈表最后那個結(jié)點）?！颈本┖娇蘸教齑髮W(xué)1999五（10分）】文檔來自于網(wǎng)絡(luò)搜索（2）已知任意單鏈表如圖所示（編者略去圖）。Head為表頭指針