計(jì)算機(jī)軟件技術(shù)基礎(chǔ)-復(fù)習(xí)題

第一節(jié)概論

1.、要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。

A.數(shù)據(jù)元素具有同一的特點(diǎn)B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)

項(xiàng)的類型要一致C.每個(gè)數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等

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

和運(yùn)算的學(xué)科。

（1）A.操作對(duì)象B.計(jì)算方法C.邏輯存儲(chǔ)D.數(shù)據(jù)映像

⑵A.結(jié)構(gòu)B.關(guān)系C.運(yùn)算D.算法

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

集合。

（1）0A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)

（2）A.操作B.映像C.存儲(chǔ)D.關(guān)系

4.在數(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.線性結(jié)構(gòu)和非線性結(jié)閡D.內(nèi)部結(jié)

構(gòu)和外部結(jié)構(gòu)

5.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。

A.隨機(jī)存取B.順序存取C.索引存取D.Hash存取

6.算法分析的目的是（）。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改

進(jìn)D.分析算法的易懂性和文檔性

7.計(jì)算機(jī)算法指的是（（1））,它必須具備輸入、輸出和（（2））等五個(gè)特征。

（1）A.計(jì)算方法B.排序方法C.解決某一問(wèn)題的有限運(yùn)算序列D.調(diào)度方法

（2）A,可行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性C.確定性，有窮性和

穩(wěn)定性D.易讀性、穩(wěn)定性和安全性

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

A.必須是連續(xù)的B.部分必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以

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

A.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性

表的線性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出

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

形式，其中解釋錯(cuò)誤的是（）。

A.集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散B.線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系

依次排列形成一條“鎖鏈”C.樹(shù)形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的

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

11.以下說(shuō)法正確的是（）o

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的

各數(shù)據(jù)項(xiàng)的集合D.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(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ù)項(xiàng)在計(jì)算機(jī)中的映像分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。

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

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

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

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

8,順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)。

三、填空題

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

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

3.數(shù)據(jù)的邏輯結(jié)構(gòu)包括、、和四種類

型。

4.在線性結(jié)構(gòu)中，開(kāi)始結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)

點(diǎn)O

5.在樹(shù)形結(jié)構(gòu)中，根結(jié)點(diǎn)只有,其余每個(gè)結(jié)點(diǎn)有且只有前驅(qū)結(jié)

點(diǎn)；葉結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以有?

6.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)可以有o

7.算法的五個(gè)重要特性是、、、

8.下列程序段的時(shí)間復(fù)雜度是o

for(i=l；i<=n；i++)A[i,i]=0；

9.下列程序段的時(shí)間復(fù)雜度是o

S=0；

for(i=l；i<=n；i++)

for(j=l；j<=n；j++)s=s+B[i,j]；

sum=s；

10.存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的實(shí)現(xiàn)。

11.從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)看，通常所說(shuō)的“數(shù)據(jù)”應(yīng)分成三個(gè)不同的層次，即

和O

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

13.通常，存儲(chǔ)結(jié)點(diǎn)之間可以有、、、

四種關(guān)聯(lián)方式，稱為四種基本存儲(chǔ)方式。

14.通常從、、、等幾方面評(píng)價(jià)算

法(包括程序)的質(zhì)量。

15.一個(gè)算法的時(shí)空性能是指該算法的和,前者是算法包含的

,后者是算法需要的。

16.在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是的函數(shù)。

17.常見(jiàn)時(shí)間復(fù)雜度的量級(jí)有：常數(shù)階0()、對(duì)數(shù)階0()、線性階

0()、平方階0()和指數(shù)階0()。通常認(rèn)為，具有指數(shù)階量級(jí)

的算法是的。

18.數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的和o

19.數(shù)據(jù)對(duì)象是性質(zhì)相同的的集合°

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

四、應(yīng)用題

1.分析下列程序段的時(shí)間復(fù)雜度。

i=l;

WHILE(i<=n)i=i*2；

2.敘述算法的定義及其重要特性。

3.簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對(duì)象。

4.邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是什么關(guān)系？

2

5.將數(shù)量級(jí)210,n,n2,n3,nlog2n,log2n,2n,n!,(2/3)n,n2/3按增長(zhǎng)率進(jìn)行排

列。

6.設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：D={kl,k2,k3,…，k9},R={<kl,k3>,<kl,k8>,<k2,k3>,

<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k6>},畫出這個(gè)邏

輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R,哪些結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？

7.設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說(shuō)出它是什么類型的邏輯結(jié)構(gòu)。

8.分析下列程序的時(shí)間復(fù)雜度(設(shè)n為正整數(shù))。

(1)intrec(intn)

{if(n=l)return(1)；elsereturn(n*rec(n-1))；}

(2)x=91；y=100；

While(y>0)if(x>10)y—；

(3)i=l：j=0：

while(i+j<=n)

if(i>j)j++;elsei++;

(4)x=n；y=0；

while(x>=(y+l)*(y+l))y++；

9.設(shè)n為正數(shù)。試確定下列各程序段中前面加記號(hào)@的語(yǔ)句的頻度:

⑴i=l；k=0；

while(i<=n-l){@k+=10*i；i++；)

(2)k=0；

for(i=l；i<=n；i++)

for(j=i；j<=n：j++)@k++；

3

第二節(jié)線性表

一、選擇題

1.、線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)（）。

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

2.線性表L=（aLa2,???,ai,???,an）,下列說(shuō)法正確的是（）。

A.每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼B.線性表中至少要有一個(gè)元素C.表中諸

元素的排列順序必須是由小到大或由大到小的D.除第一個(gè)元素和最后一個(gè)元素外其余每

個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼

3.順序表是線性表的（）。

A.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.順序存儲(chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)

4.對(duì)于順序表，以下說(shuō)法錯(cuò)誤的是（）。

A.順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對(duì)地址B.順序表

的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C.順序表的特點(diǎn)是：邏

輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰D.順序表的特點(diǎn)是：邏輯上相鄰的元素，存儲(chǔ)在

物理位置也相鄰的單元中

5.對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜度分析來(lái)說(shuō)，通常以（）為標(biāo)準(zhǔn)操作。

A.條件判斷B.結(jié)點(diǎn)移動(dòng)C.算術(shù)表達(dá)式D.賦值語(yǔ)句

6.對(duì)于順序表的優(yōu)缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是（）0

A.無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間B.可以方便地隨機(jī)存取表中的

任一結(jié)點(diǎn)C.插入和刪除操作較方便D.由于順序表要求占用連續(xù)的空間，存儲(chǔ)分配只

能預(yù)先進(jìn)行（靜態(tài)分配）

7.在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均

次數(shù)為（）。

A.nB.n/2C.（n-l）/2D.（n+l）/2

8.在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為

（）o

A.nB.n/2C.（n-l）/2D.（n+l）/2

9.帶頭結(jié)點(diǎn)的單鏈表head為空的條件是（）o

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

10.非空單循環(huán)鏈表head的尾結(jié)點(diǎn)*p滿足（）o

A.p->next=NULLB.p=NULLC.p->next=headD.p=head

11.在雙循環(huán)鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是（）。

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

>next->prior=s；s->prior=p：s->next=p->next；C.s->prior=p；s->next=p->next；p-

>next=s；p->next->prior=s；D.s->prior=p；s->next=p->next；p->next->pror=s；p-

>next=s；

12.在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入結(jié)點(diǎn)*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；

13.在一個(gè)單鏈表中，若*p結(jié)點(diǎn)不是最后結(jié)點(diǎn)。在*p之后插入結(jié)點(diǎn)*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;

14.若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)元素，則采用（）存

儲(chǔ)方式最節(jié)省時(shí)間。

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

4

15.設(shè)rear是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除表頭結(jié)點(diǎn)的操作可表示為

()。

A.p=rear；rear=rear->next；free(p)B.rear=rear->next；free(rear)；

C.rear=rear->next->next；free(rear)；D.p=rear->next->next；rear->next-

>next=p->next；free(p)；

16.在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行()o

A.q=p->next；p->next=q->next；free(q)；B.p=p->next；p->next=p->next->next；

free(p)；C.p->next=p->next；free(p->next)；D.p=p->next->next；free(p-

>next)；

17.設(shè)指針P指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱性可用()式來(lái)刻畫。

A.p->prioi'->next->=p->next->nextB.p->prior->prior==p->next->piiorC.p-

>prior->next->==p->next->priorD.p->next->next==p->prior->prior

18.在循環(huán)鏈表中，將頭指針改設(shè)為尾指針rear后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是

()o

A.rear和rear->next->nextB.rear->next和rearC.rear->next->next和rear

D.rear和rear->next

19.循環(huán)鏈表的主要優(yōu)點(diǎn)是()o

A.不再需要頭指針了B.已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū)C.在進(jìn)行

插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi)D.從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈

表

20.在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是()。

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

二、判斷題

1.順序存儲(chǔ)的線性表可以隨機(jī)存取。

2.順序存儲(chǔ)的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪?/p>

半的元素需要移動(dòng)。

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

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

5.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。

6.在單鏈表中，可以從頭結(jié)點(diǎn)開(kāi)始查找任何一個(gè)元素。

7.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。

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

9.在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的

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

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

二、填空題

1.為了便于討論，有時(shí)將含n(n>0)個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成(aLa2,an),其中每個(gè)ai

代表一個(gè)oal稱為結(jié)點(diǎn)，an稱為結(jié)點(diǎn)，i稱為ai在線性表中的

o對(duì)任意一對(duì)相鄰結(jié)點(diǎn)ai、ai+l(lWi<n),ai稱為ai+1的直接,ai+1稱為

ai的直接。

2.線性結(jié)構(gòu)的基本特征是：若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒(méi)有直接外，其他結(jié)

點(diǎn)有且僅有一個(gè)直接;除終端結(jié)點(diǎn)沒(méi)有直接外，其他結(jié)點(diǎn)有且僅有一個(gè)直接

3.所有結(jié)點(diǎn)按一對(duì)一的鄰接關(guān)系構(gòu)成的整體就是結(jié)構(gòu)。

4.線性表的邏輯結(jié)構(gòu)是結(jié)構(gòu)，其所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的

5.在單鏈表中，刪除p所指結(jié)點(diǎn)的直接后繼的操作是?

5

6.非空的單循環(huán)鏈表head的尾結(jié)點(diǎn)(由指針p所指)滿足。

7.rear是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除起始結(jié)點(diǎn)的操作可表示為

8.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在p所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為

，在給定值為X的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0

9.單鏈表表示法的基本思想是用_______________表示結(jié)點(diǎn)間的邏輯關(guān)系。

10.在順序表中插入或刪除一個(gè)元素，平均需要移動(dòng)元素，具體移動(dòng)的元素個(gè)數(shù)與

_______有關(guān)。

11.在一個(gè)長(zhǎng)度為n的向量的第i(lWiWn+l)個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng)

個(gè)元素。

12.在一個(gè)長(zhǎng)度為n的向量中刪除第i(lWiWn)個(gè)元素時(shí)，需向前移動(dòng)個(gè)元素。

13.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向,另一個(gè)指向

14.在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可

用P表示為head=。

15.設(shè)head指向單鏈表的表頭，p指向單鏈表的表尾結(jié)點(diǎn)，則執(zhí)行p->next=head后，該單鏈

表構(gòu)成o

16.在單鏈表中，若p和s是兩個(gè)指針，且滿足p->next與s相同，則語(yǔ)句p-〉next=s->next

的作用是________________s指向的結(jié)點(diǎn)。

17二設(shè)r指向單循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行

的三條語(yǔ)句是；r->next=s；r=s；

18.在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是。

19.在雙循環(huán)鏈表中，若要在指p所指結(jié)點(diǎn)前插入s所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：s-

>next=p；s->prior=p->prior；=s；p->prior=s；

20.在單鏈表中，若要在p所指結(jié)點(diǎn)之前插入s所指的結(jié)點(diǎn),可進(jìn)行下列操作：

s->next=；p->next=s；temp=p->data；

p->data=；s->data=；

四、應(yīng)用題

1.描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn))。

2.何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜？

3.在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)？具體的移動(dòng)次數(shù)取決于哪兩個(gè)因

素？

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

5.雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某個(gè)結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從

相應(yīng)的鏈表中刪除?若可以，其時(shí)間復(fù)雜度各為多少？

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

LinkListtestl(LinkListL)

{〃L是無(wú)頭結(jié)點(diǎn)的單鏈表

ListNode*q,*p；

if(LML->next)

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

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

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

returnL；}

7.如果有n個(gè)線性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總

長(zhǎng)度也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)？為什么？

6

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

的元素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？

五、算法設(shè)計(jì)題

1.試用順序表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)將線性表(aO,aLa2,…an-l)就地逆置的操作，所謂

“就地”是指輔助空間為0(1)。

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

一個(gè)有序表。

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

4.試寫出在不帶頭結(jié)點(diǎn)的單鏈表的第i個(gè)元素之前插入一個(gè)元素的算法。

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

存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)將A和B歸并成一個(gè)仍按元素值遞增有序的線性表Co

6.設(shè)指針la和1b分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn)，設(shè)計(jì)從表la中刪除第i個(gè)元

素起共len個(gè)元素，并將這些元素插入到1b中第j個(gè)結(jié)點(diǎn)之前的算法。

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

表中有這樣的結(jié)點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)空間，這里min和max是兩個(gè)給定的參數(shù)。

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

分別為pa和pb,使得A鏈表中含有原鏈表A中序號(hào)為奇數(shù)的元素，而B(niǎo)鏈表中含有原鏈表A

中序號(hào)為偶數(shù)的元素，且保持原來(lái)的相對(duì)順序。

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

個(gè)線性表C,其兀素為兩集合的交集，且表C中的兀素也依值遞增有序排列。對(duì)順序表編寫求

C的算法。

10.設(shè)有線性表A=(aLa2,???,am)和B=(bLb2,???,bn)。試編寫合并A、B為線性表C的

算法，使得：C=(al,bl,???,am,bm,bm+1,…bn)(當(dāng)mWn時(shí))或(al,bl,an,bn,

an+1,...am)(當(dāng)m>n時(shí))，線性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B

表的結(jié)點(diǎn)空間。

11.假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的

指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前驅(qū)結(jié)點(diǎn)。

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

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

他字符)，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使得每個(gè)表中只含有同一類的字

符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。

14、己知A、B和C為三個(gè)遞增有序的線性表，現(xiàn)要求對(duì)A表進(jìn)行如下操作：刪去那些既在B

表中出現(xiàn)又在C表中出現(xiàn)的元素。試對(duì)順序表編寫實(shí)現(xiàn)上述操作的算法(注：題中未特別指明

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

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

(D在值為x的結(jié)點(diǎn)之前插入值為y的結(jié)點(diǎn)。(2)在值為x的結(jié)點(diǎn)之后插入值為y的結(jié)點(diǎn)。

⑶刪除值為x的結(jié)點(diǎn)C

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

交換。

17.設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next三個(gè)域外，還有一個(gè)可訪問(wèn)頰度

域freq,在鏈表啟用之前，其值均初始為0。每當(dāng)鏈表進(jìn)行一次LocateNode(L,x)操作時(shí)令

元素值為x的結(jié)點(diǎn)中freq域的值加L并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的遞減次序排

列，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫一符合上述要求的LocateNode噪作的算法。

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

的過(guò)程。

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

7

20.約瑟夫環(huán)問(wèn)題：任給正整數(shù)n、k,按下述方法可得排列1,2,…，n的一個(gè)置換：將數(shù)字

1,2,…，n環(huán)形排列，按順時(shí)針?lè)较驈?開(kāi)始計(jì)數(shù)；計(jì)滿k時(shí)輸出該位置上的數(shù)字（并從環(huán)中

刪去該數(shù)字），然后從下一個(gè)數(shù)字開(kāi)始繼續(xù)計(jì)數(shù)，直到環(huán)中所有數(shù)字均被輸出為止。例如，

n=10,k=3時(shí)，輸出的置換是3,6,9,2,7,1,8,5,10。分別以數(shù)組和以不帶頭結(jié)點(diǎn)的、

已知尾指針的單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)解決上述問(wèn)題。

8

第三節(jié)棧和隊(duì)列

一、選擇題

1.設(shè)有一順序棧S,元素si,s2,s3,s4,s5,s6依次入棧，如果6個(gè)元素出棧的順序是

s2,s3,s4,s6,s5,si,則棧的容量至少應(yīng)該是()。

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

2.若一個(gè)棧的輸入序列是a、b、c,則通過(guò)入棧、出棧操作可能得到a、b、c的不同排列個(gè)數(shù)

為()。

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

3.設(shè)有一順序棧已經(jīng)含有3個(gè)元素，如圖3-1所示，元素a4正等待入棧。以下序列中不可能

出現(xiàn)的出棧序列是()。

A.a3,al,a4,a2B.a3,a2,a4,alC*a3,a4,a2,alD?a4,a3,a2,al

0f」?!?maxsize-1

ala2a3

Top

圖3-1

4.和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是()。

A.通常不會(huì)出現(xiàn)棧滿的情況B.通常不會(huì)出現(xiàn)棧空的情況C.插入操作更容易實(shí)現(xiàn)

D.刪除操作更容易實(shí)現(xiàn)

5.若一個(gè)棧的輸入序列是1,2,3,4,…，n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元

素是()。

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

6.以下說(shuō)法正確的是()o

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

棧本身沒(méi)有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況C.對(duì)于鏈棧而言，

在棧滿狀態(tài)下，如果再進(jìn)行入棧操作，則會(huì)發(fā)生“上溢”D.對(duì)于順序棧而言，在棧滿狀

態(tài)下，如果再進(jìn)行入棧操作，則會(huì)發(fā)生“下溢”

7.順序隊(duì)列的入隊(duì)操作應(yīng)為()。

A.sq.rear=sq.rear+1；sq.data[sq.rear]=x;B.sq.data[sq.rear]=x；

sq.rear=sq.rear+1；C.sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear+1]=x;

D.sq.data[sq.rear]=x；sq.rear=x;sq.rear=(sq.rear+1)%maxslze；

8.循環(huán)隊(duì)列的入隊(duì)操作應(yīng)為()o

A.sq.rear=sq.rear+1；sq.data[sq.rear]=xB.sq.data[sq.rear]=x；

sq.rear=sq.rear+1；C.sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear]=x；

D.sq.datafsq.rear]=x；sq.rear=(sq.rear+1)%maxsize；

9.順序隊(duì)列的出隊(duì)操作為()o

A.sq.front=(sq.front+1)%maxsize；B.sq.front=sq.front+1；

C.sq.rear=(sq.rear+1)maxsize；D.sq.rear=sq.rear+1;

10.循環(huán)隊(duì)列的出隊(duì)操作為()o

A.sq.front=(sq.front+1)%maxsize；B.sq.front=sq.front+1；

C.sq.rear=(sq.rear+1)5^maxsize；D.sq.rear=sq.rear+1；

11.循環(huán)隊(duì)列的隊(duì)滿條件為()o

A.(sq.rear+1)%maxsize==(sq.front+1)%maxsize；B.(sq.rear+1)%

maxsize==sq.front+1；C.(sq.rear+1)%maxsize==sq.front；

D.sq.rear==sq.front；

12.循環(huán)隊(duì)列的隊(duì)空條件為()o

9

A.（sq.rear+1）%maxsize==（sq.front+1）%maxsize；B.（sq.rear+1）%

maxsize==sq.front+1；C.（sq.rear+1）%maxsize==sq.front；

D.sq.rear==sq.front；

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

A.必須判別棧是否滿B.判別棧元素的類型C.必須判別棧是否空D.對(duì)棧不做任何判

別

14,向一個(gè)棧頂指針為Top的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟為（）o

A.Top->next=s；B.s->next=Top->next；Top->next=s；C.s->next=Top；

Top=s；D.s->next=Top；Top=Top->next；

15.從棧頂指針為Top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪結(jié)點(diǎn)的值保存到x中，其操作步驟為

（）o

A.x=Top->data；Top=Top->next；B.Top=Top->next；x=Top->data；C.x=Top；

Top=Top->next；D.x=Top->data；

16.在一個(gè)鏈隊(duì)中，苕f、r分別為隊(duì)頭、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（）。

A.f->next=s；f=s；B.r->next=s；r=s；C.s->next=r；r=s；D.s-

>next=f；f=s；

17.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（）o

A.e,d,c,b,aB.d,e,c,b,aC.d,c,e?a,bD.a,b,c,d,e

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

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

19.設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.棧C.隊(duì)列D.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二、判斷題

1.在順序棧棧滿情況下，不能再入棧，否則會(huì)產(chǎn)生“上溢”。

2.與順序棧相比，鏈棧的一個(gè)優(yōu)點(diǎn)是插入和刪除操作更加方便。

3.若一個(gè)棧的輸入序列為1,2,3,n,其輸出序列的第一個(gè)元素為n,則其輸出序列的

每個(gè)元素ai一定滿足ai=i+l（i=L2,—,n）。

4.在鏈隊(duì)中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。

5.在對(duì)鏈隊(duì)（帶頭指針）做出隊(duì)操作時(shí)，不會(huì)改變front指針的值。

6.循環(huán)隊(duì)列中元素個(gè)數(shù)為rear-front。

7.一個(gè)棧的輸入序列是1,2,3,4,則在棧的輸出序列中可以得到4,3,1,2.

8.一個(gè)棧的輸入序列是1,2,3,4,則在棧的輸出序列中可以得到1,2,3,4。

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

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

三、填空題

1.向一個(gè)棧頂指針為Top的鏈棧中插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，其進(jìn)行的操作是

2.從棧頂指針為Top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)保存在x中，進(jìn)行的操作是

3.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素。

4.假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列棧操作

SSXSXSSXXX之后，得到的輸出序列為o

5.設(shè)有數(shù)組A[m]作為循環(huán)隊(duì)列的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則元素x

執(zhí)行入隊(duì)操作的語(yǔ)句是。

6.在一個(gè)鏈隊(duì)中，如果f、r分別為隊(duì)頭、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作是o

7.棧的邏輯特點(diǎn)是,隊(duì)列的邏輯特點(diǎn)是,二者的共同特

點(diǎn)是O

1()

8.可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

9.在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到°

10.鏈隊(duì)在一定范圍內(nèi)不會(huì)出現(xiàn)的情況。當(dāng)lq.front==lq.rear時(shí)，隊(duì)中

無(wú)元素，此時(shí)。

11.設(shè)一個(gè)鏈棧的棧頂指針為1s,棧中結(jié)點(diǎn)的格式為data:next,棧空的條件是；如

果棧不為空，則出棧操作為p=ls;；free(p)o

12.對(duì)帶有頭結(jié)點(diǎn)的鏈隊(duì)lq,判定隊(duì)列中只有一個(gè)數(shù)據(jù)元素的條件是。

13.設(shè)有一個(gè)空棧，現(xiàn)在輸入序列為1,2,3,4,5,經(jīng)過(guò)push,push,pop,push,pop,

push后，棧頂指針?biāo)冈厥恰?/p>

14.設(shè)用一維數(shù)組A[ln]來(lái)表示一個(gè)棧，令A(yù)[n]為棧底。用整型變量t來(lái)指示當(dāng)前棧頂?shù)奈?/p>

置，A[t]為棧頂元素。往棧中壓入一個(gè)新元素時(shí)，變量t的值,從棧中彈出一

個(gè)元素時(shí)，變量t的值__________________o設(shè)空棧時(shí)，輸入序列a,b,c經(jīng)過(guò)push,pop,

push,push,pop操作后，從棧中彈出的元素是。

四、應(yīng)用題

1.試證明：若借助棧由輸入序列L2,3,n得到輸出序列pLp2,…，pn(它是輸入序

列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在i〈j<k,使pi<pj<pk。

2.設(shè)有字符串為3*-y-a/y，2,試?yán)脳懗鰧⑵滢D(zhuǎn)換為3y-*ay27-的操作過(guò)程。假定用x代

表掃描該字符串過(guò)程中順序取一個(gè)字符入棧的操作，用s代表從棧中取出一個(gè)字符加入到新字

符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS。

3.設(shè)有一個(gè)輸入序列a,b,c,d,兀素經(jīng)過(guò)一個(gè)棧到達(dá)輸出序列，而且兀素一旦離開(kāi)輸入序

列就不能再回到輸入序列，試問(wèn)經(jīng)過(guò)這個(gè)棧后可以得到多少種輸出序列？

4.按照運(yùn)算符優(yōu)先法，畫出對(duì)下面算術(shù)表達(dá)式求值時(shí)，操作數(shù)棧和運(yùn)算符棧的變化過(guò)程：9-

2*4+(8+1)/3。

5.鏈棧中為何不設(shè)置頭結(jié)點(diǎn)？

11

第五節(jié)樹(shù)

（樹(shù)根結(jié)點(diǎn)的高度為1）

一、選擇題

1.以下說(shuō)法錯(cuò)誤的是（）。

A.樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前驅(qū)B.線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有

一個(gè)直接后繼C.二叉樹(shù)與樹(shù)是兩種不同的數(shù)據(jù)結(jié)構(gòu)D.樹(shù)（及一切樹(shù)形結(jié)構(gòu)）是一種

“分支層次'結(jié)構(gòu)

2.以下說(shuō)法錯(cuò)誤的是（）。

A.二叉樹(shù)可以是空集B.二叉樹(shù)的任一結(jié)點(diǎn)都有兩棵子樹(shù)C.二叉樹(shù)與樹(shù)具有相同的樹(shù)形

結(jié)構(gòu)D、二叉樹(shù)中任一結(jié)點(diǎn)的兩棵子樹(shù)有次序之分

3.以下說(shuō)法錯(cuò)誤的是（）。

A.完全二叉樹(shù)上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號(hào)之間的關(guān)系來(lái)表達(dá)B.在三叉鏈表上，

二叉樹(shù)的求雙親操作很容易實(shí)現(xiàn)C.在二叉鏈表上，求根以及求左、右孩子等操作很容易實(shí)

現(xiàn)D.在二叉鏈表上，求雙親操作的時(shí)間性能很好

4.以下說(shuō)法錯(cuò)誤的是（）。

A.一般在哈夫曼樹(shù)中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近B.哈夫曼樹(shù)中沒(méi)有度數(shù)為1的分

支結(jié)點(diǎn)C.若初始森林中共有n棵二叉樹(shù)，最終求得的哈夫曼樹(shù)共有2nT個(gè)結(jié)點(diǎn)D.若

初始森林中共有n棵二叉樹(shù)，進(jìn)行2n-l次合并后才能剩下一棵最終的哈夫曼樹(shù)

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

A.64B.63C.32D.31

6.將含有41個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始編號(hào)，根為1號(hào)，后面按從上到下、從左到右

的順序?qū)Y(jié)點(diǎn)編號(hào)，那么編號(hào)為21的雙親結(jié)點(diǎn)編號(hào)為（）。

A.10B.11C.41D.20

7.任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在其前序、中序、后序遍歷序列中的相對(duì)位置（）。

A.肯定發(fā)生變化B.有時(shí)發(fā)生變化C.肯定不發(fā)生變化D.無(wú)法確定

8.設(shè)二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則其深度為（）。

A.n-1B.nC.Llog2nJ+1D.無(wú)法確定

9.設(shè)深度為k的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則這類二叉樹(shù)上所含結(jié)點(diǎn)總數(shù)最少（）

個(gè)。

A.k+1B.2kC.2k-lD.2k+l

10.下列說(shuō)法正確的是（）o

A.樹(shù)的前序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的前序遍歷序列相同B.樹(shù)的前序遍歷序列與其

對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同C.樹(shù)的后序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的前序遍歷序

列相同D.樹(shù)的后序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同

11.下列說(shuō)法中正確的是（）。

A.任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2B.任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為

2C.任何一棵二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的度肯定等于2D.任何一棵二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的度

都可以小于2

12.一棵二叉樹(shù)滿足下列條件：對(duì)任意結(jié)點(diǎn)，若存在左、右子樹(shù)，則其值都小于它的左子樹(shù)上

所有結(jié)點(diǎn)的值，而大于右子樹(shù)上所有結(jié)點(diǎn)的值?，F(xiàn)采用（）遍歷方式就可以得到這棵二叉樹(shù)

所有結(jié)點(diǎn)的遞減序列。

A.前序B.中序C.后序D.層次

13.設(shè)森林T中有4棵樹(shù)，結(jié)點(diǎn)個(gè)數(shù)分別是nl、n2、n3、n4,當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹(shù)

后，根結(jié)點(diǎn)的右子樹(shù)上有（）個(gè)結(jié)點(diǎn)。

A.nl-1B.nlC.nl+n2+n3D.n2+n3+n4

14.對(duì)含有（）個(gè)結(jié)點(diǎn)的非空二叉樹(shù)，采用任何一種遍歷方式，其結(jié)點(diǎn)訪問(wèn)序列均相同。

A.0B.1C.2D.不存在這樣的二叉樹(shù)

12

15.如圖6-1所示的二叉樹(shù)的中序遍歷序列是（）。

16.已知某二叉樹(shù)的后序遍歷序列是deacb,中序遍歷序列是deabc,它的前序遍歷序列是

（）。

A.acbedB.baedcC.dceabD.cedba

17.如果T1是由有序樹(shù)轉(zhuǎn)化而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是T1中結(jié)點(diǎn)的（）。

A前序B中序C后序D層次序

18.某二叉樹(shù)的前序遍歷的結(jié)點(diǎn)訪問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是

dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是（）。

A.bdgcefhaB.gdbecfhaC.bdgechfaD.gdbehfca

19.在圖6-2中的二叉樹(shù)中，（）不是完全二叉樹(shù)。

20.樹(shù)最適合用來(lái)表示（）o

A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元

素之間無(wú)聯(lián)系的數(shù)據(jù)

21.在計(jì)算遞歸函數(shù)時(shí)，如不使用遞歸過(guò)程，則一般情況下必須借助于（）數(shù)據(jù)結(jié)構(gòu)。

A.棧B.樹(shù)C.雙向隊(duì)列D.順序表

22.設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0,一棵高度為h的滿二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)是（）。

A.2hB.2h-lC.2h-lD.2h+l-l

23.以下說(shuō)法錯(cuò)誤的是（）0

A.存在這樣的二叉樹(shù)，對(duì)它采用任何次序的遍歷，其結(jié)點(diǎn)訪問(wèn)序列均相同B.二叉樹(shù)是

樹(shù)的特殊情形C.由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的D.在二叉樹(shù)只有一棵

子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)

24.已知一個(gè)算式的中綴表達(dá)式為a+（b-c）/d,則其后綴表達(dá)式是（）。

A.a+（b-c）/dB.abc-d/+C.bc-d/a+D.a+bc-d/

25.按照二叉樹(shù)的定義，具有4個(gè)結(jié)點(diǎn)所能構(gòu)造的不同的二叉樹(shù)的個(gè)數(shù)是（）。

A.4B.8C.12D.14

26.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)的個(gè)數(shù)為2,度為2的結(jié)點(diǎn)的個(gè)數(shù)為1,則度為。的

結(jié)點(diǎn)的個(gè)數(shù)為（）。

13

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

27.3個(gè)結(jié)點(diǎn)可構(gòu)成（）棵不同形態(tài)的二叉樹(shù)。

A.2B.3C.4D.5

28.哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是（）。

A.所有結(jié)點(diǎn)權(quán)值之和B.所有葉結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和C.帶權(quán)結(jié)點(diǎn)的值D.除根

以外所有結(jié)點(diǎn)權(quán)值之和

29.設(shè)有一棵22個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，那么整棵二叉樹(shù)有（）個(gè)度為0的結(jié)點(diǎn)。

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

30.已知完全二叉樹(shù)有26個(gè)結(jié)點(diǎn)，則整棵二叉樹(shù)有（）個(gè)度為1的結(jié)點(diǎn)。

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

31.在樹(shù)的孩子兄弟表示法中，（）操作花時(shí)間最多。

A.求某結(jié)點(diǎn)的兄弟B.求某結(jié)點(diǎn)的第i個(gè)孩子C.求某結(jié)點(diǎn)的父結(jié)點(diǎn)D.求樹(shù)的根結(jié)點(diǎn)

32.已知如圖6-3所示的哈夫曼樹(shù)，那么電文CDAA的編碼是（）。

A.110100B.11011100C.010110111D.11111100

33.在n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，對(duì)任一結(jié)點(diǎn)i（lWi<n）,i的左孩子可能是（）。

A.i/2B.2i+lC.2iD.都不是

34.已給出圖6-3所示的二叉樹(shù)，A,B,C,D的權(quán)值分別為7,5,2,4,則該樹(shù)的帶權(quán)路徑

長(zhǎng)度為（）。

A.46B.36C.35D.都不是

35.下列敘述中正確的是（）。

A.二叉樹(shù)是度為2的有序樹(shù)B.二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分C.二叉樹(shù)

中必有度為2的結(jié)點(diǎn)D.二叉樹(shù)中結(jié)點(diǎn)最多有兩棵子樹(shù)，并且有左右之分

36.圖6-4所示的幾種結(jié)構(gòu)中屬于樹(shù)形結(jié)構(gòu)的是（）o

二、判斷題

1.二叉樹(shù)是樹(shù)的特殊形式。

2.樹(shù)和二叉樹(shù)之間最主要的差別是：二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分為左右子樹(shù)，即使在結(jié)點(diǎn)只

有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。

3.一棵有n個(gè)結(jié)點(diǎn)的d度樹(shù)，若用多重鏈表表示，樹(shù)中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在樹(shù)的n*d

個(gè)鏈域中，有n*（dT）+l個(gè)是空鏈域，只有聯(lián)1個(gè)是非空的。

4.前序遍歷樹(shù)和前序遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果相同。

5.中序遍歷樹(shù)和中序遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同。

6.前序遍歷森林和前序遍歷與該森林對(duì)應(yīng)的二叉樹(shù)，其結(jié)果相同。

7.中序遍歷森林和中序遍歷與該森林對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同。

14

8.若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹(shù)的前

序遍歷序列中的最后一個(gè)結(jié)點(diǎn),

9.二叉樹(shù)具有兩個(gè)子女而%結(jié)點(diǎn)，在中序遍歷序列中，它的后繼結(jié)點(diǎn)最多只能有一個(gè)子女。

10.在二叉樹(shù)中，具有一個(gè)子女的父結(jié)點(diǎn)，在中序遍歷中，它沒(méi)有后繼的子女結(jié)點(diǎn)。

11.在二叉樹(shù)中插入結(jié)點(diǎn)，該二叉樹(shù)便不再是二叉樹(shù)。

12.用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。

13.已知二叉樹(shù)的前序遍歷和后序遍歷序列不能惟一地確定這棵樹(shù)。

14.不使用遞歸，也可以實(shí)現(xiàn)二叉樹(shù)的前序、中序、后序遍歷。

15.在前序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)之后。

16.有n個(gè)結(jié)點(diǎn)的不同二叉樹(shù)有n!棵。

17.在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)做特殊

處理。

三、填空題

1.樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種結(jié)構(gòu)。在樹(shù)中，結(jié)點(diǎn)沒(méi)有直接前驅(qū)。對(duì)樹(shù)上

任一結(jié)點(diǎn)x來(lái)說(shuō)，x是它的任一子樹(shù)的根結(jié)點(diǎn)惟一的。

2.一棵樹(shù)上的任何結(jié)點(diǎn)(不包括根本身)稱為根的o若B是A的子孫，則稱A是B

的。

3.二叉樹(shù)第i(i>0)層上至多有個(gè)結(jié)點(diǎn)。

4.深度為k(k>0)的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)。

5.對(duì)任何二義樹(shù)，若度為2的節(jié)點(diǎn)數(shù)為n2,則葉子數(shù)nO=。

6.滿二叉樹(shù)上各層的節(jié)點(diǎn)數(shù)已達(dá)到了二叉樹(shù)可以容納的o滿二叉樹(shù)也是

二叉樹(shù)，但反之不然。

7.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為o

8.在順序存儲(chǔ)的二叉樹(shù)中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是。

9.如果將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則對(duì)任一編號(hào)為i(O<i<n+l)的結(jié)點(diǎn)x,

有：(1)若i=l,則結(jié)點(diǎn)X是；若i>l,則X的雙親PARENT(X)的編號(hào)為

o(2)若2i>n,則結(jié)點(diǎn)x無(wú)且無(wú)；否則，X的左孩子

LCHILD(X)的編