習(xí)題精練第4和二叉樹(shù)

1、單項(xiàng)選擇題(38 題，共0.0 分) 無(wú)序的數(shù)據(jù)元數(shù)據(jù)間具有層次關(guān)系單項(xiàng)選擇題(38 題，共0.0 分) 無(wú)序的數(shù)據(jù)元數(shù)據(jù)間具有層次關(guān)系的數(shù)數(shù)據(jù)間沒(méi)有關(guān)系的數(shù)【：】2.對(duì)一棵具有n Bn-Cn-【：】3.按照二叉樹(shù)的定義,3個(gè)結(jié)點(diǎn)的二叉樹(shù)有幾種形態(tài)？（不考慮數(shù)據(jù)信息的組合情況【：】 2的結(jié)點(diǎn)（2的二叉樹(shù)4 14.B任何一棵二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為度為2 的結(jié)點(diǎn)數(shù)減1C二叉樹(shù)不適合用順序結(jié)的二叉樹(shù)，第i 個(gè)結(jié)點(diǎn)的左孩子（如果存在）的試【】A B 21；選項(xiàng)C D 5.設(shè)二叉樹(shù)中有n22n11n00試【】110226.78 1試【】110226.78 17 26 3 54 45 3 62 7 【：】

2、n0 1 7+26+35+44+53+62=78（ni i 的結(jié)點(diǎn)數(shù)目m N0個(gè)葉子結(jié)點(diǎn)數(shù)，N11的結(jié)點(diǎn)，N22m 的結(jié)點(diǎn)，則有：N0=1+N2+2N3+(m-1)Nm7.有n（n0）：8.若某完全二叉樹(shù)的深度為h：9.7 10正試【】：9.7 10正試【】727-1=64 10 548108 10.244：11.510的二叉樹(shù)，數(shù)組的長(zhǎng)度至少為：12.n 【：】n 2n n1 n1 13.T n 個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū) 【：】n 2n n1 n1 13.T n 個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū) ，求每個(gè)結(jié)點(diǎn)的 大于其左右孩子的C后序遍歷序D層次遍：】對(duì)照后序遍歷的先后關(guān)系（左右子樹(shù)的大小關(guān)系，雙親

3、和孩子結(jié)點(diǎn)的相對(duì)關(guān)系【該C其分支結(jié)點(diǎn)無(wú)右子D其分支結(jié)點(diǎn)的度都為 【：】 A、B、C 試】【B其中任一結(jié)點(diǎn)無(wú)左孩右子樹(shù)為其中任一結(jié)點(diǎn)無(wú)右孩：】【不會(huì)發(fā)生改右子樹(shù)為其中任一結(jié)點(diǎn)無(wú)右孩：】【不會(huì)發(fā)生改【：】（LDR（LRD正試結(jié)構(gòu)，結(jié)點(diǎn)數(shù)據(jù)信息的存放順序依次為 A、B、C、D、E、F、G、H、I、J，】【正試】【（任何一個(gè)二叉樹(shù)/子樹(shù)的先序序列中第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)試【】 中序遍歷也可分為 3 個(gè)部分：左子樹(shù)部分、根結(jié)點(diǎn)、右試【】 中序遍歷也可分為 3 個(gè)部分：左子樹(shù)部分、根結(jié)點(diǎn)、右子樹(shù)部分。題目給出的先序序列為 ABDCE，可知 A 為根結(jié)點(diǎn)，選項(xiàng)A 給出中序序列表示BD 是左子樹(shù)部分，EC 是右子

4、樹(shù)部分，和先序序列不 ，是可能的中序序列。選B BC 是左子樹(shù)，DE ABDCE C D 21.n 【：】線(xiàn)索二叉樹(shù)是利用二叉樹(shù)的空鏈域加上線(xiàn)索，n n1 右孩雙前驅(qū)和后【：】【：】當(dāng)指定結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，若指定結(jié)點(diǎn)是“某結(jié)點(diǎn) X”的左子樹(shù)中按先序遍歷列出的最后一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn) X X 沒(méi)有右孩子，則指定結(jié)點(diǎn)沒(méi)有先序后繼當(dāng)指定結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，若指定結(jié)點(diǎn)不是任何結(jié)點(diǎn)的左子樹(shù)中按先序遍歷列出的最后一個(gè)結(jié)點(diǎn)，則指定結(jié)試【】D 25.k 叉樹(shù)，其分支結(jié)點(diǎn)數(shù)目為nBn-Dn（k-：試【】D 25.k 叉樹(shù)，其分支結(jié)點(diǎn)數(shù)目為nBn-Dn（k-：】【的右指針域?yàn)榭眨礋o(wú)右孩子n 27.X 是樹(shù)T 中的一

5、個(gè)非根結(jié)點(diǎn)，B T 所對(duì)應(yīng)的二叉樹(shù)。在B 中，X 在樹(shù)T 中，X 在樹(shù)T 中，X 一定有右邊兄弟 CT 中，X 一定是葉子結(jié)點(diǎn) D在樹(shù)T 中，X 【：】樹(shù)轉(zhuǎn)化為二叉樹(shù)的過(guò)程中，若X X 正試】【h，對(duì)應(yīng)由h 29.h，對(duì)應(yīng)由h 29.C樹(shù)的先序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相D以上都不【：】B、C、D 中后按層【：】31.二叉樹(shù)為二叉排序樹(shù)的（）條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子D既不充分也不必【：】值（當(dāng)然也小于其右孩子的值。所以，該題的選項(xiàng)中至少應(yīng)該包含必要條件，A、D 并非一個(gè)單增或單減得序列。所以正B（20，35，正試30【】352030 33.AA（20，3

6、5，正試30【】352030 33.AA 的左孩子的平衡因子為-【：】B樹(shù)D二叉排序【：】A對(duì)應(yīng)一組權(quán)值構(gòu)造出【1 的結(jié)點(diǎn)12：】A9：】【1 的分支結(jié)點(diǎn)。n n-1 n-1 樹(shù)2n-1 A9：】【1 的分支結(jié)點(diǎn)。n n-1 n-1 樹(shù)2n-1 【：】B 1010138.5個(gè)字符，根據(jù)其使用頻率設(shè)計(jì)對(duì)應(yīng)的正試】【編碼的概念和性質(zhì)。按左分支編碼為 0，右分支編碼為 1，A、B、CD D 1D 簡(jiǎn)答題(120.0 分39.n 個(gè)結(jié)點(diǎn)并且其高度為n 的二叉樹(shù)的數(shù)目是多少?簡(jiǎn)答題(120.0 分39.n 個(gè)結(jié)點(diǎn)并且其高度為n 的二叉樹(shù)的數(shù)目是多少?：n n n 2n-1 j=1，2，3 M,N i，j

7、 N M n m ：-“左根右”-N 是M N 在M N M 的右孩子，N M P M 和N 的最近公共祖先，N P 的左子樹(shù)中，M P N 在M ：C JudgeComplete(BiTreebt)：C JudgeComplete(BiTreebt)BiTreep=bt,QQ if (p= =NULL) return 1; InitQueueQ)初始化隊(duì)列while(!QueueEmpty(Q p=DeQueue (Q); /出隊(duì)ifp-lchild&flagEnQueueQ,p-lchild左孩子入elseif(p-lchild)return0; else flag=1;if(p-rchi

8、ld&flagEnQueueQ,p-rchild右孩子入隊(duì) else if (p-rchild) return 0;elsereturn：編寫(xiě)計(jì)算整個(gè)二叉樹(shù)高度的算法（二叉樹(shù)的高度也叫二叉樹(shù)的深度h h+1層，則可以通過(guò)遍歷計(jì)算二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的層次，其中最大值即為二叉bt 的高度，則遞歸定義如下:bt 0bt 1：（1）二叉樹(shù)的高度(深度)為二叉樹(shù)中結(jié)點(diǎn)層次的最大值，即結(jié)點(diǎn)的層次自根結(jié)點(diǎn)起遞推。設(shè)根結(jié)點(diǎn)為第 1（1）二叉樹(shù)的高度(深度)為二叉樹(shù)中結(jié)點(diǎn)層次的最大值，即結(jié)點(diǎn)的層次自根結(jié)點(diǎn)起遞推。設(shè)根結(jié)點(diǎn)為第 1bt 的高度，則遞歸定義如下:bt 0bt 1（1）bt 的深度算法。C 語(yǔ)言算法描

9、述如下：Height(BiTreebt) if(bt=NULL)return0; else if(hlhr)return(hl+1); else return(hr+1);（2）求二叉樹(shù)bt 的最大寬度算法。C 語(yǔ)言算法描述如下：Width(BiTreebtbt 的最大寬度 if (bt= =NULL) return 0; /空二叉樹(shù)寬度為0 else BiTreeQQ 是隊(duì)列，元素為二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大 front=1;rear=1; / front 指向隊(duì)頭元素,rear 指向隊(duì)尾元素 Qrear=bt; /根結(jié)點(diǎn)入隊(duì)列l(wèi)ast=1last temp=0;maxw=0; /temp

10、記局部寬度maxwwhile(frontlchild!=NULLQ+rear=p-lchild左孩子入隊(duì) if(p-rchild!=NULLQ+rear=p-rchild右孩子入隊(duì) if (frontlast) /一層結(jié)束if(tempmaxw) maxw=temp; /last 指向下層最右元素, return進(jìn)行遍歷，與二叉鏈表類(lèi)似。在順結(jié)構(gòu)下，判二叉樹(shù)為空時(shí)，用結(jié)點(diǎn)下標(biāo)大于n（完全二叉樹(shù)）或0（對(duì)：C voidPreOrder(ElemType歷n) /的完全二叉樹(shù)bt top=0,s/top s while(i0) while (i=n)f(bti);if(2*i+10i=stop結(jié)構(gòu)

11、，結(jié)點(diǎn)結(jié)構(gòu)為(lchild, data,rchild)：C voidexchange(BiTreebt將二叉樹(shù)所有結(jié)點(diǎn)的左右子樹(shù)交換的遞歸算法 if (bt)BiTree s； bt-rchild=s; /左右孩子交exchange(bt-lchild)交換左子樹(shù)上所有結(jié)點(diǎn)的左右子樹(shù) exchange(bt-rchild)：C /in t(ElemTypel1,h1,l2,h2)t 是二叉樹(shù)的中序和后序序列,l1,h1,l2,h2 ; /th2; /后序遍歷序列最后一個(gè)元素是根結(jié)點(diǎn)數(shù)foifth2)break; /在中序序列中查找根結(jié)if(il1bt-lchild=NULL; /elsebt-

12、t if(ih1bt-rchild=NULLelse bt-rchild=46.h 的二叉樹(shù)以一維數(shù)組BT(1:2h-1)elsebt-t if(ih1bt-rchild=NULLelse bt-rchild=46.h 的二叉樹(shù)以一維數(shù)組BT(1:2h-1)0：中對(duì)葉子結(jié)點(diǎn)的判定是根據(jù)其左為0。葉子和雙親結(jié)點(diǎn)下標(biāo)間的關(guān)系滿(mǎn)足完全C h)h len=2h-1,count=0; /BT ( if (BTi!=0) /假定二叉樹(shù)結(jié)點(diǎn)值是整數(shù)虛結(jié)點(diǎn)”用0 填if(i*2)len) count+; /i elseif(BT2*i=0&2*i+1lchild）if(bt-lchild=NULL&bt-rc

13、hild=NULL葉子結(jié)點(diǎn) if (head=NULL) /第一個(gè)葉子結(jié)點(diǎn) head=(BiTree)malloc(sizeof(BiNode); /生成頭結(jié)點(diǎn)head-lchild=NULL; /頭結(jié)點(diǎn)的左鏈為head-rchild=bt;頭結(jié)點(diǎn)的右鏈指向第一個(gè)葉子結(jié)點(diǎn) bt-lchild=head; /第一個(gè)葉子結(jié)點(diǎn)左鏈指向頭結(jié)點(diǎn) pre=bt; /pre 指向當(dāng)前葉子結(jié)點(diǎn)elsepre-rchild=bt當(dāng)前葉子結(jié)點(diǎn)鏈入雙鏈表 eafList(bt-rchild) /48.bt 采用二叉鏈表：C eafList(bt-rchild) /48.bt 采用二叉鏈表：C voidMax(BiTreebt) if(bt=NULL)returnif(bt-lchild=NULL&bt-rchild=NULL) return bt-data;elsem=Max(bt-lchild求左子樹(shù)中的最大值 n=Max(bt-rchild); /求右子樹(shù)中的最大值ifmbt-data)returnm; else return bt-data;：C KeyTypepredt=0/pr