計算機(jī)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、 習(xí) 題一、簡答題1有數(shù)據(jù)WG=7，19，2，6，32，3，21，10，則所建Huffman樹的樹高是_(1)_，帶權(quán)路徑長度WPL為_(2)_。1解：哈夫曼樹的高度是6。 帶權(quán)路徑長度為2612.分別給出直接插入排序、冒泡排序、直接選擇排序、歸并排序、快速排序和堆排序在下列條件下的執(zhí)行情況。對一個已排好序的數(shù)組進(jìn)行排序；對一個逆序的數(shù)組進(jìn)行排序。 2 解答：直接插入冒泡排序直接選擇歸并排序快速排序堆排序正序最好最好不敏感不敏感最壞不敏感逆序最壞最壞不敏感不敏感最壞不敏感判斷題： 1.一個沒有回路的連通圖是樹。 （錯） 2.中序遍歷一棵二叉查找樹的結(jié)點(diǎn)可以得到一個排好序的結(jié)點(diǎn)序列。（對）3 （

2、1）如果G1是一個具有n個頂點(diǎn)的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？（2）如果G2是一個具有n個頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？（3）如果G3是一個具有n個頂點(diǎn)的弱連通有向圖，那么G3最多有多少條邊？G3最少有多少條邊？ 3答：（1）G1最多n(n-1)/2條邊，最少n-1條邊 (2) G2最多n(n-1)條邊，最少n條邊 (3) G3最多n(n-1)條邊，最少n-1條邊 (注：弱連通有向圖指把有向圖看作無向圖時，仍是連通的) 4試用下列三種表示法畫出網(wǎng)G 的存儲結(jié)構(gòu)，并評述這三種表示法的優(yōu)、缺點(diǎn)：（1）鄰接矩陣表示法; （2）鄰接表表示法;

3、 4答：鄰接矩陣表示法，有n個頂點(diǎn)的圖占用n2個元素的存儲單元，與邊的個數(shù)無關(guān)，當(dāng)邊數(shù)較少時，存儲效率較低。這種結(jié)構(gòu)下，對查找結(jié)點(diǎn)的度、第一鄰接點(diǎn)和下一鄰接點(diǎn)、兩結(jié)點(diǎn)間是否有邊的操作有利，對插入和刪除頂點(diǎn)的操作不利。鄰接表表示法是頂點(diǎn)的向量結(jié)構(gòu)與頂點(diǎn)的鄰接點(diǎn)的鏈?zhǔn)酱鎯Y(jié)構(gòu)相結(jié)合的結(jié)構(gòu)，頂點(diǎn)的向量結(jié)構(gòu)含有n（n0）個頂點(diǎn)和指向各頂點(diǎn)第一鄰接點(diǎn)的指針，其頂點(diǎn)的鄰接點(diǎn)的鏈?zhǔn)酱鎯Y(jié)構(gòu)是根據(jù)頂點(diǎn)的鄰接點(diǎn)的實際設(shè)計的。這種結(jié)構(gòu)適合查找頂點(diǎn)及鄰接點(diǎn)的信息，查頂點(diǎn)的度，增加或刪除頂點(diǎn)和邊（?。┮埠芊奖?，但因指針多占用了存儲空間，另外，某兩頂點(diǎn)間是否有邊（?。┮膊蝗玎徑泳仃嚹敲辞宄τ邢驁D的鄰接表，查頂點(diǎn)出度

4、容易，而查頂點(diǎn)入度卻困難，要遍歷整個鄰接表。要想查入度象查出度那樣容易，就要建立逆鄰接表。無向圖鄰接表中邊結(jié)點(diǎn)是邊數(shù)的二倍也增加了存儲量。5在執(zhí)行某種排序算法的過程中出現(xiàn)了排序碼朝著最終排序序列相反的方向移動，從而認(rèn)為該排序算法是不穩(wěn)定的，這種說法對嗎？為什么？ 5答： 這種說法不對。因為排序的不穩(wěn)定性是指兩個關(guān)鍵字值相同的元素的相對次序在排序前、后發(fā)生了變化，而題中敘述和排序中穩(wěn)定性的定義無關(guān)，所以此說法不對。對4，3，2，1起泡排序就可否定本題結(jié)論。 6請回答下列關(guān)于堆(Heap)的一些問題： (1) 堆的存儲表示是順序的，還是鏈接的? (2) 設(shè)有一個小根堆，即堆中任意結(jié)點(diǎn)的關(guān)鍵碼均大于

5、它的左子女和右子女的關(guān)鍵碼。其具有最大值的元素可能在什么地方?6. 答：（1）堆的存儲是順序的（2）最大值元素一定是葉子結(jié)點(diǎn)，在最下兩層上。7二叉樹由_(1)_，_(2)_，_(3)_三個基本單元組成。7.(1)根結(jié)點(diǎn)(2)左子樹(3)右子樹 8. 有以下算法，其時間復(fù)雜度為（C ）。void fun(int n) while(i*i*ilchild),f(b-lchild),c) 其他情況其中，f()為遞歸函數(shù)，g為非遞歸函數(shù)，c為常量。（2）求二叉樹深（高）度解析：遞歸模型如下：f(b)=0 若b=NULLf(b)= MAXf(b-lchild),f(b-rchild)+1 其他情況相應(yīng)算

6、法如下：int BiTreeDepth(BiTree bt) int hl, hr; if (bt=NULL) return(0); elsehl=BiTreeDepth(bt-LChild);/*求左子樹的深度 */ hr=BiTreeDepth(bt-RChild);/*求右子樹的深度 */ return(hlhr)?(hl+1):(hr+1);) （3）統(tǒng)計一棵給定二叉樹中的所有葉子結(jié)點(diǎn)數(shù)解析：遞歸模型如下：f(b)=0 若b=NULLf(b)=1 若b-lchild=NULL 且b-rchild=NULLf(b)= f(b-lchild)+ f(b-rchild) 其他情況相應(yīng)算法如下

7、：int LeafNodes (BiTree bt) int num1,mun2; if (bt=NULL) return 0; else if (bt-lchild=NULL & bt-rchild=NULL)return 1; else num1=LeafNodes(bt-lchild); num2=LeafNodes(bt-rchild); return (num1+num2);1、已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一個結(jié)點(diǎn)的指針，是否可不用遞歸且不用棧來完成？請簡述原因。答：可以。原因：后序遍歷的順序是“左子樹右子樹根結(jié)點(diǎn)”。因此，二叉樹最左下的葉子結(jié)點(diǎn)是

8、遍歷的第一個結(jié)點(diǎn)。下面的語句段說明了這一過程（設(shè)p是二叉樹根結(jié)點(diǎn)的指針）。if (p!=null)while (p-lchild!=null | p-rchild!=null)while(p-lchild!=null) p=p-lchild;if(p-rchild!=null) p=p-rchild; return(p); /返回后序序列第一個結(jié)點(diǎn)的指針（5）已知二叉樹的前序序列、中序序列構(gòu)造二叉樹的算法。BiTree CreateBT1(char *pre，char *in, int n)/* pre存放前序序列，in存放中序序列，n為in中字符個數(shù)，本算法執(zhí)行后返回構(gòu)造的二叉樹的根結(jié)點(diǎn)指針

9、*/ BiTree bt; char *p;int k; if (ndata=*pre;for(p=in;plchild= CreateBT1(pre+1,in,k); bt-rchild= CreateBT1(pre+k+1,p+1,n-k-1); return bt; BiTree CreateBT1(char *pre，char *in, int n)for(p=in;plchild= CreateBT1(pre+1,in,k); bt-rchild= CreateBT1(pre+k+1,p+1,n-k-1); return bt; 先序序列：ABDGCEF中序序列：DGBAECF (k

10、=3)BiTree CreateBT1(char *pre，char *in, int n)for(p=in;plchild= CreateBT1(pre+1,in,k); bt-rchild= CreateBT1(pre+k+1,p+1,n-k-1); return bt; 先序序列：ABDGCEF中序序列：DGBAECF (k=2) 2在有向圖G中，如果r到G中的每個結(jié)點(diǎn)都有路徑可達(dá)，則稱結(jié)點(diǎn)r為G的根結(jié)點(diǎn)。編寫一個算法完成下列功能：（1）建立有向圖G的鄰接表存儲結(jié)構(gòu)；（2）判斷有向圖G是否有根，若有，則打印出所有根結(jié)點(diǎn)的值。2. 題目分析本題應(yīng)使用深度優(yōu)先遍歷，從主調(diào)函數(shù)進(jìn)入dfs(v)

11、時 ，開始記數(shù)，若退出dfs()前，已訪問完有向圖的全部頂點(diǎn)（設(shè)為n個），則有向圖有根，v為根結(jié)點(diǎn)。將n個頂點(diǎn)從1到n編號，各調(diào)用一次dfs()過程，就可以求出全部的根結(jié)點(diǎn)。題中有向圖的鄰接表存儲結(jié)構(gòu)、記頂點(diǎn)個數(shù)的變量、以及訪問標(biāo)記數(shù)組等均設(shè)計為全局變量。 void JudgeRoot()/判斷有向圖是否有根，有根則輸出之。 static int i ;for (i=1;iadjvex=0) dfs (p-adjvex);p=p-next; /while visitedv=0; num-; /恢復(fù)頂點(diǎn)v/dfsint num=0， visited=0 /num記訪問頂點(diǎn)個數(shù),訪問數(shù)組visit

12、ed初始化。 const n=用戶定義的頂點(diǎn)數(shù); AdjList g ; /用鄰接表作存儲結(jié)構(gòu)的有向圖g。 void dfs(v) visited v=1; num+; /訪問的頂點(diǎn)數(shù)1 if (num=n) printf(“%d是有向圖的根。n”,v); num=0;/if p=gv.firstarc; while (p) if (visiedp-adjvex=0) dfs (p-adjvex);p=p-next; /while visitedv=0; num-; /恢復(fù)頂點(diǎn)v/dfs 3 編寫算法求二叉樹中從根節(jié)點(diǎn)到各葉子節(jié)點(diǎn)路徑中最長的路徑，并輸出此路徑上各個結(jié)點(diǎn)的值。3、 解題思路 本

13、題采用非遞歸后根遍歷二叉樹的方法。引入一個輔助數(shù)據(jù)結(jié)構(gòu)棧stack。當(dāng)后根遍歷訪問到由p所指的葉結(jié)點(diǎn)時，stack中的所有結(jié)點(diǎn)均為p所指結(jié)點(diǎn)的祖先，由這些祖先便構(gòu)成了一條從根結(jié)點(diǎn)到此葉結(jié)點(diǎn)的路徑。另外，設(shè)一LongestPath數(shù)組來保存二叉樹中最長的路徑，m為最長的路徑長度。算法的C+實現(xiàn)： void LongPath (BintreeNode *root , int maxsize;) BintreeNode *stackmaxsize,*s; char LongestPathmaxsize; /保存最長路徑的數(shù)組int i, m, top; /top為棧頂指針，m為最長路徑長度int t

14、agmaxsize; /tag為標(biāo)志數(shù)組，若結(jié)點(diǎn)i的左右孩子均被訪問過，則tagi=1 m=0; top=0; s=root; do while (s! =NULL) /祖先結(jié)點(diǎn)入棧 top+; stacktop = s; tagtop = 0; /右孩子還未訪問過s = sleft; if (top0) /保存最長路徑 if (tagtop = 1) /左右孩子均已訪問過，則訪問該結(jié)點(diǎn) if (stacktop left = NULL) & (stacktop right = NULL) & (topm) for (i =1; idata; m = top; top; else s = stacktop; if (top0) s=sright; tagtop =1; while (s! =NULL) | (top! =0); for (i=1; i=m; i+) coutlongest