數(shù)據(jù)結(jié)構(gòu)習(xí)題課第8、7、6章(網(wǎng)上的答案有些有問題的)_第1頁
數(shù)據(jù)結(jié)構(gòu)習(xí)題課第8、7、6章(網(wǎng)上的答案有些有問題的)_第2頁
數(shù)據(jù)結(jié)構(gòu)習(xí)題課第8、7、6章(網(wǎng)上的答案有些有問題的)_第3頁
數(shù)據(jù)結(jié)構(gòu)習(xí)題課第8、7、6章(網(wǎng)上的答案有些有問題的)_第4頁
數(shù)據(jù)結(jié)構(gòu)習(xí)題課第8、7、6章(網(wǎng)上的答案有些有問題的)_第5頁
已閱讀5頁,還剩11頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第8章圖

8.2對(duì)于如圖8.33所示的無向圖,試給出:

m圖中每個(gè)頂點(diǎn)的度;

(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所示的是某個(gè)無向圖的鄰接表,試:

(1)畫出此圖;

(2)寫出從頂點(diǎn)A開始的DFS遍歷結(jié)果;

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

圖8.35題8.5的鄰接表

實(shí)用文檔.

(2)

從頂點(diǎn)A開始的DFS遍歷,深度優(yōu)先遍歷的根本思想:對(duì)于給定的圖

G=(V,E),首先將V中每一個(gè)頂點(diǎn)都標(biāo)記為未被訪問,然后,選取一個(gè)源點(diǎn)yeV

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

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

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

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

從頂點(diǎn)A開始的BFS遍歷,根本思想:對(duì)于給定的圖G=(V,E),從圖中某未訪

問過的頂點(diǎn)vi出發(fā):

1)訪問頂點(diǎn)vi;

2)訪問vi的所有未被訪問的鄰接點(diǎn)wl,w2,…wk;

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

到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問;

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

8.8對(duì)如圖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假設(shè)候選兩棲邊中的最小邊不

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

并入集合U中。

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

行調(diào)整。

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

實(shí)用文檔.

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

(2)采用Kruskal算法求解最小生成樹時(shí)首先要對(duì)邊進(jìn)行由小到大進(jìn)行排序,

此題對(duì)邊進(jìn)行排序的結(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對(duì)于如圖8.37所示的有向網(wǎng),用Dijkstra方法求從頂點(diǎn)A到圖中其他頂

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

況。

實(shí)用文檔.

圖8.37有向網(wǎng)

解:

Dijkstra算法的根本思想:

把圖中所有頂點(diǎn)分成兩組,第一組包括已確定最短路徑的頂點(diǎn),初始時(shí)只含有

一個(gè)源點(diǎn),記為集合S;第二組包括尚未確定最短路徑的頂點(diǎn),記為V-S。按最

短路徑長(zhǎng)度遞增的順序逐個(gè)把V-S中的頂點(diǎn)加到S中去,直至從vO出發(fā)可以到

達(dá)的所有頂點(diǎn)都包括到S中。在這個(gè)過程中,總保持從vO到第一組(S)各頂點(diǎn)

的最短路徑都不大于從vO到第二組(V-S)的任何頂點(diǎn)的最短路徑長(zhǎng)度,第二組

的頂點(diǎn)對(duì)應(yīng)的距離值是從vO到此頂點(diǎn)的只包括第一組(S)的頂點(diǎn)為中間頂點(diǎn)的

最短路徑長(zhǎng)度。對(duì)于S中任意一點(diǎn)j,vO到j(luò)的路徑長(zhǎng)度皆小于vO到[V-S)中

任意一點(diǎn)的路徑長(zhǎng)度。

距,向量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)

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

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

實(shí)用文檔.

8.10試寫出如圖8.38所示的A0V網(wǎng)的4個(gè)不同的拓?fù)湫蛄小?/p>

實(shí)用文檔.

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

(這里也有點(diǎn)問題,等待老師再次講解)

解:拓?fù)渑判蜻^程:

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

2)在A0V網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)(入度為0)的頂點(diǎn),并輸出之;

3)從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;

4)重復(fù)以上(2)、(3)步,直到

全部頂點(diǎn)均已輸出,拓?fù)溆行蛐蛄行纬?,拓?fù)渑判蛲瓿桑?/p>

圖8.38所示的AOV網(wǎng)的4個(gè)不同的拓?fù)湫蛄袨椋?/p>

(1)ABDCEFGIH

(2)ABDECFGIH

(3)DABCEFGIH

(4)DAECBFGIH

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

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

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

解:

(1):e(i):表示活動(dòng)ai的最早開始時(shí)間。

1(i):表示活動(dòng)最遲開始時(shí)間的向量。

關(guān)鍵活動(dòng)特征:e(i)=1(i)

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

實(shí)用文檔.

能提高整個(gè)工程的進(jìn)度。

實(shí)用文檔.

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

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

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

ye(0)=0;

<匕,匕〉持續(xù)的時(shí)間}

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

jeP(i)

集合p(i)

e(k)=ye(i);

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

求每一個(gè)頂點(diǎn)i的最晚允許發(fā)生時(shí)間M(i)可以沿

圖中的匯點(diǎn)開始,按圖中的逆拓?fù)湫蛑饌€(gè)遞推出每

個(gè)頂點(diǎn)的M(i)o

可以得出:

實(shí)用文檔.

頂點(diǎn)VeV|活動(dòng)e11-e關(guān)鍵活動(dòng)

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é)點(diǎn)的二叉樹

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

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

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

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

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

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

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

注:1023為深度是10的滿二叉樹,有512個(gè)葉子結(jié)點(diǎn),1001比1023少22個(gè)節(jié)

點(diǎn)。所以有512-22+22/2=501片葉子

(4)一棵完全二叉樹有999個(gè)結(jié)點(diǎn),它的深度為(B)。

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

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

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

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

列為(HIDEBFGCA)。

實(shí)用文檔.

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

ABFHGEDC,試畫出此二叉樹。

解:

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

出此二叉樹

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

解:

ttinclude"bintree.h〃

voidchange(bintreet)

{bintreep;

if(t)

(

p=t->lchild;

t->lchild=t->rchiId;

t->rchild=p;

change(t->lchild);

change(t->rchiId);

}

實(shí)用文檔.

intmainO

{bintreet;

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

preorder(t);

change(t);

printf(〃\n〃);

preorder(t);

)

7.18假設(shè)二叉樹采用鏈?zhǔn)椒绞酱鎯?chǔ),root為其根結(jié)點(diǎn),p指向二叉樹中的任意

一個(gè)結(jié)點(diǎn),編寫一個(gè)求從根結(jié)點(diǎn)到P所指結(jié)點(diǎn)之間路徑長(zhǎng)度的函數(shù)。

解:在后序遍歷非遞歸算法中,當(dāng)訪問的結(jié)點(diǎn)為p時(shí),其祖先點(diǎn)正好全部在棧

中,此時(shí)棧中結(jié)點(diǎn)的個(gè)數(shù)就是根結(jié)點(diǎn)到p所指結(jié)點(diǎn)之間路徑長(zhǎng)度。

#include<stdio.h>

#include<stdlib.h>

typedefchardatatype;

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

{datatypedata;

structnode*lchild,*rchild;

}bintnode;

typedefbintnode*bintree;

typedefstructstack

(

bintreedata[100];

inttag[100];

inttop;

}seqstack;

voidcreat(bintree*t);

/*函數(shù)Depth,功能:求根結(jié)點(diǎn)到x的路徑長(zhǎng)度*/

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

實(shí)用文檔.

s.top——;

t=s.data[s.top];

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

)

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在選擇存儲(chǔ)結(jié)構(gòu)時(shí),既要考慮數(shù)據(jù)值本身的存儲(chǔ),還需要考慮(數(shù)據(jù)間關(guān)

系)

的存儲(chǔ)。

6.3對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹,該樹中所有結(jié)點(diǎn)的度數(shù)之和為(n-1)。

6.4一棵樹如圖6.11所示,試答復(fù)以下問題:

圖6.11一棵樹

(1)樹中哪個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)?哪些結(jié)點(diǎn)為葉子結(jié)點(diǎn)?

答:A是根結(jié)點(diǎn);E,G,H,I,C,J,K,L為葉結(jié)點(diǎn)。

(2)結(jié)點(diǎn)B的雙親為哪個(gè)結(jié)點(diǎn)?其子女為哪些結(jié)點(diǎn)?

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

(3)哪些結(jié)點(diǎn)為結(jié)點(diǎn)I的祖先?哪些結(jié)點(diǎn)為結(jié)點(diǎn)B的子孫?

答:F,B,A是結(jié)點(diǎn)I的祖先結(jié)點(diǎn);E,F,G,H,:[是B的子孫結(jié)點(diǎn)。

(4)哪些結(jié)點(diǎn)為結(jié)點(diǎn)D的兄弟?哪些結(jié)點(diǎn)為結(jié)點(diǎn)K的兄弟?

答:B,C,L是結(jié)點(diǎn)D的兄弟結(jié)點(diǎn),J是結(jié)點(diǎn)K的兄弟結(jié)點(diǎn)。

(5)結(jié)點(diǎn)J的層次為多少?樹的高度為多少?

答:結(jié)點(diǎn)J的層次為3,樹的高度為4。

(6)結(jié)點(diǎn)A、C的度分別為多少?樹的度為多少?

實(shí)用文檔.

答:結(jié)點(diǎn)A的度為4,結(jié)點(diǎn)C的度是0,樹的度是4。

(7)以結(jié)點(diǎn)B為根的子樹的高度為多少?

答:以結(jié)點(diǎn)B為根的子樹的高度是3。

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

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

號(hào)

表示為: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è)樹采用指針方式的孩子表示法表示,試編寫一個(gè)非遞歸函數(shù),實(shí)現(xiàn)樹的

后序遍歷算法。

答:

#include"tree.h"

intPostOrderByStack(TreeNode*root)

{

TreeNode*temp;

TreeNode*stack[MAXLEN];

//childSeq表示當(dāng)前打印到了此樹第幾個(gè)孩子,

inttop,childSeq[MAXLEN];

inti;

top=-1;〃初始化空棧

temp=root;

while(1)

{

while(temp!=NULL)

(

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

{

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論