數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案

大發(fā)光火

習(xí)題1

一、單項(xiàng)選擇題

A1.數(shù)據(jù)結(jié)構(gòu)是指（）。

A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類型C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)定義

C2.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與規(guī)律地址不一致的，稱之為（）。

A.存儲(chǔ)結(jié)構(gòu)B.規(guī)律結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)D3.樹(shù)形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（）。

A.一對(duì)一關(guān)系B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系D.一對(duì)多關(guān)系

B4.設(shè)語(yǔ)句x++的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間繁雜度為（）。

for(i=1;i=n;i++)for(j=i;j=n;j++)x++;

A.O(1)

B.O(n)

2

C.O(n)

D.O(n)

3

CA5.算法分析的目的是（1），算法分析的兩個(gè)主要方面是（2）。

（1）A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出關(guān)系

C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性（2）A.空間繁雜度和時(shí)間繁雜度B.正確性和簡(jiǎn)明性

C.可讀性和文檔性D.數(shù)據(jù)繁雜性和程序繁雜性6.計(jì)算機(jī)算法指的是（1），它具備輸入，輸出和（2）等五個(gè)特性。（1）A.計(jì)算方法B.排序方法

C.解決問(wèn)題的有限運(yùn)算序列D.調(diào)度方法

（2）A.可行性，可移植性和可擴(kuò)展性B.可行性，確定性和有窮性

C.確定性，有窮性和穩(wěn)定性D.易讀性，穩(wěn)定性和安全性

7.數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（）。

A.低B.高C.一致D.不好說(shuō)8.數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程出現(xiàn)是在（）年。

A.1946B.1953C.1964D.19689.數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的規(guī)律結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)（）。

A.正確B.錯(cuò)誤

C.前半句對(duì)，后半句錯(cuò)D.前半句錯(cuò)，后半句對(duì)

大發(fā)光火

10.計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（）。

A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)二、填空題

D.數(shù)據(jù)庫(kù)

1.數(shù)據(jù)結(jié)構(gòu)按規(guī)律結(jié)構(gòu)可分為兩大類，分別是______________和_________________。2.數(shù)據(jù)的規(guī)律結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。

3.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的規(guī)律關(guān)系是__________________的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的規(guī)律關(guān)系是__________________的。

4.一個(gè)算法的效率可分為_(kāi)_________________效率和__________________效率。5.在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有__________________結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有__________________個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有__________________結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以__________________。

6.在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以__________________。7.線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹(shù)型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。

8.下面程序段的時(shí)間繁雜度是__________________。

for(i=0;in;i++)for(j=0;jn;j++)

A[i][j]=0;

9.下面程序段的時(shí)間繁雜度是__________________。

i=s=0;while(sn){i++;s+=i;}

10.下面程序段的時(shí)間繁雜度是__________________。

s=0;

for(i=0;in;i++)for(j=0;jn;j++)s+=B[i][j];sum=s;

11.下面程序段的時(shí)間繁雜度是__________________。

i=1;while(i=n)i=i*3;

12.衡量算法正確性的標(biāo)準(zhǔn)尋常是____________________________________。13.算法時(shí)間繁雜度的分析尋常有兩種方法，即___________和___________的方法，尋常我們對(duì)算法求時(shí)間繁雜度時(shí)，采用后一種方法。

大發(fā)光火

三、求以下程序段的時(shí)間繁雜度。

1.x=0;

for(i=1;in;i++)for(j=i+1;j=n;j++)x++;

2.x=0;

for(i=1;in;i++)for(j=1;j=n-i;j++)x++;

3.inti,j,k;

for(i=0;in;i++)for(j=0;j=n;j++){c[i][j]=0;

for(k=0;kn;k++)

c[i][j]=a[i][k]*b[k][j]

}

4.i=n-1;

while((i=0)A[i]!=k))j--;return(i);

5.fact(n)

{if(n=1)

return(1);

else

return(n*fact(n-1));

}

習(xí)題1參考答案

一、單項(xiàng)選擇題

1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B二、填空題

1.線性結(jié)構(gòu)，非線性結(jié)構(gòu)2.集合，線性，樹(shù)，圖3.一對(duì)一，一對(duì)多或多對(duì)多4.時(shí)間，空間

10.B

大發(fā)光火

5.前趨，一，后繼，多6.有多個(gè)

7.一對(duì)一，一對(duì)多，多對(duì)多8.O(n2

)9.O(n)10.O(n2

)11.O(log3n)

12.程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13.事后統(tǒng)計(jì)，事前估計(jì)三、算法設(shè)計(jì)題

1.O(n2

)2.O(n2

)3.O(n3

)4.O(n)5.O(n)

大發(fā)光火

習(xí)題2

一、單項(xiàng)選擇題

1.線性表是________。

A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不可以為空C．一個(gè)無(wú)限序列，可以為空D．一個(gè)無(wú)限序列，不可以為空

2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0=i=n)時(shí)，需向前移動(dòng)A．n-iB．n-i+lC．n-i-1D．i3.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址________。

A．必需是連續(xù)的B．一定是不連續(xù)的C．部分地址必需是連續(xù)的D．連續(xù)與否均可以

4.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的狀況下，需平均比較________個(gè)元素結(jié)點(diǎn)。

A．n/2B．nC．（n+1）/2D．（n-1）/2

5.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。

A．p-next=s;s-prior=p;

p-next-prior=s;s-next=p-next;B．s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;C．p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;D．s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;

6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為_(kāi)_______。

A．p-next=p-next-next;B．p=p-next;C．p=p-next-next;D．p-next=p;

7.在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0in+l)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)______個(gè)元素。

A．n-iB．n-i+lC．n-i-1D．i

8.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行

A．s-next=p-next;p-next=sB．q-next=s;s-next=p

C．p-next=s-next;s-next=p

大發(fā)光火

D．p-next=s;s-next=q

9.以下關(guān)于線性表的說(shuō)法不正確的是______。

A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B．線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。

C．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D．存在這樣的線性表：表中各結(jié)點(diǎn)都沒(méi)有直接前趨和直接后繼。10.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_______的存儲(chǔ)結(jié)構(gòu)。

A．隨機(jī)存取B．順序存取C．索引存取D．散列存取

11.在順序表中，只要知道_______，就可在一致時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A．基地址B．結(jié)點(diǎn)大小C．向量大小D．基地址和結(jié)點(diǎn)大小

12.在等概率狀況下，順序表的插入操作要移動(dòng)______結(jié)點(diǎn)。A．全部B．一半C．三分之一D．四分之一13.在______運(yùn)算中，使用順序表比鏈表好。A．插入B．刪除

C．根據(jù)序號(hào)查找D．根據(jù)元素值查找

14.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間繁雜度是_______。

A．O(1)B．O(n)

2

C．O(n)D．O(log2n)

15.設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,以下是不可能的出棧序列__________。

A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A

16.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為_(kāi)_____。

A．top不變B．top=0C．top--D．top++17.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。A．hs-next=s;B．s-next=hs;hs=s;

C．s-next=hs-next;hs-next=s;D．s-next=hs;hs=hs-next;

18.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為_(kāi)_______。

A．rear％n==frontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)

大發(fā)光火

尾指針，則判斷隊(duì)空的條件為_(kāi)_______。

A．rear％n==frontB．front+l=rear

C．rear==frontD．(rear+l)％n=front

20.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為_(kāi)_______。

A．front=front-nextB．rear=rear-nextC．rear=front-nextD．front=rear-next二、填空題

1.線性表是一種典型的_________結(jié)構(gòu)。

2.在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移____個(gè)元素。3.順序表中規(guī)律上相鄰的元素的物理位置________。

4.要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_______一個(gè)位置，移動(dòng)過(guò)程是從_______向_______依次移動(dòng)每一個(gè)元素。

5.在線性表的順序存儲(chǔ)中，元素之間的規(guī)律關(guān)系是通過(guò)_______決定的；在線性表的鏈接存儲(chǔ)中，元素之間的規(guī)律關(guān)系是通過(guò)_______決定的。

6.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。

7.當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_______存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用_______存儲(chǔ)結(jié)構(gòu)為宜。

8.順序表中規(guī)律上相鄰的元素，物理位置_______相鄰，單鏈表中規(guī)律上相鄰的元素，物理位置_______相鄰。

9.線性表、棧和隊(duì)列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對(duì)于棧只能在_______位置插入和刪除元素；對(duì)于隊(duì)列只能在_______位置插入元素和在_______位置刪除元素。

10.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_(kāi)________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為_(kāi)_______和_________。

11.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。

12.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間繁雜度為_(kāi)_____，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間繁雜度為_(kāi)______。

13.對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_(kāi)______，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_(kāi)______，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明棧的可用最大容量為_(kāi)______。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時(shí)才產(chǎn)生上溢。

14.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過(guò)push,push,pop,push,pop,push,push后，輸出序列是_________。

15.無(wú)論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間繁雜度均一致為_(kāi)_________。

大發(fā)光火

三、簡(jiǎn)答題

1.描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。2.線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？

3.對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，假使有n個(gè)線性表同時(shí)并存，而且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)改變，在此狀況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？

4.對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說(shuō)明理由。

5.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?

6.假定有四個(gè)元素A,B,C,D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫(xiě)出所有可能的出棧序列。

7.什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。8.下述算法的功能是什么?

LinkList*Demo(LinkList*L){//L是無(wú)頭結(jié)點(diǎn)的單鏈表LinkList*q,*p;if(LL-next){q=L;L=L-next;p=L;while(p-next)

p=p-next;

p-next=q;q-next=NULL;}return(L);}

四、算法設(shè)計(jì)題

1.設(shè)計(jì)在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法。2.在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength(L)運(yùn)算。3.設(shè)計(jì)將帶表頭的鏈表逆置算法。

4.假設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來(lái)，試編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)依照其值從小到大的順序鏈接起來(lái)。

5.已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫(xiě)一個(gè)刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。

6.已知線性表的元素是無(wú)序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)一個(gè)刪除表中所有值小于max但大于min的元素的算法。

7.假定用一個(gè)單循環(huán)鏈表來(lái)表示隊(duì)列（也稱為循環(huán)隊(duì)列），該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，

大發(fā)光火

不設(shè)隊(duì)首指針，試編寫(xiě)以下各種運(yùn)算的算法：

（1）向循環(huán)鏈隊(duì)列插入一個(gè)元素值為x的結(jié)點(diǎn)；（2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。

8.設(shè)順序表L是一個(gè)遞減有序表，試寫(xiě)一算法，將x插入其后仍保持L的有序性。

習(xí)題2參考答案

一、單項(xiàng)選擇題

1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C20．A二、填空題

1．線性2．n-i+13．相鄰4．前移，前，后

5．物理存儲(chǔ)位置，鏈域的指針值6．前趨，后繼

7．順序，鏈接8．一定，不一定

9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭

10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)

13．棧滿，?？眨琺，棧底，兩個(gè)棧的棧頂在棧空間的某一位置相遇14．2、315．O(1)三、簡(jiǎn)答題

1．頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。

2．線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，便利靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分派，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)便利，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。

3．應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，由于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的

大發(fā)光火

刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很簡(jiǎn)單實(shí)現(xiàn)表的容量的擴(kuò)展。

4．應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，由于每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。

5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很便利，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear-next-next和rear,查找時(shí)間都是O(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。

6．共有14種可能的出棧序列，即為：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA

7．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。當(dāng)有元素要參與隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素參與隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出〞現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。

一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：

（1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。

（2）要避免出現(xiàn)“假溢出〞現(xiàn)象可用以下方法解決：

第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。其次種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。

第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出〞的原則。

8．該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的其次個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題

1．算法思想為：

（1）應(yīng)判斷刪除位置的合法性，當(dāng)i0或in-1時(shí)，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：

（3）當(dāng)０in時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：

delete(LinkList*q,inti)

{//在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)

大發(fā)光火

LinkList*p,*s;intj;if(i0)

printf(Can'tdelete);elseif(i==0){s=q;q=q-next;free(s);}

else

{j=0;s=q;

while((ji)(s!=NULL)){p=s;s=s-next;

j++;}

if(s==NULL)

printf(Cant'tdelete);

else

{p-next=s-next;free(s);}}}

2．由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來(lái)數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：

intListLength(LinkList*L){//求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng)intlen=0;ListList*p;p=L;

while(p-next!=NULL){p=p-next;len++;}

return(len);}

3．設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域

大發(fā)光火

{rear=p;

rear-next=p;//鏈接成循環(huán)鏈表}

else//否則在隊(duì)尾插入p結(jié)點(diǎn){p-next=rear-next;

rear-next=p;rear=p;}}

（2）刪除（即出隊(duì)）算法：

delete(LinkList*rear)

{//設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif(rear==NULL)//空隊(duì)printf(underflow\n);

if(rear-next==rear)//隊(duì)中只有一個(gè)結(jié)點(diǎn)rear=NULL;else

rear-next=rear-next-next;//rear-next指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)}

8．只要從終端結(jié)點(diǎn)開(kāi)始往前找到第一個(gè)比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法描述如下：

intInsertDecreaseList(SqList*L,elemtypex){inti;

if((*L).len=maxlen){printf(“overflow);return(0);}

for(i=(*L).len;i0(*L).elem[i-1]x;i--)(*L).elem[i]=(*L).elem[i-1];//比較并移動(dòng)元素(*L).elem[i]=x;(*L).len++;return(1);}

大發(fā)光火

習(xí)題3

一、單項(xiàng)選擇題

1.空串與空格字符組成的串的區(qū)別在于（）。

A.沒(méi)有區(qū)別B.兩串的長(zhǎng)度不相等C.兩串的長(zhǎng)度相等D.兩串包含的字符不一致2.一個(gè)子串在包含它的主串中的位置是指（）。

A.子串的最終那個(gè)字符在主串中的位置

B.子串的最終那個(gè)字符在主串中首次出現(xiàn)的位置C.子串的第一個(gè)字符在主串中的位置

D.子串的第一個(gè)字符在主串中首次出現(xiàn)的位置3.下面的說(shuō)法中，只有（）是正確的。

A.字符串的長(zhǎng)度是指串中包含的字母的個(gè)數(shù)B.字符串的長(zhǎng)度是指串中包含的不同字符的個(gè)數(shù)C.若T包含在S中，則T一定是S的一個(gè)子串D.一個(gè)字符串不能說(shuō)是其自身的一個(gè)子串4.兩個(gè)字符串相等的條件是（）。

A.兩串的長(zhǎng)度相等B.兩串包含的字符一致

C.兩串的長(zhǎng)度相等，并且兩串包含的字符一致D.兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符一致

5.若SUBSTR（S，i，k）表示求S中從第i個(gè)字符開(kāi)始的連續(xù)k個(gè)字符組成的子串的操作，則對(duì)于S=“Beijing＆Nanjing〞，SUBSTR（S，4，5）=（）。

A.“ijing〞B.“jing＆〞C.“ingNa〞D.“ing＆N〞

6.若INDEX（S，T）表示求T在S中的位置的操作，則對(duì)于S=“Beijing＆Nanjing〞，T=“jing〞，INDEX（S，T）=（）。

A.2B.3C.4D.5

7.若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對(duì)于S=“Beijing＆Nanjing〞，S1=“Beijing〞，S2=“Shanghai〞，REPLACE（S，S1，S2）=（）。

A.“Nanjing＆Shanghai〞B.“Nanjing＆Nanjing〞C.“ShanghaiNanjing〞D.“Shanghai＆Nanjing〞8.在長(zhǎng)度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)當(dāng)是（）。

A.i＞0B.i≤n

大發(fā)光火

C.1≤i≤nD.1≤i≤n+1

9.字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（）。

A.鏈表的長(zhǎng)度為1

B.鏈表中只存放1個(gè)字符C.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不僅只存放了一個(gè)字符D.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符二、填空題

1.計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的方法：一種是___________，其次種是___________________。

2.兩個(gè)字符串相等的充要條件是_____________________和___________________。3.設(shè)字符串S1=“ABCDEF〞，S2=“PQRS〞，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為_(kāi)__________________。

4.串是指___________________。

5.空串是指___________________，空格串是指___________________。三、算法設(shè)計(jì)題

1.設(shè)有一個(gè)長(zhǎng)度為s的字符串，其字符順序存放在一個(gè)一維數(shù)組的第1至第s個(gè)單元中（每個(gè)單元存放一個(gè)字符）?，F(xiàn)要求此后串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串，ms，t(s-m)，并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計(jì)此刪除算法。2.設(shè)s和t是表示成單鏈表的兩個(gè)串，試編寫(xiě)一個(gè)找出s中第1個(gè)不在t中出現(xiàn)的字符（假定每個(gè)結(jié)點(diǎn)只存放1個(gè)字符）的算法。

習(xí)題3參考答案

一、單項(xiàng)選擇題1．B

2．D

3．C

4．D

5．B

6．C

7．D

8．C

9．D

二、填空題

1.固定長(zhǎng)度，設(shè)置長(zhǎng)度指針

2.兩個(gè)串的長(zhǎng)度相等，對(duì)應(yīng)位置的字符相等3.“BCDEDE〞

4.含n個(gè)字符的有限序列（n≥0）

5.不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計(jì)題1．算法描述為：

intdelete(r,s,t,m)//從串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串

大發(fā)光火

charr[];ints,t,m;{inti,j;

for(i=1;i=m;i++)

r[s+i]=r[i];for(j=m+t-i;j=s;j++)

r[s-t+j]=r[j];return(1);}//delete

2．算法思想為：

（1）鏈表s中取出一個(gè)字符；將該字符與單鏈表t中的字符依次比較；（2）當(dāng)t中有與從s中取出的這個(gè)字符相等的字符，則從t中取下一個(gè)字符重復(fù)以上比較；（3）當(dāng)t中沒(méi)有與從s中取出的這個(gè)字符相等的字符，則算法終止。

設(shè)單鏈表類型為L(zhǎng)inkList；注意，此時(shí)類型LinkList中的data成分為字符類型。

LinkStringfind(s,t)LinkString*s,*t;{LinkString*ps,*pt;ps=s;

while(ps!=NULL){pt=t;

while((pt!=NULL)(ps-data!=pt-data))pt=pt-next;if(pt==NULL)

ps=NULL;

else

{ps=ps-next;

s=ps;

}}returns;}//find

大發(fā)光火

習(xí)題4

一、單項(xiàng)選擇題

1.設(shè)二維數(shù)組A[0m-1][0n-1]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素aij的地址為（）。

A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k

2.已知二維數(shù)組A1010中，元素a20的地址為560，每個(gè)元素占4個(gè)字節(jié)，則元素a10

的地址為（）。

A.520B.522C.524D.5183.若數(shù)組A[0m][0n]按列優(yōu)先順序存儲(chǔ)，則aij地址為（）。A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]

C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]

4.若下三角矩陣Ann，按列順序壓縮存儲(chǔ)在數(shù)組Sa[0(n+1)n/2]中，則非零元素aij

的地址為（）。（設(shè)每個(gè)元素占d個(gè)字節(jié)）

(j2)(j1)

+i-1]*d

2

(j2)(j1)

B.[(j-1)*n-+i]*d

2

(j2)(j1)

C．[(j-1)*n-+i+1]*d

2

(j2)(j1)

D．[(j-1)*n-+i-2]*d

2

A.[(j-1)*n-5.設(shè)有廣義表D=(a,b,D)，其長(zhǎng)度為（），深度為（）。

A.無(wú)窮大B.3C.2D.56.廣義表A=（a），則表尾為（）。

A.aB.(())C.空表D.(a)

7.廣義表A=((x,(a,B)),(x,(a,B),y))，則運(yùn)算head(head(tail(A)))的結(jié)果為（）。A.xB.(a,B)C.(x,(a,B))D.A8.以下廣義表用圖來(lái)表示時(shí)，分支結(jié)點(diǎn)最多的是（）。A.L=((x,(a,B)),(x,(a,B),y))B.A=(s,(a,B))

C.B=((x,(a,B),y))D.D=((a,B),(c,(a,B),D)9.尋常對(duì)數(shù)組進(jìn)行的兩種基本操作是（）。

A.建立與刪除B.索引和修改C.查找和修改D.查找與索引

大發(fā)光火

10.假定在數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（）。

A.80B.100C.240D.270

11.數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為（）。

A.SA+141B.SA+144C.SA+222D.SA+22512.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表

13.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（）。

A.正確B.不正確14.一個(gè)廣義表的表頭總是一個(gè)（）。

A.廣義表B.元素C.空表D.元素或廣義表15.一個(gè)廣義表的表尾總是一個(gè)（）。

A.廣義表B.元素C.空表D.元素或廣義表16.數(shù)組就是矩陣，矩陣就是數(shù)組，這種說(shuō)法（）。A.正確B.錯(cuò)誤C.前句對(duì)，后句錯(cuò)D.后句對(duì)二、填空題