數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案[1]資料

1、1 填空在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（） 和（）有關(guān)?！窘獯稹勘黹L的一半，表長，該元素在表中的位置順序表中第一個(gè)元素的存儲地址是100.每個(gè)元素的長度為2.則第5個(gè)元素的存儲地址是（）c【解答】108【分析】第5個(gè)元素的存儲地址=第1個(gè)元素的存儲地址+ （5-1）x2=108設(shè)單鏈表中抬針p指向結(jié)點(diǎn)A.若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操 作為（）【解答】p-next=（p-next）-next収鏈表中設(shè)宜頭結(jié)點(diǎn)的作用是（）。【解答】為了運(yùn)算方便【分析】例如在插入和刪除操作時(shí)不必對表頭的情況進(jìn)行特殊處理非空的單循

2、環(huán)鏈表由頭指針head指示,則其尾結(jié)點(diǎn)（由指針p所指）滿足（【解答】p-next=head【分析】如圖28所示。在由尾指針rear扌X示的單循環(huán)鏈表中.在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（）：刪除開始結(jié)點(diǎn)的操作 序列為（）o【解答】s-next =rear-next: rear-next =s: rear =s：（將S的指針域先弄成表屋抬針域.而表尾指針域是代表 下個(gè)結(jié)點(diǎn)的地址信息，所以要將指針域要用S替代.最后把表尾給S）q=rear-next-next: rear-next-next=q-next; delete q:【分析】操作示意圖如圖29所示：MBIear |reS甸29帶尾指針的循環(huán)

3、鏈表中插入和刪除操作示意因一個(gè)具有n個(gè)結(jié)點(diǎn)的的鏈表，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）：在給定值為x 的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)朵度為（）【解答】0（1）, O（n）【分析】在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針.所以時(shí)間復(fù)雜度為0（1）（是表示常數(shù)計(jì)算時(shí)間）: 而在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需要先査找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)朵度為O（n）?？捎梢粋€(gè)尾指針唯一確定的鏈表有（人（）、（）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表.雙鏈表2. 選擇題線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu).線性表的鏈接存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。A隨機(jī)存取B順序存取C索引存取D散列存取【解答】A

4、, B【分析】參見221。線性表采用鏈接存儲時(shí).其地址（）0A必須是連續(xù)的B部分地址必須是連續(xù)的C 一定是不連續(xù)的D連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任總的存儲*1元存儲線性表的數(shù)據(jù)元素.這組存儲爪元可以連續(xù)，也 可以不連續(xù)，甚至可以零散分布在內(nèi)存中任總位宜。訊循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。A不再需要頭指針了B從表中任一結(jié)點(diǎn)岀發(fā)都能掃描到整個(gè)鏈表：C已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)：D在進(jìn)行插入、刪除操作時(shí)，能迴好地保證鏈表不斷開。【解答】B鏈表不具有的持點(diǎn)是（）。A可隨機(jī)訪問任一元素B插入、刪除不需要移動(dòng)元素C不必事先估訃存儲空間D所需空間與線性表長度成正比【

5、解答】A若某線性表中報(bào)常用的操作是取第i個(gè)元素和找笫i個(gè)元素的前驅(qū)則采用（）存儲方法最節(jié)省時(shí)間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i個(gè)元素，所以.應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表同時(shí)在順序表中 査找第i個(gè)元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取.査找第i個(gè)元素的前驅(qū)也不方 便，雙鏈表雖然能快速査找第i個(gè)元素的前驅(qū)，但不能實(shí)現(xiàn)隨機(jī)存取。若鏈表中最常用的操作是在鍛后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（）存儲方法 最節(jié)省時(shí)間。A單鏈表B帶頭扌&針的譏循環(huán)鏈表C雙鏈表D帯圧抬針的敢循壞鏈表【解答】D【分析】在鏈表中的昴后一個(gè)結(jié)點(diǎn)之后

6、插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，譏鏈表、帶頭抬針 的單循環(huán)鏈表.雙鏈表都不合適.考慮在帶尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是0（1）, 所以.答案是D o若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲方 法昴節(jié)省運(yùn)算時(shí)間。A單鏈表B循環(huán)應(yīng)鏈表C訊循環(huán)鏈表D帯尾抬針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、訊循環(huán)鏈 表都不合適，刪除最后一個(gè)結(jié)點(diǎn)需耍知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址.所以，帶尾抬針的單循環(huán)鏈表不合 適，而循環(huán)雙鏈表滿足條件。在具有n個(gè)結(jié)點(diǎn)的有序訊鏈表中插入一個(gè)新

7、結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是（）。A0（l）B 0（ n） C 0（n2） D O（nlog2n）【解答】B【分析】首先應(yīng)順序査找新結(jié)點(diǎn)在單鏈表中的位邏。對于n個(gè)元素組成的線性表.建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是()。AO(1)B 0(n)C0(n2)DO(nlog2n)【解答】C【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需O(n)o(使用雙鏈表存儲線性表，其優(yōu)點(diǎn)是可以()。A提商査找速度B更方便數(shù)據(jù)的插入和刪除C節(jié)約存儲空間D很快回收存儲空間【解答】B【分析】在鏈表中一般只能進(jìn)行順序査找，所以.雙鏈表并不能提舟查找速度，因?yàn)殡p鏈表中有兩個(gè)抬針 域，顯然不能節(jié)約存儲空間

8、，對于動(dòng)態(tài)存儲分配.回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性. 所以.其插入和刪除操作更加方便。)在一個(gè)單鏈表中.已知q所指結(jié)點(diǎn)是p所抬結(jié)點(diǎn)的直接前驅(qū).若在q和p之間插入s所抬結(jié)點(diǎn).則執(zhí)行 ()操作。A s-nexl=p-next: p-next=s: B q-next=s: s-nexl=p:C p-nexl=s-next: s-next=p: D p-next=s: s-next=q;【解答】B【分析】注總此題是在q和p之間插入新結(jié)點(diǎn).所以，不用考慮修改指針的順序(13在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所抬結(jié)點(diǎn)的操作是(A p-next=s: s-prior=p: p-next-pr

9、ior=s: s-next=p-next:B p-next=s: p-next-prior=s: s-prior=p; s-next=p-next:C s-prior=p: s-next=p-next: p-next=s: p-next-prior=s:D s-prior=p: s-nexl=p-next: p-next-prior=s; p-next=s【解答】D【分析】在鏈表中.對指針的修改必須保持線性表的邏輯關(guān)系.否則.將違背線性表的邏輯特征.圖210 給出備選答案C和D的圖解。(Q備選答案C操作示意鈕第4步指針修改無法進(jìn)行)(b)備選答案D操作示意因團(tuán)2-10雙漣表插入操作修改指針操作

10、示意團(tuán)3. 判斷題線性表的邏輯順序和存儲順序總是一致的。【解答】錯(cuò)。順序表的邏輯順序和存儲順序一致.鏈表的邏輯順序和存儲順序不一定一致。線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)?！窘獯稹垮e(cuò)。兩種存儲結(jié)構(gòu)各有優(yōu)缺點(diǎn)。設(shè)p，q是指針，若p=q.則取p=*q【解捽】錯(cuò)；p=q只能表示p和q指向同-起始地址，而所拓啖型則不一定相同。線性結(jié)構(gòu)的基木特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼?！窘獯稹垮e(cuò)。每個(gè)元素最藝只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū).報(bào)后一個(gè)元素沒有 后繼。在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e(cuò)。嬰找到該結(jié)點(diǎn)

11、的地址，必須從頭指針開始査找.所以爪鏈表是順序存収結(jié)構(gòu)。4. 請說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。若線性表的總長度基木穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以報(bào)快的速度存取線性表中的元素。如果n個(gè)線性表同時(shí)并存并且在處理過程中各表的長度會動(dòng)態(tài)發(fā)生變化。描述一個(gè)城市的設(shè)計(jì)和規(guī)劃。【解答】順序表的優(yōu)點(diǎn)無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間：可以快速地 存取表中任一位置的元素(即隨機(jī)存取)。順序表的缺點(diǎn)：插入和刪除操作需移動(dòng)大呈元素：表的容 雖:難以確定：造成存儲空間的“碎片角巾鏈表的優(yōu)點(diǎn)：不必事先知道線性表的長度：插入和刪除元素時(shí)只需修改扌&針

12、，不用移動(dòng)元素。瞅 鏈表的缺點(diǎn)：描針的結(jié)構(gòu)性開銷：存取表中任意元素不方便.只能進(jìn)行順序存取。應(yīng)選用順序存儲結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu).單鏈表是順序存取結(jié)構(gòu)。木題很少進(jìn)行插入和刪除 操作.所以空間變化不大，且需要快速存取.所以應(yīng)選用順序存儲結(jié)構(gòu)。應(yīng)選用鏈接存儲結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容雖的擴(kuò)充，適合表的長度動(dòng)態(tài)發(fā)生變化。應(yīng)選用鏈接存儲結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)訃和規(guī)劃涉及活動(dòng)很多.需婆經(jīng)常修改、擴(kuò)充和刪除各種信息. 才能適應(yīng)不斷發(fā)展的需要。而順序表的插入.刪除的效率低.故不合適。5. 算法設(shè)計(jì)設(shè)計(jì)一個(gè)時(shí)間復(fù)朵度為0(n)的算法.實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)右移k個(gè)位宜?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡?/p>

13、一草思想火花。下面給出具體算法。循環(huán)石移算法 Conversevoid Converse (int A , int n, int k)Reverse (A? 0, k-1);Reverse (A, k, n-1),Reverse (A, 0, nT);void Reverse (int A , int from, int to) 鳩數(shù)組 A 中元素從 from 到 to 逆置far (i=0; i若Ai為偶數(shù)并且Aj為奇 數(shù)，則將A|i與Aj交換。具體算法如下：數(shù)紐奇偶調(diào)整算法Adjust |!void Adjust (int A , n)i=0；j=n-l;while (ij)K邂“総whi

14、le (Ai% 2!=0) i+;while (Aj % 2=0) jif (iAj;JI分析算法.兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)朵度為0(n)。試編寫在無頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的總鏈表上的插入操作的實(shí) 現(xiàn)進(jìn)行比較?！窘獯稹繀⒁?23。試分別以順序表和做鏈表作存儲結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆宜的算法。【解答】順序表的逆宜，即是將對稱元素交換設(shè)順序表的長度為length,則將表中第i個(gè)元素與第length-i-1 個(gè)元素相交換。具體算法如下： 頂序表逆置 算法 Reverse template void Reversed data? int length)

15、(for (i=0; i=length/2; i十十)(temp=datai;datai =daialengthTT ; datalength-i-1 =temp;)單鏈表的逆置請參見2.2.4算法2-4和算法26。假設(shè)在長度大干1的循環(huán)鏈表中，即無頭結(jié)點(diǎn)也無頭抬針，s為抬向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算 法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)?！窘獯稹坷脝窝h(huán)鏈表的特點(diǎn)，通過指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p然后將結(jié)點(diǎn)r刪除. 如圖211所示.具體算法如下：循環(huán)鏈表刪除算去Deltemplate void Del (Node *s)p=s；工作指針p初始化I查找s的前躺結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，用p指示wh

16、ile (p-nezt-next!=s)p=p-neKt;r=p-neHt;/x為p的前駆結(jié)點(diǎn)，q為r的前駆結(jié)點(diǎn)p-neKt=s;”刪除r所指結(jié)點(diǎn)delete r;因2-11刪除結(jié)點(diǎn)s的前呃結(jié)點(diǎn)操作示意圉已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表， 使每個(gè)循環(huán)鏈表中貝含同一類字符?！窘獯稹吭趩捂湵鞟中依次取元素，若取出的元素是字俅.把它插入到字母鏈表B中.若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部.這樣表B. D. A中分別存放字母.數(shù)字和其他字符。具體算法如下：單鏈表折分算法Adjust ”template void Adjus

17、t (Node *A, Node *D, Node *B)D=new Node; D-neKt=D;0創(chuàng)淫空循環(huán)鏈表D j存放數(shù)宇B=new Node, B-next=B;刨建空循環(huán)鏈表B j存砂字符p=A; q=p-next;工作指針q初始化while (q)(if (TVyqTdata)&q-data=,Z)| iCa* data) &(q-data=*z,) p-n.eKt=q-ned; q-n.eKt=B-neKt;B-next=q;采用頭插法插在循環(huán)鏈表B的頭結(jié)點(diǎn)的后面else if (lOdata)&(q-data=99)(p-ncxt=q-neKt;q-nezt=D-next;D

18、-next=q;采用頭插法插在循環(huán)璉表D的頭結(jié)點(diǎn)的后面Ielse p=q;q=p-next;)p-next=A; R=A;將鏈表A構(gòu)造為循環(huán)鏈表，為除字母和數(shù)芋的其他字符設(shè)單鏈表以非遞減有序排列，設(shè)訃算法實(shí)現(xiàn)在譏鏈表中刪去值相同的多余結(jié)點(diǎn)?！九列臁繌念^到尾掃描譏鏈表.若訐前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則抬針后移：否則刪除 該后繼結(jié)點(diǎn)。具體算法如下：單鏈蔻刪徐相同值算法Purge _,void Purge (Node * first)：*p=first-next;while (p-next)if (p-data= =p-iLext-data) q=p-nezt;p- next=q-ne

19、Kt,delete q;)else p=p-nezt;判斷帯頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對稱?！窘獯稹吭O(shè)II作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn).若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等, 則工作指針p后移工作指針q前移直到抬針p和指針q指向同一結(jié)點(diǎn)(循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)), 或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)(循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)c如圖212所示。因2-12判斷循環(huán)雙淮表對稱的操作示意圖判斷雙讎表對稱算比Equaltemplate struct Dulblode(T data;DulNode prior, *next;；template bool Eq-ual (DulNode * first

20、)p=first-next; q=first-prior;while (p!=q & p-prior!=q)if (p-data= =q-data)(p=p-neKt;工作指針p后移 q=q-prior;工作指針q前移else return 0;return 1;學(xué)習(xí)自測及答案1. 已知一維數(shù)組A采用順序存儲結(jié)構(gòu).每個(gè)元素占用4個(gè)存儲單元.第9個(gè)元素的地址為144.則第一個(gè) 元素的地址是()。A 108 B 180 C 176 D 112【解答】D2. 在長度為n的線性表中査找值為x的數(shù)據(jù)元素的時(shí)間復(fù)朵度為：()AO(0)BO(l)CO(n)DO(n2)【解答】C3. 在一個(gè)長度為n的順序表的

21、第i (IMsn+l)個(gè)元素之前插入一個(gè)元素.需向后移動(dòng)()個(gè)元素.刪除 第i (li=l &zdatei)datai+l=datai;i+；) datai+l=x,9.已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞増有序.設(shè)汁算法刪除鏈表中所有大于mink且小干maxk的 所有元素.并釋放被刪結(jié)點(diǎn)的存儲空間。【解答】因?yàn)槭窃谟行騿捂湵砩系牟僮?，所?要充分利用其有序性。在單鏈表中査找第一個(gè)大于mink 的結(jié)點(diǎn)和第一個(gè)小于maxk的結(jié)點(diǎn).再將二者間的所有結(jié)點(diǎn)刪除。有序鏈栽珊除算法DeleteB etween template void DeleteB etween (Node * first, int

22、minh, int maKk)p=first;while (p-next & p-next-dataneKt;if (p-nezt) (l=p-neKt;while (q-datanext; p-next=q-n.ext; delete q;q=u;)10.設(shè)單循環(huán)鏈表L1,對其遍歷的結(jié)果是：xlz x2z x3,.z xn-1, xno請將該循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表 L1和L2,使得L1中含有原L1表中序號為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：xl, X3Z. : L2中含有原L1表中序 號為偶數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為，X4,X2：【解答】算法如下：循環(huán)儺表拆分算法DePatch template Nod

23、e ePatch (No de *L1)L2=new Node; L2- next=L2; q=Ll-neKt; Ll-next=Ll; P=Ll;i=l; while (q!=Ll)if (i % 2=1)(應(yīng)用尾插法p-next=q; p=q, p-next=Ll; q=q-next;i+;else L2-nezt=q, u=q-n.ext; q-neKt=L2-neKt; 艸;井4；)第3章特殊線性表?xiàng)?、?duì)列和串課后習(xí)題講解1 填空 設(shè)有一個(gè)空棧棧頂抬針為1000H,現(xiàn)有輸入序列為1、2、3、4、5,經(jīng)過push, push. pop. push, pop, push, push后，輸出

24、序列是（），棧頂指針為（）。【解答】23, 1003H棧通常采用的兩種存儲結(jié)構(gòu)是（）：其判定棧空的條件分別是（），判定棧滿的條件分別是（）?！窘獯稹宽樞虼鎯Y(jié)構(gòu)和鏈接存儲結(jié)構(gòu)（或順序棧和鏈棧）棧頂指針top= -1和top二NULL,棧頂指針 top等于數(shù)組的長度和內(nèi)存無可用空間（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）?！窘獯稹縜bc+*d-【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個(gè)操作數(shù) 的后面。棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（）隊(duì)列的

25、操作特性是（）棧和隊(duì)列的主要區(qū)別 在于（?！窘獯稹亢筮M(jìn)先出.先進(jìn)先出，對插入和刪除操作限定的位宜不同循環(huán)臥列的引入是為了克服（）O【解答】假溢出數(shù)組Qn用來表示一個(gè)循環(huán)隊(duì)列,front為隊(duì)頭元素的前一個(gè)位rear為隊(duì)尾元素的位宜.訃算隊(duì)列 中元素個(gè)數(shù)的公式為（）。【解答】（rear-front+n） % n【分析】也可以是（rearfront） %n但rear-front的結(jié)果可能是負(fù)整數(shù).而對一個(gè)負(fù)整數(shù)求模.其結(jié)果 在不同的編譯器環(huán)境下可能會有所不同。用循環(huán)鏈表表示的隊(duì)列長度為n,若只設(shè)頭抬針.則出隊(duì)和入隊(duì)的時(shí)間復(fù)朵度分別是（）和（）。【解答】0（1）, 0（n）【分析】在帶頭抬針的循環(huán)鏈表

26、中，出隊(duì)即是刪除開始結(jié)點(diǎn)，這只需修改相應(yīng)指針：入隊(duì)即是在終端結(jié)點(diǎn) 的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭抬針開始査找終端結(jié)點(diǎn)的地址。串是一種特殊的線性表.其持殊性體現(xiàn)在（）。【解答】數(shù)據(jù)元素的類型是一個(gè)字符00）兩個(gè)串相等的充分必要條件是（）。【解答】長度相同且對應(yīng)位宜的字符相等【分析】例如七bcfabcS ,abc,*,bca,e2. 選擇題若一個(gè)棧的輸入序列是2, 3，n,輸出序列的第一個(gè)元素是m則第i個(gè)輸出元素是（）。A 不確定 BniCn+l Dn-i+1【解答】D【分析】此時(shí).輸出序列一定是輸入序列的逆序。設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el. e2、e3、e4、eS. e6依次通過棧S.

27、 個(gè)元素出棧后即進(jìn) 入隊(duì)列Q,若6個(gè)元素出隊(duì)的順序是e2. e4、e3、e6、e5、el,則棧S的容址至少應(yīng)該是（）。A6B4C3D2【解答】C【分析】由于隊(duì)列具有先進(jìn)先出性.所以，此題中從列形同虛設(shè).即出棧的順序也是e2、e4、e3. e6、e5.elo一個(gè)棧的入棧序列是2, 3. 4. 5,則棧的不可能的輸出序列是（）。A 54321 B45321 C 43512 D 12345【解答】C【分析】此題有一個(gè)技巧：在輸出序列中任意元素后而不能出現(xiàn)比該元素小并且是升序（指的是元素的序 號）的兩個(gè)元素。設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號是否配對的算法采用（）數(shù)據(jù)結(jié)構(gòu)最佳A順序表B棧C隊(duì)列D鏈表【解答】

28、B【分析】每個(gè)右括號與它前面的最后一個(gè)沒有匹配的左括號配對因此具有后進(jìn)先出性。在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)宜一個(gè)打印緩沖區(qū).該緩沖區(qū)應(yīng)該是一個(gè)（） 結(jié)構(gòu)。A棧B隊(duì)列C數(shù)組D線性表【解答】B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印.因此具有先進(jìn)先出性一個(gè)臥列的入隊(duì)順序是1，2, 3, 4,則隊(duì)列的輸出順序是（）。A 4321 B 1234 C 1432 D 3241【解答】B【分析】從列的入隊(duì)順序和出隊(duì)順序總是一致的。棧和隊(duì)列的主要區(qū)別在于（）。A它們的邏輯結(jié)構(gòu)不一樣B它們的存儲結(jié)構(gòu)不一樣C所包含的運(yùn)算不一樣D插入.刪除運(yùn)算的限定不一樣【解答】D【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是

29、線性的，都有順序存儲和鏈接存儲，有可能包含的運(yùn)算不一樣.但不是 主要區(qū)別任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時(shí)包含的運(yùn)算都可能不同。設(shè)數(shù)組Sn作為兩個(gè)棧S1和S2的存儲空間，對任何一個(gè)棧只有為Sn全滿時(shí)才不能進(jìn)行進(jìn)棧操作。 為這兩個(gè)棧分配空間的最佳方案是（）。A S1的棧底位迓為0S2的棧底位宜為n-1B S1的棧底位置為0S2的棧底位宜為n/2c S1的棧底位迓為0. S2的棧底位宜為nD S1的棧底位置為0. S2的棧底位匱為1【解答】A【分析】兩棧共享空間首先兩個(gè)棧是相向増長的.棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位宜，并注 總C+中的數(shù)組下標(biāo)是從0開始的。設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的

30、位宜的運(yùn)算稱作（）。A連接B模式匹配C求子串D求串長【解答】B3. 判斷題有n個(gè)元素依次進(jìn)棧.則出棧序列有(n-l)/2種。(2n)!【解答】錯(cuò)。應(yīng)該有 + 1)創(chuàng))種。?？梢宰鳛閷?shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【解答】對。只要操作滿足后進(jìn)先岀性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。在棧滿的情況下不能做進(jìn)棧操作.否則將產(chǎn)生上溢?！窘獯稹繉?。在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位reartR向隊(duì)尾元素的位宜.則隊(duì)滿的條件是front 二 rear?！窘獯稹垮e(cuò)。這是隊(duì)空的判定條件.在循環(huán)隊(duì)列中要將從空和隊(duì)滿的判定條件區(qū)別開。空串與空格串是相同的。【解答】錯(cuò)。空串的長度為零，而空格串的長度不為0.其長

31、度是串中空格的個(gè)數(shù)。4. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳B, C. D, E,能否得到如下出棧序列，若能，請寫出操作序列.若 不能.請說明原因。 C, E A, B. D C, B, A. D. E【解答】(1)不能，因?yàn)樵赨 E出棧的情況下，A定在棧中.而且在B的下面.不可能先于B出棧。 可以.設(shè)I為進(jìn)棧操作.0為入棧操作，則其操作序列為IIIOOOIOIOo5舉例說明順序隊(duì)列的假溢出現(xiàn)紀(jì)【解答】假設(shè)有一個(gè)順序隊(duì)列.如圖3-6所示隊(duì)尾指針rear=4,隊(duì)頭指針front=l,如果再有元素入隊(duì), 就會產(chǎn)生上溢，此時(shí)的上溢又稱為“假溢出I大I為隊(duì)列并不是真的溢出了.存儲隊(duì)列的數(shù)組中還有2個(gè) 存儲

32、譏元空閑，其下標(biāo)分別為0和1。rearfront甸3-66.在操作序列push(l)、push(2). pop、push(5)、push(7). pop、push(6)之后棧頂元素和棧底元素分 別是什么？(push(k)表示整數(shù)k入棧.pop表示棧頂元素出棧。)【解答】棧頂元素為&棧底元素為1。其執(zhí)行過程如圖3-7所示。(a) push(l) 9 push(2)(b) pop j pushO) j push (7)(a) pop push (6)EJ3-7棧的執(zhí)行過程示意肉DeQueue表示隊(duì)頭元素出隊(duì))。7.在操作序列 EnQueue(l)x EnQueue(3) DeQueue、EnQue

33、ue(5)、EnQueue(7)、DeQueue. EnQueue(9) 之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？(EnQueue(k)表示整數(shù)k入隊(duì).【解答】隊(duì)頭元素為5.隊(duì)尾元素為9。其執(zhí)行過程如圖38所示。35757 9(a) EnQueue (1) /EnQueue C3)(b) DeQueue jEnQueue (5) jEnQueue (?)(c) DeQueue “EiiQueue (9)S3-S隊(duì)列的執(zhí)行過程示意因8.空串和空格串有何區(qū)別？串中的空格符有何總義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串.其長度為零。僅含空格的串稱為空格串.它的長度為串中空格符的 個(gè)數(shù)

34、。串中的空格符可用來分隔一般的字符.便于人們識別和閱讀，但計(jì)算串長時(shí)應(yīng)包括這些空格符?？?串在串處理中可作為任總串的子串。9.算法設(shè)計(jì)假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針扌旨向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭抬針C試設(shè)汁相應(yīng) 的入隊(duì)和出隊(duì)的算法?！窘獯稹砍鲫?duì)操作是在循環(huán)鏈表的頭部進(jìn)行.相、|于刪除開始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部進(jìn)行. 相十于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn).需要處理空表的特殊情況。入隊(duì)算法如下:循環(huán)隊(duì)列1入 隊(duì)算法 Enqueue |templateclass Tvoid Enqueue(Node 幷ear, T 叨s=new Node;s-data

35、=x;if (rear= =NULL) 處理空表的特殊情況rear=s;rear-next=s;)els e (處理除空表以外的一般惰況s-n.eKt=rear- next; rear-ne2d=s, rear;)出隊(duì)算法如下：循環(huán)隊(duì)列|出乩算法Dequeue |template T Dequeue (Node 牛ear)(if (rear= =NULL) throw underflow; else s=rear-next,if (s=rear) rear=NULL; else rear-next=s-next;delete s;)修！1斷表空鏈表中只有一個(gè)結(jié)點(diǎn)設(shè)順序棧S中有2n個(gè)元素，從棧頂

36、到棧底的元素依次為a2n, a2n-lal要求通過一個(gè)循環(huán)隊(duì)列 重新排列棧中元素.使得從棧頂?shù)綏５椎脑匾来螢閍2n, a2n-2a2, a2n-b a2n-3，al.請?jiān)O(shè) 計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n)【解答】操作步驟為： 將所有元素出棧并入隊(duì)： 依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn).則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，則入棧： 將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)： 將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧： 將所有元素出棧并入隊(duì)： 將所有元素出隊(duì)并入棧即為所求。用順序存儲結(jié)構(gòu)存儲串S,編寫算法刪除S中第i個(gè)字符開始的連續(xù)j個(gè)字符?！窘獯稹肯扰袛啻甋中要?jiǎng)h除的內(nèi)容是否存在.若存在則將第i+j-1之后的字符前移j

37、個(gè)位宜。算法如下:串冊除算法Del Lvoid Del (char S,int i, intj)燉蛆0號單元存放串的長度if G+jSOJ)for (k=i; k0;i)if (Si=ch) for(HH;jW0;j+) sj-i=su;S0;對串的模式匹配KMP算法設(shè)il求模式滑動(dòng)位宜的next函數(shù)?！窘獯稹繀⒁?.2.5學(xué)習(xí)自測及答案1. 在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底.以top作為棧頂抬 針，當(dāng)出棧時(shí).top的變化為（）。A 不變 B top=0; C top=top-l; D top=top+l;【解答】C2. 一個(gè)棧的入棧序列是a, b, c

38、r d, e,則棧的不可能的岀棧序列是（）。A edeba B cdeba C debca D abede【解答】C3. 從棧頂抬針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)用x保存被刪除結(jié)點(diǎn)的值.則執(zhí)行（）。A x=top; top=top-next; B x=top-data;C top=top-next; x=top-data; D x=top-data; top=top-Anext;【解答】D4. 設(shè)元素1, 2f 3, P, A依次經(jīng)過一個(gè)棧，進(jìn)棧次序?yàn)?23PA.在棧的輸出序列中.有哪些序列可作為C+ 程序設(shè)計(jì)語言的變雖名?！窘獯稹縋A321, P3A21, P32A1, P321A, AP32

39、15設(shè) SI_am_a_teacther，其長度為()?！窘獯稹?5第4章廣義線性表多維數(shù)組和廣義表課后習(xí)題講解1 填空數(shù)組通常只有兩種運(yùn)算 ()和()，這決定了數(shù)組通常采用()結(jié)構(gòu)來實(shí)現(xiàn)存儲。【解答】存取.修改，順序存儲【分析】數(shù)組是一個(gè)具有固定格式和數(shù)址的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作C除了 初始化和銷毀之外.在數(shù)組中通常只有存取和修改兩種操作。二維數(shù)組A中行下標(biāo)從10到20,列下標(biāo)從5到10,按行優(yōu)先存儲，每個(gè)元素占4個(gè)存儲單元,A10 的存儲地址是1000,則元素A1510的存儲地址是()?！窘獯稹?140【分析】數(shù)組A中每行共有6個(gè)元素元素A1510的前面共存儲61

40、0)x6+5個(gè)元素,每個(gè)元素占4 個(gè)存儲爪元，所以，其存儲地址是1000+140=1140.設(shè)有一個(gè)10階的對稱矩陣A采用圧縮存儲，A00為第一個(gè)元素，其存儲地址為d每個(gè)元素占1個(gè) 存儲單元,則元素A85的存儲地址為()。【解答】d+41【分析】元素A8的前面共存儲了(1+2+8)+5=41個(gè)元素。稀竦矩陣一般壓縮存儲方法有兩種，分別是()和()?！窘獯稹咳M順序表十字鏈表廣義表(a). (b)zc)z(d)的長度是()深度是()表頭是( 幾表尾是()?！窘獯稹?, 4. (a). (b),c),(d) 已知廣義表LS=(a, (b. c. d)e)用Head和Tail函數(shù)取出LS中原子b的

41、運(yùn)算是()?！窘獯稹縃ead(Head(Tall(LS)2. 選擇題二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范鬧從0&列下標(biāo)的范用是從09,則存 放A至少需要()個(gè)字節(jié)，A的第8列和第5行共占()個(gè)字節(jié).若A按行優(yōu)先方式存儲，元素A85的起始地址與當(dāng)A按列優(yōu)先;方式存儲時(shí)的()元素的起始地址一致cA90 B 180 C 240 D 540 E 108 F 114 G 54H A85 I A10 J A58 K A49【解答】D. E, K【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以存放A至少需耍90x6=540個(gè)存儲収元，第8列 和第5行共有18個(gè)元素(注總:行列有一個(gè)交叉元素)

42、，所以.共占108個(gè)字節(jié).元素A85按行優(yōu)先存 儲的起始地址為d+8xlo+5二d+85.設(shè)元素Aij按列優(yōu)先存儲的起始地址與之相同.則d+jx9+i=d+85 解此方程.得1=4, j=9o 將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)?)A數(shù)組元素是隨機(jī)的B對數(shù)組任一元素的存取時(shí)間是相等的C隨時(shí)可以對數(shù)組進(jìn)行訪問D數(shù)組的存儲結(jié)構(gòu)是不定【解答】B 下面的說法中.不正確的是()A數(shù)組是一種線性結(jié)構(gòu)B數(shù)組是一種定長的線性結(jié)構(gòu)C除J插入與刪除操作外.數(shù)組的基木操作還有存収、修改、檢索和排序等D數(shù)組的基木操作有存取.修改.檢索和排序等，沒有插入與刪除操【解答】C【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每

43、維中的元素個(gè)數(shù)是確定的.所以，數(shù)組通常 沒有插入和刪除操作對特殊矩陣采用壓縮存儲的目的主要是為r()A表達(dá)變得簡収B對矩陣元素的存取變得簡單C去掉矩陣中的女氽元素D減少不必婆的存儲空間【解答】D【分析】在特殊矩陣中.有很多值相同的元素并且他們的分布有規(guī)律.沒有必要為值相同的元素重復(fù)存儲。下面(不屬于特殊矩陣。A對角矩陣B三角矩陣C稀姣矩陣D對稱矩陣【解答】C若廣義表A滿足Head(A)=Tail(A),則人為()A()B( )C( ),() D(),(),()【解答】B下面的說法中，不正確的是()A廣義表是一種多層次的結(jié)構(gòu)B廣義表是一種非線性結(jié)構(gòu)C廣義表是一種共享結(jié)構(gòu)D廣義表是一種遞歸【解答】

44、B【分析】從補(bǔ)層元素體自具有的線性關(guān)系講.廣義表屬于線性結(jié)構(gòu)C下而的說法中，不正確的是()A對稱矩陣只須存放包括主對角線元素在內(nèi)的下(或上)三角的元素即可。B對角矩陣只須存放非零元素即可。C稀疏矩陣中值為零的元素較零，因此可以采用三元組表方法存儲。D稀統(tǒng)矩陣中大址值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大雖值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律. 就沒有必要存儲非零元素的行號和列號，而需要按其斥縮規(guī)律找出相應(yīng)的映盤函數(shù)。3. 判斷題數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的?！窘獯稹垮e(cuò)。例如二維

45、數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。使用三元組表存儲稀姣矩陣的元素.有時(shí)并不能節(jié)省存儲空間。【解答】對。因?yàn)槿M表除了存儲非零元素值外，還需要存儲其行號和列號。稀姣矩陣壓縮存儲后，必會失去隨機(jī)存取功能?！窘獯稹繉?。因?yàn)閴嚎s存儲后，非零元素的存儲位宜和行號.列號之間失去了確定的關(guān)系。線性表可以看成是廣義表的特例.如果廣義表中的每個(gè)元素都是取元素.則廣義表便成為線性表?！窘獯稹繉?。若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e(cuò)。如廣義表L=(), (a, b)的表頭為空表，但L不是空表。4. 一個(gè)稀疏矩陣如圖牛4所示.寫出對應(yīng)的三元組順序表和十字鏈表存儲表示。300 000-150

46、00 0【解答】對應(yīng)的三元組順序表如圖45所示，十字鏈表如圖46所示。下標(biāo)行號列號非客元素13221333-13454數(shù)）41列數(shù))4(非零無個(gè)數(shù))E14-5稀疏矩陣的三元爼順序表5. 已知A為稀疏矩陣.試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成 求運(yùn)算的優(yōu)缺點(diǎn)?！窘獯稹吭O(shè)稀疏矩陣為m行門列如果采用二維數(shù)組存儲.其空間復(fù)雜度為0(mxn)： M為要將所有的矩 陣元素累加起來，所以.需要用一個(gè)兩層的嵌套循環(huán).其時(shí)間復(fù)雜度亦為0(mxn)o如果采用三元組順序 表進(jìn)行樂縮存儲，假設(shè)矩陣中有t個(gè)非零元素.其空間復(fù)雜度為0(t),將所有的矩陣元素累加起來只需將 三元組順序表掃

47、描一遍，其時(shí)間復(fù)朵度亦為0(t)o為tvv mxn時(shí)，采用三元組順序表存儲可獲得較好的 時(shí)、空性能。&設(shè)某樂位職匚工資表ST由工資扣除和實(shí)發(fā)金額三項(xiàng)組成.其中匸資項(xiàng)包括基木工資、津貼 和獎(jiǎng)金，扣除項(xiàng)包括水電和煤氣o請用廣義表形式表示所描述的匸資表ST并用表頭和表尾求表中的獎(jiǎng)金項(xiàng)：畫出該工資表ST的存儲結(jié)構(gòu)。【解答】ST=(基木匸資，津貼，獎(jiǎng)金)，(水.電，煤氣)，實(shí)發(fā)金額)Head(Tail(Tail(Head(ST)=獎(jiǎng)金 工資表ST的頭尾表示法如圖47所示。閣4-7工資表的存儲示意H7.若在矩陣A中存在一個(gè)元素aizj (0in-l. 0勻三m-1)，該元素是第i行元素中垠小值且又是第j列

48、元 素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲矩陣A,試設(shè)汁一個(gè)求該矩陣所有 馬鞍點(diǎn)的算法并分析垠壞情況下的時(shí)間復(fù)朵度?！窘獯稹吭诰仃囍兄鹦修姓以撔兄械嫩笮≈?，然后對其所在的列尋找最大值，如果該列上的垠大值與該行 上的最小值相等，則說明該元素是鞍點(diǎn)，將它所在行號和列號輸出。具體算法如下: 馬鞍點(diǎn)算法Andian |void. Andian(mt a ,int m,mt n)(for (i=0; in; i十十) d=ai0;k=0,d為第i行中的攝小值far (j=l; jcm; j十十)if (aiDd) d=aiU3； k=j；Waik為第i行攝小值far (j=0; jd) break;if (j=n) cout*輸出鞍aik; )分析算法.外層for循環(huán)共執(zhí)行n次.內(nèi)層第一個(gè)for循環(huán)執(zhí)行m次.第二個(gè)for循環(huán)最壞悄況下執(zhí)行n 次，所以，最壞情況下的時(shí)間復(fù)雜度為0(mn+n2)o學(xué)習(xí)自測及答案(沒看)1. 二維數(shù)組M中每個(gè)元素的長度是3個(gè)字節(jié)，行下標(biāo)從0到幾列下標(biāo)從0到9.從首地址d開始存儲。若按行優(yōu)先方式存儲.元素M75的起始地址為()若按列優(yōu)先方式存儲，元素M75的起始地址為()。【解答】d+22, d+1412. 一個(gè)