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

習(xí)題1

一、單項選擇題

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

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

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

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

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

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

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

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

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

4,設(shè)語句x++的時間是單位時間，則以下語句的時間復(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.算法分析的目的是（■）,算法分析的兩個主要方面是（.）。

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

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

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

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

6.計算機(jī)算法指的是（|）,它具備輸入,輸出和（|）等五個特性。

（1）A.計算方法B.排序方法

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

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

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

7.數(shù)據(jù)在計算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱?/p>

儲比順序存儲要（）。

A.低喊C.相同D.不好說

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

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

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

A.正確|.錯蠲

C.前半句對，后半句錯D.前半句錯，后半句對

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

A.數(shù)據(jù)C.數(shù)據(jù)項D.數(shù)據(jù)庫

二、填空題

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é)點間的邏輯關(guān)系是—_—對——的，非線性結(jié)構(gòu)反映結(jié)點間的邏

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

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

5.在樹型結(jié)構(gòu)中，樹根結(jié)點沒有—前趨—結(jié)點，其余每個結(jié)點的有且只有

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

多個—o

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

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

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

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

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

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

A[i]U]=0；

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

i=s=0;

while(s<n)

{i++；

s+=i;

}

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

s=0;

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

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

s+=B[i][j];

sum=s;

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

i=l；

while(i<=n)

i=i*3;

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

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

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

三、求下列程序段的時間復(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參考答案

一、單項選擇題

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

二、填空題

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

2.集合，線性，樹，圖

3.一對一，一對多或多對多

4.時間，空間

5.前趨，一，后繼，多

6.有多個

7.一對一，一對多，多對多

8.0(〃2)

9.0(4)

10.0(〃2)

11.O(log3n)

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

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

三、算法設(shè)計題

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

-4-

習(xí)題2

一、單項選擇題

1.線性表是。

A.一個有限序列，可以為空B.一個有限序列，不可以為空

C.一個無限序列，可以為空D.?個無限序列，不可以為空

2.在一個長度為n的順序表中刪除第i個元素(0<=iv=n)時，需向前移動一個元素。

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

3.線性表采用鏈?zhǔn)酱鎯r，其地址。

A.必須是連續(xù)的B.一定是不連續(xù)的

C.部分地址必須是連續(xù)的D.連續(xù)與否均可以

4.從個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，

需平均比較個元素結(jié)點。

A.n/2B.nC.(n+1)/2D.(n-1)/2

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

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é)點m,若要刪除m之后的結(jié)點(若存在)，則需修改指針

的操作為。

A.p->next=p->next->next;B.p=p->next;

C.p=p->next->next;D.p->next=p;

7.在一個長度為n的順序表中向第i個元素(Ovivn+1)之前插入一個新元素時，需向后

移動個元素。

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

8.在?個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點,

則須執(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)于線性表的說法不正確的是。

A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。

B.線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。

C.線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。

D.存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。

10.線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)。

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

11.在順序表中，只要知道,就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。

A.基地址B.結(jié)點大小

C.向量大小D.基地址和結(jié)點大小

12.在等概率情況下，順序表的插入操作要移動結(jié)點。

A.全部B.一半

C.三分之一-D.四分之一

13.在運算中，使用順序表比鏈表好。

A.插入B.刪除

C.根據(jù)序號查找D.根據(jù)元素值查找

14.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜

度是。

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

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

15.設(shè)有一個棧，元素的進(jìn)棧次序為A,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.在一個具有n個單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top

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

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

17.向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(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個單元的順序存儲的循環(huán)隊列中，假定和rear分別為隊頭指針和隊

尾指針，則判斷隊滿的條件為o

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

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

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

-6-

尾指針，則判斷隊空的條件為。

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

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

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

作為o

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

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

二、填空題

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

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

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

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

置,移動過程是從向依次移動每一個元素。

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

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

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

_______結(jié)點O

7.當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用

存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時,則采用存儲結(jié)構(gòu)為宜。

8.順序表中邏輯上相鄰的元素，物理位置相鄰，單鏈表中邏輯上相鄰的元素，

物理位置相鄰。

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

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

位置刪除元素。

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

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

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

12.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜

度為,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為。

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

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

量為。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連

續(xù)的內(nèi)存空間時，應(yīng)將兩棧的分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)

時才產(chǎn)生上溢。

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

push后，輸出序列是。

15.無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，進(jìn)行插入或刪除運算的時間復(fù)

雜度均相同為。

三、簡答題

1.描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。

2.線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？

3.對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表

的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)

構(gòu)？為什么？

4.對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操

作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。

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

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

出棧序列。

7.什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。

8.下述算法的功能是什么？

LinkList*Dcmo(LinkList*L)

{〃L是無頭結(jié)點的單鏈表

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è)計題

1.設(shè)計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。

2.在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。

3.設(shè)計將帶表頭的鏈表逆置算法。

4.假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head,每個結(jié)點含三個域：data,next

和prioro其中data為整型數(shù)域，next和prior均為指針域。現(xiàn)在所有結(jié)點已經(jīng)由next域連

接起來，試編一個算法，利用prior域(此域初值為NULL)把所有結(jié)點按照其值從小到大

的順序鏈接起來。

5.已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一

個刪除表中所有值大于min且小于max的元素(若表中存在這樣的元素)的算法。

6.已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除

表中所有值小于max但大于min的元素的算法。

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

不設(shè)隊首指針，試編寫下列各種運算的算法：

(1)向循環(huán)鏈隊列插入一個元素值為X的結(jié)點；

(2)從循環(huán)鏈隊列中刪除一個結(jié)點。

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

習(xí)題2參考答案

一、單項選擇題

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.物理存儲位置，鏈域的指針值

6.前趨，后繼

7.順序，鏈接

8.一定，不一定

9.線性，任何，棧頂，隊尾，隊頭

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

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

12.0(1),0(n)

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

14.2、3

15.0(1)

三、簡答題

1.頭指針是指向鏈表中第一個結(jié)點(即表頭結(jié)點)的指針；在表頭結(jié)點之前附設(shè)的

結(jié)點稱為頭結(jié)點；表頭結(jié)點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。若鏈表中附設(shè)

頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。

2.線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)

可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移

動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)

點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。

3.應(yīng)選用鏈接存儲結(jié)構(gòu)，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表

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

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

充。

4.應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差?個

和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的

任一個數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu),

而鏈表則是一種順序存取的存儲結(jié)構(gòu)。

5.設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表

可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指

針為rear,則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和rear,查找時間都

是0(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為0(n)。

6.共有14種可能的出棧序列，即為：

ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,

CBDA,CDBA,DCBA

7.在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front,隊尾指針為rear,隊列的容量(即

存儲的空間大小)為maxnum1,當(dāng)有元素要加入隊列(即入隊)時，若rear=maxnum,則

會發(fā)生隊列的匕溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”

現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作

方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。

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

(1)可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低,

浪費存儲空間。

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

第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊

頭移動一個位置，假定空余空間足夠。

第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊

列中的第一個位置。

第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循

環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進(jìn)先出”的原則。

8.該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原

來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。

四、算法設(shè)計題

1.算法思想為：

(1)應(yīng)判斷刪除位置的合法性，當(dāng)i<0或i>n-l時，不允許進(jìn)行刪除操作；

(2)當(dāng)i=0時，刪除第一個結(jié)點：

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

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

delete(LinkList*q,inti)

-10-

{〃在無頭結(jié)點的單鏈表中刪除第i個結(jié)點

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.由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個

數(shù)了。算法描述如下：

intListLength(LinkList*L)

{〃求帶頭結(jié)點的單鏈表的表長

intlen=0;

ListList*p;

P=L；

while(p->ncxt!=NULL)

{p=p->next;

len++;

}

return(len);

-11-

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

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

點，p指向其原后繼結(jié)點，則只需進(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)表不為空時，逐個結(jié)點逆置

{s=q;

q=p；

p=p->next;

q->next=s;

)

p->next=q;

}

4.定義類型LinkList如下:

typedefstructnode

{intdata;

structnode*next,*prior;

}LinkList;

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

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

insert(LinkList*head)

{LinkList*p,*s,*q;

p=head->next;〃p指向待插入的結(jié)點，初始時指向第一個結(jié)點

while(p!=NULL)

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

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

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

{s=q;

q=q->prior;

)

s->prior=p;

p->prior=q;〃結(jié)點p插入到結(jié)點s和結(jié)點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.本題是對一個循環(huán)鏈隊列做插入和刪除運算，假設(shè)不需要保留被刪結(jié)點的值和不需

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

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

insert(LinkList*rcar,clcmtypcx)

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

LinkList*p;

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

-13-

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

{rear=p;

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

)

else〃否則在隊尾插入p結(jié)點

{p->next=rear->next;

rear->next=p;

rear=p;

)

}

(2)刪除(即出隊)算法：

delete(LinkList*rear)

{〃設(shè)循環(huán)鏈隊列的隊尾指針為rear

if(rear==NULL)〃空隊

printf("underflow\nn);

ifi(rear->next==rear)〃隊中只有一個結(jié)點

rear=NULL;

else

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

)

8.只要從終端結(jié)點開始往前找到第一個比x大(或相等)的結(jié)點數(shù)據(jù)，在這個位置插入

就可以了。算法描述如下：

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];〃比較并移動元素

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

(*L).len++;

rcturn(1);

-14-

習(xí)題3

一、單項選擇題

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

A.沒有區(qū)別B.兩串的長度不相等

C.兩串的長度相等D.兩串包含的字符不相同

2.一個子串在包含它的主串中的位置是指（）。

A.子串的最后那個字符在主串中的位置

B.子串的最后那個字符在主串中首次出現(xiàn)的位置

C.子串的第一個字符在主串中的位置

D.子串的第一個字符在主串中首次出現(xiàn)的位置

3.下面的說法中，只有（）是正確的。

A.字符串的長度是指串中包含的字母的個數(shù)

B.字符串的長度是指串中包含的不同字符的個數(shù)

C.若T包含在S中，則T一定是S的一個子串

D.一個字符串不能說是其自身的一個子串

4.兩個字符串相等的條件是（）。

A.兩串的長度相等

B.兩串包含的字符相同

C.兩串的長度相等，并且兩串包含的字符相同

D.兩串的長度相等，并且對應(yīng)位置上的字符相同

5.若SUBSTR（S,i,k）表示求S中從第i個字符開始的連續(xù)k個字符組成的子串的

操作，則對于S="Beijing&Nanjing”，SUBSTR(S,4,5)=()?

A.”ijing”B."jing&”

C."ingNa”D."ing&N”

6.若INDEX(S,T)表示求T在S中的位置的操作，則對于S="Beijing&Nanjing”,

T=，jing”，INDEX(S,T)=()o

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

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

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

()?

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

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

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

A.i>0B.iWn

-15-

C.lWiWnD.lWiWn+1

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

A.鏈表的長度為1

B.鏈表中只存放1個字符

C.鏈表的每個鏈結(jié)點的數(shù)據(jù)域中不僅只存放了一個字符

D.鏈表的每個鏈結(jié)點的數(shù)據(jù)域中只存放了一個字符

二、填空題

1.計算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是,第二種

是o

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

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

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

4.串是指o

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

三、算法設(shè)計題

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

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

t<(s-m),并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計此刪除算法。

2.設(shè)s和t是表示成單鏈表的兩個串，試編寫一個找出s中第1個不在t中出現(xiàn)的字

符(假定每個結(jié)點只存放1個字符)的算法。

習(xí)題3參考答案

一、單項選擇題

1.B2.D3.C4.D5.B6.C7.D8.C9.D

二、填空題

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

2.兩個串的長度相等，對應(yīng)位置的字符相等

3.“BCDEDE”

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

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

三、算法設(shè)計題

1.算法描述為：

intdeleter,s,t,m)〃從串的第m個字符以后刪除長度為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中取出一個字符；將該字符與單鏈表t中的字符依次比較；

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

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

設(shè)單鏈表類型為LinkList；注意，此時類型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

一、單項選擇題

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

每個元素占k個字節(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,每個元素占4個字節(jié)，則元素ai。

的地址為()。

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

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

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.*.,按列順序壓縮存儲在數(shù)組Sa[O…(n+l)n/2]中，則非零元素a()

的地址為()。(設(shè)每個元素占d個字節(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),其長度為(),深度為()。

A.無窮大B.3C.2D.5

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

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

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

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

8.下列廣義表用圖來表示時，分支結(jié)點最多的是()。

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.通常對數(shù)組進(jìn)行的兩種基本操作是()。

A.建立與刪除B.索引和修改

C.查找和修改D.查找與索引

-18-

10.假定在數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1

到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為()。

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

11.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,

從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為

()。

A.SA+141B.SA+144C.SA+222D.SA+225

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

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

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

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

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

A.正確