【正文】 ^.link:=(E)_。 (F)_ _:=s。 (G)_。 END ELSE BEGIN (H)__。 s:=q^.link。 (I)__。 dispose(s) END END。 dispose(q)END?！緩?fù)旦大學(xué) 1997 五（18分）】23．PROC ins__linklist(la:linkisttp。 i:integer。 b:elemtp)。{la為指向帶頭結(jié)點的單鏈表的頭指針，本算法在表中第i個元素之前插入元素b}p:=(1) 。 j:=(2) 。{指針初始化，j為計數(shù)器}WHILE (pNIL) AND ((3) ) DO [p:=(4) 。 j:=j+1；] {尋找第 i1 個結(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。{inslinklist}【燕山大學(xué) 1998 四、1（15分）】24. 已知雙鏈表中結(jié)點的類型定義為：TYPE dpointer=^list。list=RECORDdata:integer。 left,right:dpointer。END。如下過程將在雙鏈表第i個結(jié)點（i=0）之后插入一個元素為x的結(jié)點，請在答案欄給出題目中______處應(yīng)填入的語句或表達式，使之可以實現(xiàn)上述功能。PROCEDURE insert(VAR head:dpointer。i,x:integer)。VAR s,p:dpointer。 j: integer。BEGINnew(s)。 s^.data:=x。IF(i=0)THEN BEGIN s^.right:=head。 (1)___ head:=s END{如果i=0,則將s結(jié)點插入到表頭后返回}ELSE BEGIN p:=head。 (2)_______；{在雙鏈表中查找第i個結(jié)點,由p所指向} WHILE ((pNIL) AND (ji)) DO BEGIN j:=j+1。 (3) _ END。 IF pNIL 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) END ELSE writeln(‘can not find node!’) ENDEND?！緩B門大學(xué) 2002 二 （12分）】25．閱讀以下算法，填充空格，使其成為完整的算法。其功能是在一個非遞減的順序存儲線性表中，刪除所有值相等的多余元素。 CONST maxlen=30TYPE sqlisttp=RECORD elem:ARRAY[1..maxlen] OF integer。 last:0..maxlen END。PROC exam21(VAR L:sqlisttp)。 j:=1。 i:=2。 WHILE (1)______ DO [ IF [i][j] THEN [ (2)_______。 (3)______]。 i:=i+1 ] (4) ________。 ENDP。【同濟大學(xué) 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(n0)指明環(huán)形鏈表的結(jié)點個數(shù)，參數(shù) i(1=i=n)指明起始結(jié)點，參數(shù) m (m0)是步長，指明從起始結(jié)點或前次被刪除并輸出的結(jié)點之后的第m個結(jié)點作為本次被輸出并刪除的結(jié)點。例如，對于下圖中具有6個結(jié)點的環(huán)形鏈表，在調(diào)用 josephus(6,3,2)后，將輸出 5,1,3,6,4,2 請在橫線處填上適當(dāng)內(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 n0 THEN BEGIN new(head)。 p: =head。 FOR i:=1 TO n1 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 i1 DO BEGIN p:=p^.link。 i:=i1 END。 (D)___ 。 WHILE jn DO BEGIN FOR i:=1 TO m1 DO p:=p^.link。 (E)___。 write(q^.data:8)。 (F)__ 。 dispose(q)。 j:=j+1 ENDEND?！緩?fù)旦大學(xué) 1997 四（12分）】27．對于給定的線性鏈表head , 下面的程序過程實現(xiàn)了按結(jié)點值非降次序輸出鏈表中的所有結(jié)點，在每次輸出一個結(jié)點時，就把剛輸出的結(jié)點從鏈表中刪去。請在劃線處填上適當(dāng)?shù)膬?nèi)容，使之成為一個完整的程序過程，每個空框只填一個語句。TYPE nodeptr =^ nodetype；nodetype = RECORD data : integer；link : nodeptrEND。VAR head : nodeptr；PROCEDURE 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) ； END； writelnEND；【復(fù)旦大學(xué) 1996 七（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^.keyx 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^.freqp^.pre^.freq DO p:=p^.pre。IF pq THEN [ （3）______ ]]；IF （4）_ THEN [q^.next:=p, q^.pre。=p^.pre。 p^.pre^.next:=q。 p^.pre:=q]return(q)。END?！颈本┕I(yè)大學(xué) 1999 五 (12分)】29．循環(huán)鏈表a和b的結(jié)點值為字母，其中a表非遞減有序，下面的程序欲構(gòu)造一個遞增有序的循環(huán)鏈表c，其中結(jié)點的值為同時在a，b兩鏈表中出現(xiàn)的字母，且c中字母不重復(fù)，請補上程序中空缺的部分，并估計算法的時間復(fù)雜度。（設(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 pa DO [（1）___；WHILE p^.key=p^.next^.key DO [q:=p。 p=p^.next]。｛跳過相同字母｝r:=b^.next 。 （2）_____。WHILE r^.key p^.key DO r:=r^.next。IF rb 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。 　　　　　　　　　算法時間復(fù)雜度為O（4）___ 【北京工業(yè)大學(xué) 2000 四 (15分)】30. 以下程序的功能是實現(xiàn)帶附加頭結(jié)點的單鏈表數(shù)據(jù)結(jié)點逆序連接，請?zhí)羁胀晟浦oid reverse(pointer h) /* h為附加頭結(jié)點指針；類型pointer同算法設(shè)計第3題*/{ pointer p,q。 p=hnext。 hnext=NULL。while((1)________) {q=p。 p=pnext。 qnext=hnext。 hnext=(2)________。 }}【西南交通大學(xué) 2000 一、9】31. 下面是用c語言編寫的對不帶頭結(jié)點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z句。void reverse（linklist amp。L）{p=null；q=L；while（q！=null）{ (1) 。 qnext=p；p=q；(2)___ 。 } (3)_____。}【北京理工大學(xué) 2001 九、1 （6分）】32．下面程序段是逆轉(zhuǎn)單向循環(huán)鏈表的方法，p0 是原鏈表頭指針，逆轉(zhuǎn)后鏈表頭指針仍為p0。（可以根據(jù)需要增加標(biāo)識符） p:= p0。 q0:=NIL。 WHILE （1）________ DO BEGIN （2）________。 （3）________。（4）______。（5）________ END。 p^.next:= q0。 p0 ^.next:=p。 p0:=p?！局袊嗣翊髮W(xué) 2000 二、1（4分）】33．一個無頭結(jié)點的線性鏈表(不循環(huán))有兩個域。數(shù)據(jù)域data，指針域 next，鏈?zhǔn)議ead，下面算法用read(num)讀入數(shù)據(jù)，當(dāng)num小于0時，輸入結(jié)束。建立一個數(shù)據(jù)以遞增序組成的鏈表。 PROC insert( head, x)。{在鏈?zhǔn)诪閔ead的表中按遞增序插入x}new(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＾.next≠NIL ) DO[q:=p。 (5)