華東交大數(shù)據(jù)結(jié)構(gòu)自測卷及答案

華東交大數(shù)據(jù)結(jié)構(gòu)自測卷及答案

一、填空題

1.算法的計(jì)算量的大小稱之計(jì)算的（B）。

A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度

2.算法的時(shí)間復(fù)雜度取決于（C）

A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A與B

3.計(jì)算機(jī)算法指的是（C）,它務(wù)必具備（B）這三個(gè)特性。

（1）A.計(jì)算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法

（2）A.可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性

C.確定性、有窮性、穩(wěn)固性D.易讀性、穩(wěn)固性、安全性

4.從邏輯上能夠把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類。

A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

5.下列與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（D）。

A.循環(huán)隊(duì)列B.鏈表C.哈希表1）.棧

6.下列數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)不是線性結(jié)構(gòu)（B）?

A.廣義表B.二叉樹C.稀疏矩陣D.串

7.下列那一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（A）

A.棧B.哈希表C.線索樹I）.雙向鏈表

8.在下面的程序段中，對x的賦值語句的頻度為（C）

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

2

A.0(2n)B.0(n)C.0(n)D.0(log2")

9.程序段FORi:=nTDOWNTO1DO

FORj:=lTOiDO

IFA[j]>A[j+l]

THENA[j]與A[j+1]對換；

其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（D）

A.0（n）B.O（nlogn）C.0（n3）D.0（n2）

10.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（I））

A.棧B.廣義表C.有向圖D.字符串

11.下列數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹B.字符串C.隊(duì)D.棧

12.下列數(shù)據(jù)中，（C）是非線性數(shù)據(jù)結(jié)構(gòu)。

A.棧B.隊(duì)列C.完全二叉樹D.堆

13.連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（A）。

A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)

14.下列屬于邏輯結(jié)構(gòu)的是（C）。

A.順序表B.哈希表C.有序表D.單鏈表

二、推斷題

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

2.記錄是數(shù)據(jù)處理的最小單位。（T）

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系：（F）

4.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（F）

5.健壯的算法不可能因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（T）

6.算法能夠用不一致的語言描述，假如用C語言或者PASCAL語言等高級(jí)語言來描述，則

算法實(shí)際上就是程序了。（T）

7.程序一定是算法。（T）

8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。（T）

9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。（F）

10.在順序存儲(chǔ)結(jié)構(gòu)中，有的時(shí)候也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（F）

11.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（F）

12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。（T）

13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依靠于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu).（F）

三、填空

1.數(shù)據(jù)的物理結(jié)構(gòu)包含數(shù)據(jù)元素的表示與數(shù)據(jù)關(guān)系的表示。

2.關(guān)于給定的n個(gè)元素,能夠構(gòu)造出的邏輯結(jié)構(gòu)有集合，線性，樹，圖（網(wǎng)）

_四種。

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。

4.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中表示稱之存儲(chǔ)結(jié)構(gòu)。

5.抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示與

實(shí)現(xiàn)無關(guān),即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變,都不影響其外部使用。

6.數(shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個(gè)重要指標(biāo)是時(shí)間復(fù)雜度與空間復(fù)雜度

7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，與它們之間的相互關(guān)系，并對與這種

結(jié)構(gòu)定義相應(yīng)的操作，設(shè)計(jì)出相應(yīng)的算法。

8.一個(gè)算法具有5個(gè)特性：有窮性、確定性、可行性，有零個(gè)或者多個(gè)輸入、有一個(gè)

或者多個(gè)輸出。

9.已知如下程序段

for（i=n;i>=1;i-）{語句1}

（

x=x+1;{語句2}

for（j=n；j>i；j—）{語句3}

y=y+1;{語句4}

）;

語句1執(zhí)行的頻度為n+l；語句2執(zhí)行的頻度為上；語句3執(zhí)行的頻度為n（n+l）/2；

語句4執(zhí)行的頻度為（n-l）n/2。

10.在下面的程序段中，對x的賦值語句的頻度為6+3/+211）/6（表示為n的函數(shù)）

for（i=1;i<=n；i++）

for（j=1;j<=i;j++）

for（k=1;k<=j;k++）

x:=x+delta;

11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是：1。刎

i=1；whiIe（i<n）i=i*2；

12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（nlog2n）。

1=1；

whiIe（i<n）{for（j=1;j<=n;j++）x=x+1;i=i*2}

13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是(logm)

i=n*nwhile(i!=1)i=i/2；

14.計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為_(n+3)(n-2)/2.。

for(i=l;i<n-1；i++)

for(j=n；j>=i;j-)

s；

15.下面程序段的時(shí)間復(fù)雜度為Ji"____o(n>l)

sum=1；

for(i=0;sum<n;i++)suirr+-=i;

四、應(yīng)用題

1、有如下幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對應(yīng)的邏輯圖表示形式,

并指出它們分別屬于何種結(jié)構(gòu)。(注意：?表示有方向，()表示無方向)

(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)、

r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

線性表、棧與隊(duì)列測試題

姓名班級(jí)學(xué)號(hào)

選擇題(共25分)

(B)1、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？

A.線性表使用順序存儲(chǔ)，務(wù)必占用一片連續(xù)的存儲(chǔ)單元。

B.線性表使用順序存儲(chǔ)，便于進(jìn)行插入與刪除操作。

C.線性表使用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。

D.線性表使用鏈接存儲(chǔ)，便于插入與刪除操作。

(A)2、若某線性表最常用的操作是存取任一指定序號(hào)的元素與在最后

進(jìn)行插入與刪除運(yùn)算，則利用()存儲(chǔ)方式最節(jié)約時(shí)間。

A.順序表B.雙鏈表

C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表

(C)3、若長度為n的線性表使用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一

個(gè)新元素的算法的時(shí)間復(fù)雜度為()(l<=i<=n+l)。

A.0(0)B.0(1)C.0(n)D.0(n2)

(B)4、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操

作是：

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

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

(B)5、關(guān)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表

的條件是()

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

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

(B)6.棧中元素的進(jìn)出原則是

A.先進(jìn)先出B.后進(jìn)先出C棧空則進(jìn)D棧滿

則出

(C)7.若已知一個(gè)棧的入棧序列是1,2,3,…，n,其輸出序列為

pl,p2,p3,...?pn,若pl=n,貝Upi為

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

(B)8.判定一個(gè)棧ST(最多元素為mO)為空的條件是

A.ST->top<>0B.ST->top=0C.ST->top<>mO

D.ST->top=mO

(A)9.判定一個(gè)隊(duì)列QU(最多元素為mO)為滿隊(duì)列的條件是

A.QU->rear—QU->front==mOB.QU->rear—QU->front

-1==mO

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

(D)10.數(shù)組Q[n]用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的

前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n,

計(jì)算隊(duì)列中元素的公式為

(A)r—f;(B)(n+f—r)%n;(C)n+r—f;(D)(n

+r—f)%n

11.設(shè)有4個(gè)數(shù)據(jù)元素al、a2、a3與a4,對他們分別進(jìn)行棧操作或者隊(duì)操作。

在進(jìn)?；蛘哌M(jìn)隊(duì)操作時(shí)，按al、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)

?；蛘哧?duì)的初始狀態(tài)都是空。

現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，

第一次出棧得到的元素是②,第二次出棧得到的元素是

④—;類似地，考慮對這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一

次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是—①—，第

二次出隊(duì)得到的元素是—②—。經(jīng)操作后，最后在棧中或者隊(duì)中的元素還

有一②一個(gè)。

供選擇的答案:A?D：①al②a2③a3④a4E：①1②2

③3@0

答：A、B、C、D、E分別為、、、、

12.棧是一種線性表，它的特點(diǎn)是A。設(shè)用一維數(shù)組來表示一個(gè)

棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧

中推入(PUSH)一個(gè)新元素時(shí)，變量T的值5___；從棧中彈出(POP)

一個(gè)元素時(shí)，變量T的值_____o設(shè)?？諘r(shí)，有輸入序列a,b,c,通過

PUSH,POP,PUSH,PUSH,POP操作后，從棧中彈出的元素的序列是

D，變量T的值是E。

供選擇的答案:

A：①先進(jìn)先出②后進(jìn)先出③進(jìn)優(yōu)于出④出優(yōu)于進(jìn)⑤

隨機(jī)進(jìn)出

B,C：①加1②減1③不變④清0⑤加2

⑥減2

D：①a,b②b,c③c,a④b,a⑤c,b

⑥a,c

E：①n+1②n+2③n@n-l⑤n-2

答：A、B、C、D、E分別為②_、_②—、①、(6)_?_

13.在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否_A_；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧

是否3o當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的

最大容量為C。

為了增加內(nèi)存空間的利用率與減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的

內(nèi)存空間時(shí)，應(yīng)將兩棧的3分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有

當(dāng)E時(shí),才產(chǎn)生上溢。

供選擇的答案:

A,B：①空②滿③上溢④下溢

C：①n-1②n③n+1@n/2

D：①長度②深度③棧頂④棧底

E：①兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn)

②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)

③兩個(gè)棧的棧頂在棧空間的某一位置相遇

④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底

答：A、B、C、D、E分別為―②—、―①—、_②、_?、_?

二、推斷題(共10分)

(F)1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)能夠是一

個(gè)復(fù)雜類型。

(F)2.在表結(jié)構(gòu)中最常用的是線性表，棧與隊(duì)列不太常用。

(T)3.棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一

種后進(jìn)先出型結(jié)構(gòu)。

(T)4.關(guān)于不一致的使用者，一個(gè)表結(jié)構(gòu)既能夠是棧，也能夠是隊(duì)列，也能

夠是線性表。

(F)5.棧與鏈表是兩種不一致的數(shù)據(jù)結(jié)構(gòu)。

(F)6.棧與隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。

(T)7.棧與隊(duì)列的存儲(chǔ)方式既但是順序方式，也但是鏈接方式。

(T)8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì),

應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。

(F)9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)

后出型結(jié)構(gòu)。

(F)10.一個(gè)棧的輸入序列是12345,則棧的輸出序列不可能是12345o

三、填空題(共20分)

1.線性表、棧與隊(duì)列都是線性結(jié)構(gòu),能夠在線性表的任意位

置插入與刪除元素；關(guān)于棧只能在棧頂插入與刪除元素:關(guān)于隊(duì)列

只能在隊(duì)尾插入與隊(duì)頭刪除元素。

2.棧是一種特殊的線性表，同意插入與刪除運(yùn)算的一端稱之棧頂。

不同意插入與刪除運(yùn)算的一端稱之棧底。

3.隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算,在表的另一端進(jìn)行刪

除運(yùn)算的線性表。

4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的當(dāng)前位置。

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

6.向棧中壓入元素的操作是先插入數(shù)據(jù)，后移動(dòng)指

針o

7.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先讀取元素，后移動(dòng)指

針O

8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長度等于0。

9.表達(dá)式23+((12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是

_23123*2-4/345*7/++1089/+

10.已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元

素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。

a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是：(4)(1)o

b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是：711841-

c.在表首插入S結(jié)點(diǎn)的語句序列是：512o

d.在表尾插入S結(jié)點(diǎn)的語句序列是：916。

供選擇的語句有：

(1)P->next=S;(2)P->next=P->next->next;(3)P->next=S->next;

(4)S->next=P->next;(5)S->next=L;(6)S->next=NULL;(7)Q=P;

(8)while(P->next!=Q)P=P->next;(9)while(P->next!=NULL)P=P->next;

(10)P=Q;(11)P=L;(12)L=S;(13)L=P;

四、簡答題(共15分)

1、說明線性表、棧與隊(duì)的異同點(diǎn)。

2、順序隊(duì)的“假溢出”是如何產(chǎn)生的？如何明白循環(huán)隊(duì)列是空還是滿？

3、設(shè)循環(huán)隊(duì)列的容量為40(序號(hào)從0到39),現(xiàn)通過一系列的入隊(duì)與出隊(duì)

運(yùn)算后，有

①front=ll,rear=19;②front=19,rear=l1；問在這兩種情況下，循環(huán)隊(duì)列中

各有元素多少個(gè)？

五、算法設(shè)計(jì)(共30分)

1、寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。

StatusDelete_k(SqlistL,inti,intk)

(

if(i<O||i>L.length||i+k>L.length)returnerror;

for(intj=i+k;j<L.length;j++)

(

L.elem[j-k]=L.elem[j];

L.length-=k;

returnOK;

2、試寫一個(gè)算法，判別讀入的一個(gè)以，@，為結(jié)束符的字符序列是否是“回文”。

(正讀與反讀都相同的字符序列為“回文”，比如，匕bba，與匕bcba，是回文，

匕bcde'與'ababab'則不是回文。)

StatusHuiWen(chars[])

(

inti=0;

SqStackS;

InitStack(S);

while(s[i]!=,@,)

{

Push(S,s[i]);

cout?"push,,?s[i];

i++；

)

i=0;

while(s[i]!=,@,)

{

chare;

Pop(S,e);

cout?e?n*n?s[i];

if(e!=s[i])break;

i++；

)

if(s[i]=-@-)retum1;//返回結(jié)果1表示是回文，0表示不是回文

elsereturn0;

)

3、假設(shè)有一個(gè)循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點(diǎn)也無頭指針。已知s

為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前

趨結(jié)點(diǎn)。

StatusDelete(LinkLists)

(

p=s；

while(p->next->next!=s)〃查找s的前一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)；

p=p->next;

q=p->next;

p->next=s;

deleteq;

returnOK;

)

第6章樹與圖自測卷姓名__班級(jí).一學(xué)建

題號(hào)—■二三四五總分

題分1017174016100

得分

一、下面是有關(guān)二叉樹的敘述，請推斷正誤(每小題1分，共10分)

()1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n-1個(gè)非空

指針域。

()2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于lo

()3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。

()4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或者有兩棵空子樹。

()5.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2i-l,其中k是樹的深度。

()6.關(guān)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2'—1

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

()7.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。

()8.不一致的求最小生成樹的方法最后得到的生成樹是相同的.

()9.有n個(gè)頂點(diǎn)的無向圖，使用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣中非零元素

之與的一半。

()10.無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。

二、填空(每空1分，共17分)

1.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有種形態(tài)。

2.一棵深度為6的滿二叉樹有個(gè)分支結(jié)點(diǎn)與個(gè)葉子。

3.一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為o

4.設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有個(gè)葉子結(jié)點(diǎn)。

5.用5個(gè)權(quán)值｛3,2,4,5,1｝構(gòu)造的哈夫曼(Huffman)樹的帶權(quán)路徑長度是。

6.推斷一個(gè)無向圖是一棵樹的條件是.

7.在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間能夠互相到達(dá)，則至少需要條弧。

8.G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有—_個(gè)頂點(diǎn)

9.N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有個(gè)非零元素。

10.在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)____。

11.設(shè)有一稀疏圖G,則G使用存儲(chǔ)較省空間。

12.設(shè)有一稠密圖G,則G使用存儲(chǔ)較省空間。

13.n個(gè)頂點(diǎn)e條邊的圖使用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為:

若使用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為。

14.已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列

是。則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是。

0111101

1001001

1000100

1100110

1011010

0001101

1100010

三、選擇題(每小題1分，共17分)

()1.不含任何結(jié)點(diǎn)的空樹

(A)是一棵樹；(B)是一棵二叉樹；

(C)是一棵樹也是一棵二叉樹;(D)既不是樹也不是二叉樹

()2.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，因此

(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);(B)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存

儲(chǔ);

(C)順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；(D)順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)

結(jié)構(gòu)都不能使用

()3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。

(A)Flog2(n)l(B)Lloga(n)J(C)Llog2(n)J+l(D)Flogs(n)+11

()4.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是。

(A)唯一的(B)有多種

(C)有多種，但根結(jié)點(diǎn)都沒有左孩子(D)有多利*但根結(jié)點(diǎn)都沒有右

孩子

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

A.1/2B.1C.2D.4

()7.在一個(gè)有向圖中，所有頂點(diǎn)的入度之與等于所有頂點(diǎn)的出度之與的____倍。

A.1/2B.1C.2D.4

()8.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是使用_______—來實(shí)現(xiàn)算法的。

A.棧B.隊(duì)列C.樹D.圖

()9.深度優(yōu)先遍歷類似于二叉樹的

A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷

()10.廣度優(yōu)先遍歷類似于二叉樹的

A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷

11.樹是結(jié)點(diǎn)的有限集合，它」根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m(m20)個(gè)」

的集合Tl,T2,…，Tm,每個(gè)集合又都是樹，如今結(jié)點(diǎn)T稱之T,的父結(jié)點(diǎn)，T；稱之T的子

結(jié)點(diǎn)(iWiWm)。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的」。

供選擇的答案

A：①有0個(gè)或者1個(gè)②有。個(gè)或者多個(gè)③有且只有1個(gè)④有1個(gè)或者

1個(gè)以上

B:①互不相交②同意相交③同意葉結(jié)點(diǎn)相交④同意樹枝結(jié)點(diǎn)

相交

C：①權(quán)②維數(shù)③次數(shù)④序

答案：A=B=C=

12.二叉樹A。在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒有B,則它必定是葉結(jié)點(diǎn)。每棵

樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左子女是N

在原樹里對應(yīng)結(jié)點(diǎn)的」，而N的右子女是它在原樹里對應(yīng)結(jié)點(diǎn)的」。

供選擇的答案

A：①是特殊的樹②不是樹的特殊形式③是兩棵樹的總稱④有是只有二個(gè)根結(jié)點(diǎn)

的樹形結(jié)構(gòu)

B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者者沒有右子結(jié)點(diǎn)④兄弟

C~D：①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近的右兄弟④最鄰近

的左兄弟

⑤最左的兄弟⑥最右的兄弟

答案：A=B=C=D=

四、閱讀分析題(每題5分，共40分)

1.給定二叉樹的兩種遍歷序列，分別是：

前序遍歷序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,II,A,G,I,

F,

試畫該出二叉樹

殳先序、列。

3,

4,

5該圖的八

每個(gè)頂點(diǎn)的入心曲.

31頂點(diǎn)12346

鄰接矩陣；圖2

圖1(2)1度321圖32

q⑶鄰接表；

出度022313

(4)逆鄰接表。

6.請對下圖的無向帶權(quán)圖：

（1）寫出它的鄰接矩陣，并按普里姆算

法求其最小生成樹；

(2)寫出它的鄰接表,并按克魯斯卡爾算法求其最小生成樹。

7.已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別

畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹與廣度優(yōu)

先生成樹。10000001010

8.給定下列網(wǎng)G:（10分）:0010001000

0001000100

40000100010

50000010001

61100000000

70010000001

81001000010

90000101001

101000010000

1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖;

2用兩種不一致的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖;

3用C語言（或者其他算法語言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。

五、算法設(shè)計(jì)題（前「5題中任選2題，第6~7題中任選1題，共16分）

1.編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。

2.寫出求二叉樹深度的算法，先定義二叉樹的抽象數(shù)據(jù)類型。

3.編寫遞歸算法，求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。

4.編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。

5.編寫算法判別給定二叉樹是否為完全二叉樹。

6.編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息與各條弧的信息建立有向

圖的鄰接表。

解：StatusBuildAdjList（ALGraph&G）〃輸入有向圖的頂點(diǎn)數(shù)，邊數(shù)，頂點(diǎn)信息與邊的信

息，以建立鄰接表

returnOK;

}//BuildAdjList

7.試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w),即刪除一條邊的操作。

(假如要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？提示：將鄰接矩陣的第i行全部置0)

解：〃設(shè)本題中的圖G為有向無權(quán)圖

StatusDeleteArc(MGraph&G,charv,charw)〃在鄰接矩陣表示的圖G上刪除邊

(v,w)

returnOK;}//Delete_Arc

答案：

12345678910

VXXXXXVXVX

—*、

156n個(gè)頂點(diǎn)n-1條邊的連通圖11鄰接表

231,327n12鄰接矩陣

3989130(n2)

0(n+e)

435092(n-1)140134256

0123465

53312*(n-1)15

0

四、

1、

答：

前序遍歷序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,H,A,

G,I,F,

試畫出二叉樹B,并簡述由任意二叉樹B的前序遍歷序列與中序遍歷序列求二叉樹B的思

想方法。

解：方法是：由前序先確定root,由中序可確定root的左、右子樹。然后由其左子樹的元

素集合與右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將

他們分別作為新的root,不斷遞歸，則所有元素都將被唯一確定，問題得解。

2、答：DLR：ABDFJGKCEH1LM

LDR:BFJDGKACHELIM

LRD：JFKGDBHLMIECA

3、

答：注意全部兄弟之間都要連線（包含度為2的兄弟），并注意原有連線結(jié)點(diǎn)一律歸入左子

樹，新添連線結(jié)點(diǎn)一律歸入右子樹。

4、

答：注意根右邊的子樹確信是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟。

001011

100000

110010

⑶

1

2

3

1

125人

(4)

126人

23

34

42

543

633

6、

解：設(shè)起點(diǎn)為a。能夠直接由原始圖畫出最小生成樹,

04300000000co而且最小生成樹只有一種（類）！

40559000000鄰接矩陣為：

3505oooooo5

005507654

009oo703oooo

00oooo6302oo

00oooo5oo206

00oo54oooo60

e

PRIM算滄最小生成樹f￡b

\2

VbcdefghUv-u

VexaLaaaa{a}{b,c,d,e,f,g,h}

43oooooocooo

lowcost

Vexa0CaaaC{a,c}{b,d,e,f,g,h}

45ooooco5

lowcost

Vex00cbaac{a,c,b}{d,e,f,g,h}

59ooco5

lowcost

Vex000dddd{a,c,b,d){e,f,g,h}

7654

lowcost

Vex000ddd0{a,c,b,d,h{e,f,g}

765

lowcost)

Vex000dg00{a,c,b,d,h,{f,e}

72

lowcostg}

Vex000f000{a,c,b,d,h,{e}

3

lowcostg,f}

Vex0000000{a,c,b,d,h,()

g,f,e}

lowcost

鄰接表為:

0a1423

1b042535

2c031535

3d15254765—*74A

4e193753

5f364362

6g355276

7h253466

克魯斯卡爾算法步驟

tt-iM3+n**、"-cI—3—ea—I—bd—I—h

（按邊歸并，堆排序）：,,__,g珈一人士、茁八昌七比wr

T—7—T-7二一~?~取b—?—d,g—d就把二個(gè)連通分量連接起來了O

7、

8、

1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖；

2用兩種不一致的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；

3用C語言（或者其他算法語言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。

解：1.最小生成樹可直接畫出，如右圖所示。

2.可用鄰接矩陣與鄰接表來描述：

——F

0012000040000

1200200089CO

描述存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型可參見教材或者電子教案:

00200015000012注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表與鄰接矩陣

#defineINFINITYINT_MAX//最大值8

00001500000010

#defineMAX_VERTEX_NUM20〃假設(shè)的最大頂點(diǎn)數(shù)（可取為7）

48CO00006COTypedefenum{DG,DN,AG,AN}GraphKind;〃有向/無向圖，有向/無向網(wǎng)

T\pcdefstructArcCell{〃弧（邊）結(jié)點(diǎn)的定義

009000060000

VRTypeadj;//頂點(diǎn)間關(guān)系，無權(quán)圖取1或者0;有權(quán)圖取權(quán)值類型

00001210000000InfoType*info;〃該弧有關(guān)信息的指針

JArcCell,AdjMatrix[MAX_VERTEX_NUM]f