計算機數(shù)據(jù)結構復習題

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

2、1）如果G1是一個具有n個頂點的連通無向圖，那么G1最多有多少條邊？G1最少有多少條邊？（2）如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？（3）如果G3是一個具有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 的存儲結構，并評述這三種表示法的優(yōu)、缺點：（1）鄰接矩陣表示法; （2）鄰接表表示法;

3、 4答：鄰接矩陣表示法，有n個頂點的圖占用n2個元素的存儲單元，與邊的個數(shù)無關，當邊數(shù)較少時，存儲效率較低。這種結構下，對查找結點的度、第一鄰接點和下一鄰接點、兩結點間是否有邊的操作有利，對插入和刪除頂點的操作不利。鄰接表表示法是頂點的向量結構與頂點的鄰接點的鏈式存儲結構相結合的結構，頂點的向量結構含有n（n0）個頂點和指向各頂點第一鄰接點的指針，其頂點的鄰接點的鏈式存儲結構是根據(jù)頂點的鄰接點的實際設計的。這種結構適合查找頂點及鄰接點的信息，查頂點的度，增加或刪除頂點和邊（?。┮埠芊奖悖蛑羔樁嗾加昧舜鎯臻g，另外，某兩頂點間是否有邊（弧）也不如鄰接矩陣那么清楚。對有向圖的鄰接表，查頂點出度

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

5、它的左子女和右子女的關鍵碼。其具有最大值的元素可能在什么地方?6. 答：（1）堆的存儲是順序的（2）最大值元素一定是葉子結點，在最下兩層上。7二叉樹由_(1)_，_(2)_，_(3)_三個基本單元組成。7.(1)根結點(2)左子樹(3)右子樹 8. 有以下算法，其時間復雜度為（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 其他情況相應算

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)計一棵給定二叉樹中的所有葉子結點數(shù)解析：遞歸模型如下：f(b)=0 若b=NULLf(b)=1 若b-lchild=NULL 且b-rchild=NULLf(b)= f(b-lchild)+ f(b-rchild) 其他情況相應算法如下

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的后序序列中的第一個結點的指針，是否可不用遞歸且不用棧來完成？請簡述原因。答：可以。原因：后序遍歷的順序是“左子樹右子樹根結點”。因此，二叉樹最左下的葉子結點是

8、遍歷的第一個結點。下面的語句段說明了這一過程（設p是二叉樹根結點的指針）。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); /返回后序序列第一個結點的指針（5）已知二叉樹的前序序列、中序序列構造二叉樹的算法。BiTree CreateBT1(char *pre，char *in, int n)/* pre存放前序序列，in存放中序序列，n為in中字符個數(shù)，本算法執(zhí)行后返回構造的二叉樹的根結點指針

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中的每個結點都有路徑可達，則稱結點r為G的根結點。編寫一個算法完成下列功能：（1）建立有向圖G的鄰接表存儲結構；（2）判斷有向圖G是否有根，若有，則打印出所有根結點的值。2. 題目分析本題應使用深度優(yōu)先遍歷，從主調函數(shù)進入dfs(v)

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

12、ed初始化。 const n=用戶定義的頂點數(shù); AdjList g ; /用鄰接表作存儲結構的有向圖g。 void dfs(v) visited v=1; num+; /訪問的頂點數(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-; /恢復頂點v/dfs 3 編寫算法求二叉樹中從根節(jié)點到各葉子節(jié)點路徑中最長的路徑，并輸出此路徑上各個結點的值。3、 解題思路 本

13、題采用非遞歸后根遍歷二叉樹的方法。引入一個輔助數(shù)據(jù)結構棧stack。當后根遍歷訪問到由p所指的葉結點時，stack中的所有結點均為p所指結點的祖先，由這些祖先便構成了一條從根結點到此葉結點的路徑。另外，設一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為標志數(shù)組，若結點i的左右孩子均被訪問過，則tagi=1 m=0; top=0; s=root; do while (s! =NULL) /祖先結點入棧 top+; stacktop = s; tagtop = 0; /右孩子還未訪問過s = sleft; if (top0) /保存最長路徑 if (tagtop = 1) /左右孩子均已訪問過，則訪問該結點 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