數(shù)據(jù)結(jié)構(gòu) 線性表 練習題 試卷及答案

1、.第2章 線性表 后面紅色的答案一 選擇題1下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（ ）【北方交通大學 2001 一、4（2分）】A存儲密度大 B插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示2下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ ）【北方交通大學 2001 一、14（2分）】A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有n個（ ）的有限序列（n>0）。 【清華大學 1998 一、4（2分）】A表元素 B字符 C數(shù)

2、據(jù)元素 D數(shù)據(jù)項 E信息項4若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間?！竟枮I工業(yè)大學 2001 二、1（2分）】A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。【南開大學 2000 一、3】A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用( )最節(jié)省時間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點的雙循環(huán)

3、鏈表【合肥工業(yè)大學 2000 一、1（2分）】7若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。則采用（ ）存儲方式最節(jié)省運算時間。【北京理工大學 2000 一、1（2分）】A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ ）. 【北京理工大學 2001 六、2（2分）】A 內(nèi)存地址 B數(shù)組下標 C下一元素地址 D左、右孩子地址9. 鏈表不具有的特點是（ ） 【福州大學 1998 一、8 (2分)】A插入、刪除不需要移動元素 B可隨機訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比10. 下面的敘述不正確的是（ ）【南

4、京理工大學 1996 一、10（2分）】A線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比 B. 線性表在鏈式存儲時，查找第i個元素的時間同i的值無關(guān)C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)11. 線性表的表元存儲方式有(（1）)和鏈接兩種。試指出下列各表中使用的是何種存儲方式：表1是(（2）)存儲方式；表2是(（3）)存儲方式；表3是(（4）)存儲方式；表4是(（5）)存儲方式。表左的s指向起始表元。 表元編號貨號數(shù)量表元間聯(lián)系1 618 40 2 2 205 2 3 3 103 15 4 4 501 20

5、 5 5 781 17 6 6 910 24 0表1s 表元編號貨號數(shù)量表元間聯(lián)系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 2 5 781 17 6 6 910 24 3表2s 表元編號貨號數(shù)量表元間聯(lián)系 1 618 40 5 2 205 2 13 103 15 4 4 501 20 0 5 781 17 6 6 910 24 3表3s 表元編號貨號數(shù)量表元間聯(lián)系 1 2 1 618 40 5 2 2 205 2 1 0 3 103 15 4 6 4 501 20 0 3 5 781 17 6 1 6 910 24 3 5表4s 供選擇的答案：A.連續(xù)

6、 B.單向鏈接 C.雙向鏈接 D.不連接 E.循環(huán)鏈接 F.樹狀 G.網(wǎng)狀 H.隨機 I.順序 J.順序循環(huán)【上海海運學院 1995 二、1（5分）】12.(1) 靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。 (2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。 (3) 靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（ ）【南京理工大學 2000 一、3（1.5分）】 A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個

7、新元素的算法的時間復雜度為（ ）(1<=i<=n+1)?！颈本┖娇蘸教齑髮W 1999 一、1（2分）】A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)【青島大學 2000 五、1（2分）】15線性表（ a1,a2,an）以鏈接方式存儲時，訪問第i位置元素的時間復雜性為（ ）AO（i） BO（1） CO（n） DO（i-1）【中山大學 1999 一、2】16非空的循環(huán)單鏈表head的尾結(jié)點p滿足

8、（ ）?！疚錆h大學 2000 二、10】Ap.link=head Bp.link=NIL Cp=NIL Dp= head17循環(huán)鏈表H的尾結(jié)點P的特點是（ ）?！局猩酱髮W 1998 二、2（2分）】 AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一個以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（）【南京理工大學1998 一、15（2分）】 A. p.next=h B. p.next=NIL C. p.next.next=h D. p.data=-119完成在雙循環(huán)鏈表結(jié)點p之后插入s的操作是（ ）；【北方交通大學 1999 一、4（3分）】

9、A p.next:=s ; s.priou:=p; p.next.priou:=s ; s.next:=p.next;B p.next.priou:=s; p.next:=s; s.priou:=p; s.next:=p.next;C s.priou:=p; s.next:=p.next; p.next:=s; p.next.priou:=s ;D s.priou:=p; s.next:=p.next; p.next.priou:=s ; p.next:=s;20在雙向循環(huán)鏈表中,在p指針所指向的結(jié)點前插入一個指針q所指向的新結(jié)點,其修改指針的操作是( )。【北京郵電大學 1998 二、2（2

10、分）】注:雙向鏈表的結(jié)點結(jié)構(gòu)為(llink,data,rlink)。 供選擇的答案：A p.llink：=q； q.rlink：=p； p.llink.rlink：=q； q.llink：=q；B p.llink：=q； p.llink.rlink：=q ； q.rlink：= p； q.llink:=p.llink；C q.rlink：=p； q.llink：=p.llink； p.llink.rlink：=q; p.llink：=q;D q.llink:=p.llink；q.rlink:=p； p.llink：=q；p.llink：=q；（編者按：原題如此）21在非空雙向循環(huán)鏈表中q所指的

11、結(jié)點前插入一個由p所指的鏈結(jié)點的過程依次為:rlink(p) q; llink(p) llink(q); llink(q) p; （ ） Arlink(q) p Brlink(llink(q) p Crlink(llink(p) p Drlink(rlink(p) p 【北京航空航天大學 2000 一、1（2分）】22 雙向鏈表中有兩個指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個結(jié)點，q指向一待插入結(jié)點，現(xiàn)要求在p前插入q，則正確的插入為（ ）【南京理工大學1996 一、1（2分）】 A. p.llink:=q; q.rlink:=p; p.llink.rlink:

12、=q; q.llink:=p.llink;B. q.llink:=p.llink; p.llink.rlink:=q; q.rlink:=p; p.llink:=q.rlink; C. q.rlink:=p; p.rlink:=q; p.llink.rlink:=q; q.rlink:=p;D. p.llink.rlink:=q; q.rlink:=p; q.llink:=p.llink; p.llink:=q;23在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（ ）。【青島大學 2000 五、2（2分）】A. p->Llink=q;q->Rlink=p;p->Llink

13、->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（ ）。Ap->nex

14、t=s;s->next=p->next; B s->next=p->next;p->next=s;Cp->next=s;p->next=s->next; D p->next=s->next;p->next=s;【青島大學 2001 五、3（2分）】25對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（ ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL【北京工商大學 2001 一、5（3分）】26. 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）

15、。A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink;B p.llink:=(p.llink).llink (p.llink).rlink:=p;C (p.rlink).llink:=p p.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink;【西安電子科技大學 1998 一、1（2分）】27. 雙向鏈表中有兩個指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一個結(jié)點，現(xiàn)要求刪去p所指結(jié)點，則正確的刪除是（ ）（鏈中結(jié)點數(shù)大于2，

16、p不是第一個結(jié)點）Ap.llink.rlink:=p.llink; p.llink.rlink:=p.rlink; dispose(p);Bdispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink;Cp.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink;D以上A，B，C都不對。 【南京理工大學 1997 一、1（2分）】二、判斷1. 鏈表中的頭結(jié)點僅起到標識的作用。( )【南京航空航天大學 1997 一、1（1分）】2. 順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。(

17、)【南京航空航天大學1997 一、2（1分）】3線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。( )【北京郵電大學 1998 一、2（2分）】4順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。( )【北京郵電大學 2002 一、2（1分）】5. 對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。( )【南京航空航天大學 1997 一、3（1分）】6順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )【中科院軟件所 1999 六、1-2（2分）】【上海海運學院 1997 一、1（1分）】7集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。( )【大連海事大學 2001 一、5 ( 1分)】8

18、. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。( )【合肥工業(yè)大學 2000 二、1（1分）】9. 線性表的特點是每個元素都有一個前驅(qū)和一個后繼。( )【合肥工業(yè)大學2001 二、1（1分）】10. 取線性表的第i個元素的時間同i的大小有關(guān). ( )【南京理工大學 1997 二、9（2分）】11. 循環(huán)鏈表不是線性表. ( )【南京理工大學 1998 二、1（2分）】12. 線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。( )【青島大學 2001 四、2（1分）】13. 線性表就是順序存儲的表。( )【青島大學 2002 一、1（1分）】14為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。( )【上海海運學

19、院 1995 一、1（1分）】 【上海海運學院 1997 一、2（1分）】15. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( ) 【上海海運學院 1996 一、1（1分）】 【上海海運學院 1999 一、1（1分）】16. 鏈表是采用鏈式存儲結(jié)構(gòu)的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。 ( ) 【上海海運學院 1998 一、2（1分）】三、填空1當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_存儲結(jié)構(gòu)。【北方交通大學 2001 二、4】2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素

20、的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_?！颈狈浇煌ù髮W 2001 二、9】3設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點 , 若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句:_； _;【華中理工大學 2000 一、4（2分）】4在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動_個元素?！颈本┕ど檀髮W 2001 二、4（4分）】5在單鏈表中設(shè)置頭結(jié)點的作用是_。【哈爾濱工業(yè)大學 2000 二、1（1分）】6對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)

21、點*p后插入一個新結(jié)點的時間復雜度為_,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為_?！竟枮I工業(yè)大學 2001 一、1（2分）】7根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_?！疚靼搽娮涌萍即髮W1998 二、4（3分）】8 在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是_、_、_、_。【中國礦業(yè)大學 2000 一、1（3分）】9. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針所指的結(jié)點之前插入指針為s 所指的結(jié)點，則需執(zhí)行下列語句：s .next:=p； s .prior:= _；p .prior:=s；

22、_:=s；【福州大學 1998 二、7 (2分)】10鏈接存儲的特點是利用_來表示數(shù)據(jù)元素之間的邏輯關(guān)系?！局猩酱髮W 1998 一、1 （1分）】11.順序存儲結(jié)構(gòu)是通過_表示元素之間的關(guān)系的;鏈式存儲結(jié)構(gòu)是通過_表示元素之間的關(guān)系的?！颈本├砉ご髮W 2001 七、2 （2分）】12. 對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 _個，單鏈表為_個。【南京理工大學 2000 二、2 （3分）】13. 循環(huán)單鏈表的最大優(yōu)點是：_?！靖Ｖ荽髮W 1998 二、3 (2分)】14. 已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是：_【合肥工業(yè)大學 1999 三、2 （2分）】

23、15. 帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是：_【合肥工業(yè)大學 1999 三、3 2000 三、2（2分）】16. 在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：_ 【合肥工業(yè)大學 2001 三、3 （2分）】17.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是：_。 【北京理工大學 2000 二、1 （2分）】 【青島大學 2002 三、1 （2分）】18. 在單鏈表p結(jié)點之后插入s結(jié)點的操作是：_?！厩鄭u大學 2002 三、2（2分）】19. 請在下列算法的橫線上填入適當?shù)恼Z句?！厩迦A大學 1994 五 （15分）】FUNCTION inclusion(ha,hb:linklisttp

24、):boolean;以ha和hb為頭指針的單鏈表分別表示有序表A和B，本算法判別表A是否包含在表B內(nèi)，若是，則返回“true”，否則返回“false”BEGIN pa:=ha.next; pb:=hb.next; （1） ;WHILE（2） DOIF pa.data=pb.data THEN（3） ELSE（4） ;（5） END; 20完善算法：已知單鏈表結(jié)點類型為：TYPE ptr=node； node=RECORD data：integer； next：ptrEND；過程create建立以head為頭指針的單鏈表。PROCEDURE create ( (1) )；VAR p,q：ptr；

25、 k：integer；BEGIN new（head）； q:=head；read（k）；WHILE k>0 DO BEGIN (2); (3); (4); (5); read（k） END;q.next：=NIL;END;【北京師范大學 1999 三】21. 已給如下關(guān)于單鏈表的類型說明： TYPE list=node ;node=RECORD data: integer; next: list; END; 以下程序采用鏈表合并的方法，將兩個已排序的單鏈表合并成一個鏈表而不改變其排序性（升序），這里兩鏈表的頭指針分別為p和q.PROCEDURE mergelink(VAR p,q:lis

26、t): VAR h,r: list; BEGIN （1）_ h.next:= NIL; r:=h; WHILE(p<>NIL) AND (q<>NIL) DO IF (p.data<=q.data)THEN BEGIN （2）_； r:=p; p:=p.next； END ELSE BEGIN （3）_； r:=q; q:=q.next; END; IF (p=NIL) THEN r.next:=q; （4）_； p:=h.next; dispose(h); END;【廈門大學 2000 三、2 （8分）】22假設(shè)鏈表p和鏈表q中的結(jié)點值都是整數(shù),且按結(jié)點值的遞增

27、次序鏈接起來的帶表頭結(jié)點的環(huán)形鏈表。各鏈表的表頭結(jié)點的值為max,且鏈表中其他結(jié)點的值都小于max，在程序中取max為9999。在各個鏈表中，每個結(jié)點的值各不相同，但鏈表p和鏈表q可能有值相同的結(jié)點（表頭結(jié)點除外）。下面的程序?qū)㈡湵韖合并到鏈表p中，使得合并后的鏈表是按結(jié)點值遞增次序鏈接起來的帶表頭結(jié)點的環(huán)形鏈表，且鏈表中各個結(jié)點的值各不相同。請在劃線處填上適當內(nèi)容，每個框只填一個語句或一個表達式，鏈表的結(jié)點類型如下TYPE nodeptr=nodetype； nodetype=RECORD data：integer； link：nodeptr;END；CONST max=9999;PROCE

28、DURE merge(VAR p:nodeptr;q:nodeptr); VAR r,s: nodeptr; BEGIN r:=p; WHILE (A)_ DO BEGIN WHILE r.link.data<q.link.data DO (B)_; IF r.link.data>q.link.data THEN BEGIN s:=(C)_; (D)_:=s.link; s.link:=(E)_; (F)_ _:=s; (G)_; END ELSE BEGIN (H)_; s:=q.link; (I)_; dispose(s) END END; dispose(q)END;【復旦大

29、學 1997 五（18分）】23PROC ins_linklist(la:linkisttp; i:integer; b:elemtp);la為指向帶頭結(jié)點的單鏈表的頭指針，本算法在表中第i個元素之前插入元素bp:=(1) ; j:=(2) ;指針初始化，j為計數(shù)器WHILE (p<>NIL) AND (3) ) DO p:=(4) ; j:=j+1； 尋找第 i-1 個結(jié)點IF (p=NIL) OR (5) ) THEN error (No this position) ELSE new(s) ; s.data:=b; s.next:=p.next; p.next:=s;ENDP

30、;ins-linklist【燕山大學 1998 四、1（15分）】24. 已知雙鏈表中結(jié)點的類型定義為：TYPE dpointer=list;list=RECORDdata:integer; left,right:dpointer;END;如下過程將在雙鏈表第i個結(jié)點（i>=0）之后插入一個元素為x的結(jié)點，請在答案欄給出題目中_處應填入的語句或表達式，使之可以實現(xiàn)上述功能。PROCEDURE insert(VAR head:dpointer;i,x:integer);VAR s,p:dpointer; j: integer;BEGINnew(s); s.data:=x;IF(i=0)TH

31、EN BEGIN s.right:=head; (1)_ head:=s END如果i=0,則將s結(jié)點插入到表頭后返回ELSE BEGIN p:=head; (2)_；在雙鏈表中查找第i個結(jié)點,由p所指向 WHILE (p<>NIL) AND (j<i) DO BEGIN j:=j+1; (3) _ END; IF p<>NIL THENIF （p.right=NIL） THEN BEGIN p.right:=s; s.right:=NIL; (4) _END ELSE BEGIN s.right:=p.right; (5) _;p.right:=s; (6) E

32、ND ELSE writeln(can not find node!) ENDEND;【廈門大學 2002 二 （12分）】25閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個非遞減的順序存儲線性表中，刪除所有值相等的多余元素。 CONST maxlen=30TYPE sqlisttp=RECORD elem:ARRAY1.maxlen OF integer; last:0.maxlen END;PROC exam21(VAR L:sqlisttp); j:=1; i:=2; WHILE (1)_ DO IF L.elemi<>L.elemj THEN (2)_; (3)

33、_; i:=i+1 (4) _; ENDP;【同濟大學 2000 二、1 (10分)】26在本題的程序中，函數(shù)過程Create_link_list(n)建立一個具有n個結(jié)點的環(huán)形鏈表;程序過程 josephus(n,i,m)對由Create_link_list(n)所建立的具有n個結(jié)點的環(huán)形鏈表按一定的次序逐個輸出并刪除鏈表中的所有結(jié)點，參數(shù) n(n>0)指明環(huán)形鏈表的結(jié)點個數(shù)，參數(shù) i(1<=i<=n)指明起始結(jié)點，參數(shù) m (m>0)是步長，指明從起始結(jié)點或前次被刪除并輸出的結(jié)點之后的第m個結(jié)點作為本次被輸出并刪除的結(jié)點。例如，對于下圖中具有6個結(jié)點的環(huán)形鏈表，在調(diào)

34、用 josephus(6,3,2)后，將輸出 5,1,3,6,4,2 請在橫線處填上適當內(nèi)容，每空只填一個語句。 TYPE nodeptr=nodetype; nodetype=RECORDdata: intrger; link: nodeptr END; VAR n,i,m: integer; FUNCTION Create_link_list(n: integer): nodeptr; VAR head,p,q: nodeptr; i:integer; BEGIN head := NIL; IF n>0 THEN BEGIN new(head); p: =head; FOR i:=1

35、 TO n-1 DO BEGIN p.data:=i; new(q); (A)_; (B)_ END； p.data:=n; (C)_; END; Creat_link_list:=headEND;PROCEDURE josephus(n,i,m:integer); VAR p,q:nodeptr; j:integer;BEGIN p:=Creat_link_list(n); WHILE i>1 DO BEGIN p:=p.link; i:=i-1 END; (D)_ ; WHILE j<n DO BEGIN FOR i:=1 TO m-1 DO p:=p.link; (E)_;

36、write(q.data:8); (F)_ ; dispose(q); j:=j+1 ENDEND;【復旦大學 1997 四（12分）】27對于給定的線性鏈表head , 下面的程序過程實現(xiàn)了按結(jié)點值非降次序輸出鏈表中的所有結(jié)點，在每次輸出一個結(jié)點時，就把剛輸出的結(jié)點從鏈表中刪去。請在劃線處填上適當?shù)膬?nèi)容，使之成為一個完整的程序過程，每個空框只填一個語句。TYPE nodeptr = nodetype；nodetype = RECORD data : integer；link : nodeptrEND;VAR head : nodeptr；PROCEDURE sort_output_delet

37、e (head : nodeptr);VAR p,q,r,s: nodeptr; BEGIN WHILE head <> NIL DOBEGIN p:= NIL ；q:= head；r:= q ；s:=q.link ； WHILE s <> NIL DO BEGIN IF s.data < q.data THEN BEGIN (1)_; (2)_ END ； r:= s ； (3)_ END；write(q.data : 5) ；IF p=NIL THEN (4)_ ELSE (5)_ ； dispose (q) ； END； writelnEND；【復旦大學 1

38、996 七（20分） 1995 一（12分）與本題相似】28下面函數(shù)的功能是在一個按訪問頻度不增有序的，帶頭結(jié)點的雙向鏈環(huán)上檢索關(guān)鍵值為x的結(jié)點，對該結(jié)點訪問頻度計數(shù)，并維護該鏈環(huán)有序。若未找到，則插入該結(jié)點。所有結(jié)點的頻度域初值在建表時都為零。請將程序中四處空缺補寫完整。 TYPE link=nodenode=RECORDkey:char; freq:integer; pre,next:link;END;VAR l:link;FUNCTION loc(l:link;x:char):link;VAR p,q:link;BEGIN p:=l.next; （1）_； WHILE p.key<

39、>x DO p:=p.next; IF p=l THEN new(q); q.key:=x; q.freq:=0 ELSE 找到 p.freq:=p.freq+1; q:=p; （2）_；WHILE q.freq>p.pre.freq DO p:=p.pre;IF p<>q THEN （3）_ ；IF （4）_ THEN q.next:=p, q.pre;=p.pre; p.pre.next:=q; p.pre:=qreturn(q);END;【北京工業(yè)大學 1999 五 (12分)】29循環(huán)鏈表a和b的結(jié)點值為字母，其中a表非遞減有序，下面的程序欲構(gòu)造一個遞增有序的循

40、環(huán)鏈表c，其中結(jié)點的值為同時在a，b兩鏈表中出現(xiàn)的字母，且c中字母不重復，請補上程序中空缺的部分，并估計算法的時間復雜度。（設(shè)a，b的結(jié)點數(shù)分別為m，n） TYPE link=node; node=RECORD key:char; next:link END; PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN new(c);c.next:=c; q:=a; p:=a.next; WHILE p<>a DO （1）_；WHILE p.key=p.next.key DO q:=p; p=p.next;跳過相同字母r:=b.ne

41、xt ; （2）_;WHILE r.key <>p.key DO r:=r.next;IF r<>b THEN s:=p; q.next:=p.next; （3） ;s.next:=c.next; c.next:=s; c:=s ELSE q:=p; p:=p.next ; c:=c.next；END; 算法時間復雜度為O（4）_ 【北京工業(yè)大學 2000 四 (15分)】30. 以下程序的功能是實現(xiàn)帶附加頭結(jié)點的單鏈表數(shù)據(jù)結(jié)點逆序連接，請?zhí)羁胀晟浦?。void reverse(pointer h) /* h為附加頭結(jié)點指針；類型pointer同算法設(shè)計第3題*/ poi

42、nter p,q; p=h->next; h->next=NULL;while(1)_) q=p; p=p->next; q->next=h->next; h->next=(2)_; 【西南交通大學 2000 一、9】31. 下面是用c語言編寫的對不帶頭結(jié)點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當?shù)恼Z句。void reverse（linklist &L）p=null；q=L；while（q！=null） (1) ; q->next=p；p=q；(2)_ ; (3)_;【北京理工大學 2001 九、1 （

43、6分）】32下面程序段是逆轉(zhuǎn)單向循環(huán)鏈表的方法，p0 是原鏈表頭指針，逆轉(zhuǎn)后鏈表頭指針仍為p0。（可以根據(jù)需要增加標識符） p:= p0; q0:=NIL; WHILE （1）_ DO BEGIN （2）_; （3）_;（4）_;（5）_ END; p.next:= q0; p0 .next:=p; p0:=p;【中國人民大學 2000 二、1（4分）】33一個無頭結(jié)點的線性鏈表(不循環(huán))有兩個域。數(shù)據(jù)域data，指針域 next，鏈首head，下面算法用read(num)讀入數(shù)據(jù)，當num小于0時，輸入結(jié)束。建立一個數(shù)據(jù)以遞增序組成的鏈表。 PROC insert( head, x);在鏈首

44、為head的表中按遞增序插入xnew(r);r.data:=x; IF head=NIL THEN head:=(1) _; r.next:= (2)_ ELSE IF (3)_ THEN r .next:=head; head:=r ELSE p:=head;WHILE (4)_ AND (p.nextNIL ) DOq:=p; (5)_ ; IF (6)_ THEN q .next:=(7)_; r.next:= (8)_; ELSE p.next:=(9)_; r.next:= (10)_; ENDP;PROC creat(head); head:= (11)_; read(num);

45、WHILE num>0 DO insert(head,num); read(num) ENDP;【南京理工大學 1999 三、4（11分）】34. 一元稀疏多項式以循環(huán)單鏈表按降冪排列，結(jié)點有三個域，系數(shù)域coef ，指數(shù)域exp和指針域 next；現(xiàn)對鏈表求一階導數(shù) ，鏈表的頭指針為ha，頭結(jié)點的exp域為 1。 derivative(ha) q=ha ; pa=ha->next; while( (1)_) if ( (2)_) ( (3)_); free(pa); pa= ( (4) _); else pa->coef ( (5) _); pa->exp( (6)_

46、); q=( (7) _); pa=( (8)_); 【南京理工大學 2000 三、3（10分）】35.下面是刪除單鏈表L中最大元素所在結(jié)點的類PASCAL語言算法，請在橫線填上內(nèi)容，完成其功能。 TYPE pointer =node； node=RECORD data:integer; next: pointer END;PROCEDURE delmax (L:pointer); VAR p,q,r:pointer; m:integer; BEGIN r:=L； p:=L.next; IF p<>NIL THEN m:=p.data; (1)_; p:=p.next;WHILE

47、p<>NIL DO IF (2)_THEN (3)_ ; m:=p.data; (4)_; p:=p.next;q:=r.next; (5)_; dispose(q); END;【北京科技大學 1998 二】36對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，完成其功能。typedef struct node int data; struct node *next; linknode,*link;void Insertsort(link L) link p,q,r,u; p=L->next; (1)_; while(2)_)

48、 r=L; q=L->next; while(3)_&& q->data<=p->data) r=q; q=q->next; u=p->next; (4)_; (5)_; p=u; 【北京科技大學 2001 二 （10分）】37下面是一個求兩個集合A和B之差C=A-B的程序，即當且僅當e是A的一個元素，但不是B中的一個元素時，e才是C中的一個元素。集合用有序鏈表實現(xiàn)，初始時，A，B集合中的元素按遞增排列，C為空；操作完成后A，B保持不變，C中元素按遞增排列。下面的函數(shù)append(last,e)是把值為e的新結(jié)點鏈接在由指針last指向的結(jié)點的后面，并返回新結(jié)