國開數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案 (一)

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2020秋季

第一章緒論

一、選擇題

1、把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏緝結(jié)構(gòu)稱為（）。

A.給相關(guān)變量分配存儲(chǔ)單元

B.物理結(jié)構(gòu)

C.算法的具體實(shí)現(xiàn)

D.邏輯結(jié)構(gòu)

、下列說法中，不正確的是（）

2o

A.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位

B.數(shù)據(jù)元素是數(shù)據(jù)的基本單位

C,數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成

D.數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成

3、一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（）。

A.數(shù)據(jù)元素

B.數(shù)據(jù)結(jié)構(gòu)

C.數(shù)據(jù)項(xiàng)

D.數(shù)據(jù)類型

4、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）。

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

B.物理和存儲(chǔ)結(jié)構(gòu)

C.物理結(jié)構(gòu)

D.邏輯結(jié)構(gòu)

5、下列的敘述中，不屬于算法特性的是（）。

A.可行性

B.輸入性

C.可讀性

D.有窮性

6、算法的時(shí)間復(fù)雜度與（）有關(guān)。

A.計(jì)算機(jī)的操作系統(tǒng)

B.算法本身

C,數(shù)據(jù)結(jié)構(gòu)

D.所使用的計(jì)算機(jī)。

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

i=s=O;

while(s<n){

i++；

s+=i;

}

A.O(n0.5)B.O(log2n)C.0(n)D.O(l)

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

intffunsignedintn){

if(n==0||n==l)return1;

elsereturnn*f(n-l);

}

A.O(l)B.O(log2n)C.O(n!)D.O(n)

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

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

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

11、執(zhí)行下面程序段時(shí)，執(zhí)行S語句的次數(shù)為（）。

for(inti=l;i<=n;i++)

for(intj=l;i<=i;j++)

S；

A.n2B.n2/2C.n(n+1)D.n(n+l)/2

12、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（

A.數(shù)據(jù)元素間的關(guān)系的表示

B.數(shù)據(jù)處理的方法

C.數(shù)據(jù)元素的類型

D.相關(guān)算法

13、樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

A.一對(duì)一

B.多對(duì)多

C.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

D.一對(duì)多

14、一種邏輯結(jié)構(gòu)（）。

A.與存儲(chǔ)該邏輯結(jié)構(gòu)的計(jì)算機(jī)相關(guān)

B.只能有唯一的存儲(chǔ)結(jié)構(gòu)

C.可以有不同的存儲(chǔ)結(jié)構(gòu)

D.是指某一種數(shù)據(jù)元素的性質(zhì)

15、把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（）o

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

B.數(shù)據(jù)元素的存儲(chǔ)

C.存儲(chǔ)結(jié)構(gòu)

D,給數(shù)據(jù)元素分配存儲(chǔ)空間

二、判斷題

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

2.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立

的。（）

3.算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的。（）

4.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（）

5.算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有

效性。（）

6.只有用面向?qū)ο蟮挠?jì)算機(jī)語言才能描述數(shù)據(jù)結(jié)構(gòu)算法。（）

7.數(shù)據(jù)元素可以有一人或多個(gè)數(shù)據(jù)項(xiàng)組成。（）

8.數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。（）

3、intsum2(intn)

ints=0;

for(int1=1;l<=n;I++){

intp=l;

for(intj=l;j<=l;j++)

P*=j；

s+=p；

)

returns;

)

4、intfun(intn)

(

int1=1,s=l;

while(s<n)

s+=++l;

returnI;

)

第二章線性表

一、選擇題

1、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新

表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（）。

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

2、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（）o

A.IB.n-i-1C.n-iD.n-i+1

3、在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相知的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所

指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語句（）。

A.q->next=NULLB.p->next=q->next

C.p=q->nextD.p->next=q

4、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）o

A.p->next=s;s->next=p->nextB.p->next=s->next;

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

5、非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head,指針p指向尾結(jié)

點(diǎn)）。

A.p->next==headB.p==NULL

C.p==headD.p->next==NULL

、鏈表不具有的特點(diǎn)是（）

60

A.不必事先估計(jì)存儲(chǔ)空間

B.可隨機(jī)訪問任一元素

C.邏輯上相鄰的元素在物理位置上不一定相鄰

D.插入刪除不需要移動(dòng)元素

7、帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（）（設(shè)頭指針為head）。

A.head->next==head

B.head==NULL

C.head->next==NULL

D.head!=NULL

8、在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開始從后到

前依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（）。

A.19B.21C.20D.25

9、有關(guān)線性表的正確說法是（）o

A.線性表至少要求一個(gè)元素

B.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

C.表中的元素必須按由小到大或由大到下排序

D.除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)

直接后繼

10、向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來的順序不變,

平均要移動(dòng)（）個(gè)元素。

A.63.5B.7

C.63D.8

11、一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90,每個(gè)元素的長(zhǎng)度為2,則第6個(gè)元

素的地址是（）o

A.106B.98

C.102D.100

12、在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)

點(diǎn)，現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)。

可用的語句是p=p->next;和（）o

A.q->next=pB.p->next=q

C.q=pD.p=q->next

13、在線性表的順序結(jié)構(gòu)中，以下說法正確的是（）o

A.邏輯上相鄰的元素在物理位置上不一定相鄰

B.數(shù)據(jù)元素是不能隨機(jī)訪問的

C.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高

D.邏輯上相鄰的元素在物理位置上也相鄰

14、對(duì)鏈表，以下敘述中正確的是（）。

A.不能隨機(jī)訪問任一結(jié)點(diǎn)

B.插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)

C.結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的

D.可以通過下標(biāo)對(duì)鏈表進(jìn)行直接訪問

15、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新

表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（）。

A.n-i+1B.i

C.n-i-1D.n-i

16、在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行

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

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

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

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

17、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p

之間插入s結(jié)點(diǎn)，則以下操作哪個(gè)是正確的（）。

A.s->next=p->next；p->next=s；

B.p->next=s->next；s->next=p；

C.p->next=s；s->next=q；

D.q->next=s；s->next=p；

、在循環(huán)雙鏈表的所指結(jié)點(diǎn)之后插入所指結(jié)點(diǎn)的操作是（）

18psc

A.p->right=s；s->left=p：p->right->left=s；s->right=p->right；

B.p->right=s；p->right->left=s；s->left=p；s->right=p->right；

C.s->left=p；s->right=p->right：p->right=s；p->right->left=s；

D.s->left=p；s->right=p->righl；p->right->leri=s；p->righl=s；

19、若HL為一個(gè)不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表的表頭指針，若有HL->next=二HL

條件存在，則該循環(huán)單鏈表是（）o

A.空表B.只有1個(gè)元素；

C.空表或只有一個(gè)元素D.非空表

20、若HL為一個(gè)帶表頭結(jié)點(diǎn)的單鏈表的表頭指針，則該表為空表的條件是

()o

A.HL==NULLB.HL->next==NULL

C.HL->next==HLD.HL!=NULL

21、設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn)，則通過以下操作

()可使其成為單向循環(huán)鏈表。

選擇一項(xiàng)：

A.head=p;B.p=head;

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

二、判斷題

1、設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,指針p指向尾

結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語句p=p->npxt；c()

2、設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,p指向尾結(jié)點(diǎn),

為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next二head。()

3、設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,指針p指向

表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next==head;的結(jié)果為真，則p所指結(jié)點(diǎn)為尾垢點(diǎn)。

()

4、要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈

表中結(jié)點(diǎn)的指針域?yàn)閚ext,可執(zhí)行p->next=s;s->next=p->next；的操作。［)

5、要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前

驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,則可執(zhí)行q->next=p->next。()

6、要在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)

的單向循環(huán)鏈表，若結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,尾指針為p,則可執(zhí)

行hedd=hedd->next;p->nexl=hedd；。()

7、設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為head,鏈表中結(jié)點(diǎn)的指針域?yàn)閚ex3P指

向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)

行操作p->next=head；。()

8、設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為3K)

9、線性表用關(guān)鍵字的順序方式存儲(chǔ)，可以用二分法排序。()

10、線性表用順序方式存儲(chǔ)可以隨機(jī)訪問。()

三、程序填空

1、設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以下程序的功

能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data,完成程序中空格部分。

#defineNULL0

voidmain()

{NODE*head,*p;

p=head;/*p為工作指針*/

do

{printf(/z%d\n；

[1]；

[2];

}while

[3]；

2、設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)

點(diǎn)類型的指針變量，P指向鏈表中結(jié)點(diǎn)。，(設(shè)置表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)口

的數(shù)據(jù)域相同)，寫出相關(guān)語句

(1)使該單向鏈表成為單向循環(huán)鏈表

(2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)

q=p;x=p->data;

while([4])q=q->next;

q->next=head;

q=p;p=p->next;

while(p->data!=x)

{q=p;

[5]

)

s->next=p;

[6]

3、設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head,p、prep是指向結(jié)點(diǎn)類型

的指針，該鏈表在輸入信息時(shí)不慎把相鄰兩個(gè)結(jié)點(diǎn)的信息重復(fù)輸入，以下程序段

是在該單向鏈表中查找這相鄰兩個(gè)結(jié)點(diǎn)，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印出來，并

把其中之一從鏈表中刪除，填寫程序中的空格。

prep=head;

p=prep->next;

while(p->data!=prep->data)

(

prep=p;

[7];

)

printf("min=%d”,

[8]);

prep->next=[9]；

第三章數(shù)組和廣義表

一、選擇題

1.若讓元素1，2,3依次進(jìn)棧，則出棧順序不可能為（）o

A.3,2,1B.2,1,3

C.3,1,2D.1,3,2

2.一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4。則隊(duì)列的輸出序列是（）o

A.4,3,2,1B.1,2,3,4

C.1,4,3,2D.3,2,4,1

3.一個(gè)棧的進(jìn)棧序列是10,20,30,40,50,則棧的不可能輸出序列是（）

（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A.10,20z^0,40z50R.40,30,50,10,20

C.40,50,30,20,10D.50,40,30,20,10

4.元素4,6,8,10按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該

隊(duì)列的可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。

A.10,8,4,6B.10,6,4,8

C.8,4,6,10D.10,8,6,4

5.向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）o

A.先移動(dòng)棧頂指針，再存入元素

B.先存入元素，再移動(dòng)棧頂指針

C.先后次序無關(guān)緊要

D.同時(shí)進(jìn)行

6.在一個(gè)棧頂指針為top的鏈棧中,將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）0

A.lup->nexl=p;

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

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

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

7.在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，

則執(zhí)行（）o

A.x=top;top=top->next;

B.x=top->data;

C.top=top->next;x=top->data;

D.x=top->data;top=top->next;

8.一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（）o

A.棧B.隊(duì)列

C.堆棧或隊(duì)列D.數(shù)組

9.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）<>+++

A.abcd*+-B.abc+*d-C.abc*++d-D.-+*abcd

10.判斷一個(gè)順序隊(duì)列sq（最多元素為m）為空的條件是（）o

A.sq->rear-sq->front==mB.sq->rear-sq->front-l==m

C.sq->front==sq->rparD.sq->front==sq->rpar+1

11.判斷一個(gè)循環(huán)隊(duì)列Q（最多元素為m）為滿的條件是（）o

A.Q->front==Q->rearB.Q->front!=Q->rear

C.Q->front==（Q->rear+l）%mD.Q->front!=（Q->rear+l）%m

12.判斷棧s滿（元素個(gè)數(shù)最多n個(gè)）的條件是（）o

A.s->top==0B.s->top!=0

C.s->top==n-lD.s->top!=n-l

13.一個(gè)隊(duì)列的入隊(duì)順序是a,b,c,d,則離隊(duì)的順序是（）。

A.a,d,cbB.a,b,c,dC.d,c,b,aD.c,b,d,a

14.如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（）。

A.必須判斷棧是否滿B.判斷棧元素類型

C.必須判斷棧是否空D.對(duì)棧不作任何判斷

15.在解決沖算機(jī)主機(jī)與打卬機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打卬數(shù)據(jù)緩

沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)

打印，該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。

A.堆棧B.隊(duì)列C.數(shù)組D.先性表

16.一個(gè)遞歸算法必須包括（）o

A.遞歸部分B.終止條件和遞歸部分

C.迭代部分D.終止條件和迭代部分

17.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí):用變量x保存被刪結(jié)點(diǎn)的

值，則執(zhí)行（）0

A.x=top->data;tcp=top->next;B.x=top->data;

C.top=top->next;x=top->data;D.top=top->next;x=data;

18.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算

為（）。

A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;

19.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)

算為（）。

A.f->next=s;f=s;B.r->next=s;r=s;

C.s->npxt=r;r=<;;D.s->npxt=f;f=s;

20.在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則從該對(duì)

列中刪除一個(gè)結(jié)點(diǎn)并把結(jié)點(diǎn)的值保存在變量x中的運(yùn)算為（）。+++

A.x=r->data；r=r->next;B.r=r->next;x=r->data

C.x=f->data；f=f->next;D.f=f->next;x=f->data

21.棧和隊(duì)列的共同特點(diǎn)是（）o

A.都是先進(jìn)后出B.元素都可以隨機(jī)進(jìn)出

C.只容許在端點(diǎn)處插入和刪除元素D.都是先進(jìn)先出

22.棧的插入和刪除操作在（）進(jìn)行。

A.棧頂B.棧底

C.任意位置D.指定位置

23.在一個(gè)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（）位置。

A.前一個(gè)B.后一，個(gè)

C.當(dāng)刖D.后面

當(dāng)利用大小為的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（）

24.n0

A.n-2B.n-1C.nD.n+1

25.從一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，首先需要（）o

A.隊(duì)頭指針加一B.隊(duì)頭指針減一

C.取出隊(duì)頭指針?biāo)傅脑谼.取出隊(duì)尾指針?biāo)傅脑?/p>

二、判斷題

1.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。（）

2.在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置。（）

3.棧和隊(duì)列都是順序存取的線性表，但它們對(duì)存取位置的限制不同。（）

4.若讓元素1,2,3依次進(jìn)棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。（）

5.在用單鏈表表示的鏈?zhǔn)疥?duì)列Q中，隊(duì)頭指針為Q->front,隊(duì)尾指針為Q->rear,

則隊(duì)空條件為Q->front==Q->rear。（）

6.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實(shí)現(xiàn)對(duì)它的操作。（）

7.遞歸的算法簡(jiǎn)單、易懂、容易編寫，而且執(zhí)行效率也高。（）

8.遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問題在于重復(fù)計(jì)算太多，

而且調(diào)用本身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時(shí)間與空間開銷通常

都比較大。（）

9.用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)一定要使用遞歸工作棧。（）

10.棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)后出表』）

11.隊(duì)列的特性是先進(jìn)后出。（）

12.往棧中插入元素的噪作方式是：先寫入元素，后移動(dòng)棧頂指針。（）

13彳盾環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針前一個(gè)位置，隊(duì)列是“滿”狀態(tài)。（）

14.在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針后移，當(dāng)刪

除一個(gè)元素隊(duì)列時(shí)，頭指針后移。（）

15.向一個(gè)棧頂指針為h的鏈棧（結(jié)點(diǎn)的指針域?yàn)閚ext）中插入一個(gè)s所指結(jié)點(diǎn)時(shí),

先執(zhí)行s?>next=h,再執(zhí)行h=s操作。（）

16.一個(gè)遞歸算法不必包括遞歸終止條件。（）

17.在一個(gè)鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針與隊(duì)尾指針的值相同，則表示該隊(duì)列至多有

1個(gè)結(jié)點(diǎn)。（）

18.在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾

指針。（）

三、程序選擇題

1.在下面空格處填寫一條語句，以使下面的鏈?zhǔn)疥?duì)列全部元素出隊(duì)的算法完整。

intwrite(LinkQueue*q)

{QueueNode*p;

if(q->front==q->rear)/*隊(duì)空*/

{printf("隊(duì)空!無元素可取〃);

exit(O);

)

while(q->front->next!=NULL)

{p=q->front->next;

q->front->next=p->next;/*出隊(duì)*/

printf("%4d〃,p->data);

free(p);/*釋放己出隊(duì)結(jié)點(diǎn)*/

)

/*隊(duì)空時(shí)，頭尾指針指向頭結(jié)點(diǎn)*/

}

A.q->front=q->rear;

B.q=q->next;

C.q->rear=q->front;

D.p=p->next;

2.在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法完整

defineMAXSIZE100;

typedefcharElemtype;

typedefstruct

(

Elemtypequeue[MAXSIZE];

intfront,rear;

Jsequeuetype;

SequeuetypeQ;

intencqueue(sequeuetype*Q,elemtypex)

if((Q->rear?l)%MAXSIZE==Q->front)

{

printf("隊(duì)列已滿!\n〃)；

return1;

)

else

(

Q->rear=(Q->rear+l)%MAXSIZE;

(1)

return0;

)

}/*入隊(duì)算法*/

Elemtypedel_cqueue(sequeuetype*Q)

{

if((2))

(

printf(〃隊(duì)列為空!\n〃)；

return1;

)

else

(

Q->front=(Q->front+l)%MAXSIZE;

return(Q->queue[Q->front]);

)

}/*出隊(duì)算法*/

A.(1)(Q->rear+l)%MAXSIZE==Q->front(2)Q->front=(Q->front+l)%MAXSIZE;

B.(1)(Q->front+l)%MAXSIZE==Q->rear(2)Q->rear=(Q->rear+l)%MAXSIZE;

C.(1)Q->front==Q->rear(2)Q->queue[Q->rear]=x;

D.(1)Q->queue[Q->rear]=x;(2)Q->front==Q->rear

3.寫出下列程序執(zhí)行后的結(jié)果

SeqQueueQ;

InitQueue(Q);

inta[4]={5,8/12,15);

for(inti=0;i<4;i++)lnQueue(Q,a[i]);

lnQueue(Q,OutQueue(Q));

；

lnQueue(Q,30)

lnQueue(QyOutQueue(Q)+10);

while(!QueueEmpty(Q))printf(zz%d〃,OutQueue(Q));

執(zhí)行后的輸出結(jié)果為：.

A.58121530

B.121553018

C.812153018

D.121551830

4.寫出下列程序執(zhí)行后的結(jié)果

SeqStackS;

InitStack(S);

Push(S,3)；

Push(S,4);

Push(S,5);

intx=Pop(S)+2*Pop(S);

Push(Szx);

inti,a[4]={5,8/12/15};

for(i=0;i<4;i++)Push(S,a[i]);

while(!StackEmpty(S))Printf("%d7Pop⑸)；

執(zhí)行后的輸出結(jié)果為：0

A.151285133

B.358121315

C.151312853

D.151213385

5.在下面空格處填寫一條語句，以使下面的進(jìn)棧算法完整。

voidPush(structSeqStack*s/ElemTypex)

{

If(s->top==MaxSize-l){

printf("棧滿溢出錯(cuò)誤！\n〃)；

exit(l);

)

s->data[s->top]=x;

)

A.s->top=s->data;

B.s->data++;

C.s->top++；

D.s->data=s->top;

6.在下面空格處填寫一條語句，以使下面的出棧算法完整。

ElemTypePop(structSeqStack*s,ElemTypex)

{

If(StackEmpty(s)){

prinlf("棧下溢出錯(cuò)誤!\n〃)；

exit(l);

}

x=s->data[s->top];

returnx;

)

A.s->top-;

B.s->data-;

C.s->top=s->data;

D.s->data=s->top;

第四章字符串

一、選擇題

1.以下陳述中正確的是（）o

A.串是一種特殊的線性表B.串的長(zhǎng)度必須大于零

C.串中元素只能是字母D.空串就是空白串

2.設(shè)有兩個(gè)串p和q,其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱

為（）0

A.求子串B.連接

C.匹配D.求串長(zhǎng)

3.串是（）o

A.不少于一個(gè)字母的序列B.任意個(gè)字母的序列

C.不少于一個(gè)字符的序列D.有限個(gè)字符的序列

4.串的長(zhǎng)度是指（）。

A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)

C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)

5.若串S=="English”,其子串的個(gè)數(shù)是（）o+++

A.9B.16C.36D.28

6.下面關(guān)于串的敘述中，不正確的是（）o

A.串是字符的TT限序列

B.空串是由空格構(gòu)成的串

C.模式匹配是串的一種重要運(yùn)算

D.串即可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

7.串與普通的線性表相比較，它的特殊性體現(xiàn)在（

A.順序的存儲(chǔ)結(jié)構(gòu)B.鏈接的存儲(chǔ)結(jié)構(gòu)

C.數(shù)據(jù)元素是一個(gè)字符D.數(shù)據(jù)元素可以任意

8.空串與空格串（）oB

A.相同B.不相同C.可能相同D.無法確定

9.兩個(gè)字符串相等的條件是（）。

A.兩串的長(zhǎng)度相等

B.兩串包含的字符相同

C.兩串的長(zhǎng)度相等，并且兩串包含的字符相同

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

10.串函數(shù)Strcat(a,b)的功能是進(jìn)行串()。

A.比較B.復(fù)制C.賦值D.連接

11.串函數(shù)StrCmp(“ABCd”，“ABCD”)的值為()。

A.0B.-1C.1D.3

12.設(shè)主串為“FABcCDABcdEFaBc"，以下模式串能與主串成功匹配的是()。

A.EFaBcB.ABCdE

C.DABCCD.FAbcC

13.以下四個(gè)串中最小的是(，

A.〃ABADF〃B.〃ABAFD〃

C.〃ABADFA〃D.〃ABAF〃

14.在實(shí)際應(yīng)用中，要輸入多個(gè)字符串，且長(zhǎng)度無法預(yù)定。則應(yīng)該采用()

存儲(chǔ)比較合適。

A.鏈?zhǔn)紹.順序C.堆結(jié)構(gòu)D.無法確定

二、判斷題

1.用字符數(shù)組存儲(chǔ)長(zhǎng)度為n的字符串，數(shù)組長(zhǎng)度至少為n+1。()

2.串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符。()

3.串的兩種最基本的存儲(chǔ)方式是順序和鏈接。()

4.空串的長(zhǎng)度是1。()

5.一個(gè)空格的串的長(zhǎng)度是0。()

6.兩個(gè)串相等的充分必要條件是每一個(gè)對(duì)應(yīng)位置的字符相同。()

7.字符串a(chǎn)l二'、heijing",a2="hen",a3="heifang",a4="heni〃最小的是

a2o()

8.串函數(shù)StrCmp(“ABCd”，“ABCD”)的值為-1。()

三、程序選擇題

1.一下程序段的結(jié)果是：c的值為()

char*a[5]={“12378〃,“1237〃,“1236789〃,“1237",“123708〃}

inti,c=0

for(i=0;i<5;i++)

if(strcmp(a[i]/1237w)==0)C++;

A.2B.5C.OD.1237

2.以下程序段的結(jié)果是：c的值為()+++

chara[5]=w1236789w；

int*p=a,c=O;

While(*p++)C++;

A.8B.7C.10D.12

第五章數(shù)組和廣義表

一、選擇題

1.一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)

地址為100,則該數(shù)組的首地址是（）。+++

A.64B.28

C.70D.90

2.稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（）o

A.表達(dá)變得簡(jiǎn)單B.對(duì)矩陣元素的存取變得簡(jiǎn)單

C.去掉矩陣中的多余元素D.減少不必要的存儲(chǔ)空間的開銷

一個(gè)非空廣義表的表頭（）

3.o

A.不可能是原子B.只能是子表

C.只能是原子D.可以是子表或原子

4.常對(duì)數(shù)組進(jìn)行的兩種基本操作是（）o

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

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

5.設(shè)二維數(shù)組A⑸⑹按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知A⑼⑼起始地址為1000,

每個(gè)數(shù)組元素占用5個(gè)存儲(chǔ)單元，則元素A[4]⑷的地址為（）o

A.1140B.1145C.1120D.1125

6.設(shè)有一個(gè)20階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序

為主序存儲(chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)

組中的下標(biāo)是（）

B0

A.41B.32C.18D.38

廣義表的(深度是(

7.d,(d,d,b),hz(e,((iJ),k))))o

A.6B.10

C.8D.4

8.廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長(zhǎng)度是)o

A.6B.10

C.8D.4

9.設(shè)有一個(gè)廣義表A(a),其表尾為()0

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

10.下列廣義表中的線性表是()。

A.E(a,(b,c))B.E(a,E)C.E(a,b)D.E(azL())

二、判斷題

1.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。()

2.一個(gè)廣義表的表頭總是一個(gè)廣義表。()

3.一個(gè)廣義表的表尾總是一個(gè)表。()

一個(gè)廣義表(的長(zhǎng)度為深度為

4.(a),((b),c),(((d))))3,4O()

.一個(gè)廣義表的表尾是

5((a),((b),c),(((d))))((b),c),(((d)))o()

6.需要壓縮存儲(chǔ)的矩陣可分為特殊矩陣矩陣和稀疏矩陣矩陣兩種.()

7.設(shè)廣義表L二((),()),則其表頭是(())。()

8.設(shè)廣義表L=((),()),則其表尾是()。()

9.設(shè)廣義表L=((),()),則其長(zhǎng)度是0。()

10.廣義表A((a,b,c),(d,e,f))的表尾為((d,e,f?()

11.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的

行號(hào)、列號(hào)和元素值三項(xiàng)信息。()

12.設(shè)有n階對(duì)稱矩陣A,用一維數(shù)組s壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從

零開始，元素s[26]相應(yīng)于A中的元素為a7,6。()

第六章樹和二叉樹

一、選擇題

1.樹最適合用來表示（）。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)

2.樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（）。

A.1B.0C.2D.-1

對(duì)于一個(gè)滿二叉樹，個(gè)樹葉，個(gè)結(jié)點(diǎn)，深度為則（）

3.mnh,0

A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1

5.深度為5的二叉樹至多有（）個(gè)結(jié)點(diǎn)。

A.16B.32C.31D.10

6.假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,則葉子結(jié)點(diǎn)數(shù)

為（）o

A.15B.16C.17D.47

7.二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。

A.2kB.2k-lC.2k-lD.2k-l

8.在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為()o

A.31B.32C.33D.16

9.在一棵二叉樹上，第5層的結(jié)點(diǎn)數(shù)最多為（)o

A.8B.15C.16D.32

10.具有127個(gè)結(jié)點(diǎn)的完全二又樹其深度為（)o

A.8B.7C.6D.5

11.設(shè)一棵二叉樹中沒有度為1的結(jié)點(diǎn)，已知葉子結(jié)點(diǎn)數(shù)為n,此樹的結(jié)點(diǎn)數(shù)為

（）o

A.2n+2B.2n+lC.2nD.2n-l

12.設(shè)二叉樹中有n2個(gè)度為2的結(jié)點(diǎn)，nl個(gè)度為1的結(jié)點(diǎn)，nO個(gè)葉子結(jié)點(diǎn)，則

此二叉樹中空指針域個(gè)數(shù)為（）o

A.n0+nl+n2B.n2+nl+2nOC.2n2+nlD.2n0+nl

13.n個(gè)結(jié)點(diǎn)的二叉樹中，用二叉鏈表做存儲(chǔ)，非空指針數(shù)目為（）o

A.nB.2nC.n-1D.n+1

14.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）0

A.0B.1C.2D.-1

15.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）0

A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)

C.只有左子樹上的所有結(jié)點(diǎn)D.只有左子樹上的部分結(jié)點(diǎn)

16.如圖所示二叉樹的中序遍歷序列是（r

A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh

17.設(shè)n、m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，中序遍歷時(shí)n在m前的條件是（）。

A.n在m右方B.n是m祖先C.n在m左方D.n是m子孫

18.某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定（）o

A.空或只有一個(gè)結(jié)點(diǎn)B.完全二叉樹

C.二叉排序樹D.深度等于其結(jié)點(diǎn)數(shù)

19.二叉樹的先序遍歷和中序遍歷如下：

先序遍歷：EFHIGJK

中序遍歷：HFIEJKG

該二叉樹根的右子樹的根是（）。

A.EB.FC.GD.H

20.如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長(zhǎng)度最

小，則該樹稱為（）o

A.哈夫曼樹B.平衡二叉樹C.二叉樹D.完全二叉樹

21.利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（）個(gè)結(jié)點(diǎn)。

A.nB.n+1C.2*nD.2*n-l

22.利用2、4、5、10這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫蛙樹，該樹中

所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（）o

A.18B.16C.38D.30

23.哈夫曼樹是（）o

A.滿二叉樹B.二叉排序樹

C.樹的路徑長(zhǎng)度最短的二叉樹D.帶權(quán)路徑長(zhǎng)度最短的二叉樹

24.用權(quán)值分別為15,2,4,5的四個(gè)結(jié)點(diǎn),構(gòu)造出的哈夫曼樹為（D）0

A.2n-lB.2nC.2n+lD.不確定

二、判斷題

1.樹是一種線性結(jié)構(gòu)。（）

2.樹最適合表示元素之間具有層次關(guān)系的數(shù)據(jù)。（）

3.如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是4。（）

4.樹中全部結(jié)點(diǎn)的度均大于0。（）

5.森林是m（m2。）棵互不相交的樹的集合。（）

6.深度為k的完全二叉樹至少有2k-l個(gè)結(jié)點(diǎn)。（）

7.完全二叉樹中沒有度為1的結(jié)點(diǎn)。（）

8.若樹的度為2時(shí)，該數(shù)為二叉樹。（）

9.具有三個(gè)結(jié)點(diǎn)的二叉樹有五種。（）

10.深度為5的二叉樹最多有3層。（）

11.具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為9o（）

12.具有100個(gè)結(jié)點(diǎn)的完全二叉樹有50個(gè)葉子。（）

13.在二叉樹的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)設(shè)置三個(gè)域：值域、左指針域和右指針域。

（）

14.二叉樹只能采用二叉鏈表來存儲(chǔ)。（）

15.具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ).共有n+1個(gè)空鏈域。（）

16.二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面。（）

17.已知一棵樹的先序序列和后序序列，一定能陶造出該樹。（）

18.二叉樹的遍歷就是按照一定次序訪問樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)的值僅被

訪問一次的過程。（）

19.哈夫曼樹一定是完全二叉樹或滿二叉樹。（）

20.哈夫曼樹只存在著雙支結(jié)點(diǎn)，不存在單支結(jié)點(diǎn)。（）

三、本章綜合應(yīng)用或程序題（都用客觀選擇形式）

1.有一棵樹如圖所示，回答下面問題:

（1）這棵樹的根結(jié)點(diǎn)是（）；

（2）這棵樹的葉子結(jié)點(diǎn)是（）；

（3）這棵樹的度是（）;

（4）這棵樹的深度是（）；

（5）c結(jié)點(diǎn)的孩子結(jié)點(diǎn)是（）；

（6）c結(jié)點(diǎn)的父母結(jié)點(diǎn)是（）o

A.3B.4C.aD.e、fE.b、e、d、g

2.由如圖所示的二叉樹，回答以下問題：（6.4）

（1）其中序遍歷序列（）;

（2）其前序遍歷序列（）;

（3）其后序遍歷序列（）；

A.gdbeihfcaB.gbaechifC.abdgcefhi

3.以3,4,5,8,9,作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。該樹的帶權(quán)路徑長(zhǎng)

度為（）

A.61B.62C.63D.65

4.以2,3,4,7,8,9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。權(quán)重值為4的葉

結(jié)點(diǎn)的哈夫曼編碼為（）

A.000B.001C.010D.10

第七章圖

一、單選題(共25題)

1.在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的()倍。

A.1/2

B.1

C.2

D.4

2.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖包含()條邊。

A.n(n-1)

B.n(n+1)

C.n(n-1)/2

D.n(n+1)/2

3.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含()條邊。

A.n(n-1)

B.n(n+1)

C.n(n-1)/2

D.n(n+1)/2

4.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有頂點(diǎn)

鄰接表中的結(jié)點(diǎn)總數(shù)為()。

A.n

B.e

C.2n

D.2e

5.在有向圖的鄰接表口，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有()鄰接點(diǎn)。

A.入邊

B.出邊

C.入邊和出邊

D.不是入功也不是出動(dòng)

6.鄰接表是圖的一種（:）。

A.順序存儲(chǔ)結(jié)構(gòu)

B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.索引存儲(chǔ)結(jié)構(gòu)

D.散列存儲(chǔ)結(jié)構(gòu)

7.如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn),

則該圖一定是（）。

A.完全圖