數(shù)據(jù)結(jié)構(gòu)04292

1、1. 將森林轉(zhuǎn)換為二叉樹。用左子女-右兄弟表示實現(xiàn)的樹定義：typedef struct node TreeData data; struct node * firstChild, * nextSibling; TreeNode;2. 圖的鄰接矩陣、鄰接表的存儲表示。圖的鄰接矩陣存儲：兩點之間有邊矩陣對應(yīng)的位置處填1，兩點之間無邊對應(yīng)位置處填0EdgeData EdgeNumVerticesNumVertices; 圖的鄰接表存儲： 2. 計算AOE網(wǎng)絡(luò)的關(guān)鍵路徑。完成整個工程所需的時間取決于從源點到匯點的最長路徑長度, 即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路

2、徑關(guān)鍵活動：最早開始時間和最晚開始時間相等4. 畫出下圖的結(jié)構(gòu)，并分別給出以A頂點開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。ABDCFE深度優(yōu)先搜索：ABDCEF廣度優(yōu)先搜索：ABCDEF5. (1) 哈希函數(shù)常用的構(gòu)造方法有哪些?處理沖突的方法有哪些？(2) 用除留余數(shù)法構(gòu)建哈希表，并以線性探測再散列處理沖突。1、常用的構(gòu)造方法：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機數(shù)法處理沖突的方法：開放定址法、再哈希法、鏈地址法2、除留余數(shù)法：H(key) = key % p -m為表長，p為不大于m的素數(shù)P為素數(shù)？如key（關(guān)鍵字）：12 39 18 24 33 21 若p = 9 則哈

3、希函數(shù)值為：3 3 0 6 6 3可見，當p的因子中含有素數(shù)3，則所有含因子3的關(guān)鍵字都對應(yīng)到“3的倍數(shù)”的地址上，從而增加了沖突的可能!/*表長為6，關(guān)鍵字個數(shù)6，p<=m且p為素數(shù)，故p取5,但是這樣最后一個數(shù)21將永遠不會放到下標為5的地方！那么這個p的取法不是有錯嗎？還是說表長必須比給的關(guān)鍵字個數(shù)大？*/如key（關(guān)鍵字）：12 39 18 24 33 21 若p = 7 則哈希函數(shù)值為: 5 4 4 3 5 0先行探測在散列處理沖突：Key = 18：18 % 7 = 4(沖突)(4+1)%7=5(沖突)(5+1)%7=6key = 33: 33%7=5（沖突）(5+1)%7=

4、6（沖突）(6+1)%7=0Key = 21:21%7 = 0(沖突)(0+1)%7 = 1所以最后得：5 4 6 3 0 101234563321243912186. 證明二叉樹性質(zhì)：n0=n2+1 ( n0度為0的結(jié)點；n2:度為2的結(jié)點 )n1為度為1的節(jié)點，e表示二叉樹的邊數(shù)；這里用到的一個等式是二叉樹邊的兩種表達:e=n0+n1+n2-1 /每一個節(jié)點對應(yīng)一條邊，根節(jié)點除外所以減一e=2*n2+n1 /2倍的度為2的節(jié)點數(shù)目加上度為1的節(jié)點數(shù)目，就是邊的數(shù)目得：n0 = n2 + n17. 求最小生成樹 1、Prim（普里姆）算法從連通圖中的某一頂點 u0 出發(fā), 選擇與它關(guān)聯(lián)的具有

5、最小權(quán)值的邊，將其頂點加入到生成樹頂點集合中2、Kruskal（克魯斯卡爾）算法對每一條邊按照權(quán)值從小到大排序，每一次選擇最小的權(quán)值的邊，注意避免選擇出現(xiàn)環(huán)的邊！8.以權(quán)重集合 4, 5, 6, 7, 8 構(gòu)建哈夫曼樹（霍夫曼樹）。帶權(quán)路徑長度達到最小的二叉樹即為哈夫曼樹。 9. 給出用下列關(guān)鍵字構(gòu)建大頂堆的全過程，關(guān)鍵字集合為 70 40 55 81 74 18 46 70 01234567704055817418467010. 給出上述集合數(shù)據(jù)的快速排序的過程選定初始關(guān)鍵字temp，首先從右向左遍歷，當遇到比temp小的時候，就讓ai = aj, i+;然后重左向右遍歷，當遇到比temp大

6、的時候，就讓aj = ai, j-;然后循環(huán)做上述兩個過程，直到i=j時，就讓ai = temp;這時樞軸就是ai;然后遞歸調(diào)用從（l, i-1）和(i+1,r);11. 請按照給出的數(shù)字順序構(gòu)造二叉排序樹。如：50 30 80 20 40 90 10 25 35 85 23 8812. 計算從頂點b到其它頂點的最短路徑。答題不能這樣寫，這樣寫最多2分，要寫出步驟！這只是草稿，方便看！Dijkstra 逐步求解的過程:<b, a, 2><b, e, 10><b, a, c, 22><b, e, d, 23><b, a, c, f, 28&g

7、t;13. 二叉樹計數(shù)。1、由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹前序序列 ABHFDECKG /確定根節(jié)點中序序列 HBDFAEKCG /在前序序列確定根節(jié)點的基礎(chǔ)上，確定左右孩子節(jié)點 2、計算具有 n 個結(jié)點的不同二叉樹的棵數(shù)14. 給出求順序表A和B并集和交集的程序?qū)崿F(xiàn)，要求并集存儲在表A當中。運行結(jié)果：La :0 1 2 3 4 5 6 7 8 9Lb :0 2 4 6 8 10 12 14 16 18BingJi :0 1 2 3 4 5 6 7 8 9 10 12 14 16 18JiaoJi :0 2 4 6 8請按任意鍵繼續(xù). . .代碼：#include <

8、iostream>#define NewSeqList (SeqList*)malloc(sizeof(SeqList)#define NewListData (int*)malloc(40 * sizeof(int)using namespace std;typedef struct int *data, length;SeqList;void SetL(SeqList *&L) cout << "請輸入共多少數(shù)：" cin >> L->length;for (int i = 0; i < L->length; +i

9、) cin >> L->datai;void Show(SeqList *&L) for (int i = 0; i < L->length; +i) cout << L->datai << " " cout << endl;bool InL(SeqList *&L, int &key) for (int i = 0; i < L->length; +i) if (key = L->datai) return true;return false;void Ins

10、ert(SeqList *&L, int key) L->dataL->length+ = key; void Delete(SeqList *&L, int &pos) /pos代表要刪除的元素的下標for (int i = pos; i < L->length - 1; +i) L->datai = L->datai + 1;-L->length;void Union(SeqList *&La, SeqList *&Lb) for (int i = 0; i < Lb->length; +i) i

11、f (!InL(La, Lb->datai) Insert(La, Lb->datai);/如果Lb中元素不在La中就把該元素插入到La中void Intersect(SeqList *&La, SeqList *&Lb) for (int i = 0; i < La->length; +i) if (!InL(Lb, La->datai) Delete(La, i); -i; /如果La中元素不在Lb中就把La中該元素刪除int main()SeqList *La = NewSeqList, *Lb = NewSeqList;/NewSeqLis

12、t 用宏定義創(chuàng)建結(jié)構(gòu)體La->data = NewListData;/NewListData 用宏定義創(chuàng)建數(shù)組Lb->data = NewListData;La->length = Lb->length = 0;SetL(La);/向順序表La輸入數(shù)據(jù)SetL(Lb);/向順序表Lb輸入數(shù)據(jù)cout << "輸出集合La：" Show(La);cout << "輸出集合Lb：" Show(Lb);Union(La, Lb);/并集cout << "并集結(jié)果：" Show(La

13、);Intersect(La, Lb);/交集cout << "交集結(jié)果：" Show(La);system("pause");return 0;15. 用C語言給出鄰接表的定義。給出構(gòu)建鄰接表的源程序（先后輸入頂點表和邊表）。編寫程序求頂點表中頂點V的入度和出度。無向圖的每個頂點的入度和出度相等，所以只要求出入度即可。有向圖求入度和出度有兩種方法：1、 求入度一個一個遍歷，遇到即ans+2、 在一個結(jié)構(gòu)體中建立兩個表，入度表，和出度表，查詢的時候做相同的遍歷即可法1：（按無向圖來處理的，若按有向圖處理只需刪去建tail->head的代

14、碼即可）運行結(jié)果：please input VertexNum and EdgeNum :4 5please input VertexNode :A B C Dplease input Edge as A B 10 :A C 2A B 1A D 3B C 1B D 5A Chu Du is : 3B Chu Du is : 3C Chu Du is : 2D Chu Du is : 2A Ru Du is : 3B Ru Du is : 3C Ru Du is : 2D Ru Du is : 2請按任意鍵繼續(xù). . .代碼：#include <iostream>#include &

15、lt;cstring>using namespace std;const int VertexNum = 10;typedef struct nodeint dex, cost;struct node *link;EdgeNode;typedef char VertexData;typedef struct VertexData data;EdgeNode *first_link;VertexNode;typedef struct VertexNode VexListVertexNum;int n, e;AdjGraph;int FindPos(AdjGraph &G, char

16、 &ch) for (int i = 0; i < G.n; +i) if (G.VexListi.data = ch) return i;void CrateGraph(AdjGraph &G) cout << "please input VertexNum and EdgeNum : " << endl; cin >> G.n >> G.e; cout << "please input VertexNode : " << endl;for (int i =

17、0; i < G.n; +i) cin >> G.VexListi.data; G.VexListi.first_link = NULL; cout << "please input Edge as A B 10 : " << endl;for (int i = 0; i < G.e; +i) char ch1, ch2;int head, tail, key;cin >> ch1 >> ch2 >> key;head = FindPos(G, ch1);tail = FindPos(G,

18、ch2);EdgeNode *p = new EdgeNode;p->cost = key;p->dex = tail;p->link = G.VexListhead.first_link;G.VexListhead.first_link = p;p = new EdgeNode;p->cost = key;p->dex = head;p->link = G.VexListtail.first_link;G.VexListtail.first_link = p;void EveryChuDu(AdjGraph &G) for (int i = 0;

19、i < G.n; +i) int ans = 0;EdgeNode *p = G.VexListi.first_link;while (p) +ans; p = p->link; cout << G.VexListi.data << " Chu Du is : " << ans << endl;cout << endl << endl;void EveryRuDu(AdjGraph &G) EdgeNode *p;for (int i = 0; i < G.n; +i) int

20、 ans = 0;for (int j = 0; j < G.n; +j) if (j = i) continue;p = G.VexListj.first_link;while (p) if (p->dex = i) +ans; p = p->link; cout << G.VexListi.data << " Ru Du is : " << ans << endl;cout << endl;int main() AdjGraph G;CrateGraph(G);EveryChuDu(G);Ev

21、eryRuDu(G);system("pause");return 0;法2 :按照有向圖來處理的：運行結(jié)果：4 5A B C DA BA CA DB DB CA In Du is : 0B In Du is : 1C In Du is : 2D In Du is : 2A Out Du is : 3B Out Du is : 2C Out Du is : 0D Out Du is : 0請按任意鍵繼續(xù). . .代碼：#include <iostream>#include <cstring>using namespace std;typedef st

22、ruct nodeint dex;struct node *link; EdgeNode;typedef char VertexData;typedef struct VertexData data;EdgeNode *first_link;VertexNode;const int VertexNum = 10;typedef structVertexNode InVexListVertexNum;VertexNode OutVexListVertexNum;int n, e;AdjGraph;int FindPos(AdjGraph &G, char ch) for (int i =

23、 0; i < G.n; +i) if (ch = G.InVexListi.data) return i;void CreateGraph(AdjGraph &G)cin >> G.n >> G.e;for (int i = 0; i < G.n; +i) cin >> G.InVexListi.data; G.OutVexListi.data = G.InVexListi.data;G.OutVexListi.first_link = G.InVexListi.first_link = NULL; char ch1, ch2;int head, tail;for (int i = 0; i < G.e; +i) cin >> ch1 >> ch2;head = FindPos(G, ch1);tail = FindPos(G, ch2);EdgeNode *p = new EdgeNode;p->dex = tail;p->link = G.OutVexListhead.first_link;G.OutVexLi