數(shù)據(jù)結構練習試題附含的答案

數(shù)據(jù)構造練習題

習題1緒論

1.1單項選擇題

1.數(shù)據(jù)構造是?門研究非數(shù)值計算的程序設計問題中，數(shù)據(jù)元素的①、數(shù)據(jù)信息在計算機中的②以及一組相關的運算等的

課程。

①A.操作對象B.計算方法C.邏輯構造D.數(shù)據(jù)映象

②A.存儲構造B.關系C.運算D.算法

2.數(shù)據(jù)構造DS(DataStruct)可以被形式地定義為DS=(D,R),其中D是①的有限集合，R是D上的②有限集合。

①A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.數(shù)據(jù)對象

②A.操作B.映象C.存儲D.關系

3.在數(shù)據(jù)構造中，從邏輯上可以把數(shù)據(jù)構造分成。

A.動態(tài)構造和靜態(tài)構造B.緊湊構造和非緊湊構造

C.線性構造和非線性構造D.內(nèi)部構造和外部構造

4.算法分析的目的是①，算法分析的兩個主要方面是②。

①A.找出數(shù)據(jù)構造的合理性B.研究算法中的輸入和輸出的關系

C.分析算法的效率以求改良D.分析算法的易懂性和文檔性

②A.空間復雜性和時間復雜性B.正確性和簡明性

C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性

5.計算機算法指的是①，它必具備輸入、輸出和②等五個特性。

①A.計算方法B.排序方法

C.解決問題的有限運算序列D.調度方法

②A.可行性、可移植性和可擴大性B.可行性、確定性和有窮性

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

1.2填空題(將正確的答案填在相應的空中)

1.數(shù)據(jù)邏輯構造包括、和三種類型，樹形構造和圖形構造合稱為。

2.在線性構造中，第一個結點前驅結點，其余每個結點有且只有個前驅結點；最后一個結點后續(xù)結點，其余每個結點

有且只有個后續(xù)結點。

3.在樹形構造中，樹根結點沒有結點，其余每個結點有且只有個直接前驅結點，葉子結點沒有結點，其余每個結點的

直接后續(xù)結點可以。

4.在圖形構造中，每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以。

5.線性構造中元素之間存在關系，樹形構造中元素之間存在關系，圖形構造中元素之間存在關系。

6.算法的五個重要特性是—，—，—，—，—。

7.分析下面算法(程序段)，給出最大語句頻度，該算法的時間復雜度是一。

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

for(j=0;j<n;j++)

A[i][j]=O;

8.分析下面算法(程序段)，給出最大語句頻度，該算法的時間復雜度是一o

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

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

A[i][j]=0;

9.分析下面算法(程序段)，給出最大語句頻度，該算法的時間復雜度是—o

s=0;

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

for(j=0;j<n;j++)

for(k=0;k<n;k++)

s=s+B[i][j][k];

sum=s;

10.分析下面算法(程序段)給出最大語句頻度,該算法的時間復雜度是

i=s=O;

while(s<n)

{i++；

s+=i;〃s=s+i

)

11.分析下面算法(程序段)給出最大語句頻度，該算法的時間復雜度是

i=l；

while(i<=n)

i=i*2;

1.3算法設計題

1.試寫一算法，自大到小依次輸出順序讀入的三個數(shù)X,Y和Z的值.

2.試寫一算法，求出n個數(shù)據(jù)中的最大值。寫出最大語句頻度，該算法的時間復雜度。

習題答案

1.11.C,A2.B,D3.C4.C,A5.C,B

1.21.線性構造、樹形構造、圖形構造，非線性構造

2.沒有、1、沒有、1

3.前驅、1、后續(xù)、任意多個

4.任意多個

5.一對一、一對多、多對多

6.有窮性、確定性、可行性、輸入、輸出

7.最大語句頻度：r?,時間復雜度：.0(n2)

8.最大語句頻度:n(n+l)/2,時間復雜度：.0(n2)

9.最大語句頻度：r?「時間復雜度：.0(n3)?

10.最大語句頻度：n2,時間復雜度：.0(n?)

11.最大語句頻度：logzn,時間復雜度：.0(log2n)

習題2線性表

2.1單項選擇題

1_.一個向量(即一批地址連續(xù)的存儲單元)第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址

是o

A.110B.108C.100D.120

2.線性表的順序存儲構造是一種—的存儲構造，而鏈式存儲構造是一種—的存儲構造。

A.隨機存取B.索引存取C.順序存取D.散列存取

3.線性表的邏輯順序與存儲順序總是一致的，這種說法—?

A.正確B.不正確

4.線性表假設采用鏈式存儲構造時，要求內(nèi)存中可用存儲單元的地址一。

A.必須是連續(xù)的B.局部地址必須是連續(xù)的

C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以

5.在以下的表達中，正確的選項是」

A.線性表的順序存儲構造優(yōu)于鏈表存儲構造

B.線性表的順序存儲構造適用于頻繁插入/刪除數(shù)據(jù)元素的情況

C.線性表的鏈表存儲構造適用于頻繁插入/刪除數(shù)據(jù)元素的情況

D.線性表的鏈表存儲構造優(yōu)于順序存儲構造

6.每種數(shù)據(jù)構造都具備三個基本運算：插入、刪除和查找，這種說法—。

A.正確B.不正確

7.不帶頭結點的單鏈表head為空的判定條件是——?

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

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

8.帶頭結點的單鏈表head為空的判定條件是一。

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

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

9.非空的循環(huán)單鏈表head的尾結點(由p所指向)滿足—o

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

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

10.在雙向循環(huán)鏈表的p所指結點之后插入s所指結點的操作是—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;

11.在一個單鏈表中，q所指結點是P所指結點的前驅結點，假設在q和P之間插入s結點，則執(zhí)行—o

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

B.q->next=s;s->next=p;C.p->next=s;s->next=q;

12.在一個單鏈表中，假設p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行—。

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

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

13.在一個單鏈表中，假設刪除p所指結點的后續(xù)結點，則執(zhí)行――?

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

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

14.從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均對比一個結點。

A.nB.n/2C.(n-l)/2D.(n+l)/2

15.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是。

2

A.0(l)B.0(n)C.0(n)D,0(nlog2n)

16.給定有n個元素的向量，建設一個有序單鏈表的時間復雜度是。

A.0(1)]B.0(n)C.0(n2)D.0(n*log2n)

2.2填空題（將正確的答案填在相應的空中）

1.單鏈表可以做一的鏈接存儲表示。

2.在雙鏈表中，每個結點有兩個指針域，一個指向,另一個指向___。

3.在一個單鏈表中p所指結點之前插入一個s（值為e）所指結點時，可執(zhí)行如下操作：

q=head;

while（q->next!=p）q=q->next;

s=newNode;s->data=e;

q->next=;〃填空

s->next=;〃填空

4.在一個單鏈表中刪除p所指結點的后繼結點時，應執(zhí)行以下操作：

q=p->next;

p->next=;〃填空

delete;〃填空

5.在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行s->next=和p->next=__的操作。

6.對于一個具有n個結點的單鏈表，在p所指結點后插入一個新結點的時間復雜度是:在給定值為x的結點后插

入一個新結點的時間復雜度是o

2.3算法設計題:

1.設順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。

StatusInsert_SqList(SqList&va,intx)

{

if(va.length+l>maxsize)returnERROR;

va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i-)

va.elem[i+l]=va.elem[i];

va.elem[i+l]=x;

returnOK;

2.試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表(a，a-逆置為(a“，a-,a)。

voidreverse(inta[],intsize)

(

inti,j,tmp;

for(i=0,j=size-l;i<j;i++,j—)

(

tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

)

3.線性表中的元素以值遞增有序排列，并以單鏈表作存儲構造。試寫一算法，刪除表中所有大于x且小于y的元素(假

設表中存在這樣的元素)同時釋放被刪除結點空間。

voiddel(LinkListL,elemtypea,elemtypeb)

(

p=L;q=p->next;

while(q!=L&&q->data<a)

(

P=q；

q=q->next;

)

while(q!=L&&q->data<b)

(

r=q;

q=q->next;

free(r);

)

if(p!=q)

p->next=q;

)

4.試寫一算法，實現(xiàn)單鏈表的就地逆置(要求在原鏈表上進展)。

voidconverse(NODEPTRL)

NODEPTRp,q;

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

L->next=NULL;

while(p)/*對于當前結點p,用頭插法將結點p插入到頭結點之后*/

p->next=L->next;

L->next=p;

P二q；

q=q->next;

)

習題答案

2.11.B2.A,C3.B4.D5.C6.A7.A8.B

9.C10.D11.B12.B13.A14.D15.B16.C

2.21.線性結表2.前驅結點、后繼結點

3.s,p4.q->next,q

5.p->next,s6.0（1）,0（n）

習題3棧和隊列

3.1單項選擇題

1.一個棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是

A.edcbaB.decbaC.dceabD.abcde

2.假設一個棧的入棧序列是1,2,3,n,其輸出序列為pl,p2,p3,…，pn,假設pl=n,則pi為一。

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

3.棧構造通常采用的兩種存儲構造是——。

A.順序存儲構造和鏈式存儲構造

B.散列方式和索引方式

C.鏈表存儲構造和數(shù)組

D.線性存儲構造和非線性存儲構造

4.判定一個順序棧ST（最多元素為m0）為空的條件是一。

A.top!=0B.top==0C.top!=m0D.top==mOT

5.判定一個順序棧ST（最多元素為mO）為棧滿的條件是一。

A.top!=0B.top==0C.top!=m0D.top==mOT

6.棧的特點是隊列的特點是

A.先進先出B.先進后出

7.向一個棧頂指針為HS的鏈棧中插入一個s所指結點時，則執(zhí)行_?

（不帶空的頭結點）

A.HS一>next=s;

B.s—>next=HS—>next;11S—>next=s;

C.s->next=HS;HS=s;

D.s—>next=HS;HS=HS—>next;

8.從一個棧頂指針為HS的鏈棧中刪除一個結點時，用x保存被刪結點的值，則執(zhí)行—?（不帶空的頭結點）

A.x=HS;HS=HS一>next;B.x=HS一>data;

C.HS=HS—>next;x=HS—>data;D.x=HS—>data;HS=HS—>next;

9.一個隊列的數(shù)據(jù)入列序列是1,2,3,4,則隊列的出隊時輸出序列是o

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

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

10.判定一個循環(huán)隊列QU（最多元素為m0）為空的條件是—o

A.rear-front==m0B.rear-front-l==m0

C.front==rearD.front==rear+1

11.判定一個循環(huán)隊列QU（最多元素為mO,m0==Maxsize-l）為滿隊列的條件是__。

A.（（rear-front）+Maxsize）%Maxsize==m0

B.rear-front-l==m0

C.front==rear

D.front==rear+1

12.循環(huán)隊列用數(shù)組A[0,m-1]存放其元素值，其頭尾指針分別是front和rear,則當前隊列中的元素個數(shù)是.

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

13.棧和隊列的共同點是一o

A.都是先進后出B.都是先進先出

C.只允許在端點處插入和刪除元素D.沒有共同點

3.2填空題（將正確的答案填在相應的空中）

1.向量、棧和隊列都是—構造，可以在向量的—位置插入和刪除元素；對于棧只能在—插入和刪除元素；對于

隊列只能在插入元素和刪除元素。

2.向一個長度為n的向量的第i個元素（IWiWn+l）之前插入一個元素時，需向后移動一個元素。

3.向一個長度為n的向量中刪除第i個元素（IWiWn）時，需向前移動一個元素。

4.在具有n個單元的循環(huán)隊列中，隊滿時共有個元素。

習題答案

3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C

11.A12.A13.C

3.21.線性、任何、棧頂、隊尾、隊首2.n-i+13.n-i

4.n-1

習題6樹和二叉樹

6.1單項選擇題

1.由于二叉樹中每個結點的度最大為2,所以二叉樹是一種特殊的樹，這種說法—o

A.正確B.錯誤

2.假定在一棵二叉樹中，雙分支結點數(shù)為15,單分支結點數(shù)為30個，則葉子結點數(shù)為個。A.15B.16

C.17D.47

3.按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有種。

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

4.按照二叉樹的定義，具有3個不同數(shù)據(jù)結點的不同的二叉樹有一種。

A.5B.6C.30D.32

5.深度為5的二叉樹至多有一個結點。

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

6.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為。

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

7.對一個滿二叉樹，m個樹葉，n個結點，深度為h,則__。

A.n=h+mB.h+m=2nC.m=h-lD.n=2h-l

8.任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序—。

A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對

9.如果某二叉樹的前根次序遍歷結果為stuwv,中序遍歷為uwtvs,那么該二叉樹的后序為。A.uwvts

B.vwutsC.wuvtsD.wutsv

10.二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法。A.正確B.錯

誤

11.某二叉樹的前序遍歷結點訪問順序是abdgcefh,中序遍歷的結點訪問順序是dgbaechf,則其后序遍歷的結點訪問

順序是—o

A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca

12.在一非空二叉樹的中序遍歷序列中，根結點的右邊—o

A.只有右子樹上的所有結點B.只有右子樹上的局部結點

C.只有左子樹上的局部結點D.只有左子樹上的所有結點

13.如圖6.1所示二叉樹的中序遍歷序列是一。

A.abcdgefB.dfebagcC.dbaefcgD.defbagc

二叉樹如圖6.2所示，其中序遍歷峭列為—。

abdgcefhB.dgbaechf（S-^gdbehfcaD.

為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前的

b的右方B.a在b的左方

D.a是b的子孫

16.某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是__?A.acbedB.decabC.

deabcD.cedba

17.實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧構造，最正確方案是二叉樹采用—存儲構造。

A.二叉鏈表B.廣義表存儲構造C.三叉鏈表D.順序存儲構造

18.如圖6.3所示的4棵二叉樹，—不是完全二叉樹。

left=NULLD.以上都不對

21.二叉樹按某(B)(C)種順序線索化后，任一

結點均有指向其前驅圖6.3和后續(xù)的線索，這種說

法___。A.正確B.錯誤

22.二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法

A.正確B.錯誤

23.具有五層結點的二叉平衡樹至少有一個結點。

A.10B.12C.15D.17

24.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。

這里，我們把由樹轉化得到的二叉樹叫做這棵數(shù)對應的二叉樹。結論—是正確的。

A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列一樣

B.樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列一樣

C.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列一樣

D.以上都不對

25.樹最適合用來表示___。

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

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

6.2填空題(將正確的答案填在相應的空中)

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

⑴這棵樹的根結點是「；

⑵這棵樹的葉子結點是—;

⑶結點k3的度是____；

(4)這棵樹的度是___；

⑸這棵樹的深度是——；

(6)結點k3的子女是——；

(7)結點k3的父結點是—

2.指出樹和二叉樹的三個主要差異、

3.從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)構造，將樹轉化為二叉樹的基本目

的是一。

4.一棵二叉樹的結點數(shù)據(jù)采用順序存儲構造，存儲于數(shù)組t中，如圖6.6所示，則該二叉樹的鏈接表示形式為。

5.深度為k的完全二叉樹至少有一個結點。至多有一個結點，假設按自上而下，從左到右次序給結點編號(從1

開場)，則編號最小的葉子結點的編號是一。

123456789101112131415161718192021

圖6.6一棵二叉樹的順序存儲數(shù)組t

6.在一棵二叉樹中，度為零的結點的個數(shù)為n。，度為2的結點的個數(shù)為nz,則有n產(chǎn)—。

7.一棵二叉樹的第i(i》l)層最多有一個結點；一棵有n(n>0)個結點的滿二叉樹共有.個葉子和個非終

端結點。

8.結點最少的樹為—_,結點最少的二叉樹為_—。

9.現(xiàn)有按中序遍歷二叉樹的結果為abc,問有種不同形態(tài)的二叉樹可以得到這一遍歷結果，這些二叉樹分別是一。

10.由如圖6.7所示的二叉樹，答復以下問題：

⑴其中序遍歷序列為—；…

de

h

⑵其前序遍歷序列為

⑶其后序遍歷序列為

6.3簡答題

1.根據(jù)二叉樹的定義，具有三個結點的二叉樹有5種不同的形態(tài)，請將它們分別畫出。

2.假設一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJKo

請畫出該樹。

3.由如圖6.7所示的二叉樹，答復以下問題：

(1)畫出該二叉樹的中序線索二叉樹；

(2)畫出該二叉樹的后序線索二叉樹；

(3)畫出該二叉樹對應的森林。

4.一棵樹如圖6.8所示，轉化為一棵二叉樹，表示為.

5.以數(shù)據(jù)集｛4,5,6,7,10,12,18｝為結點權值，畫出構造Huffman樹的每一步圖示,計算

其帶權路徑長度為。

6.一棵含有N個結點的k義樹,可能到達的最大深度和最小深度各為多少？

7.證明：一棵滿k叉樹上的葉子結點數(shù)n0和非葉子結點數(shù)n,圖6.8一棵樹之間滿足以下關系:

n(,=(kT)n]+l

6.4算法設計題

1.編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。

2.試編寫算法，對一棵二叉樹，統(tǒng)計葉子的個數(shù)。

3.試編寫算法，對一棵二叉樹根結點不變，將左、右子樹進展交換，樹中每個結點的左、右子樹進展交換。

7.假設用于通訊的電文僅有八個字母(a,b,c,d,e,f,g,h)組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,

0.32,0.03,0.21,0.10o試為這八個字母設計哈夫曼編碼。

使用0-7的二進制表示形式是另一種編碼方案。對于上述實例，對比兩種方案的優(yōu)缺點。

8.試編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計葉子的個數(shù)。假設一棵二叉樹的先序序列為EBADCFHGIKJ和中

序序列為ABCDEFGI1IJK。請畫出該樹。

習題答案

6.11.B2.B3.C4.C5.C6.A7.D8.A9.C10.A

11.D2.A13.B14.B15.B16.D17.C18.C

19.B20.B21.B22.B23.B24.A25.C

6.2

1.(1)kl⑵k2,k5,k7,k4⑶2(4)3(5)4(6)k5,k6⑺kl

2.樹的結點個數(shù)至少為1(不同教材規(guī)定不同)，而二叉樹的結點個數(shù)可以為0;

樹中結點的最大度數(shù)沒有限制，而二叉樹結點的最大度數(shù)為2；

樹的結點無左、右之分，而二叉樹的結點有左、右之分；

目的‘并利用二叉樹的已有算法解

3.樹可采用孩子-兄弟鏈表(二叉鏈表)做存儲構造，

決樹的有關問題。

4.如圖6.9所示

5.2J2k-l、2k2+l

6.n2+l

[logn+l]-lr)[logn+1]1

7.2'T22/2-1

8.只有一個結點的樹;空的二叉樹圖6.9

9.5；如圖610所示

10.dgbaechif、abdgcefhi、gdbeihfca、

6.31.5種,圖6.11

2.二叉樹如圖6.12所示。

中序線索二叉樹如圖

J

圖6.11樹形5種

圖6.12

6.13（左）所示；后序線索二叉樹如圖6.13（右）所示;

該二叉樹轉換后的的森林如圖6.14所示。

樹轉化為一下，圖6.15：（a

5.〉㈣出構讀&affif也1種示、，計算其超區(qū)路徑長度為

叉樹,H能到達的最）大深度h=N-k-Klh,

應的森林

7.1單項選擇麋］6.13孩子兄弟表

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

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

2.任何一個無向連通圖的最小生成樹。

A.只有一棵B.有一棵或多棵C.一定有多棵D,可能不

存在

3.在一個有向圖中，所有頂點的入度圖6.16Huffman樹之和等于所有頂點的出度之和的一倍。

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

4.一個有n個頂點的無向圖最多有一條邊。

A.nB.n(n-l)C.n(n-l)/2D.2n

5.具有4個頂點的無向完全圖有條邊。

A.6B.12C.16D.20

6.具有6個頂點的無向圖至少應有一條邊才能確保是一個連通圖。

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

7.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要一條邊。

A.nB.n+1C.n-1D.n/2

8.對于一個具有n個頂點的無向圖，假設采用鄰接矩陣表示，則該矩陣的大小是

A.nB.（n-1）2C.nTD.n

9.對于一個具有n個頂點和3條邊的無向圖，假設采用鄰接表表示，則表頭向量的大小為一①_；所有鄰接表中的接

點總數(shù)是一②

①A.nB.n+1C.n-1D.n+e

②A.e/2B.eC.2eD.n+e

10.一個圖如圖7.1所示，假設從頂點a出發(fā)按深度搜索法進展遍歷，則可能得到

的一種頂點序列為一①一;按寬度搜索法進展遍歷,則可能得到的一種頂點序列

為—②

①A,a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b

②A.a,b,c,B.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b

11.一有周J鄰接造如圖7.2所示。

c

⑴根據(jù)有向￡1輸加算重接資想A

E出發(fā),所得到的頂點序列是

A.vl,v22A'R,v4B.vl,v2,v3,v4,v5

C.vl,v31,v2D.vl,v4,v3,v5,v2

⑵根據(jù)有向R377^04修，從|5|八飛發(fā),所得到的頂點序列是

A.vl,v24,v5B.vl,v3,v2,v4,v5

C.vl,v24A5v4D.vl,v4,v3,v5,v2

12.采用鄰接----1者的圖的深度優(yōu)先遍歷算法類似于二叉樹的

A.先序貢5百2…』歷一?4、.八店序遍歷D.按層遍歷

13.采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的—o

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

14.判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用

A.求關鍵路徑的方法B.求最短路徑的Dijkstra方法

C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法

15.關鍵路徑是事件結點網(wǎng)絡中。

A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑

C.最長的回路D.最短的回路

16.下面不正確的說法是。

(1)在AOE網(wǎng)中，減小一個關鍵活動上的權值后，整個工期也就相應減小;

(2)AOE網(wǎng)工程工期為關鍵活動上的權之和；

(3)在關鍵路徑上的活動都是關鍵活動，而關鍵活動也必在關鍵路徑上。

A.(1)B.(2)C.(3)D.⑴、(2)

17.用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印出相應的頂點，則輸出的頂點序列是。

A.逆拓樸有序的B.拓樸有序的C.無序的

18.在圖7.3所示的拓樸排列的結果序列為。

A.125634C.123456D.521634

19.一個有n個頂點的不國持廟囪田所包含的連通分量個數(shù)為。

A.0B.1圖7.3有向圖D.n+1

20.對于一個有向圖,假我一個J貝點的人度為kl,、出度為k2,則對應鄰接表中該頂點單鏈表中的結點數(shù)為。

A.klB.k2C.kl-k2D.kl+k2

21.對于一個有向圖,假設一個頂點的入度為kl,、出度為k2,則對應逆鄰接表中該頂點單鏈表中的結點數(shù)為。

A.klB.k2C.kl-k2D.kl+k2

7.2填空題(將正確的答案填在相應餓空中)

1.n個頂點的連通圖至少一條邊。

2.在無權圖G的鄰接矩陣A中，假設(vi,vj)或＜vi,vj＞屬于圖G的邊集合，則對應元素等于—，否則等于

3.在無向圖G的鄰接矩陣A中，假設等于1,則］等于一。

4.圖G的鄰接表如圖7.4所示，其從頂點vl出發(fā)的深度有限搜索序列為—，其從頂點vl出發(fā)的寬度優(yōu)先搜索序列

為…。

―圖￡v2-v5v4

5.一彳一向鄰安MUX*示■i忘制入度的方法是

6.一彳v2一豹&v34叫v5、第i個結點出發(fā)的邊的方法是—。

7.如界—頁點卜B%它有棵生成樹。

8.VJ一mV6上28條邊，則該圖至少有個頂點。

9.遍〃v4A里實加工君'BFS遍歷圖的時間復雜度為，DFS遍歷圖的時間復雜度為，兩者不同之處在于，反映在數(shù)

據(jù)構造上的

10.v5-v4一除v6v3J。

11.一I結,左刖驅制繼史東EJ鬲正是一

A

12.假v6IG的頂點度數(shù)最小值大于等于時，G至少有一條回路。

13.根據(jù)圖的存儲構造進展某種次序的遍歷，得到的頂點序列是的。

7.3綜合題

1.如圖7.5所示的有向圖，請給出該圖的:

(1)每個頂點的入/出度；1r(5

(2)鄰接距陣；

(3)鄰接表；

(4)逆鄰接表;

(5)強連通分量。

24

3

習題答案

7.11.C2.B3.B4.C5.A6.A7.C

8.D9.AC10.DB11.CB12.A13.D14.D15.A

16.A17.A18.B19.B20.B21.A

7.2l.n-12.l;03.1

4.vl,v2,v3,v6,v5,v4；vl,v2,v5,v4,v3,v6

5.求矩陣第i列非零元素之和

6.將矩陣第i行全部置為零

7.n

8.9

9.對每個頂點查找其鄰接點的過程；0S)(e為圖中的邊數(shù))；0(e)；

遍歷圖的順序不同：DFS采用棧存儲訪問過的結點，BFS采用隊列存儲訪問過

的結點。

10.鄰接矩陣鄰接表

11.一個結點可能有假設干個前驅，也可能有假設干個后繼

12.2

13.唯一

7.3

2.

3.

e

512634

512364

4.

W=6

)W=5

5.⑴該AOE圖為:h

3

(2)完成整個方窠網(wǎng)r1?大。

(3萬儂路徑為：I'，V2,V

習題8

W=9

8.1單項2.,4

4W=7

W=3

1.順序查找法適，J造為一的線性

A.散列存儲B.順序存儲或鏈接存儲

C.壓縮存儲D.索引存儲

2.對線性表進展二分查找時;要求線性表必須—o

A.以順序方式存儲B.以鏈接方式存儲

C.以順序方式存儲，且結點按關鍵字有序排序

D.以鏈接方式存儲，且結點按關鍵字有序排序

3.采