數(shù)據(jù)結(jié)構(gòu)第六章習(xí)題課

./1、下圖所示的4棵二叉樹中,不是完全二叉樹的是〔AABCD2、二叉樹的前序遍歷序列中,任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說法〔。A、正確 B、錯誤 C、不一定3、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是〔。A、acbed B、decab C、deabc D、cedba4、如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹,那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的〔。A、前序B、中序 C、后序 D、層次序5、深度為5的二叉樹至多有〔個結(jié)點(diǎn)。A、16 B、32 C、31 D、106、在一個非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊〔。A、只有右子樹上的所有結(jié)點(diǎn) B、只有右子樹上的部分結(jié)點(diǎn)C、只有左子樹上的部分結(jié)點(diǎn) D、只有左子樹上的所有結(jié)點(diǎn)7、樹最適合用來表示〔。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)。8、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序〔。A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對9、實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu),最佳方案是二叉樹采用〔存儲結(jié)構(gòu)。A、二叉鏈表B、廣義表存儲結(jié)構(gòu)C、三叉鏈表D、順序存儲結(jié)構(gòu)10、對一個滿二叉樹,m個樹葉,n個結(jié)點(diǎn),深度為h,則〔。A、n=m+hB、h+m=2nC、m=h-1D、n=2h-111、設(shè)n,m為二叉樹上的兩個結(jié)點(diǎn),在中序遍歷時,n在m前的條件是〔。A、n在m右方B、n是m祖先C、n在m左方D、n是m子12．已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為<>A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DEABAB+C*EFDG+*-/13.設(shè)有一表示算術(shù)表達(dá)式的二叉樹〔見右圖,它所表示的算術(shù)表達(dá)式是〔A.A*B+C/<D*E>+<F-G>B.<A*B+C>/<D*E>+<F-G>C.<A*B+C>/<D*E+〔F-G>D.A*B+C/D*E+F-G14.在下述結(jié)論中,正確的是〔①只有一個結(jié)點(diǎn)的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹。A．①②③B．②③④C．②④D．①④15.設(shè)森林F對應(yīng)的二叉樹為B,它有m個結(jié)點(diǎn),B的根為p,p的右子樹結(jié)點(diǎn)個數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個數(shù)是〔A．m-nB．m-n-1C．n+1D．條件不足,無法確定16．若一棵二叉樹具有10個度為2的結(jié)點(diǎn),5個度為1的結(jié)點(diǎn),則度為0的結(jié)點(diǎn)個數(shù)是〔A．9B．11C．15D．不確定17．一棵完全二叉樹上有1001個結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個數(shù)是〔A．250B．500C．254D．505E．以上答案都不對18.一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為〔A．11B．10C．11至1025之間D．10至1024之間19．深度為h的滿m叉樹的第k層有〔個結(jié)點(diǎn)。<1=<k=<h>A．mk-1B．mk-1C．mh-1D．mh-120.利用二叉鏈表存儲樹,則根結(jié)點(diǎn)的右指針是〔。A．指向最左孩子B．指向最右孩子C．空D．非空21．對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號,要求每個結(jié)點(diǎn)的編號大于其左、右孩子的編號,同一結(jié)點(diǎn)的左右孩子中,其左孩子的編號小于其右孩子的編號,可采用<>次序的遍歷實(shí)現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷22．若二叉樹采用二叉鏈表存儲結(jié)構(gòu),要交換其所有分支結(jié)點(diǎn)左、右子樹的位置,利用<>遍歷方法最合適。A．前序B．中序C．后序D．按層次23．一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反,則該二叉樹一定滿足〔A．所有的結(jié)點(diǎn)均無左孩子B．所有的結(jié)點(diǎn)均無右孩子C．只有一個葉子結(jié)點(diǎn)D．是任意一棵二叉樹24.若X是二叉中序線索樹中一個有左孩子的結(jié)點(diǎn),且X不為根,則x的前驅(qū)為<>A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)25.線索二叉樹是一種〔結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性26．n個結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為〔A．2nB．n－lC．n＋lD．n27．下面幾個符號串編碼集合中,不是前綴編碼的是〔。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}28.當(dāng)一棵有n個結(jié)點(diǎn)的二叉樹按層次從上到下,同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[l..n]中時,數(shù)組中第i個結(jié)點(diǎn)的左孩子為〔A．A[2i]<2i=<n>B.A[2i+1]<2i+1=<n>C．A[i/2]D．無法確定29、高度為h的完全二叉樹至少有多少個結(jié)點(diǎn)?至多有多少個結(jié)點(diǎn)?解：高度為h的完全二叉樹至少有2h-1個結(jié)點(diǎn),至多有2h-1個結(jié)點(diǎn)<也就是滿二叉樹>。30、在什么樣的情況下,等長編碼是最優(yōu)的前綴碼?答：在每個字符的使用概率相同的情況下,也即在哈夫曼樹中每片葉子的權(quán)重相等的時候,等長編碼是最優(yōu)的前綴碼。31.假設(shè)在樹中,結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時,用<x,y>來表示樹邊。已知一棵樹邊的集合為{<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>}用圖表示出此樹,并回答下列問題：<1>哪個是根結(jié)點(diǎn)?<2>哪些是葉結(jié)點(diǎn)?<3>哪個是g的雙親?<4>哪些是g的祖先?<5>哪些是g的孩子?<6>哪些是e的子?<7>哪些是e的兄弟?哪些是f的兄弟?<8>結(jié)點(diǎn)b和n的層次各是多少?<9>樹的深度是多少?<10>以結(jié)點(diǎn)c為根的子樹的深度是多少?<11>樹的度數(shù)是多少?答：這是測試我們對樹的基本概念的掌握情況。a是根結(jié)點(diǎn)；mndfjkl是葉結(jié)點(diǎn)；c是g的雙親；c,a是g的祖先；j,k是g的孩子；imn是e的子；d是e的兄弟,g,h是f的兄弟；b的層次是2,n的層次是5；樹的深度是5；以c為根的子樹深度是3；樹的度數(shù)是3。32、試找出分別滿足下面條件的所有二叉樹：<1>前序序列和中序序列相同；<2>中序序列和后序序列相同；<3>前序序列和后序序列相同；<4>前序、中序、后序序列均相同。答：<1>前序序列和中序序列相同的二叉樹是：沒有左子樹的二叉樹<右單支樹>。<2>中序序列和后序序列相同的二叉樹是：沒有右子樹的二叉樹<左單支樹>。<3>前序序列和后序序列相同的二叉樹是：只有根結(jié)點(diǎn)的二叉樹。<4>前序、中序、后序序列均相同的二叉樹：只有根結(jié)點(diǎn)的二叉樹。33、對二叉樹中的結(jié)點(diǎn)進(jìn)行按層次順序<每一層自左至右>的訪問操作稱為二叉樹的層次遍歷,遍歷所得到的結(jié)點(diǎn)序列稱為二叉樹層次序列?，F(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ,中序序列為DBGEHJACIF,請畫出此二叉樹。解：A

/\BC/\\

DEF/\

/GHI\

J34、對下圖所示的森林：<1>求各樹的前序序列和后序序列；<2>求森林的前序序列和后序序列；<3>將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；<4>給出<a>所示樹的以雙親鏈表表示、孩子鏈表表示、雙親孩子鏈表表示及孩子兄弟鏈表表示等四種存儲結(jié)構(gòu),并指出哪些存儲結(jié)構(gòu)易于求指定結(jié)點(diǎn)的祖先,哪些易于求指定結(jié)點(diǎn)的后代?解：<1>

<a>的前序序列：ABCDEF

后序序列：BDEFCA

<b>的前序序列：GHIJK

后序序列：IJKHG

<c>的前序序列：LMPQRNO

后序序列：QRPMNOL<2>

此森林的前序序列：ABCDEFGHIJKLMPQRNO此森林的后序序列：BDEFCAIJKHGQRPMNOL略略35．完全二叉樹中,結(jié)點(diǎn)個數(shù)為n,則編號最大的分支結(jié)點(diǎn)的編號為。答：n/236．二叉樹結(jié)點(diǎn)的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結(jié)點(diǎn)的前序序列為<1>,則該二叉樹對應(yīng)的樹林包括<2>棵樹。答：<1>EACBDGF〔2237．具有n個結(jié)點(diǎn)的滿二叉樹,其葉結(jié)點(diǎn)的個數(shù)是______。答：<n+1>/2設(shè)部節(jié)點(diǎn)數(shù)為a,葉節(jié)點(diǎn)數(shù)為b,明顯有a+b=n<1>,非空滿二叉樹中所有節(jié)點(diǎn)的出度正好等于入度,每個部節(jié)點(diǎn)出度為2,葉節(jié)點(diǎn)出度為0,所有節(jié)點(diǎn)的出度和為2a；根節(jié)點(diǎn)入度為0,其他節(jié)點(diǎn)的入度為1,所有節(jié)點(diǎn)的入度和為a+b-1;因此有2a=a+b-1<2>。由<1><2>得b=<n+1>/2,a=<n-1>/2。另外可得b=a+1,也就是說,非空滿二叉樹的葉節(jié)點(diǎn)數(shù)正好比部節(jié)點(diǎn)數(shù)多1。38．設(shè)一棵后序線索樹的高是50,結(jié)點(diǎn)x是樹中的一個結(jié)點(diǎn),其雙親是結(jié)點(diǎn)y,y的右子樹高度是31,x是y的左孩子。則確定x的后繼最多需經(jīng)過______中間結(jié)點(diǎn)〔不含后繼及x本身答：31〔x的后繼是經(jīng)x的雙親y的右子樹中最左下的葉結(jié)點(diǎn)39．有一份電文中共使用6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9,試構(gòu)造一棵哈夫曼樹,則其加權(quán)路徑長度WPL為<1>,字符c的編碼是<2>。答：<1>80<2>001〔不唯一40．下面是求二叉樹高度的類C寫的遞歸算法,試補(bǔ)充完整。[說明]二叉樹的兩指針域?yàn)閘child與rchild,算法中p為二叉樹的根,lh和rh分別為以p為根的二叉樹的左子樹和右子樹的高,hi為以p為根的二叉樹的高,hi最后返回。height<p>{if<<1>>{if<p->lchild==null>lh=<2>;elselh=<3>;if<p->rchild==null>rh=<4>;elserh=<5>;if<lh>rh>hi=<6>；elsehi=<7>;}elsehi=<8>;returnhi;}//答：<1>p<2>0<3>height<p->lchild><4>0<5>height<p->rchild><6>lh+1<7>rh+1<8>041．已知一棵滿二叉樹的結(jié)點(diǎn)個數(shù)為20到40之間的素?cái)?shù),此二叉樹的葉子結(jié)點(diǎn)有多少個？答：結(jié)點(diǎn)個數(shù)在20到40的滿二叉樹且結(jié)點(diǎn)數(shù)是素?cái)?shù)的數(shù)是31,其葉子數(shù)是16。42．用一維數(shù)組存放的一棵完全二叉樹；ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點(diǎn)序列。答：HIDJKEBLFGCA43．一棵左右子樹均不空的二叉樹在先序線索化后,其空指針域數(shù)為多少？答：左右子樹均不空的二叉樹先序線索化后,空指針域?yàn)?個〔最后訪問結(jié)點(diǎn)的右鏈為空。44．設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計(jì)一套二進(jìn)制編碼,使得上述正文的編碼最短。45．編程求以孩子—兄弟表示法存儲的森林的葉子結(jié)點(diǎn)數(shù)。要求描述結(jié)構(gòu)。[題目分析]當(dāng)森林〔樹以孩子兄弟表示法存儲時,若結(jié)點(diǎn)沒有孩子〔firstchild=null,則它必是葉子,總的葉子結(jié)點(diǎn)個數(shù)是孩子子樹〔firstchild上的葉子數(shù)和兄弟〔nextsibling子樹上葉結(jié)點(diǎn)個數(shù)之和。typedefstructnode{ElemTypedata;//數(shù)據(jù)域structnode*firstchild,*nextsibling;//孩子與兄弟域}*Tree;intLeaves<Treet>//計(jì)算以孩子-兄弟表示法存儲的森林的葉子數(shù){if<t>if<t->firstchild==null>//若結(jié)點(diǎn)無孩子,則該結(jié)點(diǎn)必是葉子return<1+Leaves<t->nextsibling>>;//返回葉子結(jié)點(diǎn)和其兄弟子樹中的葉子結(jié)點(diǎn)數(shù)elsereturn<Leaves<t->firstchild>+Leaves<t->nextsibling>>;//孩子子樹和兄弟子樹中葉子數(shù)之和}//結(jié)束Leaves46．有n個結(jié)點(diǎn)的完全二叉樹存放在一維數(shù)組A[1..n]中,試據(jù)此建立一棵用二叉鏈表表示的二叉樹,根由tree指向。BiTreeCreat<ElemTypeA[],inti>//n個結(jié)點(diǎn)的完全二叉樹存于一維數(shù)組A中,本算法據(jù)此建立以二叉鏈表表示的完全二叉樹{BiTreetree;if<i<=n>{tree=<BiTree>malloc<sizeof<BiNode>>;tree->data=A[i];if<2*i>n>tree->lchild=null；elsetree->lchild=Creat<A,2*i>；if<2*i+1>n>tree->rchild=null；elsetree->rchild=Creat<A,2*i+1>；}return<tree>；}//Creat[算法討論]初始調(diào)用時,i=1。47.以孩子兄弟鏈表為存儲結(jié)構(gòu),請?jiān)O(shè)計(jì)算法求樹/森林的深度。[題目分析]由孩子兄弟鏈表表示的樹,求高度的遞歸模型是：若樹為空,高度為零；若第一子女為空,高度為1和兄弟子樹的高度的大者；否則,高度為第一子女樹高度加1和兄弟子樹高度的大者。其非遞歸算法使用隊(duì)列,逐層遍歷樹,取得樹的高度。intTreeDepth<CSTreeT>{if<!T>return0;else{h1=TreeDepth<T->firstchild>;h2=TreeDepth<T->nextsibling>;return<max<h1+1,h2>>;}}//TreeDepth48.設(shè)計(jì)算法返回二叉樹T的先序序列的最后一個結(jié)點(diǎn)的指針,要求采用非遞歸形式,且不許用棧。[題目分析]二叉樹先序序列的最后一個結(jié)點(diǎn),若二叉樹有右子樹,則是右子樹中最右下的葉子結(jié)點(diǎn)；若無右子樹,僅有左子樹,則是左子樹最右下的葉子結(jié)點(diǎn)；若二叉樹無左右子樹,則返回根結(jié)點(diǎn)。BiTreeLastNode<BiTreebt>//返回二叉樹bt先序序列的最后一個結(jié)點(diǎn)的指針{BiTreep=bt;if<bt==null>return<null>;elsewhile<p>if<p->rchild>p=p->rchild;//若右子樹不空,沿右子樹向下elseif<p->lchild>p=p->lchild;//右子樹空,左子樹不空,沿左子樹向下elsereturn<p>;//左右子樹均為空,p即為所求}//lastnode49.設(shè)一棵二叉樹的根結(jié)點(diǎn)指針為T,C為計(jì)數(shù)變量,初值為0,試寫出對此二叉樹中結(jié)點(diǎn)計(jì)數(shù)的算法：BTLC〔T,C。intBTLC<BiTreeT,int*c>//對二叉樹T的結(jié)點(diǎn)計(jì)數(shù){if<T>{*c++;//調(diào)用時*c=0BTLC<T->lchild,&c>;//統(tǒng)計(jì)左子樹結(jié)點(diǎn)BTLC<T->rchild,&c>;//統(tǒng)計(jì)右子樹結(jié)點(diǎn)}}//50．設(shè)計(jì)算法：統(tǒng)計(jì)一棵二叉樹中所有葉結(jié)點(diǎn)的數(shù)目及非葉結(jié)點(diǎn)的數(shù)目。voidCount<BiTreebt,int*n0,*n>//統(tǒng)計(jì)二叉樹bt上葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n{if<bt>{if<bt->lchild==null&&bt->rchild==null>*n0++；//葉子結(jié)點(diǎn)else*n++;//非葉結(jié)點(diǎn)Count<bt->lchild,&n0,&n>;Count<bt->rchild,&n0,&n>;}}//Count51、編寫算法完成下列操作：無重復(fù)地輸出以孩子兄弟鏈表存儲的樹T中的所有的邊。輸出形式為〔k1,k2……〔ki,kj……,其中ki和kj為樹結(jié)點(diǎn)中的結(jié)點(diǎn)標(biāo)識。VoidOutEdger<CSTreeT>//先根遍歷輸出樹中各條邊{if<T>{p=T->firstchild;while<p>{printf<T->data,p->data>;OutEdger<p>;p=p->nextsibling;}}}//52、已知L[i]和R[i]〔i=1,2,……,n分別指示二叉樹中第i個結(jié)點(diǎn)的左孩子和右孩子結(jié)點(diǎn),0表示空,試寫出判別結(jié)點(diǎn)u是否是結(jié)點(diǎn)v的子的算法。statusdescendent<intL[],intR[],intu,intv>{if<u&&v>{if<L[v]==u||R[v]==u>returnTRUE;elseif<descendent<L,R,u,L[v]>>returnTRUE;elsereturn<descendent<L,R,u,R[v]>>;}elsereturnFALSE;}//53.設(shè)一棵二叉樹以二叉鏈表為存貯結(jié)構(gòu),結(jié)點(diǎn)結(jié)構(gòu)為<lchild,data,rchild>,設(shè)計(jì)一個算法將二叉樹中所有結(jié)點(diǎn)的左,右子樹相互交換。類似本題的另外敘述有：〔1設(shè)t為一棵二叉樹的根結(jié)點(diǎn)地址指針,試設(shè)計(jì)一個非遞歸的算法完成把二叉樹中每個結(jié)點(diǎn)的左右孩子位置交換?！?寫一個將二叉樹中每個結(jié)點(diǎn)的左右孩子交換的算法。voidexchange<BiTreebt>//將二叉樹bt所有結(jié)點(diǎn)的左右子樹交換{if<bt>{BiTrees；s=bt->lchild;bt->lchild=bt->rchild;bt->rchild=s;//左右子女交換exchange<bt->lchild>;//交換左子樹上所有結(jié)點(diǎn)的左右子樹exchange<bt->rchild>;//交換右子樹上所有結(jié)點(diǎn)的左右子樹}}[算法討論]將上述算法中兩個遞歸調(diào)用語句放在前面,將交換語句放在最后,則是以后序遍歷方式交換所有結(jié)點(diǎn)的左右子樹。中序遍歷不適合本題。下面是本題〔1要求的非遞歸算法voidexchange<BiTreet>//交換二叉樹中各結(jié)點(diǎn)的左右孩子的非遞歸算法{inttop=0;BiTrees[],p;//s是二叉樹的結(jié)點(diǎn)指針的棧,容量足夠大if<bt>{s[++top]=t;while<top>0>{t=s[top--];if<t->lchild||t->rchild>{p=t->lchild;t->lchild=t->rchild;t->rchild=p;}//交換左右if<t->lchild>s[++top]=t->lchild;//左子女入棧if<t->rchild>s[++top]=t->rchild;//右子女入棧}//while<top>0>}//if<bt>}//exchange54．要求二叉樹按二叉鏈表形式存儲,〔1寫一個建立二叉樹的算法?！?寫一個判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為K,具有N個結(jié)點(diǎn)的二叉樹的每個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至N的結(jié)點(diǎn)一一對應(yīng)。此題以此定義為準(zhǔn)。[題目分析]二叉樹是遞歸定