數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題-考試復(fù)習(xí)題目

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

第一章緒論

一、選擇題

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

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

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

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

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

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

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

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

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

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

3、一個存儲結(jié)點存儲一個（）o

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

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

C.數(shù)據(jù)項

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

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

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

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

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

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

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

A.可行性

B.輸入性

C.可讀性

D.有窮性

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

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

B,算法本身

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

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

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

i=s=O;

while(s<n){

i++；

s+=i;

}

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

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

int((unsignedintn){

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)分為（）o

A.動態(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í)行下面程序段時，執(zhí)行S語句的次數(shù)為（）o

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ù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）0

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

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

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

D.相關(guān)算法

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

A.一對一

B,多對多

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

D.一對多

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

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

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

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

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

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

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

B,數(shù)據(jù)元素的存儲

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

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

二、判斷題

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)時二者是通用的。（）

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

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

效性。（）

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

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

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

9.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示稱為邏輯結(jié)構(gòu)。()

10.數(shù)據(jù)的邏輯結(jié)構(gòu)是與存儲該結(jié)構(gòu)的計算機(jī)相關(guān)的。()

11.數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對多的關(guān)系稱為樹狀結(jié)構(gòu)。()

12.通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成樹型結(jié)構(gòu)。()

13.通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。()

14.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為圖形結(jié)構(gòu)。()

15.數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)可以由一個或多個數(shù)據(jù)項組成。()

三、程序題

指出下列各算法的時間復(fù)雜度。

1>intprime(intn)

(

inti=l;

intx=(int)sqrt(n);

while(++i<=x)

if(n%i==0)break;

if(i>x)return1;

elsereturn0;

)

2>intsuml(intn)

(

intp=l,s=0;

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

P*=i；

s+=p；

}

returns;

)

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è)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新

表的第i個元素），插入一個元素，則移動元素個數(shù)為（）=

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

2、設(shè)有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為（）o

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

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

指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（）o

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

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

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

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é)點滿足（）（設(shè)頭指針為head,指針p指向尾結(jié)

點）。

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

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

6、鏈表不具有的特點是（）o

A.不必事先估計存儲空間

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

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

D.插入刪除不需要移動元素

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

A.head->next==head

B.head==NULL

C.head->next==NULL

D.head!=NULL

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

前依次移動了15個元素。則原順序表的長度為（）0

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

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

A.線性表至少要求一個元素

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

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

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

直接后繼

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

平均要移動（）個元素。

A.63.5B.7

C.63D.8

11、一個順序表第一個元素的存儲地址是90,每個元素的長度為2,則第6個元

素的地址是（）o

A.106B.98

C.102D.100

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

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

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

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

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

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

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

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

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

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

14、對鏈表，以下敘述中正確的是（)0

A,不能隨機(jī)訪問任一結(jié)點

B.插入刪除元素的操作一定要要移動結(jié)點

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

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

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

表的第i個元素），插入一個元素，則移動元素個數(shù)為（）=

A.n-i+1B.i

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

16、在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(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、在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p

之間插入s結(jié)點，則以下操作哪個是正確的（）o

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；

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

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->right；p->right->left=s；p->right=s；

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

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

A.空表B.只有1個元素；

C.空表或只有一個元素D.非空表

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

）。

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

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

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

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

選擇一項：

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

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

二、判斷題

1、設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next,指針p指向尾

結(jié)點，現(xiàn)要使p指向第一個結(jié)點，可用語句p=p->next;。（）

2、設(shè)有一個單向鏈表，結(jié)點的指針域為next,頭指針為head,p指向尾結(jié)點，

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

3、設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為next,頭指針為head,指針p指向

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

（）

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

表中結(jié)點的指針域為next,可執(zhí)行p->next=s;s->next=p->next；的操作。（）

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

驅(qū)結(jié)點，若鏈表中結(jié)點的指針域為next,則可執(zhí)行q->next=p->next。（）

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

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

行head=head->next;p->next=head；。（）

7、設(shè)有一個單向循環(huán)鏈表，頭指針為head,鏈表中結(jié)點的指針域為next,p指

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

行操作p->next=head；。（）

8、設(shè)有一個長度為40的順序表,要刪除第8個元素需移動元素的個數(shù)為3。（）

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

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

三、程序填空

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

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

#defineNULL0

voidmain()

{NODE*head,*p;

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

do

{printf(〃％d\n〃，

[1];

[2];

Jwhile

[3]；

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

點類型的指針變量，p指向鏈表中結(jié)點a,(設(shè)鏈表中沒有結(jié)點的數(shù)據(jù)域與結(jié)點a

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

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

(2)插入結(jié)點s,使它成為a結(jié)點的直接前驅(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è)有一個不帶頭結(jié)點的單向鏈表，頭指針為head,p、prep是指向結(jié)點類型

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

是在該單向鏈表中查找這相鄰兩個結(jié)點，把該結(jié)點的數(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)棧，則出棧順序不可能為（）。

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

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

一個隊列的入隊序列是則隊列的輸出序列是（）

2.1,2,3,40o

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

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

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

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

A.10,20,30,40,50B.40,30,50,10,20

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

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

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

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

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

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

A.先移動棧頂指針，再存入元素

B.先存入元素，再移動棧頂指針

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

D.同時進(jìn)行

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

A.top->next=p;

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

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

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

7.在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值,

則執(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)換成等價的非遞歸算法應(yīng)該設(shè)置（

A.棧B.隊列

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

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

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

判斷一個順序隊列（最多元素為）為空的條件是）

10.sqm（o

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

C.sq->front==sq->rearD.sq->front==sq->rear+l

11.判斷一個循環(huán)隊列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滿（元素個數(shù)最多n個）的條件是（）o

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

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

13.一個隊列的入隊順序是a,b,c,d,則離隊的順序是（）。

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

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

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

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

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

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

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

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

一個遞歸算法必須包括（）

16.0

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

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

17.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的

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

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

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

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

為（）。

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

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

算為（

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

C.s->next=r;r=s;D.s->next=f;f=s;

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

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

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.（0

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

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

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

A.棧頂B.棧底

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

23.在一個順序隊列中，隊首指針指向隊首元素的（）位置。

A.前一個B.后一個

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

24.當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（）。

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

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

A.隊頭指針加一B.隊頭指針減一

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

二、判斷題

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

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

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

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

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

則隊空條件為Q->front==Q->rear。（）

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

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

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

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

都比較大。（）

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

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

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

12.往棧中插入元素的操作方式是：先寫入元素，后移動棧頂指針。（）

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

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

除一個元素隊列時，頭指針后移。（）

15.向一個棧頂指針為h的鏈棧（結(jié)點的指針域為next）中插入一個s所指結(jié)點時,

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

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

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

1個結(jié)點。（）

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

指針。（）

三、程序選擇題

1.在下面空格處填寫一條語句，以使下面的鏈?zhǔn)疥犃腥吭爻鲫牭乃惴ㄍ暾?/p>

intwrite(LinkQueue*q)

{QueueNode*p;

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

{printf("隊空!無元素可取”);

exit(O);

)

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

{p=q->front->next;

q->front->next=p->next;/*出隊*/

printf(〃％4d〃,p?>data);

free(p);/*釋放已出隊結(jié)點*/

)

/*隊空時，頭尾指針指向頭結(jié)點*/

}

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)隊列的入隊和出隊算法完整

defineMAXSIZE100;

typedefcharElemtype;

typedefstruct

(

Elemtypequeue[MAXSIZE];

intfront,rear;

Jsequeuetype;

SequeuetypeQ;

intencqueue(sequeuetype*Q/elemtypex)

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

(

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

return1;

)

else

f

\

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

(1)

return0;

}

}/*入隊算法*/

Elemtypedel_cqueue(sequeuetype*Q)

(

if((2))

I

printf(〃隊列為空!\n〃);

return1;

/

else

(

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

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

)

}/*出隊算法*/

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(Q,OutQueue(Q)+10);

while(!QueueEmpty(Q))printf(〃％d^OutQueue(Q));

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

A.58121530

B.121553018

C.812153018

D.121551830

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

SeqStackS;

InitStack(S);

Push(S,3);

Push(S,4);

Push(Sz5);

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

Push(S,x);

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

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

while(!StackEmpty(S))Printf(zz%d7Pop(S));

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

A.151285133

B.358121315

C.151312853

D.151213385

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

voidPush(structSeqStack*s,ElemTypex)

(

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

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

exit⑴；

}

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)){

printf("棧下溢出錯誤！\nH);

exit⑴；

}

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.串的長度必須大于零

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

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

為()。

A.求子串B.連接

C.匹配D.求串長

3.串是（）。

A.不少于一個字母的序列B.任意個字母的序列

C.不少于一個字符的序列D.有限個字符的序列

4.串的長度是指（)o

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

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

5.若串S=="English”，其子串的個數(shù)是)o+++

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

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

A.串是字符的有限序列

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

C.模式匹配是串的一種重要運算

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

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

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

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

8.空串與空格串（)?B

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

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

A.兩串的長度相等

B.兩串包含的字符相同

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

D.兩串的長度相等，并且對應(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.以下四個串中最小的是()o

A.”ABADF"B."ABAFD”

C.”ABADFA"D."ABAF"

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

存儲比較合適。

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

二、判斷題

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

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

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

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

5.一個空格的串的長度是0。()

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

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

a2?()

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

三、程序選擇題

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

char*a[5]={〃123787123771236789〃,〃1237〃,“123708〃}

inti,c=O

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

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

A.2B.5C.OD.1237

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

chara[5]=,,1236789,,；

int*p=a,c=O;

While(*p++)C++;

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

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

一、選擇題

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

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

A.64B.28

C.70D.90

2.稀疏矩陣采用壓縮存儲的目的主要是（）。

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

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

3.一個非空廣義表的表頭（）□

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

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

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

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

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

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

每個數(shù)組元素占用5個存儲單元，則元素A⑷⑷的地址為（）。

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

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

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

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

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

7.廣義表的（a,（d,a,b）,h,（e,（（i,j）,k）））深度是（7

A.6B.10

C.8D.4

8.廣義表（打憂向力,&＜：）,€1,6,（。/）,1＜））的長度是（）o

A.6B.10

C.8D.4

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

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

10,下列廣義表中的線性表是()o

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

二、判斷題

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

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

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

4.一個廣義表((a),((b),c),(((d))))的長度為3,深度為4。()

5.一個廣義表((a),((b),c),(((d))))的表尾是((b),c),(((d)))o()

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

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

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

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

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

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

行號、列號和元素值三項信息。()

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

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

第六章樹和二叉樹

一、選擇題

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

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

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

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

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

3.對于一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h,則)。

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

4.如圖所示一棵二叉樹中，（C）不是完全二叉樹

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

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

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

為（）。

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

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

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

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

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

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

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

10.具有127個結(jié)點的完全二叉樹其深度為（）。

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

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

)o

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

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

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

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

個結(jié)點的二叉樹中，用二叉鏈表做存儲，非空指針數(shù)目為（）

13.no

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

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

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

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

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

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

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

A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh

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

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

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

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

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

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

先序遍歷：EFHIGJK

中序遍歷：HFIEJKG

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

A.EB.FC.GD.H

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

小，則該樹稱為（）=

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

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

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

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

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

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

23.哈夫曼樹是（)□

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

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

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

則它的結(jié)點總數(shù)為（）。

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

二、判斷題

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

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

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

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

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

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

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

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

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

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

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

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

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

（）

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

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

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

17.已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹;（）

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

訪問一次的過程。（）

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

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

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

有一棵樹如圖所示，回答下面問題：w

1.1

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

（2）這棵樹的葉子結(jié)點是（）；e/

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

（4）這