數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題匯編

數(shù)據(jù)結(jié)構(gòu)課后練習(xí)題

第一章緒論

-、選擇題

1、數(shù)據(jù)結(jié)構(gòu)被形式定義為（D,S）,其中口是（）的有限集合，S是D上的（）有限集合。

A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯關(guān)系E、操作F、映象G、存儲H、關(guān)系

2、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的（（1））以及它們之間的（②）和運算

的學(xué)科。

（1）A、操作對象B、計算方法C、邏輯存儲D、數(shù)據(jù)映象

（2）A、結(jié)構(gòu)B、關(guān)系C、運算D、算法

3、算法分析的目的是（），算法分析的二個主要方面是（

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

C、空間復(fù)雜性和時間復(fù)雜性D、分析算法的效率以求改進

E、正確性和簡明性F、分析算法的易懂性和文檔性

4、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。

A、動態(tài)和靜態(tài)結(jié)構(gòu)B、緊湊接和非緊湊結(jié)構(gòu)

C、線性與非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

5、計算機算法指的是（），它必具備輸入、輸出和（）5個特性。

A、計算方法B、排序方法C、解決問題的有限運算序列D、可行性、可移植性和可擴充性E、可行

性、確定性和有窮性

6、線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)，線性表的鏈式存儲結(jié)構(gòu)是種（）

A、隨機存取B、順序存取C、索引存取D、散列存取

7、算法的時間復(fù)雜度取決于（）

A、問題的規(guī)模B、待處理數(shù)據(jù)的初態(tài)C、問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)

8、線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）

A、必須是連續(xù)的B、部分地址必須是連續(xù)的

C、一定是不連續(xù)的D、連續(xù)不連續(xù)都可以

9、在以下的敘述中，正確的是（）

A、線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)

B、二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表

C、棧的操作方式是先進先出

D、隊列的操作方式是先進后出

10、根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的

數(shù)據(jù)組織形式。以下解釋錯誤的是（）

A、集合中任何兩個結(jié)點之間都有邏輯關(guān)系但組織形式松散

B、線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條“鎖鏈”

C、樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點像自然界中的樹

D、圖狀結(jié)構(gòu)中的各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接

11、以下說法正確的是（）

A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B、數(shù)據(jù)項是數(shù)據(jù)的基本單位

C、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合

D、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合

二、填空題

1、數(shù)據(jù)邏輯結(jié)構(gòu)包括（）四種類型，樹型和圖型結(jié)構(gòu)合稱（）。

2、對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（）、（）、（）和（）四種。

3、算法的五個重要特性是（）。

4、評價算法的性能從利用計算機資源角度看主要從（）方面進行分析。

5、線性結(jié)構(gòu)中元素之間存在（）關(guān)系，樹型結(jié)構(gòu)中元素之間存在（）關(guān)系，圖型結(jié)構(gòu)中元素之間

存在（）關(guān)系。

6、下面程序段的時間復(fù)雜度是（）。

i=s=O;while（s<n）{i++;s++;}

7、下面程序段的時間復(fù)雜度是（）。

s=0;for（I=0;kn;I++）for（j=0;j<m;j++）s+=a[i][j]；

8、所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的。

9、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容。

10、在線性結(jié)構(gòu)中，開始結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有一個結(jié)點。

11、在樹形結(jié)構(gòu)中，根結(jié)點只有,根結(jié)點無前驅(qū)，其余每個結(jié)點有且只有前驅(qū)結(jié)點；葉子結(jié)點

沒有結(jié)點，其余每個結(jié)點的后繼結(jié)點可以。

12、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點可以有。

13、存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的實現(xiàn)。

14、從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的''數(shù)據(jù)”應(yīng)分成三個不同的層次，即、和

15、根據(jù)需要，數(shù)據(jù)元素又被稱為、、或。

16、通常，存儲結(jié)點之間可以有、、、四種關(guān)聯(lián)方式，稱為四種

基本存儲方式。

17、通常從、、、等幾方面評價算法的（包括程序）的質(zhì)量。

18、一個算法的時空性能是指該算法的和，前者是算法包含的

.后者是算法需要的。

19、在一般情況下，一個算法的時間復(fù)雜性是的函數(shù)。

20、常見時間復(fù)雜性的量級有：常數(shù)階0（）、對數(shù)階0（）、線性階0（）、

平方階0（）、和指數(shù)階0（）。通常認為，具有指數(shù)階量級的算法是的。

21、數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的和。

22、數(shù)據(jù)對象是性質(zhì)相同的的集合。

23、抽象數(shù)據(jù)類型是指一個以及定義在該模型上的一組操作。

三、判斷題

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

2.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。

3.數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)項在計算機中的映象分別稱為存儲結(jié)構(gòu)，結(jié)點，數(shù)據(jù)域。

4.數(shù)據(jù)項是數(shù)據(jù)的基本單位。

5.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。

6.數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計算機中實際的存儲形式。

7.算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。

8.順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。

四、計算應(yīng)用題

1、設(shè)n為正正數(shù)。確定下列各程序段中前置以記號@的語句的頻度。

（1）I=l;k=0;

While(I<n-l)

@{k+=10*I;

1++；}

k=0;

for(I=l;I<=n;I++)

{for(j=I；j<=n;j++)

@k++;}

(2)I=l；j=O;

While(I+j<=n)

@{if(I>j)j++;

else1++;}

2、寫出下面算法中帶標號語句的頻度。

Voidperm(inta[],k,n)

{intxj;

(1)if(k==n)

(2)for(I=1;I<=n;I++)

(3)printf("％d”,a[I]);

else

{(4)for(I=k;I<=n;I++)

(5)a[I]+=I*I;

(6)perm(a,k+l,n);}}

執(zhí)行函數(shù)調(diào)用語句perm(a,l,n)

3、指出下列兩個算法的時間復(fù)雜度。

(1)intsum1(intn)

{intp=l,sum=0,I;

for(I=1;I<=n;I++){p*=I;sum+=p;}

return(sum);}

(2)intsum2(intn)

{intsum=0,I,j;

for(I=l;I<=n;I++){p=1;for(j=1;j<=I;j++)p*=j;

sum+=p;}

returm(sum);}

4、有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們對應(yīng)的邏輯圖形表示，并指出它們屬于哪種結(jié)構(gòu)。

(1)A=(K,R),其中:K={a,b,c,d,e,f,g,h}R=(r)

r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}

(2)B=(K,R)淇中:K={a,b,c,d,e,f,g,h}R=(r)r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}

(3)C=(K,R),其中：k={1,2,345,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

(4)D=(K.R),K={48,25,64,57,82,36,75),R={rl,r2}

rl={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}

r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<84,75>}

5、設(shè)有如圖所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)。

KI

6、簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對象。

7、邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系？

2n2）

8、將數(shù)量級n,n,n\nlog2n,log2n,2,品,n!,（2/3）",n\按增長率進行排列。

五、算法設(shè)計題

1.已知輸入x,y,z三個不相等的整數(shù)，設(shè)計一個算法，使得這三個數(shù)按從大到小輸出，并考慮所用算法的比

較次數(shù)和元素移動次數(shù)。

2.編寫在輸入10個數(shù)中找出最小或最大的數(shù)的算法。

3.在數(shù)組A[n]中查找值為k的元素，若找到則輸出其位置i（lWiWn）,否則輸出0作為標志。設(shè)計求解此問題

的類C語言算法，并分析其最壞情況時間復(fù)雜度。

第二章線性表練習(xí)題

一、選擇題

1、表長為N的順序表，當(dāng)在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的

平均次數(shù)為（），刪除一個元素需要移動的元素個數(shù)為（）。

A.（N-l）/2B.NC.N+lD.N-lE.N/2F.（N+l）/2G（N-2）/2

2、線性表是具有N個（）的有限序列。

A、表元素B、字符C、數(shù)據(jù)元素D、數(shù)據(jù)項E、信息

3、”線性表的邏輯順序和物理順序總是一致的?！边@個結(jié)論是（）。

A、正確的B、錯誤的C、不一定，與具體結(jié)構(gòu)有關(guān)。

4、線性表采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）o

A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)或不連續(xù)都可以。

5、帶頭結(jié)點的單鏈表為空的判定條件是（）。

A、head==NULLB、head->next==NULLC>head->next==headD、head!=NULL

6、不帶頭結(jié)點的單鏈表head為空的判定條件是（）。

A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL

7、非空的循環(huán)單鏈表head的尾結(jié)點P滿足（）。

A、P->NEXT=NULLB、p=NULLC>p->next==headD^p=head

8、在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是（）。

A、0（1）B、0（n）C、0（n2）D、O（nlog2n）

9、在一個單鏈表中，若刪除P所指結(jié)點的后繼結(jié)點，則執(zhí)行（）。

A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;

10、在一個單鏈表中，若在P所指結(jié)點之后插入S所指結(jié)點，則執(zhí)行（）。

A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、

p->next=s;s->next=p;

11、在一個單鏈表中，已知q是p的前趨結(jié)點，若q和p之間插入結(jié)點s,則執(zhí)行（）。

A、s-next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、

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

12、假設(shè)雙鏈表結(jié)點的類型如下：

typedefstructlinknode{

intdata;//數(shù)據(jù)域

structlinknode*llink;//指向前趨結(jié)點的指針域

structlinknode*rlink;//指向后繼結(jié)點的指針域

}bnode

現(xiàn)將一個q所指新結(jié)點作為非空雙向鏈表中的p所指結(jié)點的前趨結(jié)點插入到該雙鏈表中，能iE確完成此要

求的語句段是（）。

A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;

B、p->Ilink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink

C、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q;

D、以上都不對

13、如上題結(jié)點結(jié)構(gòu)，如在此非空循環(huán)雙向鏈表的結(jié)點p之后插入結(jié)點s的操作序列是（）o

A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;

B、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink;

C、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s;

D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;

14、在一個長度為n的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（）操作與鏈表的長度無關(guān)。

A、刪除單鏈表中的第一個元素B、刪除單鏈表中最后一個元素C、在單鏈表第一個元素前插入一個

新元素D、在單鏈表最后?個元素后插入一個新元素

15、線性結(jié)構(gòu)中的一個結(jié)點代表一個（）

A、數(shù)據(jù)元素B、數(shù)據(jù)項C、數(shù)據(jù)D、數(shù)據(jù)結(jié)構(gòu)

16、非空線性表L=（ai,a2,…,a，…,an）,下列說法正確的是（）

A、每個元素都有一個直接前驅(qū)和直接后繼

B、線性表中至少要有一個元素

C、表中諸元素的排列順序必須是由小到大或由大到小的

D、除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼

17、順序表是線性表的（）

A、鏈式存儲結(jié)構(gòu)B、順序存儲結(jié)構(gòu)C、索引存儲結(jié)構(gòu)D、散列存儲結(jié)構(gòu)

18、對于順序表，以下說法錯誤的是（）

A、順序表是用--維數(shù)組實現(xiàn)的線性表，數(shù)組的下標可以看成是元素的絕對地址

B、順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列

C、順序表的特點是:邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰

D、順序表的特點是:邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中

19、對順序表上的插入、刪除算法的時間復(fù)雜性分析來說，通常以（）為標準操作。

A、插入操作B、結(jié)點移動C、算術(shù)表達式D、刪除操作

20、對于順序表的優(yōu)缺點，以下說法錯誤的是（）

A、無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間

B、可以方便地隨機存取表中的任一結(jié)點

C、插入和刪除運算較方便

D、山于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進行（靜態(tài)分配）

21、若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（）存儲方式最節(jié)

省時間。

A、順序表B、單鏈表C、雙鏈表D、單循環(huán)鏈表

22、循環(huán)鏈表主要優(yōu)點是（）

A、不再需要頭指針了

B、已知某個結(jié)點的位置后，能夠容易找到它的直接前趨

C、在進行插入、刪除運算時，能更好地保證鏈表不斷開

D、從表中任一結(jié)點出發(fā)都能掃描到整個鏈表

23、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是（）

A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表

二、填空題

1、在線性結(jié)構(gòu)中，第一個結(jié)點（）前趨結(jié)點，其余每個結(jié)點有且只有（）個前趨結(jié)點。

2、在順序表中插入或刪除一個元素，需要平均移動（）元素，具體移動的元素個數(shù)與（）有關(guān)?

3、已知L是無表頭結(jié)點的單鏈表，試從下列提供的答案中選擇合適的語句序列，分別實現(xiàn)：

（1）表首插入S結(jié)點的語句序列是（）。

（2）表尾插入S結(jié)點的語句序列是（）。

A、P->next=S;B、P=L;C、L=S;D、P->next=S->next;E、S->next=P->next;F、S->next=L;G、

S->next=NULL;H、while（P->next!=Q）p=p->next;I、while（P->nexl!=NULL）P=P->next;

4、已知L是帶表頭結(jié)點的非空單鏈表，試從下列提供的答案中選擇合適的語句序列。

（1）刪除首元結(jié)點的語句序列是（），（2）刪除尾元結(jié)點的語句序列是（）

A、P=P->next;B、P->next=P->next->next;

C、while（P!=NULL）p=p->next;

D、while（Q->next!=NULL）{P=Q;Q=Q->next;}

E^while（P->next!=Q）P=P->next;

F、Q=P;G^Q=P->next;H、P=L;I、L=L->next;

J、free（Q）;

5、已知L是帶表頭結(jié)點的非空鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中

選擇合適的語句序列。（1）刪除P結(jié)點的直接后繼結(jié)點的語句序列是（），（2）刪除P結(jié)點的

直接前趨結(jié)點的語句序列是（）

A、P->next=P->next->next;B、P=P->Pnext->next;

C、while（P->next!=Q）P=P->next;

D、while（P->next->next=Q）P=P->next;E、Q=P;

F、Q=P->next;G、P=L;

H、L=L->next;I、free（Q）;

6、已知結(jié)點編號，在各結(jié)點查找概率相等的情況下，從n個結(jié)點的單鏈表中查找一個結(jié)點，平均要訪問（）

個結(jié)點，從n個結(jié)點的雙鏈表中查找一個結(jié)點，平均要訪問（）個結(jié)點。

7、對于一個具有n個結(jié)點的單鏈表，在已知p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是（）；在值域

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

8、單鏈表是（）的鏈接存儲表示。

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

10、在單鏈表中，除首元結(jié)點外，任一結(jié)點的存儲位置由()指示。

11、在非空雙向循環(huán)鏈表中，在結(jié)點q的前面插入結(jié)點p的過程如下：

p->prior=q->prior;q->prior->next=p;p->next=q;();

12、在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向(),另一個指向()。

13、順序表中邏輯上相鄰的元素的物理位置()相鄰。單鏈表中邏輯上相鄰的元素的物理位置()

相鄰。

14、為了便于討論，有時將含n(n20)個結(jié)點的線性結(jié)構(gòu)表示成(a“a?,…,aj,其中每個去代表一個。

ai稱為結(jié)點,a"稱為結(jié)點,i稱為由在線性表中的。對任意一對相鄰結(jié)點ai、a+i(lWi<n),ai

稱為ai+i的直接，ai+i稱為4的直接。

15、線性結(jié)構(gòu)的基本特征是：若至少含有一個結(jié)點，則除起始結(jié)點沒有直接外，其他結(jié)點有且僅有一

個直接;除終端結(jié)點沒有直接外，其它結(jié)點有且僅有一個直接.

16、所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是結(jié)構(gòu)。

17、線性表的邏輯結(jié)構(gòu)是結(jié)構(gòu)。其所含結(jié)點的個數(shù)稱為線性表的o

18、在單鏈表中，指針p所指結(jié)點為最后??個結(jié)點的條件是o

三、判斷題

1.順序存儲的線性表可以隨機存取。

2.順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因為平均每次操作只有近一半的元素需要

移動。

3.線性表中的元素可以是各種各樣的，但同?線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同?數(shù)據(jù)

對象。

4.在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。

5.在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。

6.在單鏈表中，可以從頭結(jié)點進行查找任何一個元素。

7.線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。

8.在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關(guān)。

9.在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)。

10.順序存儲方式只能用于存儲線性結(jié)構(gòu)。

四、簡答題

1、若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用哪種存儲結(jié)構(gòu)？為什么？

2、描述概念：頭指針、頭結(jié)點、首元結(jié)點的區(qū)別？

3、設(shè)A是一個線性表(aia2...an),采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需

要移動的元素個數(shù)為多少？若元素插在為與ai+i之間(0<=k=n-l)的概率為2(n-i)/(n(n+l)),則平均

每插入一個元素所要移動的元素個數(shù)又是多少？

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

5、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某個結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈

表中刪除？若可以，其時間復(fù)雜度各為多少？

6、下列算法的功能是什么？

LinkedListtestl(LinkedListL)

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

ListNode*q,*p;

if(L&&L->next)

{q=L;L=L->next;p=L;

while(p->next)p=p->next;

p->next=q;q->next=NULL;

)

returnL;

)

7、如果有n個線性表同時共存，并且在處理過程中各表的長度會發(fā)生動態(tài)變化，線性表的總長度也會

自動地改變。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)。為什么？

8、若線性表的總數(shù)基本穩(wěn)定，且很少進行插入刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)

該用哪種存儲結(jié)構(gòu)。為什么？

9、設(shè)有多項式a(x)=9+8x+9x4+5xi°

b(x)=-2x+22x7-5x10

(1)用單鏈表給出a(x)、b(x)的存儲表示；

(2)設(shè)c(x)=a(x)+b(x),求得c(x)并用單鏈表給出其存儲表示。

五、設(shè)計題

1、編寫一個函數(shù)將一個順序表A(有多個元素且任何元素不為0)分拆成兩個順序表，使A中大于0

的元素存放在B中，小于0的元素存放在C中。

2、設(shè)順序表L中的數(shù)據(jù)元素遞增有序。試寫一算法，將e插入到順序表的適當(dāng)位置，插入后保持該表

的有序性。

3、A、B為元素遞增有序排列的單鏈表(同一表中可能有相同元素)，編寫算法另建一單鏈表C,保存

兩個表的公共元素，要求C的元素值各不相同且遞增有序。

4、設(shè)有一個由正整數(shù)組成的無序單鏈表，編寫算法實現(xiàn)下列功能：

(1)找出最小值結(jié)點，且顯示該數(shù)值。

(2)若該數(shù)值為奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換。

(3)若為偶數(shù)，則將其直接后繼結(jié)點刪除。

六、編程附加題

1.試分別用順序表和單鏈表作為存儲結(jié)構(gòu)，實現(xiàn)將線性表(a0,ai,a2,.…a.)就地逆置的操作，所謂“就地”

指輔助空間為O(Do

2.設(shè)順序表L是一個遞增(允許有相同的值)有序表，試寫一算法將x插入L中，并使L仍為一個有序

表。

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

4.試寫出在無頭結(jié)點的單鏈表的第i個元素之前插入一個元素的算法。

5.設(shè)A、B是兩個線性表，其表中元素遞增有序，長度分別為m和n。試寫一算法分別以順序存儲和鏈式

存儲將A和B歸并成一個仍按元素值遞增有序的線性表C,請分析算法的時間復(fù)雜度。

6.設(shè)指針la和1b分別指向兩個無頭結(jié)點的單鏈表的首結(jié)點，設(shè)計從表la中刪除第i個元素起共len個元素，

并將這些元素插入到1b中第j個結(jié)點之前的算法。

7.單鏈表L是一個遞減有序表，試寫一高效算法，刪除表中值大于min且小于max的結(jié)點(若表中有這樣

的結(jié)點)，同時釋放被刪結(jié)點空間，這里min和max是兩個給定的參數(shù)。請分析你的時間復(fù)雜度。

8.編寫一個算法將一個頭結(jié)點指針為pa的單鏈表A分解成兩個單鏈表A和B,其頭結(jié)點指針分別為pa和

pb,使得A鏈表中含有鏈表A中的序號為奇數(shù)的元素，而B鏈表中含有原鏈表A中的序號為偶數(shù)的元

素，且保持原來的相對順序。

9.假設(shè)以兩個元素依值遞增有序排列的線性表A,B分別表示兩個集合，先要求另辟空間構(gòu)造一個線性表

C,其元素為兩集合的交集，且表C中的元素也依值遞增有序排列。是對順序表編寫求C的算法。

10.設(shè)有線性表A=(ai,a2,...所)和B=(bi,b2,..息)。試寫合并A、B為線性表C的算法,使得:

c=f(?i,am,b,?,bm+x,b.)寺m<n\

l(q,伍an,bn,an+}當(dāng)m>n;

線性表A,B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表的結(jié)點空間。

11.假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點也無頭指針。S為指向鏈表中某個結(jié)點的指針，試編寫

算法刪除結(jié)點*s的直接前驅(qū)結(jié)點。

12.計算帶頭結(jié)點的循環(huán)鏈表的結(jié)點個數(shù)。

13.已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其他字符)，試

編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表使得每個表中只含有同一類的字符，且利用原表中的結(jié)點空

間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。

14.已知A,B和C為三個遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C

表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復(fù)雜度(注：題中沒特

別指明同一表中的元素值各不相同)。

15.雙向循環(huán)鏈表中，設(shè)計滿足下列條件的算法。

(1)在值為x的結(jié)點之前插入值為y的結(jié)點。

(2)刪除值為x的結(jié)點。

16.設(shè)有一個循環(huán)雙鏈表，其中有一結(jié)點的指針為P,編寫算法將P與其右邊的一個結(jié)點進行交換。

17.設(shè)有一個雙鏈表，每個結(jié)點中除有prior、data和next三個域外，還有一個可訪問頻度域freq,在鏈表被

起用之前，其值均初始為0。每當(dāng)鏈表進行一次LocateNode(L,x)運算時令元素值為x的結(jié)點中freq

域的值加1,并調(diào)整表中結(jié)點的次序，使其按訪問頻度的遞減次序排列，以便使頻繁訪問的結(jié)點總是靠

近表頭。試寫一符合上述要求的LocateNode的運算的算法。

18.給出用單鏈表存儲多項式的結(jié)構(gòu)，并編寫一個按指數(shù)值遞增次序輸入所產(chǎn)生的多項式鏈表的過程。

19.根據(jù)上題的多項式鏈表結(jié)構(gòu)，編寫一個過程實現(xiàn)兩個多項式相加的運算。

20.(Josephus環(huán))任給正整數(shù)n、k,按下述方法可得排列1,2,n的一個置換:將數(shù)字1,2,n

環(huán)形排列，按順時針方向從1開始計數(shù)；計滿K時輸出該位置上的數(shù)字(并從環(huán)中刪去該數(shù)字)，然后從

下一個數(shù)字開始繼續(xù)計數(shù)，直到環(huán)中所有數(shù)字均被輸出為止。例如，n=10,k=3時，輸出的置換是3,6,

9,2,7,1,8,5,10。分別以數(shù)組和以不帶頭結(jié)點的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu)解決上述

問題。

21已知在一維數(shù)組A[l..m+n]中依次存放著兩個向量(a,,a2”…am)和(也加，….bn),編寫算法將兩個向量的

位置互換，即把(bi,b2.....bn)放到(ai,a2......am)之前。

22給定?個不帶頭結(jié)點的單鏈表，編寫計算此鏈表長度的算法。

23設(shè)ha和hh分別是兩個帶頭結(jié)點的非遞減有序單鏈表的表頭指針，試設(shè)計一個算法，將這兩個有序鏈

表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其它的存儲

空間。表中允許有重復(fù)的數(shù)據(jù)。

24設(shè)有一個由正整數(shù)組成的無序(向后)單鏈表，編寫完成下列功能的算法：

(I)找出最小值結(jié)點，且打印該數(shù)值；

(2)若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換；

(3)若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除；

25利用順序表的操作，實現(xiàn)以下的函數(shù)。

(1)從順序表中刪除具有最小值的元素并由函數(shù)返回被刪元素的值，空出的位置由最后一個元素填補。

(2)從順序表中刪除具有給定值x的所有元素。

(3)從有序順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。

26如果以單鏈表表示集合，設(shè)計算法建立先后輸入的兩個集合的差。

27已知一個線性表中的元素按元素值非遞減有序排列，分別以順序存儲和鏈式存儲編寫一個算法刪除表中

多余的值相同的元素。

28設(shè)A=(aba2,a3，……a“)和B=(bhb2%)是兩個順序表(假定所含數(shù)據(jù)元素均為整數(shù))。若n=m且

ai=bi（i=l,...,n）廁稱A=B;若ai=bi（i=l,...,j）且aj+《bj+i（jcnWm）,則稱A<B;在其他情況下均稱A>B。是編寫一

個比較A和B的算法，當(dāng)A<B,A=B或A>B是分別輸出-1,0或者1。

29已知一個循環(huán)單鏈表如圖2.1所示，編寫一個算法將所有箭頭方向取反。

head

圖2.1

30假設(shè)有一個單循環(huán)鏈表，其結(jié)點含有三個域：prior,data,和next。其中data為數(shù)據(jù)域，next指向后繼結(jié)

點，prior為指針域，它的值為空指針，試編寫算法將此表改為雙向循環(huán)鏈表。

31設(shè)A是一個雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入一個元素x,使表A中的元素依然遞

增有序。

32寫出將雙向循環(huán)鏈表倒置的算法。

33設(shè)計一算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式各自僅有奇次幕

或偶次第項，并要求利用原鏈表中的結(jié)點空間來構(gòu)造這兩個鏈表。

34設(shè)以帶頭結(jié)點的雙向鏈表表示的線性表L=（a,,a2,...,an）,試寫一時間復(fù)雜度為0（n）的算法，將L改造為

L=（ai,a3”..,an,a4,a2）。

35設(shè)一單向鏈表的頭指針為head,鏈表的記錄中包含著整數(shù)類型的key域，試設(shè)計算法，將此鏈表的記錄

按照key遞增的順序進行就地排序。

第三章棧與隊列練習(xí)題

一、選擇題

1、棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（）。

A、順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B、散列和索引方式C、鏈表存儲結(jié)構(gòu)和數(shù)組D、線性鏈表

結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

2、設(shè)棧ST用順序存儲結(jié)構(gòu)表示，則棧ST為空的條件是（）

A^ST.top-ST.baseoOST.top-ST.base==0C、ST.top-ST.baseonD、ST.top-ST.base==n

3、向一個棧頂指針為HS的鏈棧中插入一個s結(jié)點時，則執(zhí)行（）

A^HS->next=s;s->next=HS->next;HS->next=s;C、s->next=HS;HS=s;D、s->next=HS;HS=HS->next;

4、從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行（）

A、x=HS;HS=HS->next;B、HS=HS->next;x=HS->data;C、x=HS->data;HS=HS->next;D、

s->next=Hs;Hs=HS->next;

5^表達式a*（b+c）-d的后綴表達式為（）

A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd

6、中綴表達式A-（B+C/D）*E的后綴形式是（）

A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-

7、一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是（）

A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,1

8、循環(huán)隊列SQ采用數(shù)組空間SQ.base[0,n-l]存放其元素值，已知其頭尾指針分別是front和rear,則判定此

循環(huán)隊列為空的條件是（）

A^Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+1

9、循環(huán)隊列SQ采用數(shù)組空間SQ.base[0,n-l]存放其元素值，己知其頭尾指針分別是front和rear,則判定此

循環(huán)隊列為滿的條件是（）

A^Q.front==Q.rearB、Q.front!=Q.rearC>Q.front==（Q.rear+1）%nD^Q.front!=（Q.rear+l）%n

10、若在一個大小為6的數(shù)組上實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3,當(dāng)從隊列中刪除一個

元素，再加入兩個元素后，rear和front的值分別為（）

A、1,5B、2,4C、4,2D、5,1

11、用單鏈表表示的鏈式隊列的隊頭在鏈表的（）位置

A、鏈頭B、鏈尾C、鏈中

12、判定一個鏈隊列Q（最多元素為n個）為空的條件是（）

A^Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==（Q.rear+l）%nD^Q.front!=（Q.rear+l）%n

13、在鏈隊列Q中，插入s所指結(jié)點需順序執(zhí)行的指令是（）

A、Q.front->next=s;f=s;B、Q.rear->next=s;Q.rear=s;C、s->next=Q.rear;Q.rear=s;D、

s->next=Q.front;Q.front=s;

14、在一個鏈隊列Q中，刪除一個結(jié)點需要執(zhí)行的指令是（）

A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、

Q.front=Q.rear->next;

15、用不帶頭結(jié)點的單鏈表存儲隊列，其隊頭指針指向隊頭結(jié)點，隊尾指針指向隊尾結(jié)點，則在進行出隊操

作時（）

A、僅修改隊頭指針B、僅修改隊尾指針C、隊頭尾指針都要修改D、隊頭尾指針都可能要修改。

16、棧和隊列的共同點是（）

A、都是先進后出B、都是先進先出C、只允許在端點處插入和刪除元素D、沒有共同點

17、消除遞歸（）需要使用棧。

A、一定B、不一定

18、設(shè)有一順序棧S,元素設(shè),s2,s3,s4,s5,s6依次進棧,如果6個元素出棧的順序是s2,s3,s4,s6,s5,sl,則棧的

容量至少應(yīng)該是（）

A、2B、3C、5D、6

19、若一個棧的輸入序列是a,b,c,則通過入、出棧操作可能得到a,b,c的不同排列個數(shù)為（）

A、4B、5C、6D、7

20、設(shè)有一順序棧已經(jīng)含有3個元素，如圖3.1所示元素a4正等待進棧。下列不可能出現(xiàn)的出棧序列是（）

A、a3,al,a4,a2B、a3,a2,a4,alC、a3,a4,a2,alD、a4,a3,a2,al

0maxsize-1

ala2a3

丁

Top

圖3.1

21、鏈棧和順序棧相比，有一個比較明顯的優(yōu)勢是（）

A、通常不會出現(xiàn)棧滿的情況B、通常不會出現(xiàn)?？盏那闆r

C、插入操作更容易實現(xiàn)D、刪除操作更加容易實現(xiàn)

22、若一個棧的輸入序列是1,2,3,4,…,n,輸出序列的第一個元素是n,則第i個輸出元素是（）

A、不確定B、n-iC、n-i+1D、n-i-1

23、以下說法正確的是（）

A、因鏈棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況

B、因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況

C、對于鏈棧而言，在棧滿狀態(tài)下，如果此忖再作進棧運算，則會發(fā)生“上溢”

D、對于順序棧而言在棧滿狀態(tài)下如果此時再作進棧運算，則會發(fā)生“下溢”。

二、判斷題

1、在順序棧棧滿情況下，不能做進棧運算，否則會產(chǎn)生“上溢”。

2、鏈棧與順序棧相比的一個優(yōu)點是鏈棧插入和刪除操作更加方便。

3、若一個棧的輸入序列為1,2,3,…，n,其輸出序列的第一個元素為n,則其輸出序列的每個元素

比一定滿足ai=i+l(i=l,2,…,n)。

4、在鏈隊列中，即使不設(shè)置尾指針也能進行入隊操作。

5、在對鏈隊列(帶頭指針)做出隊操作時，不會改變front指針的值。

6、循環(huán)隊列中元素個數(shù)為rear-fronto

7、一個棧的輸入序列是123,4,則在棧的輸出序列中可以得到4,3,1,2。

8、一個棧的輸入序列是123,4,則在棧的輸出序列中可以得到1,2,3,4。

9、若以鏈表作為棧的存儲結(jié)構(gòu)，則進棧需要判斷棧是否滿。

10、若以鏈表作為棧的存儲結(jié)構(gòu)，則出棧需要判斷棧是否空。

三、填空題

1、棧的特點是()，隊列的特點是()。

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

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

3、有程序如下，則此程序的輸出結(jié)果(棧的元素類型是SelemType為char)是()。

Voidmain()

{stacks;charx,y;initstack(s);x='c';y='k';

push(s,x);push(s,'a');push(s,y);

pop(s,x);push(s,,t,);push(s,x);pop(s,x)；push(s,,s,);

while(istackemply(s)){pop(s,y);printf(y);}

printf(x);}

4、在棧頂指針為HS的鏈棧中，判定棧空的條件是()。

5、向棧中壓入元素的操作是先()后()。

6、對棧進行退棧操作是先()后()。

7、用循環(huán)鏈表表示的隊列長度為n,若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別是()和()；

若只設(shè)尾指針，則出隊和入隊的時間復(fù)雜度分別是()和()。

8、從循環(huán)隊列中刪除一個元素時，其操作是()。

9、在一個循環(huán)隊列中，隊首指針指向隊首元素的()。

10、在具有n個單元的循環(huán)隊列中，隊滿時共有()個元素。

11、在HQ的鏈隊列中，判斷只有一個結(jié)點的條件是()。

12、設(shè)棧S和隊列Q的出始狀態(tài)為空，元素2力,3<1?1?依次通過棧5,一個元素出棧后即進入隊列Q。若這6

個元素出隊列的順序是b,d,c,f,e,a則棧S的容量至少應(yīng)該是()。

13、有程序如下，則此程序的輸出結(jié)果(隊列的元素類型是QSelemType為char)是()。

Voidmain()

{charx=，e',y='c';

enqueue(q,'h');enqueue(q,T);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);

enqueue(q,'a');

while(!queueempty(q)){dequeue(q,y);printf(y);)

printf(x);}

14、有如下遞歸函數(shù)：

intdunno(intm)

(intvalue;if(m==0)value=3;

elsevalue=dunno(m-l)+5;

return(value);}

執(zhí)行語句printf("％d\n”,dunno(3));的結(jié)果是()。

四、簡答題

1、對于堆棧，給出三個輸入項A,B,C,如果輸入項序列為ABC,試給出全部可能的輸出序列，并寫

出每種序列對應(yīng)的操作。例如：A進B進C進C出B出A出，產(chǎn)生的序列為CBA。

2、簡述以下算法的功能(棧的元素類型是SelemType為int)。

(1)statusalgo1(stacks)

{intI,n,a[255];n=0;while(!stackempty(s)){n++;pop(s,a[n]);}

for(I=1;I<=n;I++)push(s,a[I]);}

(2)statusalgo2(stacks,inte)

{stackt;intd;initstack(t);while(!stackempty(s)){pop(s,d);if(d!=e)push(t,d);)

while(!stackempty(t)){pop(t,d);push(s,d);}}

3、內(nèi)存中?片連續(xù)空間(不妨假設(shè)地址從0到m-l)提供給兩個棧si和s2使用，怎樣分配這部分存儲

空間，使得對任一棧僅當(dāng)這部分空間全滿時才發(fā)生溢出。

4、有遞歸過程如下：

voidprint(intw){intI;if(w!=O){print(w-l)

for(I=1;k=w;I++)printf("％3d”,w);printf("\n");}}

問：調(diào)用語句print(4)的結(jié)果是什么？

5、簡述以下算法的功能(棧和隊列的元素類型均為int)

voidalgo(queue&q)

{stacks;intd;initstack(s);

while(!