數(shù)據(jù)結(jié)構(gòu)習題課第8、7、6章(網(wǎng)上的答案有些有問題的)

第8章圖

8.2對于如圖8.33所示的無向圖，試給出：

m圖中每個頂點的度；

(2)該圖的鄰接矩陣；

(3)該圖的鄰接表；

(4)該圖的連通分量。

圖8.33無向圖

(1)D(V0)=2；D(VI)=2；D(V2)=3；D(V3)=3；D(V4)=2；D(V5)=1；

D(V6)=1.

'0101000'

'0101000'

1010000

1010000

0101100

0101100

1010100

⑵鄰接矩陣1010100

0011000

0011000

0000001

0000001

0000010

0000010

veV-

(3)鄰接表

(4)連通分量

?—?

8.5圖&35所示的是某個無向圖的鄰接表，試:

(1)畫出此圖；

(2)寫出從頂點A開始的DFS遍歷結(jié)果；

(3)寫出從頂點A開始的BFS遍歷結(jié)果。

圖8.35題8.5的鄰接表

實用文檔.

(2)

從頂點A開始的DFS遍歷，深度優(yōu)先遍歷的根本思想：對于給定的圖

G=(V,E),首先將V中每一個頂點都標記為未被訪問，然后，選取一個源點yeV

將v標記為被訪問，再遞歸地用深度優(yōu)先搜索方法，依次搜索v的所有鄰接點

w.假設w未曾訪問過，那么以w為新的出發(fā)點繼續(xù)深度優(yōu)先搜索遍歷，如果從v

出發(fā)所有路的頂點都已被訪問過，那么結(jié)束。

A,B,C,F,E,G,D

從頂點A開始的BFS遍歷，根本思想：對于給定的圖G=(V,E),從圖中某未訪

問過的頂點vi出發(fā)：

1)訪問頂點vi；

2)訪問vi的所有未被訪問的鄰接點wl,w2，…wk；

3)依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點；依此類推，直

到圖中所有訪問過的頂點的鄰接點都被訪問；

A,B,C,D,F,E,G

8.8對如圖8.36所示的連通圖，分別用Prim和Kruskal算法構(gòu)造其最小生成

樹。

圖8.36無向連通網(wǎng)

解：(1)Prime算法的根本思路、步驟P167

Prim算法的根本步驟如下：

(1)初始化：U={uO},TREE={};

(2)如果U=V(G),那么輸出最小生成樹T,并結(jié)束算法；

(3)在所有兩棲邊中找一條權(quán)最小的邊(u,v)1假設候選兩棲邊中的最小邊不

止一條，可任選其中的一條)，將邊(u,v)參加到邊集TREE中，并將頂點v

并入集合U中。

(4)由于新頂點的參加，U的狀態(tài)發(fā)生變化，需要對U與V-U之間的兩棲邊進

行調(diào)整。

(5)轉(zhuǎn)步驟⑵

實用文檔.

Prim算法構(gòu)造最小生成樹過程

(2)采用Kruskal算法求解最小生成樹時首先要對邊進行由小到大進行排序，

此題對邊進行排序的結(jié)果是：(D,F)1、(C,F)2、此F)3、(A,C)4、此G)4、

(D.E)4、(D,B)4、(C,D)5、(E.G)5、(A,D)6、(D,G)6、(A,B)7。根據(jù)

8.9對于如圖8.37所示的有向網(wǎng)，用Dijkstra方法求從頂點A到圖中其他頂

點的最短路徑，并寫出執(zhí)行算法過程中距離向量d與路徑向量p的狀態(tài)變化情

況。

實用文檔.

圖8.37有向網(wǎng)

解：

Dijkstra算法的根本思想：

把圖中所有頂點分成兩組，第一組包括已確定最短路徑的頂點，初始時只含有

一個源點，記為集合S；第二組包括尚未確定最短路徑的頂點，記為V-S。按最

短路徑長度遞增的順序逐個把V-S中的頂點加到S中去，直至從vO出發(fā)可以到

達的所有頂點都包括到S中。在這個過程中，總保持從vO到第一組（S）各頂點

的最短路徑都不大于從vO到第二組（V-S）的任何頂點的最短路徑長度，第二組

的頂點對應的距離值是從vO到此頂點的只包括第一組（S）的頂點為中間頂點的

最短路徑長度。對于S中任意一點j,vO到j的路徑長度皆小于vO到［V-S）中

任意一點的路徑長度。

距,向量d路徑向量p

循環(huán)集合SV

01234560123456

初始化{A}-0480015288400-100-I0

1{AD}3048co152848380-10033

2{ADE}40486115284838040033

3{ADG}604S6115284838040033

4{ADGB}10486015284838010033

5{ADGBF}50485715284838050033

6{ADGBFC}20485715284838050033

（后面四行需要在集合S加上E）

從表中可以看出源點A到其它各頂點的最短距離及路徑為:

AfB：48路徑：A-*B

A-C：57路徑：A-D-F—C

A-D：15路徑：A-D

A—E：28路徑：A—E

A-F：48路徑：AfDfF

A-G：38路徑：A-D-G

實用文檔.

8.10試寫出如圖8.38所示的A0V網(wǎng)的4個不同的拓撲序列。

實用文檔.

圖8.38題8.10的AOV網(wǎng)

(這里也有點問題，等待老師再次講解)

解：拓撲排序過程：

1)輸入A0V網(wǎng)絡。令n為頂點個數(shù)。

2)在A0V網(wǎng)絡中選一個沒有直接前驅(qū)(入度為0)的頂點，并輸出之；

3)從圖中刪去該頂點，同時刪去所有它發(fā)出的有向邊；

4)重復以上(2)、(3)步，直到

全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；

圖8.38所示的AOV網(wǎng)的4個不同的拓撲序列為：

(1)ABDCEFGIH

(2)ABDECFGIH

(3)DABCEFGIH

(4)DAECBFGIH

8.11計算如圖8.39所示的A0E網(wǎng)中各頂點所表示的事件的發(fā)生時間ve(j),

vl(j),各邊所表示的活動的開始時間e(i),l(i),并找出其關(guān)鍵路徑。

圖8.39題8.10的A0E網(wǎng)

解：

(1)：e(i)：表示活動ai的最早開始時間。

1(i)：表示活動最遲開始時間的向量。

關(guān)鍵活動特征：e(i)=1(i)

1(j)-e(j)的值表示完成活動aj的時間余量，提前完成非關(guān)鍵活動并不

實用文檔.

能提高整個工程的進度。

實用文檔.

事件可能的最早開始時間ve(i)：對于某一事件vi,它可能的最早發(fā)生時間

事件允許的最晚發(fā)生時間vl(i)：對于某一事件vi,它允許的最晚發(fā)生時間是

在保證按時完成整個工程的前提下，該事件最晚必須發(fā)生的時間

ye(0)=0；

<匕,匕〉持續(xù)的時間｝

y8(i)=max{ve(J)+活動(1<Z<H-1)

jeP(i)

集合p(i)

e(k)=ye(i)；

I(k)=yt(j)-ten(<Vj,y>)；

求每一個頂點i的最晚允許發(fā)生時間M(i)可以沿

圖中的匯點開始，按圖中的逆拓撲序逐個遞推出每

個頂點的M(i)o

可以得出:

實用文檔.

頂點VeV|活動e11-e關(guān)鍵活動

Voj0▲0a。i0i00

V1j6j6aij0111

:5

V2|4a2?6；60(

V3j1313|41

V；22522a41

44fP

V52525a513130

2613152

22220

a7

第7章二叉樹

7.1選擇題。

(1)前序遍歷和中序遍歷結(jié)果相同的二叉樹為(F)；前序遍歷和后序遍歷結(jié)

果相同的二叉樹為(B)。

A.一般二叉樹B.只有根結(jié)點的二叉樹

C.根結(jié)點無左孩子的二叉樹D.根結(jié)點無右孩子的二叉樹

E.所有結(jié)點只有左子樹的二叉樹F.所有結(jié)點只有右子樹的二叉樹。

(2)以下有關(guān)二叉樹的說法正確的選項是(B

A.二叉樹的度為2B.一棵二叉樹的度可以小于2

C.二叉樹中至少有一個結(jié)點的度為2D.二叉樹中任一個結(jié)點的度均為2

(3)一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)為(D

A.250B.500C.254D.501

注：1023為深度是10的滿二叉樹，有512個葉子結(jié)點，1001比1023少22個節(jié)

點。所以有512-22+22/2=501片葉子

(4)一棵完全二叉樹有999個結(jié)點，它的深度為(B)。

A.9B.10C.11D.12

(5)一棵具有5層的滿二叉樹所包含的結(jié)點個數(shù)為(B

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

7.2用一維數(shù)組存放完全二叉樹：ABCDEFGHI,那么后序遍歷該二叉樹的結(jié)點序

列為(HIDEBFGCA)。

實用文檔.

7.10一棵二叉樹的中序遍歷的結(jié)果為ABCEFGHD，后序遍歷的結(jié)果為

ABFHGEDC,試畫出此二叉樹。

解：

7.11一棵二叉樹的前序遍歷的結(jié)果為ABCDEF,中序遍歷的結(jié)果為CBAEDF，試畫

出此二叉樹

7.14試編寫一個函數(shù)，將一棵給定二叉樹中所有結(jié)點的左、右子女互換。

解：

ttinclude"bintree.h〃

voidchange(bintreet)

{bintreep;

if(t)

(

p=t->lchild;

t->lchild=t->rchiId;

t->rchild=p;

change(t->lchild);

change(t->rchiId);

}

實用文檔.

intmainO

{bintreet;

creat(&t);/*建立二叉樹t的存儲結(jié)構(gòu)*/

preorder(t);

change(t);

printf(〃\n〃)；

preorder(t);

)

7.18假設二叉樹采用鏈式方式存儲，root為其根結(jié)點，p指向二叉樹中的任意

一個結(jié)點，編寫一個求從根結(jié)點到P所指結(jié)點之間路徑長度的函數(shù)。

解：在后序遍歷非遞歸算法中，當訪問的結(jié)點為p時，其祖先點正好全部在棧

中，此時棧中結(jié)點的個數(shù)就是根結(jié)點到p所指結(jié)點之間路徑長度。

#include<stdio.h>

#include<stdlib.h>

typedefchardatatype;

typedefstructnode/*二叉樹結(jié)點定義*/

{datatypedata;

structnode*lchild,*rchild;

}bintnode;

typedefbintnode*bintree;

typedefstructstack

(

bintreedata[100];

inttag[100];

inttop;

}seqstack;

voidcreat(bintree*t);

/*函數(shù)Depth,功能：求根結(jié)點到x的路徑長度*/

intDepth(bintreet,datatypex)

(

seqstacks;

inti=0,j;

s.top=0;

while(t||s.top!=0)

(

while(t)

{

s.data[s.top]=t;

s.tag[s.top]=0;

s.top++;

t=t->lchild;

)

while(s.top>0&&s,tag[s.top-1])

實用文檔.

s.top——;

t=s.data[s.top];

if(t->data==x)returns.top;//此時棧中的結(jié)點都是x的祖先結(jié)點

)

if(s.top>0)

{

t=s.data[s.top-1];

s.tag[s.top-l]=l;

t=t->rchild;

)

elset=NULL;

第6章樹

6.1樹最適合用來表示具有(有序)性和(層次)性的數(shù)據(jù)。

6.2在選擇存儲結(jié)構(gòu)時，既要考慮數(shù)據(jù)值本身的存儲，還需要考慮(數(shù)據(jù)間關(guān)

系)

的存儲。

6.3對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為(n-1)。

6.4一棵樹如圖6.11所示，試答復以下問題：

圖6.11一棵樹

(1)樹中哪個結(jié)點為根結(jié)點？哪些結(jié)點為葉子結(jié)點？

答：A是根結(jié)點；E,G,H,I,C,J,K,L為葉結(jié)點。

(2)結(jié)點B的雙親為哪個結(jié)點？其子女為哪些結(jié)點？

答：B的雙親結(jié)點是A,其子女結(jié)點為E和F。

(3)哪些結(jié)點為結(jié)點I的祖先？哪些結(jié)點為結(jié)點B的子孫？

答：F,B,A是結(jié)點I的祖先結(jié)點；E,F,G,H,：［是B的子孫結(jié)點。

(4)哪些結(jié)點為結(jié)點D的兄弟？哪些結(jié)點為結(jié)點K的兄弟？

答：B,C,L是結(jié)點D的兄弟結(jié)點，J是結(jié)點K的兄弟結(jié)點。

(5)結(jié)點J的層次為多少？樹的高度為多少？

答：結(jié)點J的層次為3,樹的高度為4。

(6)結(jié)點A、C的度分別為多少？樹的度為多少？

實用文檔.

答：結(jié)點A的度為4,結(jié)點C的度是0,樹的度是4。

(7)以結(jié)點B為根的子樹的高度為多少？

答：以結(jié)點B為根的子樹的高度是3。

(8)試給出該樹的括號表示及層號表示形式。

答：該樹的括號表示為：A(B(E,F(G,H,I)),C,D(J,K),L),該樹的層

號

表示為：10A,20B,30E,30F,40G,40H,401,20C,20D,25J,25K,20L

6.5試寫出圖6.11所示樹的前序遍歷、后序遍歷和層次遍歷的結(jié)果。

圖6.11一棵樹

答：前序遍歷：ABEFGHICDJKL

后序遍歷：EGHIFBCJKDLA

層次遍歷：ABCDLEFJKGHI

6.9假設樹采用指針方式的孩子表示法表示，試編寫一個非遞歸函數(shù)，實現(xiàn)樹的

后序遍歷算法。

答：

#include"tree.h"

intPostOrderByStack(TreeNode*root)

{

TreeNode*temp;

TreeNode*stack[MAXLEN];

//childSeq表示當前打印到了此樹第幾個孩子，

inttop,childSeq[MAXLEN];

inti;

top=-1;〃初始化空棧

temp=root;

while(1)

{

while(temp!=NULL)

(

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

{