假設(shè)有兩個(gè)按元素值遞增次序排列的線性表

1、假設(shè)有兩個(gè)按元素值遞增次序排列的線性表假設(shè)有兩個(gè)按元素值遞增次序排列的線性表一 選擇題1下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ ）【北方交通大學(xué) 2001 一、4（2分）】A存儲(chǔ)密度大 B插入運(yùn)算方便 C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）【北方交通大學(xué) 2001 一、14（2分）】A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3線性表是具有n個(gè)（ ）的有限序列（n>0）。 【清華大學(xué) 19

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

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

4、成正比10. 下面的敘述不正確的是（ ）【南京理工大學(xué) 1996 一、10（2分）】A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)C. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)11. 線性表的表元存儲(chǔ)方式有(（1）)和鏈接兩種。試指出下列各表中使用的是何種存儲(chǔ)方式：表1是(（2）)存儲(chǔ)方式；表2是(（3）)存儲(chǔ)方式；表3是(（4）)存儲(chǔ)方式；表4是(（5）)存儲(chǔ)方式。表左的s指向起始表元。 表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系1 618 40 2 2 205 2

5、 3 3 103 15 4 4 501 20 5 5 781 17 6 6 910 24 0表1s 表元編號(hào)貨號(hào)數(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 表元編號(hào)貨號(hào)數(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 表元編號(hào)貨號(hào)數(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

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

7、性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）(1<=i<=n+1)?！颈本┖娇蘸教齑髮W(xué) 1999 一、1（2分）】A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)【青島大學(xué) 2000 五、1（2分）】15線性表（ a1,a2,an）以鏈接方式存儲(chǔ)時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為（ ）AO（i） BO（1） CO（n） DO（i-1）【中山大學(xué) 1999 一、2

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

9、；【北方交通大學(xué) 1999 一、4（3分）】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指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針的操作是

10、( )?！颈本┼]電大學(xué) 1998 二、2（2分）】注:雙向鏈表的結(jié)點(diǎn)結(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；（編者按

11、：原題如此）21在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過程依次為: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 【北京航空航天大學(xué) 2000 一、1（2分）】22 雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ）【南京理工大學(xué)1996 一、1（2分）】 A. p.llink:=q; q.rl

12、ink:=p; p.llink.rlink:=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é)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是（ ）?！厩鄭u大學(xué) 2000 五、2（2分）】A. p->Llink=q;q-&

13、gt;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=q;p->Llink=q;p->Llink=q;24在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)

14、，正確的操作是：（ ）。Ap->next=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;【青島大學(xué) 2001 五、3（2分）】25對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL【北京工商大學(xué) 2001 一、5（3分）】26. 在雙向鏈表存

15、儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。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;【西安電子科技大學(xué) 1998 一、1（2分）】27. 雙向鏈表中有兩個(gè)指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去p所指結(jié)

16、點(diǎn)，則正確的刪除是（ ）（鏈中結(jié)點(diǎn)數(shù)大于2，p不是第一個(gè)結(jié)點(diǎn)）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都不對(duì)。 【南京理工大學(xué) 1997 一、1（2分）】二、判斷1. 鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。( )【南京航空航天大學(xué) 1997 一、1（1分）】2. 順序存

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

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

19、可以使用雙向鏈表存放數(shù)據(jù)。( )【上海海運(yùn)學(xué)院 1995 一、1（1分）】 【上海海運(yùn)學(xué)院 1997 一、2（1分）】15. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( ) 【上海海運(yùn)學(xué)院 1996 一、1（1分）】 【上海海運(yùn)學(xué)院 1999 一、1（1分）】16. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。 ( ) 【上海海運(yùn)學(xué)院 1998 一、2（1分）】三、填空1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_存儲(chǔ)結(jié)構(gòu)?！颈狈浇煌ù髮W(xué) 2001 二、4】2線性表L=（a1,

20、a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。【北方交通大學(xué) 2001 二、9】3設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn) , 若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句:_； _;【華中理工大學(xué) 2000 一、4（2分）】4在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。【北京工商大學(xué) 2001 二、4（4分）】5在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_?！竟枮I工業(yè)大學(xué) 2000 二、1（1分）

21、】6對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_。【哈爾濱工業(yè)大學(xué) 2001 一、1（2分）】7根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_?！疚靼搽娮涌萍即髮W(xué)1998 二、4（3分）】8 在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_、_、_、_?！局袊?guó)礦業(yè)大學(xué) 2000 一、1（3分）】9. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：s .next:=p； s .

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

23、【合肥工業(yè)大學(xué) 1999 三、2 （2分）】15. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：_【合肥工業(yè)大學(xué) 1999 三、3 2000 三、2（2分）】16. 在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：_ 【合肥工業(yè)大學(xué) 2001 三、3 （2分）】17.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：_。 【北京理工大學(xué) 2000 二、1 （2分）】 【青島大學(xué) 2002 三、1 （2分）】18. 在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是：_?！厩鄭u大學(xué) 2002 三、2（2分）】19. 請(qǐng)?jiān)谙铝兴惴ǖ臋M線上填入適當(dāng)?shù)恼Z句?！厩迦A大學(xué) 1994 五 （15分）】FUNCTION incl

24、usion(ha,hb:linklisttp):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é)點(diǎn)類型為：TYPE ptr=node； node=RECORD data：integer； next：ptrEND；過程create建立以head為頭指針的單鏈表。PROCEDURE creat

25、e ( (1) )；VAR p,q：ptr； 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;【北京師范大學(xué) 1999 三】21. 已給如下關(guān)于單鏈表的類型說明： TYPE list=node ;node=RECORD data: integer; next: list; END; 以下程序采用鏈表合并的方法，將兩個(gè)已排序的單鏈表合并成一個(gè)鏈表而不改變其排序性（升序），這里兩鏈表的頭指針分別為p和q.PROCEDURE

26、 mergelink(VAR p,q:list): 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;【廈門大學(xué) 2000 三、2 （8分）】22假設(shè)鏈表p

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

28、D；CONST max=9999;PROCEDURE 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 E

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

30、p.next; p.next:=s;ENDP;ins-linklist【燕山大學(xué) 1998 四、1（15分）】24. 已知雙鏈表中結(jié)點(diǎn)的類型定義為：TYPE dpointer=list;list=RECORDdata:integer; left,right:dpointer;END;如下過程將在雙鏈表第i個(gè)結(jié)點(diǎn)（i>=0）之后插入一個(gè)元素為x的結(jié)點(diǎn)，請(qǐng)?jiān)诖鸢笝诮o出題目中_處應(yīng)填入的語句或表達(dá)式，使之可以實(shí)現(xiàn)上述功能。PROCEDURE insert(VAR head:dpointer;i,x:integer);VAR s,p:dpointer; j: integer;BEGINnew(s

31、); s.data:=x;IF(i=0)THEN BEGIN s.right:=head; (1)_ head:=s END如果i=0,則將s結(jié)點(diǎn)插入到表頭后返回ELSE BEGIN p:=head; (2)_；在雙鏈表中查找第i個(gè)結(jié)點(diǎn),由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; (

32、5) _;p.right:=s; (6) END ELSE writeln(can not find node!) ENDEND;【廈門大學(xué) 2002 二 （12分）】25閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個(gè)非遞減的順序存儲(chǔ)線性表中，刪除所有值相等的多余元素。 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<>

33、L.elemj THEN (2)_; (3)_; i:=i+1 (4) _; ENDP;【同濟(jì)大學(xué) 2000 二、1 (10分)】26在本題的程序中，函數(shù)過程Create_link_list(n)建立一個(gè)具有n個(gè)結(jié)點(diǎn)的環(huán)形鏈表;程序過程 josephus(n,i,m)對(duì)由Create_link_list(n)所建立的具有n個(gè)結(jié)點(diǎn)的環(huán)形鏈表按一定的次序逐個(gè)輸出并刪除鏈表中的所有結(jié)點(diǎn)，參數(shù) n(n>0)指明環(huán)形鏈表的結(jié)點(diǎn)個(gè)數(shù)，參數(shù) i(1<=i<=n)指明起始結(jié)點(diǎn)，參數(shù) m (m>0)是步長(zhǎng)，指明從起始結(jié)點(diǎn)或前次被刪除并輸出的結(jié)點(diǎn)之后的第m個(gè)結(jié)點(diǎn)作為本次被輸出并刪除的結(jié)點(diǎn)。

34、例如，對(duì)于下圖中具有6個(gè)結(jié)點(diǎn)的環(huán)形鏈表，在調(diào)用 josephus(6,3,2)后，將輸出 5,1,3,6,4,2 請(qǐng)?jiān)跈M線處填上適當(dāng)內(nèi)容，每空只填一個(gè)語句。 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(hea

35、d); p: =head; FOR i:=1 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-

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

37、DURE sort_output_delete (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) ； E

38、ND； writelnEND；【復(fù)旦大學(xué) 1996 七（20分） 1995 一（12分）與本題相似】28下面函數(shù)的功能是在一個(gè)按訪問頻度不增有序的，帶頭結(jié)點(diǎn)的雙向鏈環(huán)上檢索關(guān)鍵值為x的結(jié)點(diǎn)，對(duì)該結(jié)點(diǎn)訪問頻度計(jì)數(shù)，并維護(hù)該鏈環(huán)有序。若未找到，則插入該結(jié)點(diǎn)。所有結(jié)點(diǎn)的頻度域初值在建表時(shí)都為零。請(qǐng)將程序中四處空缺補(bǔ)寫完整。 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;

39、 （1）_； WHILE p.key<>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è)大學(xué) 1999 五 (12分)】29循環(huán)鏈表a和b的結(jié)點(diǎn)值為字母，其中a表

40、非遞減有序，下面的程序欲構(gòu)造一個(gè)遞增有序的循環(huán)鏈表c，其中結(jié)點(diǎn)的值為同時(shí)在a，b兩鏈表中出現(xiàn)的字母，且c中字母不重復(fù)，請(qǐng)補(bǔ)上程序中空缺的部分，并估計(jì)算法的時(shí)間復(fù)雜度。（設(shè)a，b的結(jié)點(diǎn)數(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;

41、p=p.next;跳過相同字母r:=b.next ; （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; 算法時(shí)間復(fù)雜度為O（4）_ 【北京工業(yè)大學(xué) 2000 四 (15分)】30. 以下程序的功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)點(diǎn)逆序連接，請(qǐng)?zhí)羁胀晟浦?。void reverse(pointer h) /* h為附加頭結(jié)點(diǎn)指針；類

42、型pointer同算法設(shè)計(jì)第3題*/ pointer p,q; p=h->next; h->next=NULL;while(1)_) q=p; p=p->next; q->next=h->next; h->next=(2)_; 【西南交通大學(xué) 2000 一、9】31. 下面是用c語言編寫的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z句。void reverse（linklist &L）p=null；q=L；while（q！=null） (1) ; q->next=p；p=q；(2)_ ; (

43、3)_;【北京理工大學(xué) 2001 九、1 （6分）】32下面程序段是逆轉(zhuǎn)單向循環(huán)鏈表的方法，p0 是原鏈表頭指針，逆轉(zhuǎn)后鏈表頭指針仍為p0。（可以根據(jù)需要增加標(biāo)識(shí)符） p:= p0; q0:=NIL; WHILE （1）_ DO BEGIN （2）_; （3）_;（4）_;（5）_ END; p.next:= q0; p0 .next:=p; p0:=p;【中國(guó)人民大學(xué) 2000 二、1（4分）】33一個(gè)無頭結(jié)點(diǎn)的線性鏈表(不循環(huán))有兩個(gè)域。數(shù)據(jù)域data，指針域 next，鏈?zhǔn)議ead，下面算法用read(num)讀入數(shù)據(jù)，當(dāng)num小于0時(shí)，輸入結(jié)束。建立一個(gè)數(shù)據(jù)以遞增序組成的鏈表。 PRO

44、C insert( head, x);在鏈?zhǔn)诪閔ead的表中按遞增序插入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); hea

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

46、) _); pa->exp( (6)_); q=( (7) _); pa=( (8)_); 【南京理工大學(xué) 2000 三、3（10分）】35.下面是刪除單鏈表L中最大元素所在結(jié)點(diǎn)的類PASCAL語言算法，請(qǐng)?jiān)跈M線填上內(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;

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

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