2005考研試題所有分支結(jié)點的度為2的二叉樹稱為正則二叉樹，試用二叉鏈表做存儲結(jié)構(gòu)，編寫一遞歸函數(shù)intFormalTree(Bitreet)，判斷二叉樹是否為正則二叉樹。intFormalTree(Bitreet){if(t==NULL)return1;if((t->lchild==NULL)&&(t->rchild==NULL))return1;if((t->lchild==NULL)||(t->rchild==NULL))return0;return(FormalTree(t->lchild))&&(FormalTree(t->rchild));}2005考研試題所有分支結(jié)點的度為2的二叉樹稱為正12005考研試題從空的平衡二叉排序樹開始，按以下順序插入關(guān)鍵字，請給出最終的平衡二叉樹。假設(shè)6個關(guān)鍵字的查找概率相等，求該樹的平均查找長度。

27,31,49,38,41,676731274927314938413127413849RR調(diào)整LR調(diào)整RR調(diào)整2005考研試題從空的平衡二叉排序樹開始，按以下順序插入關(guān)鍵22005考研試題從空的平衡二叉排序樹開始，按以下順序插入關(guān)鍵字，請給出最終的平衡二叉樹。假設(shè)6個關(guān)鍵字的查找概率相等，求該樹的平均查找長度。

27,31,49,38,41,67673127413849RR調(diào)整413149386727ASL=(3*3+2*2+1*1)/6=14/62005考研試題從空的平衡二叉排序樹開始，按以下順序插入關(guān)鍵32006考研試題下面不能唯一確定一棵二叉樹的兩個遍歷序列是____。A)先序序列和中序序列 B)先序序列和后序序列C)后序序列和中序序列 C)都不能在樹的孩子兄弟表示法中，二叉鏈表的左指針指向___________，右指針指向___________。B)先序序列和后序序列第一個孩子下一個兄弟2006考研試題下面不能唯一確定一棵二叉樹的兩個遍歷序列是_4在二叉鏈表的每個結(jié)點中添加一個域intdepth，表示以該結(jié)點為根的子樹的深度，即：typedefstructBiTNode{ //結(jié)點結(jié)構(gòu)

TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針intdepth;//以該結(jié)點為根的子樹的深度}BiTNode,*BiTree;a.試編寫一遞歸函數(shù)BiTreeDepth(BiTreeT)，計算二叉樹T中每個結(jié)點的depth值，函數(shù)的返回值為樹T的深度。b.在a的基礎(chǔ)上（即已求出二叉樹中每個結(jié)點的depth值），編寫一遞歸函數(shù)BiTreeBalance(BiTreeT)，判斷二叉排序樹T是否為平衡二叉樹，如果是平衡二叉樹，則函數(shù)的返回值為真。在二叉鏈表的每個結(jié)點中添加一個域intdepth，表示以該5a.intBiTreeDepth(BiTreeT){intldepth,rdepth;if(!T)return-1;ldepth=BiTreeDepth(T->lchild);rdepth=BiTreeDepth(T->rchild);if(ldepth>=rdepth)T->depth=ldepth+1;elseT->depth=rdepth+1;returnT->depth;}???a.???6b.StatusBiTreeBalance(BiTreeT){intldepth,rdepth;if(T==NULL)returnTRUE;if(T->lchild)ldepth=T->lchild->depth;elseldepth=-1;if(T->rchild)rdepth=T->rchild->depth;elserdepth=-1;lrdepth=ldepth–rdepth;if((lrdepth==0||lrdepth==1||lrdepth==-1)

&&(BiTreeBalance(T->lchild)&&BiTreeBalance(T->rchild))returnTRUE;returnFALSE;}?b.?72007考研試題在中序線索二叉樹中，若結(jié)點的左指針lchild不是線索，則該結(jié)點的前驅(qū)結(jié)點應(yīng)是遍歷其左子樹時_____________________;若結(jié)點的右指針rchild不是線索，則該結(jié)點的后繼結(jié)點應(yīng)是遍歷其右子樹時_____________________。最后訪問的一個結(jié)點；最先訪問的一個結(jié)點2007考研試題在中序線索二叉樹中，若結(jié)點的左指針lchi82007考研試題如果兩棵二叉樹的形狀相同，并且相應(yīng)結(jié)點中的數(shù)據(jù)也相同，則這兩棵二叉樹相等。試用二叉鏈表做存貯結(jié)構(gòu)，編寫判斷兩棵二叉樹是否相等的遞歸算法，要求函數(shù)的原型為：intEqualBTree(BiTreeT1,BiTreeT2)。intEqualBTree(BiTreeT1,BiTreeT2){if(!T1&&!T2)return1;if(!T1||!T2)return0;return((T1->data==T2->data)&&EqualBTree(T1->lchild,T2->lchild) &&EqualBTree(T1->rchild,T2->rchild);}??2007考研試題如果兩棵二叉樹的形狀相同，并且相應(yīng)結(jié)點中的數(shù)92008考研試題在5階B-樹中，非終端根結(jié)點至少有___個孩子結(jié)點，除根之外的所有非終端結(jié)點至少有___孩子結(jié)點。

23若一棵二叉樹有126個節(jié)點，在第7層（根結(jié)點在第1層）至多有（）個結(jié)點。A．32 B．64C．63D．不存在第7層C)63對于有1000個結(jié)點的完全二叉樹從0開始編號（從上到下逐層編號，每層從左到右編號），結(jié)點174的雙親結(jié)點編號為_______________，結(jié)點499的右孩子結(jié)點編號為________________________。

(174+1)/2-1=86沒有(2*500+1-1=1000)2008考研試題在5階B-樹中，非終端根結(jié)點至少有___個孩10試編寫先根遍歷樹的遞歸算法PreOrderTree(T,visit),其中T為要遍歷的樹，visit為訪問函數(shù)，樹的存儲結(jié)構(gòu)采用孩子兄弟表示法，其類型定義如下：typedefstructTreeNode{ElementTypedata;structTreeNode*FirstChild;structTreeNode*NextSibling;}TreeNode,*Tree;voidPreOrderTree(TreeT,void(*visit)(ElementType)){if(!T)return;(*visit)(T->data);for(p=T->FirstChild;p;p=p->NextSibling) PreOrderTree(p,visit);}??試編寫先根遍歷樹的遞歸算法PreOrderTree(T,v11樹和二叉樹—2009試題給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4，則其遍歷方式是A．LRN B．NRL C．RLN D．RNLD．RNLC．1113215476已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是A．39 B．52 C．111 D．119樹和二叉樹—2009試題給定二叉樹如下圖所示。設(shè)N代表二12樹和二叉樹—2009試題下列二叉排序樹中，滿足平衡二叉樹定義的是BABCD下列敘述中，不符合m階B樹定義要求的是A．根結(jié)點最多有m棵子樹 B．所有葉結(jié)點都在同一層上C．各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列 D．葉結(jié)點之間通過指針鏈接D樹和二叉樹—2009試題下列二叉排序樹中，滿足平衡二叉樹定義13樹和二叉樹—2009考博試題對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號小于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，實現(xiàn)編號應(yīng)采用的遍歷次序是______。A．先序 B．中序 C．后序 D．都不是設(shè)二叉樹只有度為0和2的結(jié)點，其結(jié)點個數(shù)為21，則該二叉樹的最大深度為________。

A．5 B．6 C．10 D．11A．先序D．11樹和二叉樹—2009考博試題對二叉樹的結(jié)點從1開始進行連續(xù)編14樹和二叉樹—2009考博試題利用哈夫曼算法為報文“abigblackbugbitabigblackbag”設(shè)計一個編碼（注意：包括空格），使該報文的長度最短。要求給出最終的哈夫曼樹，每個字符的哈夫曼編碼，以及報文最終的長度。5*3+7*3+２*４+4*3+3*3+2*4+2*4+5+5+8*2=107a:5 b:7 c:2 g:4 i:3 k:2 l:2 t:1 u:1”:8a:000b:001c:0100g:011i:100k:1010l:1011t:01010u:01011”:11tu2kl4c4i7g8ab12“352015樹和二叉樹—2009考博試題利用哈夫曼算法為報文“abig15圖—2005試題設(shè)圖的鄰接表的類型定義如下。若帶權(quán)圖中邊的權(quán)值類型為整型，請對該鄰接表的類型定義做出適當修改，使之能夠用于表示邊帶權(quán)的圖。#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVnode{VertexTypedata;ArcNode*finrstarc;}Vnode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvexs;intvexnum,arcnum;}ALGraph;typedefstructArcNode{intadjvex;intweight;structArcNode*nextarc;}ArcNode;圖—2005試題設(shè)圖的鄰接表的類型定義如下。若帶權(quán)圖16圖—2006試題算法FindPath是求圖G中頂點v到s的一條路徑PATH（用線性表表示的一個頂點序列）。頂點均用頂點的編號。StatusFindPath(GraphG,intv,ints,List&PATH){visited[v]=TRUE;//標示第v個頂點已被訪問

ListInsert(PATH,ListLength(PATH)+1,v);if(v==s)returnTRUE;for(w=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w))if(____________________) if(FindPath(G,w,s,PATH))returnTRUE;ListDelete(PATH,_________________,e);returnFALSE;}visited[w]==FALSEListLength(PATH)圖—2006試題算法FindPath是求圖G中頂點v到s的一17在求連通網(wǎng)的最小生成樹時，普里姆（Prim）算法適用于___________，克魯斯卡爾（Kruskal）算法適用于____________。拓撲排序可以用來檢查________中是否存在回路。圖—2007試題下列圖的存儲結(jié)構(gòu)中，只能用來表示有向圖的是A.鄰接矩陣 B.鄰接表 C.十字鏈表 D.鄰接多重表有向圖邊稠密的網(wǎng)C.十字鏈表邊稀疏的網(wǎng)在求連通網(wǎng)的最小生成樹時，普里姆（Prim）算法適用18圖—2008試題TopologicalSort是一個利用隊列對圖G進行拓撲排序的算法，請在該算法的空白處填入合適的語句或表達式。提示：數(shù)組InDegree事先已存放每個頂點的入度；數(shù)組TopOrder在算法執(zhí)行后將存放每個頂點在拓撲排序中的順序。intTopologicalSort(GraphG){QueueQ;intCounter=0;intI,V,W;InitQueue(Q);for(I=0;I<G.vexnum;I++)if(InDegree[I]==0)Enqueue(Q,I);while(______________){Dequeue(Q,V);TopOrder[V]=++Counter;for(W=FirstAdjVex(G,V);W!=-1;W=NextAdjVex(G,V,W))if(_________________)Enqueue(Q,W);}DestroyQueue(Q);return(Counter==G.vexnum);}!QueueEmpty(Q)--Indegree[W]==0 圖—2008試題TopologicalSort是一個利用隊列19圖—2009試題下列關(guān)于無向連通圖特性的敘述中，正確的是I．所有頂點的度之和為偶數(shù) II．邊數(shù)大于頂點個數(shù)減1III．至少有一個頂點的度為1A．只有I B．只有II C．I和II D．I和IIIA．只有I圖—2009試題下列關(guān)于無向連通圖特性的敘述中，正確的是A．20圖—2009試題帶權(quán)圖（權(quán)值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假設(shè)從初始頂點到目標頂點之間存在