2023年春電大數(shù)據(jù)結構形考答案

一、單項選擇題

1.C2.D3.B4.C5.D6.C7.B8.C9.A10.B*

11.C12.D13.C14.A15.B16.C17.C18.B19.B20.D

A

二、填空題lA&.n-i+l

△2.n-iA

3.集合線性結構樹形結構圖狀結構A

4.物理結構存儲結構

a5.線性結構非線性結構△

6.有窮性擬定性可形性有零個或多個輸入有零個或多個輸出7AA.圖狀結構A

8.樹形結構

9.線性結構

A10.n—1O(n)A

11.s—>next=p->next;

A12.head13.q—>next=p->next;l"A.p->next=head;A

15.單鏈表

16.順序存儲鏈式存儲

17.存儲結構

A18.兩個直接后繼直接前驅尾結點頭結點AA19.頭結點的指針指向第一個結點的

指針

A20.鏈式鏈表A

A三、問答題

1.簡述數(shù)據(jù)的邏輯結構和存儲結構的區(qū)別與聯(lián)系，它們如何影響算法的設計與實現(xiàn)?

答：若用結點表達某個數(shù)據(jù)元素，則結點與結點之間的邏輯關系就稱為數(shù)據(jù)的邏輯結構。數(shù)

據(jù)在計算機中的存儲表達稱為數(shù)據(jù)的存儲結構?？梢姡瑪?shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間的固

有關系，而數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表達。盡管因采用的存儲結構不同，邏

輯上相鄰的結點，其物理地址未必相同，但可通過結點的內部信息，找到其相鄰的結點，從

而保存了邏輯結構的特點。采用的存儲結構不同，對數(shù)據(jù)的操作在靈活性，算法復雜度等方

面差別較大。4

A2.解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的優(yōu)缺

陷。

A答：4順序結構存儲時,相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結構和存儲結構是統(tǒng)一的，，

規(guī)定內存中存儲單元的地址必須是連續(xù)的。八

優(yōu)點:一般情況下,存儲密度大，存儲空間運用率高。

缺陷：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預先分派較大的

空間，往往使存儲空間不能得到充足運用;⑶表的容量難以擴充。

鏈式結構存儲時，相鄰數(shù)據(jù)元素可隨意存放,所占空間分為兩部分，一部分存放結點值，另一部

分存放表達結點間關系的指針。4優(yōu)點:插入和刪除元素時很方便，使用靈活。

△缺陷：存儲密度小，存儲空間運用率低。

43.什么情況下用順序表比鏈表好？

△答：順序表適于做查找這樣的靜態(tài)操作，鏈表適于做插入和刪除這樣的動態(tài)操作。假如線

性表的變化長度變化不大，且其重要操作是查找，則采用順序表；假如線性表的長度變化較

大，且其重要操作是插入、刪除操作,則采用鏈表。

-4.解釋頭結點、第一個結點(或稱首元結點)、頭指針這三個概念的區(qū)別？

答:A

頭結點是在鏈表的開始結點之前附加的一個結點；第一個結點(或稱首元結點)是鏈表中存

儲第一個數(shù)據(jù)元素的結點；頭指針是指向鏈表中第一個結點(或為頭結點或為首元結點)的指

針。

A5.解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別。A

答：4帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別重要體現(xiàn)在其結構上和算法操作上。

A在結構上，帶頭結點的單鏈表，不管鏈表是否為空，均具有一個頭結點，不帶頭結點的單鏈表

不含頭結點。

A在操作上，帶頭結點的單鏈表的初始化為申請一個頭結點。無論插入或刪除的位置是地第

一個結點還是其他結點，算法環(huán)節(jié)都相同。不帶頭結點的單鏈表，其算法環(huán)節(jié)要分別考慮插

入或刪除的位置是第一個結點還是其他結點。由于兩種情況的算法環(huán)節(jié)不同。4

AAA四、程序填空題

1.A

(l)p->data=N

(2)p->next=NULL3(.*-*)q->next=p

(4)q=P

A

A2.A

(1)head=pAn(2)q=p3(aa)p->next=NULL

(4)p->next=q->next

(5)q—>next=pA

3.AA(i)p=q->nexU

(2)q->next=p->nex

4五、完畢：實驗1一一線性表4根據(jù)實驗規(guī)定(見教材P201-202)認真完畢本實驗，并提交

實驗報告。-

作業(yè)2答案(本部分作業(yè)覆蓋教材第3-5章的內容)

AA一、單項選擇題

1.C2.B3.A4.C5.B6.A7.B8.C9.A10.C

A1l.B12.C13.B14.B15.A16.C17.B18.A19.C20.D

△2l.B22.D23.C24.B25.D26.A27.C28.D29.D30.C31.A32.DAA

A二、填空題4*1.后進先出42.下一個A

3.增1增1A&4.假上溢

5.

A棧是否滿s->top=MAXSIZE-1棧頂指針棧頂相應的數(shù)組元素棧是否空s->top=

-1棧頂元素修改棧頂指針AA6.bceda*

7.終止條件遞歸部分8AA.LU—>front==LU->rear*

9.運算符操作數(shù)ab+c/fde/------A

lO.s—>next=h;

11.h=h->next；A

12.r—>next=s；IAA3.f=f->next;

Al4.字符A

15.順序存儲方式鏈式存儲方改

16.0空格字符的個數(shù)A

17.特殊稀疏A

18.()(())2A

19.((d,e,f))

串長度相等且相應位置的字符相等行下標、列下標、非零元

20.21AA.j(j-1)/2+j22AA.

素偉

三、問答題

1.簡述棧和一般線性表的區(qū)別。A

答：棧是一種先進后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表

可以在線性表的任何位置進行插入和刪除操作。

2.簡述隊列和一般線性表的區(qū)別。AA隊列是一種先進先出的線性表，隊列的插入只能在隊尾

進行,隊列的刪除只能在隊頭進行，而一般的線性表可以在線性表的任何位置進行插入和刪除

操作。AA

3.鏈棧中為什么不設頭結點？-答：由于鏈棧只在鏈頭插入和刪除結點，不也許在鏈表中間插

入和刪除結點，算法實現(xiàn)很簡樸，所以一般不設立頭結點。3

A

4.運用一個棧，則：

*(1)假如輸入序列由A,B,C組成，試給出所有也許的輸出序列和不也許的輸出序列。2(一)

假如輸入序列由A,B,C,D組成，試給出所有也許的輸出序列和不也許的輸出序列。

答：

(1)棧的操作特點是后進先出，因此輸出序列有:"A入，A出，B入,B出，C入C出，輸出序

列為ABC。

A入，A出，B入，C入,C出，B出，輸出序列為ACB。&

A入,B入,B出,A出,C入,C出，輸出序列為BAC。AAA入,B入,B出，C入，C出，A出，輸出

序列為BCAo

A入，B入，C入,C出，B出,A出，輸出序列為CBA。

由A,B,C組成的數(shù)據(jù)項，除上述五個不同的組合外，尚有一個C,A,B組合。但不也許先

把C出棧，再把A出棧，(A不在棧頂位置)，最后把B出棧，所以序列CAB不也許由輸入序

列A,B,C通過棧得到。4(2)按照上述方法，也許的輸出序列有：

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

CDBA,DCBAe

△不也許的輸出序列有:

DABC,ADBC,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABD

A

A5.用S表達入棧操作，X表達出棧操作，若元素入棧順序為1234,為了得到1342出棧順序,

相應的S和X操作串是什么？A

答:應是SXSSXSXXo各操作結果如下*

S1入棧

△X1出棧輸出序列:1

&S2入棧

S3入棧

&X3出棧輸出序列：13A

S4入棧

X4出棧輸出序列：134*

X2出棧輸出序列:1342馬

A

6.有5個元素，其入棧順序為：A、B、C、D、E,在各種也許的出棧順序中,以元素C、D

最先的順序有哪兒個？△

答:從題中可知，要使C第一個且D第二個出棧，應是A入棧,B入棧，C入棧，C出棧，D入棧。

之后可以有以下幾種情況：

(1)B出棧，A出棧，E入棧，E出棧,輸出序列為：CDBAE。

(2)B出棧，E入棧,E出棧,A出棧，輸出序列為CDBEA。*

(3)E入棧,E出棧，B出棧，A出棧，輸出序列為CDEBA*

所以也許的順序有:CDBAE,CDBEA,CDEBA

A7.寫出以下運算式的后綴算術運算工6

(1)3x2+x-l/x+5

A(2)(A+B)*C-D/(E+F)+G

A答；相應的后綴算術運算式AA⑴3X2A*X+1X/-5+AA⑵AB+C*DEF+/-G2A

簡述廣義表和線性表的區(qū)別和聯(lián)系。A

答:廣義表是線性表的的推廣,它也是n(n>0)個元素al,a2...ai...an的有限序列，其中ai或者

是原子或者是一個廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結構，而線性表沒有這種特性，線

性表可以當作廣義表的特殊情況，當ai都是原子時，廣義表退化成線性表。

八四、程序填空題A

1.A

(1)q—>front->next=p->next;

A(2)free(p)泠

(3)q->rear=q->front

五、綜合題

ALA

答：出隊序列是e2,e4,e3,e6,e5,e1的過程：心⑴el入棧(棧底到棧頂元素是el)AA⑵

e2入棧(棧底到棧頂元素是el,e2)A

⑶e2出棧(棧底到棧頂元素是e1)

(4)e3入棧(棧底到棧頂元素是el,e3)4⑸e4入棧(棧底到棧頂元素是el,e3,e4)

A

（6）e4出棧（棧底到棧頂元素是el,e3）

⑺e3出棧（棧底到棧頂元素是e1^（8）e5入棧（棧底到棧頂元素是el,e5）4⑼e6入

棧（棧底到棧頂元素是el,e5,e6）

A⑩e6出棧（棧底到棧頂元素是el,e5）

（IDe5出棧（棧底到棧頂元素是el）

A（12）el出棧（棧底到棧頂元素是空）

△棧中最多時有3個元素，所以棧S的容量至少是3。

2.4算法設計如下:4/*只有一個指針rear的鏈式隊的基本操作*/

A#include<stdio,h>*Atypedefcharelemtype；AAstructnode/*定義鏈隊列結

點*/

乂

△elemtypedata；

structnode*next;^A}；A

typedefstruetqueue/*定義鏈隊列數(shù)據(jù)類型*/4{

Astructnode*rear；A

}LinkQueue；A

AAvoidinitqueue(LinkQueue*Q)/*初始化隊列*/—{

Q=(structqueue*)malloc(sizeof(structqueue))戶

Q->rear=NULL;

AAVoidenqueue(LinkQueue*Q,elemtypex)/*入隊算法*/

{A

structnode*s,*p;A

s=(structnode*)malloc(sizeof(structnode))；AAs->data=x；a

if(Q->rear==NULL)/*原為空隊時57A

(

AQ—>rear=s;AAs->next=s;

A}

else/*原隊不為空時*/

(

Ap=Q->rear->next；/*p指向第一個結點*/

AQ-Arear->next=s;/*將s鏈接到隊尾*/

Q->rear=s;/*Q->rear指向隊尾*A

s—>next=p；AA}AA}

AAAVOiddelqueue(LinkQueue*Q)/*出隊算法*/

structnode*t;AAif(Q->rear==NULL)A{AA

Printf(H隊列為空!\n”)；

Areturn(0)；AA}

△elseif(Q->rear->next==Q->reaij/*只有一個結點時*/A

9

t=Q->rear;

AQ—>rear=NULL；

A}AAelse/*