數(shù)據(jù)結(jié)構(gòu)第2章作業(yè)

1、頁眉內(nèi)容第2章線性表一選擇題1下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（）A.存儲(chǔ)密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3線性表是具有n個(gè)（）的有限序列（n>0）。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)4若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A

2、.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表5某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表6. 設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（）最節(jié)省時(shí)間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表7若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（）.A.內(nèi)存地址B

3、.數(shù)組下標(biāo)C.下一元素地址D.左、右孩子地址9. 鏈表不具有的特點(diǎn)是（）A.插入、刪除不需要移動(dòng)元素B.可隨機(jī)訪問任一元素C.不必事先估at存儲(chǔ)空間D.所需空間與線性長度成正比10. 下面的敘述不正確的是（）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.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ù)在表定義

4、時(shí)就確定了，以后不能增加。（3） 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。以上錯(cuò)誤的是（）A（1），（2）B（1）C（1），（2）,（3）D.（2）13 .若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）（1<=i<=n+1）。A.O(0)B.O(1)C.O(n)D.O(n2)14 .對于順序存儲(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)15 .線性表(a1,a2,an)以鏈接方式存儲(chǔ)時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為()AO(i)

5、BO(1)CO(n)DO(i-1)16 .非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)pT滿足()。ApT.link=headBpT.link=NILC.p=NILD.p=head17循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是()。APA.NEXTkHBPA.NEXTkHANEXTC.P:=HD.P:=HA.NEXT18在一個(gè)以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是()A.p"next=hB.p人.next=NILC.p人.next.人next=hD.p"data=-119完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是()；ApA.next:=s;sA.priou:=p;pA.nextA.priou:

6、=s;sA.next:=pA.next;8 pA.nextA.priou:=s;pA.next:=s;sA.priou:=p;sA.next:=pA.next;CsA.priou:=p;sA.next:=pA.next;pA.next:=s;pA.nextA.priou:=s;DsA.priou:=p;sA.next:=pA.next;pA.nextA.priou:=s;pA.next:=s;2021在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過程依次為:rlink(p)-q;llink(p)-llink(q);llink(q)-p;()A.rlink(q)-pB.rlink(

7、llink(q)-pC.rlink(llink(p)-pD.rlink(rlink(p)-p22雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q,則正確的插入為()A. p人.llink:=q;q人.rlink:=p;p人.llink人.rlink:=q;qA.|ink：=pA.|ink；B. q人.llink:=pA.llink；p人.IlinkA.rlinkkq；q人.rlink:=p;pA.llink：=qA.riink；C. qA.rlink:=p;pA.rlink:=q;pA.llinkA.rlink

8、:=q;qA.rlink:=p;D. pA.llinkA.rlink:=q;qA.rlink:=p;qA.llink:=pA.llink;pA.llink:=q;23在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是()。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;

9、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)，正確的操作是：()。Ap->next=s;s->next=p->next;Bs->next=p->next;p->next=s;Cp->next=s;p->next=s->next;Dp->next=s->next;p->next=s;25對于一個(gè)頭指針為head

10、的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是()A.head=NULLB.headfnext=NULLC.headfnext=headD.head!=NULL26. 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針()。A. (pA.llink.rlink:=pA.rlink(pA.rlink)A.llink:=pA.llink;B. pA.llink：=(pA.|ink)A.iiink(pA.|ink)A.riink：=p；C(pA.rlink)A.llink:=ppA.rlink:=(pA.rlink)A.rlinkDpA.rlink:=(pA.llink)A.llinkpA.llink:

11、=(pA.rlink)A.rlink;27. 雙向鏈表中有兩個(gè)指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去p所指結(jié)點(diǎn)，則正確的刪除是()(鏈中結(jié)點(diǎn)數(shù)大于2，p不是第一個(gè)結(jié)點(diǎn))ApA.llinkA.rlink:=pA.llink;pA.llinkA.rlink:=pA.rlink;dispose(p);Bdispose(p);pA.llinkA.rlink:=pA.llink;pA.llinkA,rlink:=pA.rlink;CpA.llinkA.rlink:=pA.llink;dispose(p);pA.llinkA.rlink:=pA.rlink;

12、D.以上A,B,C都不對。二、判斷1. 鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。()2. 順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。()3. 線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。()4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。()5 .對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。()6 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。()7集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。()8. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。()9. 線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。()10. 取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān).()11. 循環(huán)鏈表不是線性表

13、.()12. 線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。()13. 線性表就是順序存儲(chǔ)的表。()14為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()15. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。()16. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。()三、填空1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用存儲(chǔ)結(jié)構(gòu)。2 .線性表L=(a1,a2,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是。3 設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)

14、，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語句:；;4 在一個(gè)長度為n的順序表中第i個(gè)元素(1<=i<=n)之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素。5 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是。6 .對于一個(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ù)雜度為。7 .根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成和；而又根據(jù)指針的連接方式，鏈表又可分成和。8 .在雙向循環(huán)鏈表中，向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)

15、，其操作是、O9 .在雙向鏈表結(jié)構(gòu)中，若要求在p指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：sA.next:=p;sA.prior:=;pA.prior:=s;:=s;10 .鏈接存儲(chǔ)的特點(diǎn)是利用來表示數(shù)據(jù)元素之間的邏輯關(guān)系。11 .順序存儲(chǔ)結(jié)構(gòu)是通過表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過表示元素之間的關(guān)系的。12 .對于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共個(gè)，單鏈表為個(gè)。13 .循環(huán)單鏈表的最大優(yōu)點(diǎn)是：。14 .已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：15 .帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：16 .在單鏈表L中，指針p所

16、指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：17 .帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：。18 .在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是：。19 .請?jiān)谙铝兴惴ǖ臋M線上填入適當(dāng)?shù)恼Z句。FUNCTIONinclusion(ha,hb:linklisttp):boolean;以ha和hb為頭指針的單鏈表分別表示有序表A和B,本算法判別表A是否包含在表B內(nèi)，若是，則返回“true:否則返回“false”BEGINpa:=haA.next;pb:=hbA.next;(1);WHILE(2)DOIFpaA.data=pbA.dataTHENELSE(4);END;20 .完善算法：已知單鏈表結(jié)點(diǎn)類型為：TYPEptr=A

17、node；node=RECORDdata:integer;next:ptrEND過程create建立以head為頭指針的單鏈表。PROCEDUREcreate(1):VARp,q:ptr;k:integer;BEGINnew(head);q:=head;read(k);WHILEk>0DOBEGIN3(3X(4)；read(k)END;qA.next:=NIL;END;21 .已給如下關(guān)于單鏈表的類型說明：TYPElist=Anode;node=RECORDdata:integer;next:list;END;以下程序采用鏈表合并的方法，將兩個(gè)已排序的單鏈表合并成一個(gè)鏈表而不改變其排序性

18、(升序)，這里兩鏈表的頭指針分別為p和q.PROCEDUREmergelink(VARp,q:list):VARh,r:list;BEGIN(1)hA.next:=NIL;r:=h;WHILE(p<>NIL)AND(q<>NIL)DOIF(pA.data<=qA.data)THENBEGIN(2);r:=p;p:=pA.next;ENDELSEBEGIN(3):r:=q;q:=qA.next;END;IF(p=NIL)THENrA.next:=q;(4);p:=hA.next;dispose(h);END;22 .假設(shè)鏈表p和鏈表q中的結(jié)點(diǎn)值都是整數(shù)，且按結(jié)點(diǎn)值的

19、遞增次序鏈接起來的帶表頭結(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)的值各不相同。請?jiān)趧澗€處填上適當(dāng)內(nèi)容，每個(gè)框只填一個(gè)語句或一個(gè)表達(dá)式，鏈表的結(jié)點(diǎn)類型如下TYPEnodeptHnodetype；nodetype=RECORDdata:integer；link:nodeptr;ENDCONSTmax=9999;PROCEDUREm

20、erge(VARp:nodeptr;q:nodeptr);VARr,s:nodeptr;BEGINr：=p;WHILE(A)DOBEGINWHILErA.linkA.data<qA.iinkA.dataDO(B);IFrA.linkA.data>qA.linkA.dataTHENBEGINs:=(C)_;(D)_:=sA.link;sA.link：=(E)_;(F)_:=s;(G)_;ENDELSEBEGIN(H);s:=qA.link;(I);dispose(s)ENDEND;dispose(q)END;23 .PROCins_linklist(la:linkisttp;i:in

21、teger;b:elemtp);la為指向帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法在表中第i個(gè)元素之前插入元素bp：=(1；j：=(2);指針初始化，j為計(jì)數(shù)器WHILE(p<>NIL)AND(3)DOp:=(4);j:=j+1;尋找第i-1個(gè)結(jié)點(diǎn)IF(p=NIL)OR()THENerror('Nothisposition')ELSEnew(s);sT.data:=b;sT.next:=pT.next;pT.next:=s;ENDP;ins-linklist24 .已知雙鏈表中結(jié)點(diǎn)的類型定義為：TYPEdpointer=A|ist；list=RECORDdata:integ

22、er;left,right:dpointer;END;如下過程將在雙鏈表第i個(gè)結(jié)點(diǎn)(i>=0)之后插入一個(gè)元素為x的結(jié)點(diǎn)，請?jiān)诖鸢笝诮o出題目中處應(yīng)填入的語句或表達(dá)式，使之可以實(shí)現(xiàn)上述功能。PROCEDUREinsert(VARhead:dpointer;i,x:integer);VARs,p:dpointer;j:integer;BEGINnew(s);sA.data：=x;IF(i=0)THENBEGINsA.rightkhead;(1)head:=sEND如果i=0,貝U將s結(jié)點(diǎn)插入到表頭后返回ELSEBEGINp:=head;在雙鏈表中查找第i個(gè)結(jié)點(diǎn)，由p所指向WHILE(p<

23、;>NIL)AND(j<i)DOBEGINj:=j+1;(3)END;IFp<>NILTHENIF(pA.right=NIL)THENBEGINpA.rightks;sA.rightkNIL;(4)ENDELSEBEGINsA.rightkpA.right;5);pA.right：=s;(6)_ENDELSEwriteln('cannotfindnode!')ENDEND;25 .閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個(gè)非遞減的順序存儲(chǔ)線性表中，刪除所有值相等的多余元素。CONSTmaxlen=30TYPEsqlisttp=RECORD

24、elem:ARRAY1.maxlenOFinteger;last:0.maxlenEND;PROCexam21(VARL:sqlisttp);j:=1;i:=2;THEN (2)； (3)；WHILE(1)DOIFL.elemi<>L.elemji:=i+1(4)ENDP;建立一個(gè)具有n個(gè)結(jié)點(diǎn)的環(huán)形鏈表 所建立的具有n個(gè)結(jié)點(diǎn)的環(huán)形鏈表按 n(n>0)指明環(huán)形鏈表的結(jié)點(diǎn)個(gè)數(shù)，參 指明從起始結(jié)點(diǎn)或前次被刪除并輸出的例如，對于下圖中具有6個(gè)結(jié)點(diǎn)的環(huán)26 .在本題的程序中，函數(shù)過程Create_link_list(n)程序過程josephus(n,i,m)對由Create_link_

25、list(n)一定的次序逐個(gè)輸出并刪除鏈表中的所有結(jié)點(diǎn)，參數(shù)數(shù)i(1<=i<=n)指明起始結(jié)點(diǎn)，參數(shù)m(m>0)是步長,結(jié)點(diǎn)之后的第m個(gè)結(jié)點(diǎn)作為本次被輸出并刪除的結(jié)點(diǎn)。形鏈表，在調(diào)用josephus(6,3,2)后，將輸出5,1,3,6,4,2請?jiān)跈M線處填上適當(dāng)內(nèi)容，每空只填一個(gè)語句。TYPEnodeptr=Anodetype;nodetype=RECORDdata:intrger;link:nodeptrEND;VARn,i,m:integer;FUNCTIONCreate_link_list(n:integer):nodeptr;VARhead,p,q:nodeptr;i

26、:integer;BEGINhead:=NIL;IFn>0THENBEGINnew(head);p:=head;FORi:=1TOn-1DOBEGINpA.dataki;new(q);(A);(BEND;pA.data:=n;(C);END;Creat_link_list:=headEND;PROCEDUREjosephus(n,i,m:integer);VARp,q:nodeptr;j:integer;BEGINp:=Creat_link_list(n);WHILEi>1DOBEGINp:=pA.link;i:=i-1END;(D)_;WHILEj<nDOBEGINFORi

27、:=1TOm-1DOp:=pA.link;(E);write(qA.data:8);(F)_;dispose(q);j:=j+1ENDEND;27 .對于給定的線性鏈表head,下面的程序過程實(shí)現(xiàn)了按結(jié)點(diǎn)值非降次序輸出鏈表中的所有結(jié)點(diǎn)，在每次輸出一個(gè)結(jié)點(diǎn)時(shí)，就把剛輸出的結(jié)點(diǎn)從鏈表中刪去。請?jiān)趧澗€處填上適當(dāng)?shù)膬?nèi)容，使之成為一個(gè)完整的程序過程，每個(gè)空框只填一個(gè)語句。TYPEnodeptr二人nodetype;nodetype=RECORDdata:integer;link:nodeptrEND;VARhead:nodeptr;PROCEDUREsort_output_delete(head:nod

28、eptr);VARp,q,r,s:nodeptr;BEGINWHILEhead<>NILDOBEGINp:=NIL;q:=head;rkq;s:=qA.link;WHILEs<>NILDOBEGINIFsA.data<qA.datathenBEGIN；(2)END;r：=s;(3)ENDwrite(qA.data:5);IFp=NILTHEN(4)ELSE(5);dispose(q);ENDwritelnEND【復(fù)旦大學(xué)1996七(20分)1995(12分)與本題相似】28 .下面函數(shù)的功能是在一個(gè)按訪問頻度不增有序的，帶頭結(jié)點(diǎn)的雙向鏈環(huán)上檢索關(guān)鍵值為x的結(jié)點(diǎn)，對

29、該結(jié)點(diǎn)訪問頻度計(jì)數(shù)，并維護(hù)該鏈環(huán)有序。若未找到，則插入該結(jié)點(diǎn)。所有結(jié)點(diǎn)的頻度域初值在建表時(shí)都為零。請將程序中四處空缺補(bǔ)寫完整。TYPElink=Anodenode=RECORDkey:char;freq:integer;pre,next:link;END;VARl:link;FUNCTIONloc(l:link;x:char):link;VARp,q:link;BEGINp:=|A.next;(1);WHILEpA.key<>xDOp:=pA.next;IFp=lTHENnew(q);qA.key:=x;qA.freq:=0ELSE找到pA.freq:=pA.freq+1;q:=p

30、;(2):WHILEqA.freq>pA.preA.freqDOp:=pA.pre;IFp<>qTHEN£3j;IF(4)THENqA.next:=p,qA.pre產(chǎn)pA.pre;pA.preA.next:=q;pA.pre:=qreturn(q);END;29 .循環(huán)鏈表a和b的結(jié)點(diǎn)值為字母，其中a表非遞減有序，下面的程序欲構(gòu)造一個(gè)遞增有序的循環(huán)鏈表c,其中結(jié)點(diǎn)的值為同時(shí)在a,b兩鏈表中出現(xiàn)的字母，且c中字母不重復(fù)，請補(bǔ)上程序中空缺的部分，并估計(jì)算法的時(shí)間復(fù)雜度。(設(shè)a,b的結(jié)點(diǎn)數(shù)分別為m,n)TYPElink=Anode;node=RECORDkey:char;

31、next:linkEND;PROCjj(a,b:link;VARc:link);VARp,q,r,s:link;BEGINnew(c);cA.next:=c;q:=a;p:=aA.next;WHILEp<>aDO(1)；WHILEpA.key=pA.nextA.keyDOq:=p;p=pA.next;跳過相同字母r:=bA.next;(2);WHILE.key<>pA.keyDOr:=rA.next;IFr<>bTHENs:=p;qA.next:=pA.next;(3);sA.next:=cA.next;cA.next:=s;c:=sELSEq:=p;p:=

32、pA.next;c:=cA.next;END;算法時(shí)間復(fù)雜度為O(4)30 .以下程序的功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)點(diǎn)逆序連接，請?zhí)羁胀晟浦oidreverse(pointerh)/*h為附加頭結(jié)點(diǎn)指針；類型pointer同算法設(shè)計(jì)第3題*/pointerp,q;p=h->next;h->next=NULL;while(1)q=p;p=p->next;q->next=h->next;h->next=(2);31 .下面是用c語言編寫的對不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z句。voidre

33、verse(linklist&L)p=null;q=L;while(q!=null)(1)；q->next=p;p=q；(2);(3)一：四應(yīng)用題1.線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：(1)如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？(2)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？2 線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，

34、往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。3 若較頻繁地對一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)？為什么？4 線性結(jié)構(gòu)包括、和。線性表的存儲(chǔ)結(jié)構(gòu)分成和5 .線性表（ai,a2,，an）用順序映射表示時(shí)，a，和a，+i（1<=i<n的物理位置相鄰嗎？鏈接表示時(shí)呢？【東南大學(xué)1996一、1（5分）】6 .說明在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別；頭結(jié)點(diǎn)與首元結(jié)點(diǎn)的關(guān)系。7 .試述頭結(jié)點(diǎn),首元結(jié)點(diǎn),頭指針這三個(gè)概念的區(qū)別.8 .已知有如下定義的靜態(tài)鏈表：TYPEcomponen

35、t=RECORDdata:elemtp;next:0.maxsizeENDVARstalist:ARRAY0.maxsizeOFcomponent;以及三個(gè)指針:av指向頭結(jié)點(diǎn)，p指向當(dāng)前結(jié)點(diǎn)，pre指向前驅(qū)結(jié)點(diǎn)，現(xiàn)要求修改靜態(tài)鏈表中next域中的內(nèi)容，使得該靜態(tài)鏈表有雙向鏈表的功能，從當(dāng)前結(jié)點(diǎn)p既能往后查找，也能往前查找：（1）定義next域中的內(nèi)容。（用老的next域中的值表示）；（2）如何得到當(dāng)前結(jié)點(diǎn)p的前驅(qū)（pre）的前驅(qū)，給出計(jì)算式;（ 3） 如何得到p的后繼，給出計(jì)算式;9 .在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任何一個(gè)結(jié)點(diǎn)?10 .如何通過改鏈的方法，把一個(gè)單向鏈表變成

36、一個(gè)與原來鏈接方向相反的單向鏈表？11 .下面是一算法的核心部分，試說明該算法的功能。pre:=LT.next;L是一單鏈表，結(jié)點(diǎn)有數(shù)據(jù)域data和指針域nextIFpre<>NILTHENWHILEpreT.next<>NILDOBEGINp:=preT.next;IFpT.data>=preT.dataTHENpre:=pELSEreturn（false）END;return（true）;12 .設(shè)單鏈表結(jié)點(diǎn)指針域?yàn)閚ext,試寫出刪除鏈表中指針p所指結(jié)點(diǎn)的直接后繼的C語言語句。13 .設(shè)單鏈表中某指針p所指結(jié)點(diǎn)（即p結(jié)點(diǎn)）的數(shù)據(jù)域?yàn)閐ata，鏈指針域?yàn)閚ex

37、t，請寫出在p結(jié)點(diǎn)之前插入s結(jié)點(diǎn)的操作（PASCA造句）?！颈本┛萍即髮W(xué)1999一、2（2分）】14 .有線性表（ai,a2,an）,采用單鏈表存儲(chǔ)，頭指針為H,每個(gè)結(jié)點(diǎn)中存放線性表中一個(gè)元素，現(xiàn)查找某個(gè)元素值等于X的結(jié)點(diǎn)。分別寫出下面三種情況的查找語句。要求時(shí)間盡量少。（1）線性表中元素?zé)o序。（2）線性表中元素按遞增有序。（3）線性表中元素按遞減有序。15 設(shè)pa，pb分別指向兩個(gè)帶頭結(jié)點(diǎn)的有序（從小到大）單鏈表。仔細(xì)閱讀如下的程序，并回答問題：(1)程序的功能。(2)si,s2中值的含義。(3)pa,pb中值的含義。PROCEDUREexam(pa,pb)BEGINp1:=paT.next

38、;p2:=pbT.next;paT.next:=A;s1:=0;s2:=0;WHILEplwAANDp2wADOCASEpiT.data<p2T.data:p:=p1;p1:=p1T.next;s2:=s2+1;dispose(p);piT.data>p2T.data:p2:=p2"next;piT.data=p2T.data:p:=p1;p1:=p1T.next;pT.next:=pa"next;paT.next:=p;p2:=p2T.next;si:=si+i;END;WHILEpiwADOp:=pi;pi:=piT.next;dispose(p);s2:=

39、s2+iEND;18.已知L是一個(gè)數(shù)據(jù)類型linkedlist的單循環(huán)鏈表，pa和pb是指向L中結(jié)點(diǎn)的指針。簡述下列程序段的功能。TYPElinkedlist=Tnode;node=RECORDdata:datatype;next:linkedlistEND;PROCMp(pa,pb:linkedlist);PROCsubp(s,q:linkedlist);p：=s;WHILEpT.next<>qDOp:=pT.next;pT.next:=sENDP;subp(pa,pb);subp(pb,pa);ENDP;五、算法設(shè)計(jì)題i.假設(shè)有兩個(gè)按元素值遞增次序排列的線性表，均以單鏈表形式存

40、儲(chǔ)。請編寫算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表，并要求利用原來兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表?！颈本┐髮W(xué)1998三、1(5分)】類似本題的另外敘述有：(1)設(shè)有兩個(gè)無頭結(jié)點(diǎn)的單鏈表，頭指針分別為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分)】PROCEDUREmerge(ha,hb);(2)已知頭指針分別為la和lb的帶頭結(jié)點(diǎn)的單鏈表中，結(jié)點(diǎn)按元素值非遞減有

41、序排列。寫出將la和lb兩鏈表歸并成一個(gè)結(jié)點(diǎn)按元素值非遞減有序排列的單鏈表(其頭指針為lc),并計(jì)算算法的時(shí)間復(fù)雜度。【燕山大學(xué)1998五(20分)】2.帶有頭結(jié)點(diǎn)且頭指針為ha和hb的兩線性表A和B分別表示兩個(gè)集合。兩表中的元素皆為遞增有序。請寫一算法求A和B的并集AUB要求該并集中的元素仍保持遞增有序。且要利用A和B的原有結(jié)點(diǎn)空間。類似本題的另外敘述有：(1)已知遞增有序的兩個(gè)單鏈表A,B分別存儲(chǔ)了一個(gè)集合。設(shè)計(jì)算法實(shí)現(xiàn)求兩個(gè)集合的并集的運(yùn)算A:=AUB(2)已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。編一函數(shù)，求A與B的交集，并存放于A鏈表中。(3)設(shè)有兩個(gè)從小到大排序的帶頭結(jié)點(diǎn)

42、的有序鏈表。試編寫求這兩個(gè)鏈表交運(yùn)算的算法(即L1AL2)。要求結(jié)果鏈表仍是從小到大排序，但無重復(fù)元素。(4)己知兩個(gè)線性表A,B均以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)，且表中元素按值遞增有序排列。設(shè)計(jì)算法求出A與B的交集C,要求C另開辟存儲(chǔ)空間，要求C同樣以元素值的遞增序的單鏈表形式存貯。(5)已知遞增有序的單鏈表A,B和C分別存儲(chǔ)了一個(gè)集合，設(shè)計(jì)算法實(shí)現(xiàn)A:=AU(BAQ,并使求解結(jié)構(gòu)A仍保持遞增。要求算法的時(shí)間復(fù)雜度為O(|A|+|B|+|C|)。其中,|A|為集合A的元素個(gè)數(shù)。3 .知L1、L2分別為兩循環(huán)單鏈表的頭結(jié)點(diǎn)指針，m,n分別為L1、L2表中數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù)。要求設(shè)計(jì)一算法，用最快速度將

43、兩表合并成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表。類似本題的另外敘述有：(1)試用類Pascal語言編寫過程PROCjoin(VARla:link;lb：link)實(shí)現(xiàn)連接線性表la和lb(lb在后)的算法，要求其時(shí)間復(fù)雜度為0(1),占用輔助空間盡量小。描述所用結(jié)構(gòu)。(2)設(shè)有兩個(gè)鏈表，ha為單向鏈表，hb為單向循環(huán)鏈表。編寫算法，將兩個(gè)鏈表合并成一個(gè)單向鏈表，要求算法所需時(shí)間與鏈表長度無關(guān)。4 .順序結(jié)構(gòu)線性表LA與LB的結(jié)點(diǎn)關(guān)鍵字為整數(shù)。LA與LB的元素按非遞減有序，線性表空間足夠大。試用類PASCA匿言給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避免移

44、動(dòng)元素。5 .已知不帶頭結(jié)點(diǎn)的線性鏈表list,鏈表中結(jié)點(diǎn)構(gòu)造為(data、link)，其中data為數(shù)據(jù)域，link為指針域。請寫一算法，將該鏈表按結(jié)點(diǎn)數(shù)據(jù)域的值的大小從小到大重新鏈接。要求鏈接過程中不得使用除該鏈表以外的任何鏈結(jié)點(diǎn)空間。6 .設(shè)L為單鏈表的頭結(jié)點(diǎn)地址，其數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)都是正整數(shù)且無相同的，試設(shè)計(jì)利用直接插入的原則把該鏈表整理成數(shù)據(jù)遞增的有序單鏈表的算法。類似本題的另外敘述有：(1)設(shè)一單向鏈表的頭指針為head,鏈表的記錄中包含著整數(shù)類型的key域，試設(shè)計(jì)算法，將此鏈表的記錄按照key遞增的次序進(jìn)行就地排序.【中科院計(jì)算所1999五、1(10分)】7.設(shè)Listhead為一

45、單鏈表的頭指針，單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域DAT解口指針域NEXT組成，整數(shù)在單鏈表中是無序的。編一PASCAM程，將Listhead鏈中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈，分別由P,Q指向，每個(gè)鏈中的數(shù)據(jù)按由小到大排列。程序中不得使用NEW過程申請空間。類似本題的另外敘述有：(1)設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表日C,其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表A的元素類型為整型，要求BC表利用A表的結(jié)點(diǎn))。(2)設(shè)L為一單鏈表的頭指針，單鏈表的每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域data和指針域NEXTfi成，整數(shù)在單鏈表中是無序的。設(shè)計(jì)算法，將

46、鏈表中結(jié)點(diǎn)分成一個(gè)奇數(shù)鏈和一個(gè)偶數(shù)鏈，分別由巳Q指向，每個(gè)鏈中的數(shù)據(jù)按由小到大排列，算法中不得申請新的結(jié)點(diǎn)空間。(3)將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B,使得A表中含有原表中序號(hào)為奇數(shù)的元素，而B表中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對順序不變。1)寫出其類型定義：2)寫出算法。8.已知線性表(ala2a3an)按順序存于內(nèi)存，每個(gè)元素都是整數(shù)，試設(shè)計(jì)用最少時(shí)間把所有值為負(fù)數(shù)的元素移到全部正數(shù)值元素前邊的算法：例：(x,-x,-x,x,x,-xx)變?yōu)?-x,-x,-xx,x,x)。類似本題的另外敘述有：(1)設(shè)有一元素為整數(shù)的線性表L=(ai,a2,a3,an),存

47、放在一維數(shù)組AN中，設(shè)計(jì)一個(gè)算法，以表中an作為參考元素，將該表分為左、右兩部分，其中左半部分每個(gè)元素小于等于an,右半部分每個(gè)元素都大于an,an位于分界位置上(要求結(jié)果仍存放在AN中)。(2)順序存儲(chǔ)的線性表A,其數(shù)據(jù)元素為整型，試編寫一算法，將A拆成B和C兩個(gè)表，使A中元素值大于等于0的元素放入B,小于0的放入C中.要求：1)表B和C另外設(shè)置存儲(chǔ)空間；2)表B和C不另外設(shè)置，而利用A的空間.【山東大學(xué)2001九、1(12分)】(3)知線性表(a1,a2,a3,，an)按順序存儲(chǔ)，且每個(gè)元素都是整數(shù)均不相同，設(shè)計(jì)把所有奇數(shù)移到所有偶數(shù)前邊的算法。(要求時(shí)間最少，輔助空間最少)【東北大學(xué)1997三(15分)】(4)編寫函數(shù)將一整數(shù)序列中所有負(fù)數(shù)移到所有正數(shù)之前，要求時(shí)間復(fù)雜度為O(n)(5)已知一個(gè)由n(設(shè)n=1000)個(gè)整數(shù)組成的線性表，試設(shè)計(jì)該線性表的一種存儲(chǔ)結(jié)構(gòu)，并用標(biāo)準(zhǔn)pascal語言描述算法，實(shí)現(xiàn)將n個(gè)元素中所有大于等于19的整數(shù)放在所有小于19的整數(shù)之后。要求算法的時(shí)間復(fù)雜度為O(n),