計算機學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)

計算機學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)-5一、綜合應(yīng)用題（總題數(shù)：10,分?jǐn)?shù)：100.00）一棵高度為h的滿m叉樹有如下性質(zhì)：第h層上的結(jié)點都是葉結(jié)點，其余各層上每個結(jié)點都有m棵非空子樹。如果按層次自頂向下，同一層自左向右，順序從1開始對全部結(jié)點進(jìn)行編號，試問：（1）.各層的結(jié)點個數(shù)是多少？（分?jǐn)?shù)：4.00）可以參照二叉樹的性質(zhì)，將其擴展到m叉樹。因為第1層有1個結(jié)點，第2層有m個結(jié)點，第3層有m2個結(jié)點……一般地，第i層有mi-1個結(jié)點（1WiWh）。（2）.編號為i的結(jié)點的父結(jié)點（若存在）的編號是多少？（分?jǐn)?shù)：4.00），根在m叉樹的情形，結(jié)點i的第1個子女編號為j=（i-1）Xm+2。反過來，結(jié)點i的雙親的編號是結(jié)點沒有雙親，所以以上計算式要求i〉1。如果考慮對于i=1也適用（根的雙親設(shè)為0），可將上式改為（3）.編號為i的結(jié)點的第k個子女結(jié)點（若存在）的編號是多少？（分?jǐn)?shù)：4.00）因為結(jié)點i的第1個子女編號為（i-1）Xm+2，若設(shè)該結(jié)點子女的序號為k=1，2,…，m，則第k個子女結(jié)點的編號為（i-1）Xm+k+1（1WkWm）。，根（4）.編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少？（分?jǐn)?shù)：4.00）當(dāng)結(jié)點i不是其雙親的第m個子女時才有右兄弟。若設(shè)其雙親編號為當(dāng)結(jié)點i不是其雙親的第m個子女時才有右兄弟。若設(shè)其雙親編號為j，可得j=，結(jié)點j的第m個子女的編號為：（j-1）Xm+m+1=jXm+1所以當(dāng)結(jié)點的編號iWjXm時才有右兄弟，右兄弟的編號為i+1。（5）.若結(jié)點個數(shù)為n，則高度h是n的什么函數(shù)關(guān)系？（分?jǐn)?shù)：4.00）針對二叉樹BiTree，利用二叉樹遍歷的思想編寫解決下列問題的遞歸算法。（分?jǐn)?shù)：24.00）（1）.intsize（BiTNode*t）；//返回以*t為根的二叉樹中所有結(jié)點個數(shù)（分?jǐn)?shù)：4.00）返回以*t為根的二叉樹中所有結(jié)點個數(shù)：intsize(BinTreeNode*t){if(t==NULL)return0;return1+size(t-〉lchild)+size(t-〉rchild);}.intleaves(BiTNode*t)；//返回以*t為根的二叉樹的葉結(jié)點個數(shù)(分?jǐn)?shù)：4.00)返回以*t為根的二叉樹中葉結(jié)點個數(shù)：intleayes(BiTNode*t){if(t==NULL)return0;if(t-〉lchild==NULL&&t-〉rchild==NULL)return1;returnleayes(t-〉lchild)+leayes(t-〉rchild);}.intheight(BiTNode*t)；//返回以*t為根的二叉樹的高度(分?jǐn)?shù)：4.00)返回以*t為根的二叉樹的高度：intheight(BiTNode*t){if(t==NULL)return0;inth1=height(t-〉lchild);inthr=height(t-〉rchild);if(h1〉hr)returnh1+1;elsereturnhr+1;}.intlevel(BiTNode*t,BiTNode*p)；//返回二叉樹指定結(jié)點*p在以*t為根的子樹中的層次(分?jǐn)?shù)：4.00)返回以*t為根的二叉樹中指定結(jié)點*p所在層次：intlevel(BiTNode*t,BiTNode*p,intd){if(t==NULL)return0;if(t==p)return(d);intlevel;if(level=level(t-〉lchild,p,d+1))return(level1);elsereturn(level(t-〉rchild,p,d+1));}.voidreflect(BiTNode*t)；//交換以*t為根的二叉樹中每個結(jié)點的兩個子女(分?jǐn)?shù)：4.00)交換以*t為根的二叉樹中每個結(jié)點的兩個子女：voidreflect(BiTNode*t){if(t==NULL)return;reflect(t-〉lchild);reflect(t-〉rchild);BiTNode*p=t-〉lchild;t-〉lchiId=t-〉rchild;t-〉rchild=p;}.voiddefoliate(BiTNode*&t)；〃從以*t為根的二叉樹中刪去所有葉結(jié)點(分?jǐn)?shù)：4.00)從以*t為根的二叉樹中刪去所有葉結(jié)點：voiddefoliate(BiTNode*&t){if(t==NULL)return;if(t-〉lchild==NULL&&t-〉rchild==NULL){free(t);t=NULL;}else{defoliate(t-〉lchild);defoliate(t-〉rchild);}}巳知一棵二叉樹的前序遍歷序列為ABECDFGHIJ,中序遍歷序列為EBCDAFHIGJ,試畫出這棵二叉樹并寫出它的后序遍歷序列。(分?jǐn)?shù)：4.00)當(dāng)前序序列為ABECDFGHU，中序序列為EBCDAFHIGJ時，逐步形成二叉樹的過程如下圖所示。其后序遍歷序列為EDCBIHJGFA。設(shè)二叉樹根結(jié)點在第1層，樹的深度d為距離根最遠(yuǎn)的葉結(jié)點所在層次，試給出：（分?jǐn)?shù)：8.00）（1）.深度為d的完全二叉樹的不同二叉樹棵數(shù)。（分?jǐn)?shù)：4.00）深度為d的完全二叉樹的1到d-1層都是滿的，第d層有多少結(jié)點就有多少種選擇。第d層最多有2d-1個結(jié)點，所以不同二叉樹的棵數(shù)有2d-1棵。（2）.深度為d的滿二叉樹的不同二叉樹棵數(shù)。（分?jǐn)?shù)：4.00）深度為d的不同的滿二叉樹只有1棵。畫出一個二叉樹，使得它既滿足大根堆的要求又滿足二叉排序樹的要求。（分?jǐn)?shù)：4.00）大根堆要求根結(jié)點的關(guān)鍵字值既大于或等于左子女的關(guān)鍵字值又大于或等于右子女的關(guān)鍵字值，二叉排序樹要求根結(jié)點的關(guān)鍵字值大于左子女的關(guān)鍵字值同時小于右子女的關(guān)鍵字值。兩種的交集是：根結(jié)點的關(guān)鍵字值大于左子女的關(guān)鍵字值。這意味著是一棵左斜單枝樹。但大根堆要求其是完全二叉樹，因此最好得到的是如下圖所示的只有兩個結(jié)點的二叉樹。給定一個關(guān)鍵字集合｛25，18,34,9，14,27,42,51，38｝，假定查找各關(guān)鍵字的概率相同，請畫出其最佳二叉排序樹。（分?jǐn)?shù)：4.00）當(dāng)各關(guān)鍵字的查找概率相等時，最佳二叉排序樹應(yīng)是高度最小的二叉排序樹。構(gòu)造過程分兩步走：首先對各關(guān)鍵字值從小到大排序，然后仿照折半查找的判定樹的構(gòu)造方法構(gòu)造二叉排序樹。這樣得到的就是最佳二叉排序樹，如下圖所示。巳知一棵樹的先根次序遍歷的結(jié)構(gòu)與其對應(yīng)二叉樹表示（子女-兄弟鏈表表示）的前序遍歷結(jié)果相同，樹的后根次序遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同。請回答以下問題：（分?jǐn)?shù)：8.00）（1）.利用樹的先根遍歷結(jié)果和后根遍歷結(jié)果能否唯一確定一棵樹?舉例說明。（分?jǐn)?shù)：4.00）因為給出二叉樹的前序遍歷序列和中序遍歷序列能夠唯一地確定這棵二叉樹，因此，根據(jù)題目給出的條件，利用樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能夠唯一地確定一棵樹。例如，對于下圖中左圖所示的樹，對應(yīng)二叉樹的前序序列為1,2,3,4,5,6,8,7，中序序列為3,4,8,6,7,5,2,1。原樹的先根遍歷序列為1,2,3,4,5,6,8,7，后根遍歷序列為3,4,8,6,7,5,2,1。（2）.n個結(jié)點的不同形狀的樹有多少種？（分?jǐn)?shù)：4.00）確定n個結(jié)點的不同樹的數(shù)目可以歸結(jié)到確定其對應(yīng)二叉樹的計數(shù)。因為樹轉(zhuǎn)化為二叉樹后，根結(jié)點沒有右子女，該二叉樹的計數(shù)歸結(jié)到對應(yīng)二叉樹根下左子樹可能有多少種不同構(gòu)造。可以利用n-1個結(jié)點的Catalan函數(shù)來計算。下面是一個二叉樹的前序遍歷的遞歸算法。voidPreOrder（BiTNode*t）｛if（t!=NULL）｛//遞歸結(jié)束條件cout<<t->data;〃訪問（輸出）根結(jié)點Preorder（t-〉lchild）;//前序遍歷根的左子樹Preorder（t->rchild）;//前序遍歷根的右子樹｝｝（分?jǐn)?shù)：8.00）（1）.改寫PreOrder算法，消去第二個遞歸調(diào)用PreOrder（t->rchild）；（分?jǐn)?shù)：4.00）消去第二個遞歸語句時，視第一個遞歸語句為一般語句，按尾遞歸處理。voidpreOrder(BiTNode*t){while(t!=NULL){〃按尾遞歸改為循環(huán)cout<<t->data;PreOrder(t-〉lchild);t=t->rchild;//向右子樹循環(huán)}}(2).利用棧改寫PreOrder算法，消去兩個遞歸調(diào)用。(分?jǐn)?shù)：4.00)定義一個棧，在訪問某一個結(jié)點時保存其右、左子女結(jié)點的地址。下一步將先從棧中退出右子女結(jié)點，對其進(jìn)行遍歷，然后從棧中退出左子女結(jié)點，對其進(jìn)行遍歷。voidPreOrder(BiTNode*t){BiTNode*p;StackS;initStack(S);push(S,t);while(!IsEmpty(s)){pop(S,p);cout<<p->data;if(p->rchild!=NULL)push(S,p->rchild);if(p->lchild!=NULL)push(S,p->ichild);}}請回答下列關(guān)于圖的一些問題：(分?jǐn)?shù)：15.00)(1).有n個頂點的有向強連通圖最多有多少條邊?最少有多少條邊？有n個頂點的有向強連通圖最多有n(n-1)條邊，最少有n條邊。(2).表示一個有1000個頂點、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否為稀疏矩陣?有1000個頂點、1000條邊的有向圖的鄰接矩陣有1000000個矩陣元素，其中只有1000個非零元素，是一個稀疏矩陣。注意，它不一定是對稱的。.對于一個有向圖，不用拓?fù)渑判?，如何判斷圖中是否存在環(huán)？對一個有向圖，還可以用以下方法判斷圖中是否存在環(huán)：①如果圖中所有頂點的出度至少為1，入度也至少為1，則圖中存在環(huán)。這個條件太強。②如果對圖進(jìn)行深度優(yōu)先搜索，從某個頂點出發(fā)，又走到以前巳經(jīng)訪問過的頂點，則圖中存在環(huán)。在有關(guān)圖的算法中常用到兩個圖的操作：intgetFirstNeighbor(GraphG,intv);//取頂點v的第一個鄰接頂點intgetNextNeighbor(GraphG,intv,intw);〃取鄰接頂點w的下一鄰接頂點試分別給出在鄰接矩陣和鄰接表為存儲結(jié)構(gòu)的情形下它們的實現(xiàn)。(1)用鄰接矩陣做存儲結(jié)構(gòu)的場合。為了找到頂點v的第一個臨界頂點，順序地檢測鄰接矩陣的第v行，最先遇到的非零元素(帶權(quán)圖情形是小于maxValue的元素)就是頂點v的第一個鄰接頂點。從這個矩陣元素繼續(xù)向后找，就可以以類似的判斷找到下一個鄰接頂點。intgetFirstNeighbor(Graphmtx&G,intv){〃給出頂點v的第一個鄰接頂點，如果找不到，則函數(shù)返回-1。if(v!=-1){for(intcol=0;col<G.numvertices;col++)if(G.Edge[v][col]〉0&&G.Edge[v][col]<maxValue)returncol;}return-1;}intgetNextNeighbor(Graphmtx&G,intv,intw){〃給出頂點v的某鄰接頂點w的下一個鄰接頂點if(v!=-1&&w!=-1){for(intcol=w+1;col<G.numVertices;col++)if(G.Edge[v][col]〉0&&G.Edge[V][col]<maxWeight)returncol;}return-1;}(2)用鄰接表作存儲結(jié)構(gòu)的場合。為了找到頂點v的第一個鄰接頂點，檢測鄰接表第v個邊鏈表，如果鏈表非空，第一個邊結(jié)點中dest域存放的頂點(號)就是頂點v的第一個鄰接頂點。在此鏈表中該邊結(jié)點的下一個邊結(jié)點就是下一個鄰接頂點。intgetFirstNeighbor(Graphlnk&G,intv){〃給出頂點v的第一個鄰接頂點，如果找不到，則函數(shù)返回-1。if(v!=-1){〃頂點v存在Edge*p=G.NodeTable[v].adj;〃對應(yīng)邊鏈表第一個邊結(jié)點if(p!=NULL)returnp-〉dest;//存在,返回第一個鄰接頂點}Return-1;〃第