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

習(xí)題1

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

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

A.數(shù)據(jù)兀索的組織形式B.數(shù)據(jù)類型

C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)定義

2.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（）o

A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)

C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)

3.樹(shù)形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（）。

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

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

4,設(shè)語(yǔ)句x++的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間復(fù)雜度為（）。

fbr（i=l;i<=n;i++）

fbr（j=i;j<=n;j++）

x++;

A.0（1）B.0（/?2）C.0（n）D.0（n3）

5.算法分析的目的是（■）,算法分析的兩個(gè)主要方面是（.）。

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

C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性

（2）A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)明性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

6.計(jì)算機(jī)算法指的是（|）,它具備輸入,輸出和（|）等五個(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)酱?/p>

儲(chǔ)比順序存儲(chǔ)要（）。

A.低喊C.相同D.不好說(shuō)

8.數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程出現(xiàn)是在（）年。

A.1946B.1953C.1964D.1968

9.數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu),這種觀點(diǎn)（）。

A.正確|.錯(cuò)蠲

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

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

A.數(shù)據(jù)C.數(shù)據(jù)項(xiàng)D.數(shù)據(jù)庫(kù)

二、填空題

1.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是—線性結(jié)構(gòu)—和非線性結(jié)構(gòu)」

2.數(shù)據(jù)的邏輯結(jié)構(gòu)仃四種基本形態(tài)，分別是_線性、圖

和偏。

3.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是—_—對(duì)——的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏

輯關(guān)系是一■多或者是多對(duì)國(guó)的。

4.?個(gè)算法的效率可分為■效率和喊效率。

5.在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有—前趨—結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有

I個(gè)前趨驅(qū)結(jié)點(diǎn);葉子結(jié)點(diǎn)沒(méi)有.結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以

多個(gè)—o

6.在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以^

7.線性結(jié)構(gòu)中元素之間存在--對(duì)一關(guān)系;樹(shù)型結(jié)構(gòu)中元素之間存在——對(duì)

多關(guān)系；圖型結(jié)構(gòu)中元素之間存在多對(duì)多—關(guān)系。

8.下面程序段的時(shí)間復(fù)雜度是

for(i=0;i<n;i+4-)

for(j=0;j<n;j-H-)

A[i]U]=0；

9.下面程序段的時(shí)間復(fù)雜度是。

i=s=0;

while(s<n)

{i++；

s+=i;

}

10.下面程序段的時(shí)間復(fù)雜度是o

s=0;

fbr(i=0;i<n;i-H-)

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;

11.下面程序段的時(shí)間復(fù)雜度是O

i=l；

while(i<=n)

i=i*3;

12,衡量算法正確性的標(biāo)準(zhǔn)通常是o

13.算法時(shí)間復(fù)雜度的分析通常有兩種方法，即和的方法，通

常我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。

三、求下列程序段的時(shí)間復(fù)雜度。

1.x=0;

fbr(i=l;i<n;i++)

fbr(j=i+l；j<=n;j++)

x++;

O

2.x=0;

fbr(i=l;i<n;i++)

ford=l；j<=n-i；j++)

x++;

3.inti,j,k;

fbr(i=O;i<n;i++)

for(j=0;j<=n;j++)

{c[i]0]=0;

for(k=0;k<n;k++)

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

}

4.i=n-l;

while((i>=O)&&A[i]!=k))

j-;

return(i);

5.fact(n)

{if(n<=l)

return(1);

else

return(n*fhct(n-l));

)

習(xí)題1參考答案

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

1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B

二、填空題

1.線性結(jié)構(gòu)，非線性結(jié)構(gòu)

2.集合，線性，樹(shù)，圖

3.一對(duì)一，一對(duì)多或多對(duì)多

4.時(shí)間，空間

5.前趨，一，后繼，多

6.有多個(gè)

7.一對(duì)一，一對(duì)多，多對(duì)多

8.0(〃2)

9.0(4)

10.0(〃2)

11.O(log3n)

12.程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。

13.事后統(tǒng)計(jì)，事前估計(jì)

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

l.O(n2)2.0(/)3.0(n3)4.0(n)5.0(D)

-4-

習(xí)題2

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

1.線性表是。

A.一個(gè)有限序列，可以為空B.一個(gè)有限序列，不可以為空

C.一個(gè)無(wú)限序列，可以為空D.?個(gè)無(wú)限序列，不可以為空

2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0<=iv=n)時(shí)，需向前移動(dòng)一個(gè)元素。

A.n-iB.n-i+1C.n-i-1D.i

3.線性表采用鏈?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)(若存在)，則需修改指針

的操作為。

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è)元素(Ovivn+1)之前插入一個(gè)新元素時(shí)，需向后

移動(dòng)個(gè)元素。

A.n-iB.n-i+1C.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=s

B.q->next=s;s->next=p

C.p->next=s->next;s-〉next二p

-5-

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í)間復(fù)雜

度是。

A.0(1)B.O(n)

C.O(n2)D.O(log2n)

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

A.A,B,C,D,EB.B,C,D,E,A

C.E,A,B,C,DD.E,D,C,B,A

16.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top

作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為。

A.top不變B.top=0C.top-D,top++

17.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行o

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ì)列中，假定和rear分別為隊(duì)頭指針和隊(duì)

尾指針，則判斷隊(duì)滿的條件為o

A.rear%n==frontB.(front+1)%n==rear

C.rear%n-1==frontD.(rear+1)%n=-front

19.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定價(jià)ont和rear分別為隊(duì)頭指針和隊(duì)

-6-

尾指針，則判斷隊(duì)空的條件為。

A.rear%n==frontB.front+l=rear

C.rear==frontD.(rear+1)%n=front

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

作為o

A.front=front->nextB.rear=rear->next

C.rear=front->nextD.front=rear->next

二、填空題

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

2.在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移_個(gè)元素。

3.順序表中邏輯上相鄰的元素的物理位置o

4.要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需一個(gè)位

置,移動(dòng)過(guò)程是從向依次移動(dòng)每一個(gè)元素。

5.在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的；在線性表的

鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的。

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

_______結(jié)點(diǎn)O

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.順序表中邏輯上相鄰的元素，物理位置相鄰，單鏈表中邏輯上相鄰的元素，

物理位置相鄰。

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

對(duì)于棧只能在位置插入和刪除元素；對(duì)于隊(duì)列只能在位置插入元素和在

位置刪除元素。

10.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為

和;而根據(jù)指針的聯(lián)接方式，鏈表又可分為和。

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

12.對(duì)于一個(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ù)雜度為。

13.對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為，作退棧運(yùn)算時(shí)，應(yīng)先判別

棧是否為,當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明棧的可用最大容

量為。為了增加內(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í)間復(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*Dcmo(LinkList*L)

{〃L是無(wú)頭結(jié)點(diǎn)的單鏈表

LinkList*q,*p;

if(L&&L->next)

{q=L;L=L->ncxt;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

和prioro其中data為整型數(shù)域，next和prior均為指針域?，F(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ì)尾指針，

不設(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.B

13.C14.B15.C16.C17.B18.D19.C20.A

二、填空題

1.線性

2.n-i+1

3.相鄰

4.前移，前，后

5.物理存儲(chǔ)位置，鏈域的指針值

6.前趨，后繼

7.順序，鏈接

8.一定，不一定

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

10.單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表

11.使空表和非空表統(tǒng)「算法處理一致

12.0(1),0(n)

13.棧滿，棧空，m,棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇

14.2、3

15.0(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)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表

中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的

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

充。

4.應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(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í)間都

是0(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為0(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ǔ)的空間大小)為maxnum1,當(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)i<0或i>n-l時(shí)，不允許進(jìn)行刪除操作；

(2)當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：

(3)當(dāng)Ovivn時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)

點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：

delete(LinkList*q,inti)

-10-

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

LinkList*p,*s;

intj;

if(i<0)

printf(MCan'tdelete");

elseif(i==0)

{s=q;

q=q->next;

free(s);

)

else

{j=0;s=q;

while((j<i)&&(s!=NULL))

{P=s；

s=s->next;

j++；

}

if(s==NULL)

printfifCant'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->ncxt!=NULL)

{p=p->next;

len++;

}

return(len);

-11-

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

作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)

點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q->next=s;操作即可，算法描述如下：

voidinvert(LinkList*head)

{//逆置head指針?biāo)赶虻膯窝h(huán)鏈表

linklist*p,*q,*s;

q=head;

p=head->next;

while(p!=head)〃當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置

{s=q;

q=p；

p=p->next;

q->next=s;

)

p->next=q;

}

4.定義類型LinkList如下:

typedefstructnode

{intdata;

structnode*next,*prior;

}LinkList;

此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有

序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：

insert(LinkList*head)

{LinkList*p,*s,*q;

p=head->next;〃p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn)

while(p!=NULL)

{s=head;//s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn)

q=head->prior;//q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn)

while((q!=NULL)&&(p->data>q->data))〃杳找插入結(jié)點(diǎn)p的合適的插入位置

{s=q;

q=q->prior;

)

s->prior=p;

p->prior=q;〃結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間

p=p->next;

)

)

5.算法描述如下：

delete(LinkList*head,intmax,intmin)

{linklist*p,*q;

if(head!=NULL)

{q=head;

p=head->next;

while((p!=NULL)&&(p->data<=min))

{q=p;

p=p->next;

}

while((p!=NULL)&&(p->data<max))

p=p->next;

q->next=p;

}

}

6.算法描述如下：

delete(LinkList*head,intmax,intmin)

{LinkList*p,*q;

q=head;

p=head->next;

while(p!=NULL)

if((p->data<=min)||(p->data>=max))

{q=p;

p=p->next;

)

else

{q->next=p->next;

free(p);

p=q->ncxt;

)

}

7.本題是對(duì)一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需

要回收結(jié)點(diǎn)，算法描述如下：

(1)插入(即入隊(duì))算法：

insert(LinkList*rcar,clcmtypcx)

{〃設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear,x為待插入的元素

LinkList*p;

p=(LinkList*)malIoc(sizeof^LinkList));

-13-

if(rear==NULL)〃如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一個(gè)結(jié)點(diǎn)

{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ì)尾指針為rear

if(rear==NULL)〃空隊(duì)

printf("underflow\nn);

ifi(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)

{printfi(€4overflown);

rcturn(O);

)

fbr(i=(*L).lcn;i>0&&(*L).clcm[i-1]<x;i—)

(*L).eIem[i]=(*L).elem[i-1];〃比較并移動(dòng)元素

(*L).elcm[i]=x;

(*L).len++;

rcturn(1);

-14-

習(xí)題3

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

i.空串與空格字符組成的串的區(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)=()o

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

7.若REPLACE(S,SI,S2)表示用字符串S2替換字符串S中的子串S1的操作，

則對(duì)于S="Beijing&Nanjing”,Sl="Beijing”,S2="Shanghai”,REPLACE(S,SI,S2)=

()?

A."Nanjing&Shanghai"B."Nanjing&Nanjing”

C."ShanghaiNanjing"D."Shanghai&Nanjing”

8.在長(zhǎng)度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)該是()。

A.i>0B.iWn

-15-

C.lWiWnD.lWiWn+1

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

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)度的方法：一種是,第二種

是o

2.兩個(gè)字符串相等的充要條件是和o

3.設(shè)字符串S1="ABCDEF"，S2=“PQRS”；則運(yùn)算S=CONCAT(SUB(SI,2,LEN

(S2)),SUB(SI,LEN(S2),2))后的串值為。

4.串是指o

5.空串是指,空格串是指o

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

1.設(shè)有一個(gè)長(zhǎng)度為s的字符串，其字符順序存放在一個(gè)一維數(shù)組的第1至第s個(gè)單元

中(每個(gè)單元存放一個(gè)字符)?，F(xiàn)要求從此串的第巾個(gè)字符以后刪除長(zhǎng)度為t的子串，m<s,

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.B2.D3.C4.D5.B6.C7.D8.C9.D

二、填空題

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

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

3.“BCDEDE”

4.含n個(gè)字符的有限序列(n20)

5.不含任何字符的串，僅含空格字符的字符串

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

1.算法描述為：

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

-16-

charr[];

ints,t,m;

{inti,j;

fbr(i=l;i<=m;i-H-)

r[s+i]=r[i];

fbr(j=in+t-i;j<=sj++)

r[s-t+j]=r|j];

return(I);

}//delete

2.算法思想為：

(1)鏈表s中取出一個(gè)字符；將該字符與單鏈表t中的字符依次比較；

(2)當(dāng)t中有與從s中取出的這個(gè)字符相等的字符，則從t中取下一個(gè)字符重復(fù)以上比較;

(3)當(dāng)t中沒(méi)有與從s中取出的這個(gè)字符相等的字符，則算法結(jié)束。

設(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

-17-

習(xí)題4

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

1.設(shè)二維數(shù)組A[0……n-l]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p,

每個(gè)元素占k個(gè)字節(jié)，則元素a,)的地址為()。

A.p+[i*n+j-l]*kB.p+[(i-l)*n+j-l]*k

C.p+[(j-l)*n+i-l]*kD.p+[j*n+i-l]*k

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

的地址為()。

A.520B.522C.524D.518

3.若數(shù)組A[0…m][0…n]按列優(yōu)先順序存儲(chǔ)，則地址為()。

A.^(aoo)+[j*m+i]B.LOC(aM)+[j*n+i]

C.LOC(aM)+[(j-l)*n+i-l]D.LOC(aM)+[(j-l)*m+i-l]

4.若下三角矩陣A.*.,按列順序壓縮存儲(chǔ)在數(shù)組Sa[O…(n+l)n/2]中，則非零元素a()

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

A.[(j-D*n-生2)(j二D+1]*d

2

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

2

C.[—2)(1-l)+i+i]*d

2

D.[(jT)*n-《/2)(-D+i_2]*d

2

5.設(shè)有廣義表D=(a,b,D),其長(zhǎng)度為(),深度為()。

A.無(wú)窮大B.3C.2D.5

6.廣義表A=(a),則表尾為()。

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

7.廣義表A=((x,(a,B)),(x,(a,B),y)),則運(yùn)算head(head(tail(A)))的結(jié)果為(7

A.xB.(a,B)C.(x,(a,B))D.A

8.下列廣義表用圖來(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.查找與索引

-18-

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+225

12.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即()。

A.二維數(shù)組和三維數(shù)組B.三元組和散列

C.三元組和十字鏈表D.散列和卜字鏈表

13.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換,

就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)()?

A.正確