1、第8章圖關(guān)于如圖所示的無向圖，試給出：1）圖中每個極點的度；2）該圖的毗鄰矩陣；3）該圖的毗鄰表；4）該圖的連通重量。1）D(V0)=2；D（V1）=2；D（V2）=3；D（V3）=3；D（V4）=2；D（V5）=1；D(V6)=1.0101000010100010100001010000010110001011001010100毗鄰矩陣1010100001100000110000000001000000100000100000010V3）毗鄰表連通重量1：2：圖所示的是某個無向圖的毗鄰表，試：1）畫出此圖；2）寫出從極點A開始的DFS遍歷結(jié)果；3）寫出從極點A開始的BFS遍歷結(jié)果。1）圖毗鄰

2、表對應的無向圖如圖所示2）從極點A開始的DFS遍歷，深度優(yōu)先遍歷的基本思想：關(guān)于給定的圖G=（V,E），第一將V中每一個極點都標志為未被接見，此后，采納一個源點vV將v標志為被接見，再遞歸地用深度優(yōu)先搜尋方法，挨次搜尋v的所有毗鄰點w.若w不曾接見過，則以w為新的出發(fā)點連續(xù)深度優(yōu)先搜尋遍歷，假如從v出發(fā)所有路的極點都已被接見過，則結(jié)束。A，B，C，F(xiàn)，E，G，D從極點A開始的BFS遍歷，基本思想：關(guān)于給定的圖G=（V,E），從圖中某未接見過的極點vi出發(fā)：1）接見極點vi；2）接見vi的所有未被接見的毗鄰點w1,w2,wk；3）挨次從這些毗鄰點出發(fā)，接見它們的所有未被接見的毗鄰點;依此類推，直

3、到圖中所有接見過的極點的毗鄰點都被接見；A，B，C，D，F(xiàn)，E，G對如圖所示的連通圖，分別用Prim和Kruskal算法結(jié)構(gòu)其最小生成樹。解：（1）Prime算法的基本思路、步驟P167Prim算法的基本步驟以下：1）初始化：U=u0，TREE=;2）假如U=V（G），則輸出最小生成樹T，并結(jié)束算法；3）在所有兩棲邊中找一條權(quán)最小的邊（u，v）（若候選兩棲邊中的最小邊不單一條，可任選此中的一條），將邊（u，v）加入到邊集TREE中，并將極點v并入會合U中。4）因為新極點的加入，U的狀態(tài)發(fā)生變化，需要對U與V-U之間的兩棲邊進行調(diào)整。5）轉(zhuǎn)步驟（2）Prim算法結(jié)構(gòu)最小生成樹過程：2）采納Kru

4、skal算法求解最小生成樹時第一要對邊進行由小到大進行排序，此題對邊進行排序的結(jié)果是：（D,F）1、（C,F）2、（A,F）3、（A,C）4、（F,G）4、D,E）4、（D,B）4、（C,D）5、（E,G）5、（A,D）6、（D,G）6、（A,B）7。依據(jù)Kruskal算法，結(jié)構(gòu)最小生成樹的過程如圖關(guān)于如圖所示的有向網(wǎng)，用Dijkstra路徑，并寫出履行算法過程中距離向量方法求從極點d與路徑向量A到圖中其余極點的最短p的狀態(tài)變化狀況。解：Dijkstra算法的基本思想：把圖中所有極點分紅兩組，第一組包含已確立最短路徑的極點，初始時只含有一個源點，記為會合S；第二組包含還沒有確立最短路徑的極點，

5、記為V-S。按最短路徑長度遞加的次序逐一把V-S中的極點加到S中去，直至從v0出發(fā)可以抵達的所有極點都包含到S中。在這個過程中，總保持從v0到第一組（S）各極點的最短路徑都不大于從v0到第二組（V-S）的任何極點的最短路徑長度，第二組的極點對應的距離值是從v0到此極點的只包含第一組（S）的極點為中間極點的最短路徑長度。關(guān)于S中隨意一點j，v0到j的路徑長度皆小于v0到（V-S）中隨意一點的路徑長度。(后邊四行需要在會合S加上E)從表中可以看出源點A到其余各極點的最短距離及路徑為：AB：48路徑：ABAC：57路徑：ADFCAD：15路徑：ADAE：28路徑：AEAF：48路徑：ADFAG：38

6、路徑：ADG試寫出如圖所示的AOV網(wǎng)的4個不同樣的拓撲序列。(這里也有點問題，等候老師再次解說)解：拓撲排序過程：輸入AOV網(wǎng)絡。令n為極點個數(shù)。在AOV網(wǎng)絡中選一個沒有直接前驅(qū)（入度為0）的極點,并輸出之;從圖中刪去該極點,同時刪去所有它發(fā)出的有向邊;重復以上(2)、(3)步,直到所有極點均已輸出，拓撲有序序列形成，拓撲排序達成；圖所示的AOV網(wǎng)的4個不同樣的拓撲序列為：（1）ABDCEFGIH（2）ABDECFGIH3）DABCEFGIH4）DAECBFGIH計算如圖所示的AOE網(wǎng)中各極點所表示的事件的發(fā)生時間ve(j)，vl(j)，各邊所表示的活動的開始時間e(i)，l(i)，并找出其重

7、點路徑。解：(1):e（i）：表示活動ai的最早開始時間。（i）：表示活動最遲開始時間的向量。重點活動特點：e（i）=l（i）l（j）-e（j）的值表示達成活動aj的時間余量，提早達成非重點活動其實不可以提升整個工程的進度。事件可能的最早開始時間ve（i）：關(guān)于某一事件vi，它可能的最早發(fā)生時間事件贊成的最晚發(fā)生時間vl（i）：關(guān)于某一事件vi，它贊成的最晚發(fā)生時間是在保證準時達成整個工程的前提下，該事件最晚必然發(fā)生的時間可以得出：第7章二叉樹選擇題。1）前序遍歷和中序遍歷結(jié)果同樣的二叉樹為（F）；前序遍歷和后序遍歷結(jié)果同樣的二叉樹為（B）。A一般二叉樹B只有根結(jié)點的二叉樹C根結(jié)點無左孩子的二

8、叉樹D根結(jié)點無右孩子的二叉樹E所有結(jié)點只有左子樹的二叉樹F所有結(jié)點只有右子樹的二叉樹。2）以下相關(guān)二叉樹的說法正確的選項是（B）。A二叉樹的度為2B一棵二叉樹的度可以小于2C二叉樹中最罕有一個結(jié)點的度為2D二叉樹中任一個結(jié)點的度均為23）一棵完滿二叉樹上有1001個結(jié)點，此中葉子結(jié)點的個數(shù)為（D）。A250B500C254D501注：1023為深度是10的滿二叉樹，有512個葉子結(jié)點，1001比1023少22個節(jié)點。因此有512-22+22/2=501片葉子4）一棵完滿二叉樹有999個結(jié)點，它的深度為（B）。A9B10C11D12（5）一棵擁有5層的滿二叉樹所包含的結(jié)點個數(shù)為（B）。A15B3

9、1C63D32用一維數(shù)組寄存完滿二叉樹：ABCDEFGHI，則后序遍歷該二叉樹的結(jié)點序列為HIDEBFGCA）。已知一棵二叉樹的中序遍歷的結(jié)果為ABCEFGHD，后序遍歷的結(jié)果為ABFHGEDC，試畫出此二叉樹。解：已知一棵二叉樹的前序遍歷的結(jié)果為ABCDEF，中序遍歷的結(jié)果為CBAEDF，試畫出此二叉樹解：試編寫一個函數(shù)，將一棵給定二叉樹中所有結(jié)點的左、右兒女交換。解：#includevoidchange(bintreet)bintreep;if(t)p=t-lchild;t-lchild=t-rchild;t-rchild=p;change(t-lchild);change(t-rchil

10、d);intmain()bintreet;creat(&t);/*成立二叉樹t的儲蓄結(jié)構(gòu)*/preorder(t);change(t);printf(n);preorder(t);假定二叉樹采納鏈式方式儲蓄，root為其根結(jié)點，p指向二叉樹中的隨意一個結(jié)點，編寫一個求從根結(jié)點到p所指結(jié)點之間路徑長度的函數(shù)。解：在后序遍歷非遞歸算法中，當接見的結(jié)點為p時，其先人點正好所有在棧中，此時棧中結(jié)點的個數(shù)就是根結(jié)點到p所指結(jié)點之間路徑長度。#include#includetypedefchardatatype;typedefstructnode/*二叉樹結(jié)點定義*/datatypedata;struct

11、node*lchild,*rchild;bintnode;typedefbintnode*bintree;typedefstructstackbintreedata100;inttag100;inttop;seqstack;voidcreat(bintree*t);/*函數(shù)Depth，功能：求根結(jié)點到x的路徑長度*/intDepth(bintreet,datatypex)seqstacks;inti=0,j;=0;while(t|!=0)while(t)=t;=0;+;t=t-lchild;while0&);t=;if(t-data=x)return;/此時棧中的結(jié)點都是x的先人結(jié)點if0)t

12、=;=1;t=t-rchild;elset=NULL;第6章樹樹最適適用來表示擁有（有序）性和（層次）性的數(shù)據(jù)。在選擇儲蓄結(jié)構(gòu)時，既要考慮數(shù)據(jù)值自己的儲蓄，還需要考慮（數(shù)據(jù)間關(guān)系）的儲蓄。關(guān)于一棵擁有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為（n-1）。已知一棵樹如圖所示，試回答以下問題：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(xiàn)，G，H，I是B的后代結(jié)點。

13、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(xiàn)（G，H，I），C，D（J，K），L），該樹的層號表示為：10A，20B，30E，30F，40G，40H，40I，20C，20D，25J，25K，20L試寫出圖所示樹的前序遍歷

14、、后序遍歷和層次遍歷的結(jié)果。答：前序遍歷：ABEFGHICDJKL后序遍歷：EGHIFBCJKDLA層次遍歷：ABCDLEFJKGHI假定樹采納指針方式的孩子表示法表示，試編寫一個非遞歸函數(shù)，實現(xiàn)樹的后序遍歷算法。答：#includeintPostOrderByStack(TreeNode*root)TreeNode*temp;TreeNode*stackMAXLEN;/childSeq表示目前打印到了此樹第幾個孩子，inttop,childSeqMAXLEN;inti;top=-1;/初始化空棧temp=root;while(1)while(temp!=NULL)for(i=0;ichildi!=NULL)childSeq+top=i+1;stacktop=temp;temp=temp-childi;break;假如此節(jié)點是葉子節(jié)點，則輸出該結(jié)點if(i=MAXN)printf(%5c,temp-key);temp=NULL;break;while(top!=-1)for(i=childSeqtop;ichildi!=NULL)temp=stacktop-childi;childSeqtop=i+1