【正文】 ， 其指針字段的總數(shù)為 _________個 ， 其中 _________個用于鏈接孩子結(jié)點 ， _________個空閑 。 A. 只有右子樹上的所有結(jié)點 B. 只有右子樹上的部分結(jié)點 C. 只有左子樹上的所有結(jié)點 D. 只有左子樹上的部分結(jié)點 (10)任何一棵二叉樹的葉結(jié)點在先序 、 中序和后序遍歷序列中的相對次序 ___。 (4) 設(shè)計算法 ， 將給定二叉樹的葉子結(jié)點連成一個帶頭結(jié)點的單鏈表 ， 并要求葉子結(jié)點按照從左到右的順序插入 ， 而排列順序為從右到左 (逆置 )的單鏈表 。 ? 2. 有向圖 : 每條邊都有方向 (如圖 (b))的圖稱為有向圖 。 ? 11. 子圖 : 圖 G1的所有的頂點是圖 G的頂點 ， G1的所有的邊是 G的邊 ， 那么 G1是 G的子圖 。 ??????間沒有邊與間有邊與jijiVVVVjiA01]][[圖 G1的鄰接矩陣如圖 ， 圖 G2的鄰接矩陣如圖 。(Gvexs[i]))。Ch2!=Gvexs[j]。 EdgeNode * s。 //生成新邊表結(jié)點 s(也可為 s=(EdgeNode*)malloc (sizeof(EdgeNode))) sadjvex=j。 } void DFSM(MGraph *G， int i) { int j。iGn。amp。 (4) 一個具有 n個頂點的有向完全圖的弧數(shù)為 ____________。 (3) 假設(shè)一棵完全圖包含 A， B， C， D四個結(jié)點 ， 畫出其鄰接表 。 第 7章 內(nèi) 部 排 序 ? 排序概述 ? 插入排序 ? 快速排序 ? 選擇排序 ? 基數(shù)排序 ? 各種內(nèi)部排序方法的比較 ? 上機(jī)實習(xí) ? 習(xí)題 排序概述 ? 排序 (Sorting)是計算機(jī)程序設(shè)計中的一種重要操作 ， 它的功能是將若干個數(shù)據(jù)元素 (或記錄 )構(gòu)成的任意序列 ， 重新排列成一個按關(guān)鍵字排序的序列 。 ? 提示： 假設(shè)記錄 Ri和 Rj (1≤i≤n， 1≤j≤n， i≠j)的關(guān)鍵字 Ki=Kj，且在排序前的序列中 Ri領(lǐng)先于 Rj(即 ij)， 若在排序后的序列中 Ri仍領(lǐng)先于 Rj， 則稱所用的排序方法是穩(wěn)定的 。 ??????????????????????????????01010000011000101000001100111101111011110(a) (b) 圖 鄰接矩陣 圖 加權(quán)圖 圖 有向圖 012340 1 2 3 4V 0 1 1 0 0V 1 0 1 1 1V 1 1 0 1 1V 0 1 1 0 1V 0 1 1 1 0 V V V V V????????????????圖 一個無向圖 G的鄰接矩陣 012340 1 2 3 4V 0 0 0 1 0V 0 0 1 0 1V 0 1 0 0 0V 1 0 0 0 0V 0 1 0 0 0V V V V V??????????圖 某無向圖 G的鄰接矩陣 圖 無向圖 G的鄰接表 Q amp。 A. 對稱矩陣 B. 零矩陣 (9) 下列說法中正確的是 _______。 ? 2. 構(gòu)造最小生成樹的 Kruskal方法 圖 Kruskal方法構(gòu)造最小生成樹的過程。Q)。 for(i=0。i++) visited[i]=FALSE。k++) //建立邊表 { scanf(\n%d,%d,amp。// AdjList是鄰接表類型 typedef struct{ AdjList adjlist。 for(i=0。 for(i=0。 圖的相關(guān)術(shù)語 圖 連通圖和連通分量 圖 圖 G2的兩個強(qiáng)連通分量 圖的基本操作 圖有以下基本操作： 1. CreatGraph(G):輸入圖 G的頂點和邊 ， 建立圖 G的存儲 。 路徑上邊的數(shù)目稱為該路徑的長度 。 E ={ (V1， V2) ， (V1， V4) ， (V2， V3) ， (V2， V5) ， (V3， V4) ， (V3， V5) } 。 (9) 將圖 。 +n3 +n2+n3 (6) 設(shè)深度為 k的二叉樹上只有度為 0或度為 2的結(jié)點 ， 則這類二叉樹上所含結(jié)點總數(shù)至少 _____。 levorder(root)。 if(t!=null) { front=0。 int front=0,rear=0。 trchild=p。 bitree* creat() /*建立二叉樹 */ { bitree *t。 ? 先根 (次序 )遍歷 若樹非空 ， 則遍歷方法為首先訪問根結(jié)點；然后從左到右 ，依次先根遍歷根結(jié)點的每一棵子樹 。 ChildPtr firstchild。該存儲結(jié)構(gòu)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點上附設(shè)一個指示器，指示其雙親結(jié)點的位置。 ? 樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 。 ? 先序遍歷 (DLR)： 若二叉樹為空 ， 則空操作 ， 否則依次執(zhí)行如下三個操作： (1) 訪問根結(jié)點； (2)先序遍歷左子樹； (3) 先序遍歷右子樹 。 根據(jù)二叉鏈表的結(jié)構(gòu)特點 ， 可以得出：若一棵二叉樹含有 n個結(jié)點 ， 則它的二叉鏈表中必含有 2n個指針字段 ， 其中 n+1個為空鏈字段 。 ?二叉樹的抽象數(shù)據(jù)類型的定義如下： ADT BinaryTree ? 二叉樹的概念 圖 二叉樹的五種基本形態(tài) ? 二叉樹的概念 ? 二叉樹的概念 ?基本操作： InitBiTree(BiTree)： DestoryBiTree(TBiree)： CreateTree(BiTree)： BiTreeEmpty(BiTree)： ROOT(BiTree)： BiTreeDepth(BiTree)： Parent(BiTree， x)： LeftChild(BiTree， x)： RightChild(BiTree， x)： InsertChild(BiTree， p， i， Child)： DeleteChild(BiTree， p， i)： Value(BiTree， x)： Assign(BiTree，x， value)： PreOrderTraverse(BiTree， visit())： InOrderTraverse(BiTree， visit())： PostOrderTraverse(BiTree， visit())： LevelOrderTraverse(BiTree， visit())： 二叉樹的概念 2. 滿二叉樹 棵深度為 k且有 2k1個結(jié)點的二叉樹稱為滿二叉樹 。 ROOT(Tree)：返回樹 Tree的根 。 ? 樹的高度 (深度 )： 樹中所有結(jié)點的層次的最大值 。 本章介紹的樹型結(jié)構(gòu) ， 其結(jié)點間關(guān)系具有惟一的前驅(qū)而后繼不惟一 ， 即結(jié)點之間是一對多的關(guān)系 。 ? 分支結(jié)點 (非終端結(jié)點 )： 度不為零的結(jié)點 。 ? 數(shù)據(jù)關(guān)系 R： 若 D為空集 ， 則為空樹 。 將 Child插入 Tree中 ， 作為 p所指向結(jié)點的子樹 。 (2) 若 2in，則序號為 i的結(jié)點無左孩子；若 2i≤n，則序號為 i的結(jié)點的左孩子結(jié)點的序號為 2i； (3) 若 2i+1n，則序號為 i的結(jié)點無右孩子；若 2i+1≤n，則序號為 i的結(jié)點的右孩子結(jié)點的序號為 2i+1。 ? 先訪問根 ， 再遍歷右子樹 ， 最后遍歷左子樹 (記做 DRL)。 } } 二叉樹的遍歷 __算法 后序遍歷二叉樹的算法 : void PostOrder(BiTree *p) { if(p!=NULL) { PostOrder(plchild)。 利用二叉樹可以設(shè)計出二進(jìn)制編碼的前綴編碼 ， 將需要編碼的字符做為葉子結(jié)點構(gòu)造一棵二叉樹 ， 并且約定二叉樹的左分支表示的字符為 0， 右分支表示的字符為 1， 則可以從根結(jié)點到葉子結(jié)點的路徑分支上的 0、 1組成的序列作為該葉子結(jié)點字符的編碼 。 typedef struct { PTNode nodes[MAX]。 樹、森林與二叉樹的轉(zhuǎn)換 ? 具體步驟如下： (1) 將樹的根結(jié)點作為二叉樹的根結(jié)點； (2) 對于樹中的每個結(jié)點 ， 都將其第一個孩子結(jié)點作為該二叉樹結(jié)點的左子樹 ， 將其第一個兄弟結(jié)點作為該二叉樹結(jié)點的右子樹 。 ② 訪問第一棵樹的根結(jié)點。 } return t。 inorder(root)。 trchild=creat()。 } if(trchild!=Null) { rear=rear%max+1。 (9) 有 m個葉子結(jié)點的哈夫曼樹 ， 其結(jié)點總數(shù)為 ________________。 ( ) 習(xí) 題 __解答題 4. 解答題 (參見教材題目及圖例 ) (1) 已知一棵樹邊的集合為 {(I， M)， (I， N)， (E， I)， (B， E)， (B， D)， (A，B)， (G， J)， (G， K)， (C， G)， (C， F)， (H， L)， (C， H)， (A， C)}，畫出這棵樹，并回答下列問題： ① 哪個結(jié)點是根結(jié)點？ ② 哪些結(jié)點是葉子結(jié)點 ? ③ 哪個結(jié)點是結(jié)點 G的雙親結(jié)點 ? ④ 哪些結(jié)點是結(jié)點 G的祖先結(jié)點？ ⑤ 哪些結(jié)點是結(jié)點 G的孩子結(jié)點 ? ⑥ 哪些結(jié)點是結(jié)點 E的子孫結(jié)點 ? ⑦ 哪些結(jié)點是結(jié)點 E的兄弟結(jié)點？哪些是結(jié)點 F的兄弟結(jié)點？ ⑧ 結(jié)點 B和 N的層次分別是多少 ? ⑨ 樹的深度是多少 ? ⑩ 以結(jié)點 C為根的子樹的深度是多少 ? (2) 說明一棵度為 2的樹與一棵二叉樹之間的區(qū)別。 ? 教學(xué)目標(biāo)： 通過本章的學(xué)習(xí) ， 使讀者能掌握圖的概念 、有關(guān)術(shù)語 、 存儲方式和遍歷算法等內(nèi)容 ， 理解圖的應(yīng)用 。 ? 5. 稠密圖 /稀疏圖 : 若邊數(shù)為 e， 頂點數(shù)為 n， 邊數(shù)稀少到 enlogn，則稱該圖為稀疏圖 ， 否則該圖為稠密圖 。 圖的相關(guān)術(shù)語 (3) ? 13. 強(qiáng)連通圖和強(qiáng)連通分量 : 有向圖中任意一對頂點 Vi和 Vj間互相有路徑 ， 稱該有向圖是強(qiáng)連通圖 。 int n,e。j++) 圖的鄰接矩陣 (4) Gedges[i][j]=0。 ? 2. 鄰接表的數(shù)據(jù)類型 (算法 ) define MAXLEN 10 // 最大頂點數(shù)為 10 typedef struct node{ // 邊表結(jié)點 int adjvex。 //讀入頂點數(shù)和邊數(shù) printf(請輸入頂點信息 (輸入格式為：頂點號 CR)每個頂點以回車作為結(jié)束 :\n)。 圖的遍歷 (2) ? 深度優(yōu)先搜索 ? 廣度優(yōu)先搜索 深度優(yōu)先搜索 ? 深度優(yōu)先搜索 (Depth First Search)遍歷類似于樹的先根遍歷 ， 是樹的先根遍歷的推廣 。amp。Q)。 //進(jìn)隊 } } } 生成樹和最小生成樹 ? 生成樹 ? 最小生成樹 生成樹 ? 構(gòu)造生成樹的方法有以下兩種 : ?