【正文】 第 2 章 線性表 一．選擇題 ,C 二．判斷題 1. 2.√ 3. √ 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. √ 15. 16. √ 部分答案解釋如下。 頭結(jié)點并不“僅起”標(biāo)識作用，并且使操作統(tǒng)一。另外，頭結(jié)點數(shù)據(jù)域可寫入鏈表長度，或作監(jiān)視哨。 4．兩種存儲結(jié)構(gòu)各有優(yōu)缺點，應(yīng)根據(jù)實際情況選用，不能籠統(tǒng)說哪一個好。 7．集合中元素?zé)o邏輯關(guān)系。 9．非空線性表第一個元素?zé)o前驅(qū)，最后一個元素?zé)o后繼。 13．線性表是邏輯結(jié)構(gòu)，可以順序存儲，也可鏈?zhǔn)酱鎯Α? 三．填空題 1．順序 2．（ n1） /2 3． pynext=pxnext。 pxnext=py 4 ． ni+1 5．主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入 元素 和刪除第一個結(jié)點不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。 6． O(1)， O(n) 7．單鏈表， 多重 鏈表，（動態(tài)）鏈表，靜態(tài)鏈表 8． fnext=pnext。 fprior=p。 pnextprior=f。 pnext=f。 9． p^.prior s^.prior^.next 10． 指針 11．物理上相鄰 指針 12． 4 2 13．從任一結(jié)點出發(fā)都可訪問到鏈 表中每一個元素。 14 ． u=pnext。 pnext=unext。 free(u)。 15 ． Lnextnext==L 16． pnext!=null 17． Lnext==L amp。amp。 Lprior==L 18． snext=pnext。pnext=s。 19． (1) IF pa=NIL THEN return(true)。 (2) pbNIL AND pa^.data=pb^.data (3) return(inclusion(pa,pb))。 (4) pb:=pb^.next。 (5) return(false)。 非遞歸算法： (1)pre:=pb。 (2) paNIL AND pbNIL AND pb^.data=pa^.data (3)pa:=pa^.next。 pb:=pbnext。 (4)pb:=pre^.next。pre:=pb。pa:=pa^.next。(5)IF pa=NIL THEN return(true) ELSE return(false)。 [注 ]：本題是在鏈表上求模式匹配問 題。非遞歸算法中用指針 pre指向主串中開始結(jié)點（初始時為第一元素結(jié)點）。若主串與子串對應(yīng)數(shù)據(jù)相等，兩串工作指針 pa和 pb 后移；否則，主串工作指針從 pre的下一結(jié)點開始（這時 pre 又指向新的開始結(jié)點），子串工作指針從子串第一元素開始，比較一直繼續(xù)到循環(huán)條件失敗。若 pa為空，則匹配成功，返回 true，否則，返回 false。 20． A． VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(帶頭結(jié)點 ) 21．（ 1） new(h)?！紊深^ 結(jié)點，以便于操作。 （ 2） r^.next:=p。 (3) r^.next:=q。 (4) IF (q=NIL) THEN r^.next:=p。 22． A: r^.link^.datamax AND q^.link^.datamax B: r:=r^.link C: q^.link D: q^.link E: r^.link F: r^.link G: r:=s（或 r:= r^.link） H: r:=r^.link I: q^.link:=s^.link 23． (1)la (2)0 (3)ji1 (4)p↑ .next (5)i1 24.(1)head^.left:=s ∥ head的前驅(qū)指針指向插入結(jié)點 (2)j:=1。 (3)p:=p^.right ∥工作指針后移 (4)s^.left:=p (5)p^.right^.left:=s。 ∥ p后繼的前驅(qū)是 s (6)s^.left:=p。 25.(1)i= ∥ 為元素 個數(shù) (2)j:=j+1 ∥有值不相等的元素 (3)[j]:=[i] ∥元素前移 (4):=j ∥元素個數(shù) 26.(A)p^.link:=q?！卫湘?，前驅(qū)指向后繼 (B)p:=q?！涡碌那膀?qū) (C)p^.link:=head?！涡纬裳h(huán)鏈表 (D)j:=0。 ∥計數(shù)器，記被刪結(jié)點 (E)q:=p^.link∥記下被刪結(jié)點 (F)p^.link=q^.link ∥刪除結(jié)點 27. (1)p:=r?！?r指向工作指針 s的前驅(qū)， p指向最小值的前驅(qū)。 (2)q:=s?！?q指向最小值結(jié)點， s是工作指針 (3)s:=s^.link∥工作指針后移 (4)head:=head^.next?！蔚谝粋€結(jié)點值最小； (5)p^link:=q^.link?！慰邕^被刪結(jié)點（即刪除一結(jié)點） 28． (1) l^.key:=x?！晤^結(jié)點 l這時起監(jiān)視哨作用 (2) l^.freq:=p^.freq ∥頭結(jié)點起監(jiān)視哨作用 (3) qprenext=qnext。 qnextpre=qpre。 ∥先將 q結(jié)點從鏈 表上摘下 q^.next:=p。 q^.pre:=p^.pre。 p^.prenext:=q。 p^.pre:=q。 ∥結(jié)點 q插入結(jié)點 p前 (4) q^.freq=0 ∥鏈表中無值為 x的結(jié)點，將新建結(jié)點插入到鏈表最后（頭結(jié)點前）。 29． (1)a^.key:=’ @’∥ a的頭結(jié)點用作監(jiān)視哨，取不同于 a鏈表中其它數(shù)據(jù)域的值 (2)b^.key:=p^.key∥ b的頭結(jié)點起監(jiān)視哨作用 (3)p:=p^.next∥找到 a,b表中共同字母， a表指針后移 (4)0(m*n) 30. C 部 分： (1)p!=null ∥鏈表未到尾就一直作 (2)q ∥將當(dāng)前結(jié)點作為頭結(jié)點后的第一元素結(jié)點插入 31. (1)L=Lnext。 ∥暫存后繼 (2)q=L。 ∥待逆置結(jié)點 (3)L=p。 ∥頭指針仍為 L 32. (1) p^.nextp0 (2)r:= p^.next (3) p^.next:= q0。 (4) q0:= p。 (5) p:=r 33. (1)r (2)NIL (3)xhead^.data (4)p^.datax (5)p:=p^.next (6)p^.data=x。 (7)r (8)p (9)r (10)NIL (11)NIL 34． (1)pa!=ha ∥或 paexp!=1 (2)paexp==0 ∥若指數(shù)為 0，即本項為常數(shù)項 (3)qnext=panext ∥刪常數(shù)項 (4)qnext ∥取下一元素 (5)=pacoef*paexp (6) ∥指數(shù)項減 1 (7)pa ∥前驅(qū)后移 ,或 qnext (8)panext ∥取下一元素 35． (1)q:=p。 ∥ q是工作指針 p的前驅(qū) (2)p^.datam ∥ p是工作指針 (3)r:=q。 ∥ r 記最大值 的前驅(qū)， (4)q:=p。 ∥或 q:=q^.next。 (5)r^.next:=q^.next。 ∥或 r^.next:=r^.next^.next 刪最大值結(jié)點 36． (1)Lnext=null ∥置空鏈表 ,然后將原鏈表結(jié)點逐個插入到有序表中 (2)p!=null ∥當(dāng)鏈表尚未到尾， p為工作指針 (3)q!=null ∥查 p結(jié)點在鏈表中的插入位置，這時 q是工作指針。 (4)pnext=rnext ∥將 p結(jié)點鏈入鏈表中 (5)rnext=p ∥ r是 q的前驅(qū)， u是下個待插入結(jié)點的指針。 37．程序（ a） PASCAL部分 (編者略） 程序（ b） C部分 (1)(A!=null amp。amp。 B!=null) ∥兩均未空時循環(huán) (2)Aelement==Belement ∥兩表中相等元素不作結(jié)果元素 (3)B=Blink ∥向后移動 B表指針 (4)A!=null ∥將 A 表剩余部分放入結(jié)果表中 (5)lastlink=null ∥置鏈表尾 四、 應(yīng)用題 1．（ 1）選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪 除時間復(fù)雜度為 O（ 1）。 （ 2）選順序存儲結(jié)構(gòu)。順序表可以隨機存取，時間復(fù)雜度為 O（ 1）。 2．鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為 O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當(dāng)空間不允 許時，就不能克服順序存儲的缺點。 3．采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，它根據(jù)實際需要申請內(nèi)存空間，而當(dāng)不需要時又可將不用結(jié)點空間返還給系統(tǒng)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中插入和刪除操作不需要移動元素。 4．線性表 棧 隊列 串 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 順序存儲結(jié)構(gòu)的定義是： CONST maxlen=線性表可能達到的最大長度； TYPE sqlisttp=RECORD elem:ARRAY[1..maxlen] OF ElemType。 last:0..maxlen。 END。 鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義是： TYPE pointer=↑ nodetype。 nodetype=RECORD data:ElemType。 next:pointer。 END。 linklisttp=pointer。 射時， ai與 ai+1的物理位置相鄰；鏈表表示時 ai與 ai+1的物理位置不要求相鄰。 6．在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、 用做監(jiān)視哨 等等），有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié) 點后邊的第一個結(jié)點。 7． 見上題 6。 8． (1)將 next域變?yōu)閮蓚€域 : pre和 next，其值域均為 0..maxsize。初始化時，頭結(jié)點（下標(biāo)為 0的元素）其 next域值為 1，其 pre域值為 n（設(shè) n是元素個數(shù)，且 nmaxsize） (2) stalist[stalist[p].pre].pre。 (3) stalist[p].next。 9. 在單鏈表中不能從當(dāng)前結(jié)點（若當(dāng)前結(jié)點不是第一結(jié)點）出發(fā)訪問到任何一個結(jié)點，鏈表只能從頭指針開始，訪問到鏈表中每個結(jié)點。在雙鏈表中求前驅(qū)和后繼都容易，從 當(dāng)前結(jié)點向前到第一結(jié)點，向后到最后結(jié)點，可以訪問到任何一個結(jié)點。 10．本題是鏈表的逆置問題。設(shè)該鏈表帶頭結(jié)點，將頭結(jié)點摘下，并將其指針域置空。然后從第一元素結(jié)點開始，直到最后一個結(jié)點為止，依次前插入頭結(jié)點的后面，則實現(xiàn)了鏈表的逆置。 11．該算法的功能是判斷鏈表 L是否是非遞減有序，若是則返回“ true”；否則返