數據結構課后練習題匯編

數據結構課后練習題

第一章緒論

-、選擇題

1、數據結構被形式定義為（D,S）,其中口是（）的有限集合，S是D上的（）有限集合。

A、算法B、數據元素C、數據操作D、邏輯關系E、操作F、映象G、存儲H、關系

2、數據結構是一門研究非數值計算的程序設計問題中計算機的（（1））以及它們之間的（②）和運算

的學科。

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

（2）A、結構B、關系C、運算D、算法

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

A、給出數據結構的合理性B、研究算法中輸入輸出的關系

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

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

4、在數據結構中，從邏輯上可以把數據結構分成（）。

A、動態(tài)和靜態(tài)結構B、緊湊接和非緊湊結構

C、線性與非線性結構D、內部結構和外部結構

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

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

性、確定性和有窮性

6、線性表的順序存儲結構是一種（）的存儲結構，線性表的鏈式存儲結構是種（）

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

7、算法的時間復雜度取決于（）

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

8、線性表若采用鏈表存儲結構時，要求內存中可用存儲單元的地址（）

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

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

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

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

B、二維數組是它的每個數據元素為一個線性表的線性表

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

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

10、根據數據元素之間關系的不同特性，以下四類基本的邏輯結構反映了四類基本的

數據組織形式。以下解釋錯誤的是（）

A、集合中任何兩個結點之間都有邏輯關系但組織形式松散

B、線性結構中結點按邏輯關系依次排列形成一條“鎖鏈”

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

D、圖狀結構中的各個結點按邏輯關系互相纏繞，任何兩個結點都可以鄰接

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

A、數據元素是數據的最小單位

B、數據項是數據的基本單位

C、數據結構是帶有結構的各數據項的集合

D、數據結構是帶有結構的數據元素的集合

二、填空題

1、數據邏輯結構包括（）四種類型，樹型和圖型結構合稱（）。

2、對于給定的n個元素，可以構造出的邏輯結構有（）、（）、（）和（）四種。

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

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

5、線性結構中元素之間存在（）關系，樹型結構中元素之間存在（）關系，圖型結構中元素之間

存在（）關系。

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

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

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

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

8、所謂數據的邏輯結構指的是數據元素之間的。

9、數據結構是相互之間存在一種或多種特定關系的數據元素的集合，它包括三方面的內容。

10、在線性結構中，開始結點前驅結點，其余每個結點有且只有一個結點。

11、在樹形結構中，根結點只有,根結點無前驅，其余每個結點有且只有前驅結點；葉子結點

沒有結點，其余每個結點的后繼結點可以。

12、在圖形結構中，每個結點的前驅結點和后繼結點可以有。

13、存儲結構是邏輯結構的實現。

14、從數據結構的觀點看，通常所說的''數據”應分成三個不同的層次，即、和

15、根據需要，數據元素又被稱為、、或。

16、通常，存儲結點之間可以有、、、四種關聯方式，稱為四種

基本存儲方式。

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

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

.后者是算法需要的。

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

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

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

21、數據結構的基本任務是數據結構的和。

22、數據對象是性質相同的的集合。

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

三、判斷題

1.數據元素是數據的最小單位。

2.數據結構是帶有結構的數據元素的集合。

3.數據結構，數據元素，數據項在計算機中的映象分別稱為存儲結構，結點，數據域。

4.數據項是數據的基本單位。

5.數據的邏輯結構是指各數據元素之間的邏輯關系，是用戶按使用需要建立的。

6.數據的物理結構是數據在計算機中實際的存儲形式。

7.算法和程序沒有區(qū)別，所以在數據結構中二者是通用的。

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

四、計算應用題

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

（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í)行函數調用語句perm(a,l,n)

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

(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、有下列幾種用二元組表示的數據結構，畫出它們對應的邏輯圖形表示，并指出它們屬于哪種結構。

(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、設有如圖所示的邏輯結構圖，給出它的邏輯結構。

KI

6、簡述下列術語：數據，數據元素，數據結構，數據對象。

7、邏輯結構與存儲結構是什么關系？

2n2）

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

五、算法設計題

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

較次數和元素移動次數。

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

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

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

第二章線性表練習題

一、選擇題

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

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

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

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

A、表元素B、字符C、數據元素D、數據項E、信息

3、”線性表的邏輯順序和物理順序總是一致的。”這個結論是（）。

A、正確的B、錯誤的C、不一定，與具體結構有關。

4、線性表采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）o

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

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

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

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

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

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

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

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

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

9、在一個單鏈表中，若刪除P所指結點的后繼結點，則執(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所指結點之后插入S所指結點，則執(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的前趨結點，若q和p之間插入結點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、假設雙鏈表結點的類型如下：

typedefstructlinknode{

intdata;//數據域

structlinknode*llink;//指向前趨結點的指針域

structlinknode*rlink;//指向后繼結點的指針域

}bnode

現將一個q所指新結點作為非空雙向鏈表中的p所指結點的前趨結點插入到該雙鏈表中，能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、如上題結點結構，如在此非空循環(huán)雙向鏈表的結點p之后插入結點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的單鏈表上，設有頭和尾兩個指針，執(zhí)行（）操作與鏈表的長度無關。

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

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

15、線性結構中的一個結點代表一個（）

A、數據元素B、數據項C、數據D、數據結構

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

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

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

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

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

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

A、鏈式存儲結構B、順序存儲結構C、索引存儲結構D、散列存儲結構

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

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

B、順序表的所有存儲結點按相應數據元素間的邏輯關系決定的次序依次排列

C、順序表的特點是:邏輯結構中相鄰的結點在存儲結構中仍相鄰

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

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

A、插入操作B、結點移動C、算術表達式D、刪除操作

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

A、無需為表示結點間的邏輯關系而增加額外的存儲空間

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

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

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

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

省時間。

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

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

A、不再需要頭指針了

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

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

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

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

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

二、填空題

1、在線性結構中，第一個結點（）前趨結點，其余每個結點有且只有（）個前趨結點。

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

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

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

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

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是帶表頭結點的非空單鏈表，試從下列提供的答案中選擇合適的語句序列。

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

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是帶表頭結點的非空鏈表，且P結點既不是首元結點，也不是尾元結點，試從下列提供的答案中

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

直接前趨結點的語句序列是（）

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、已知結點編號，在各結點查找概率相等的情況下，從n個結點的單鏈表中查找一個結點，平均要訪問（）

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

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

為給定值的結點后插入一個新結點的時間復雜度是（）。

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

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

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

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

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

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

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

相鄰。

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

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

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

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

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

16、所有結點按1對1的鄰接關系構成的整體就是結構。

17、線性表的邏輯結構是結構。其所含結點的個數稱為線性表的o

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

三、判斷題

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

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

移動。

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

對象。

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

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

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

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

8.在線性表的順序存儲結構中，插入和刪除元素時，移動元素的個數與該元素的位置有關。

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

10.順序存儲方式只能用于存儲線性結構。

四、簡答題

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

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

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

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

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

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

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

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

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

LinkedListtestl(LinkedListL)

{//L是無頭結點的單鏈表

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)變化，線性表的總長度也會

自動地改變。在此情況下，應選擇哪一種存儲結構。為什么？

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

該用哪種存儲結構。為什么？

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

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

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

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

五、設計題

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

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

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

的有序性。

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

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

4、設有一個由正整數組成的無序單鏈表，編寫算法實現下列功能：

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

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

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

六、編程附加題

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

指輔助空間為O(Do

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

表。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

l(q,伍an,bn,an+}當m>n;

線性表A,B和C均以單鏈表作存儲結構，且C表利用A表和B表的結點空間。

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

算法刪除結點*s的直接前驅結點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18.給出用單鏈表存儲多項式的結構，并編寫一個按指數值遞增次序輸入所產生的多項式鏈表的過程。

19.根據上題的多項式鏈表結構，編寫一個過程實現兩個多項式相加的運算。

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

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

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

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

問題。

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

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

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

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

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

空間。表中允許有重復的數據。

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

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

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

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

25利用順序表的操作，實現以下的函數。

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

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

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

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

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

多余的值相同的元素。

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

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

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

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

head

圖2.1

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

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

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

增有序。

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

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

或偶次第項，并要求利用原鏈表中的結點空間來構造這兩個鏈表。

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

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

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

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

第三章棧與隊列練習題

一、選擇題

1、棧結構通常采用的兩種存儲結構是（）。

A、順序存儲結構和鏈表存儲結構B、散列和索引方式C、鏈表存儲結構和數組D、線性鏈表

結構和非線性存儲結構

2、設棧ST用順序存儲結構表示，則棧ST為空的條件是（）

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

3、向一個棧頂指針為HS的鏈棧中插入一個s結點時，則執(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的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執(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采用數組空間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采用數組空間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的數組上實現循環(huán)隊列，且當前rear和front的值分別為0和3,當從隊列中刪除一個

元素，再加入兩個元素后，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所指結點需順序執(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中，刪除一個結點需要執(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、用不帶頭結點的單鏈表存儲隊列，其隊頭指針指向隊頭結點，隊尾指針指向隊尾結點，則在進行出隊操

作時（）

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

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

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

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

A、一定B、不一定

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

容量至少應該是（）

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

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

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

20、設有一順序棧已經含有3個元素，如圖3.1所示元素a4正等待進棧。下列不可能出現的出棧序列是（）

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、通常不會出現棧滿的情況B、通常不會出現棧空的情況

C、插入操作更容易實現D、刪除操作更加容易實現

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

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

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

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

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

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

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

二、判斷題

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

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

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

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

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

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

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

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

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

9、若以鏈表作為棧的存儲結構，則進棧需要判斷棧是否滿。

10、若以鏈表作為棧的存儲結構，則出棧需要判斷棧是否空。

三、填空題

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

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

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

3、有程序如下，則此程序的輸出結果(棧的元素類型是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的鏈棧中，判定?？盏臈l件是()。

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

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

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

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

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

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

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

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

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

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

13、有程序如下，則此程序的輸出結果(隊列的元素類型是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、有如下遞歸函數：

intdunno(intm)

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

elsevalue=dunno(m-l)+5;

return(value);}

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

四、簡答題

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

出每種序列對應的操作。例如：A進B進C進C出B出A出，產生的序列為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、內存中?片連續(xù)空間(不妨假設地址從0到m-l)提供給兩個棧si和s2使用，怎樣分配這部分存儲

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

4、有遞歸過程如下：

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

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

問：調用語句print(4)的結果是什么？

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

voidalgo(queue&q)

{stacks;intd;initstack(s);

while(!