數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)(6樹習(xí)題)

1、2022-7-41數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)(習(xí)題)22022-7-4第六章 樹和二叉樹(選擇題)1已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE2算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ ）Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+32022-7-43. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）A5 B6 C7 D84. 在下述結(jié)論中，正確的是（ ）只有一個(gè)結(jié)點(diǎn)

2、的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換; 深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。 A B C D因?yàn)槊總€(gè)結(jié)點(diǎn)都有一條枝指向它，分支數(shù)為1*4+2*2*3*1+4*1所有結(jié)點(diǎn)數(shù)為分支數(shù)+1，所以1*4+2*2*3*1+4*1=4+2+1+1+x x=842022-7-46若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定7. 設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定8

3、設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M3 森林轉(zhuǎn)換得到的二叉樹中，其左子樹加根為森林的第一棵樹52022-7-49一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）A 250 B 500 C254 D50110. 設(shè)給定權(quán)值總數(shù)有n 個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為( ) A不確定 B2n C2n+1 D2n-1完全二叉樹中度為1的結(jié)點(diǎn)最多只有1個(gè)，由二叉樹的度和結(jié)點(diǎn)的關(guān)系n=n0+n1+n2 n=n1+2n2+1 得n=2n0+n1-1哈夫曼樹中沒有度為1的

4、節(jié)點(diǎn)，葉子節(jié)點(diǎn)個(gè)數(shù)為n62022-7-411. 有關(guān)二叉樹下列說法正確的是（ ）A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為212. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）A11 B10 C11至1025之間 D10至1024之間13一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有( )結(jié)點(diǎn)A2h B2h-1 C2h+1 Dh+1 完全二叉樹和單枝樹之間72022-7-414對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為（ ）Anlog2n Blog2n Clog2n|+1 D不確定15. 一棵具有 n個(gè)結(jié)點(diǎn)的完全

5、二叉樹的樹高度（深度）是（ ）Alogn+1 Blogn+1 Clogn Dlogn-1 16深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=k=lchild=null & p-rchlid=null 12202022-7-44在完全二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是5在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是 。6一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有_ _個(gè)度為1的結(jié)點(diǎn)、有_ _個(gè)分支 （非 終端）結(jié)點(diǎn)和_ _個(gè)葉子，該滿二叉樹的深度為_ _ 。 log2i=log2j log2s=log2t 用順序存儲(chǔ)二叉樹時(shí)，要按完全二叉樹的形式存儲(chǔ)，非完全二叉樹存儲(chǔ)時(shí)，要加“

6、虛結(jié)點(diǎn)”。設(shè)編號(hào)為i和j的結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)為s 和t ,則結(jié)點(diǎn)i和j在同一層上的條件是log2s=log2t。0(n-1)/2(n+1)/2log2n+1212022-7-47設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在向量A1:N中，其下標(biāo)值最大的分支結(jié)點(diǎn)為_。8高度為K的完全二叉樹至少有_ _個(gè)葉子結(jié)點(diǎn)。 9已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是_。10一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹的高度為_。11如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是_。 N/22k-299114222022-7-412設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對(duì)應(yīng)的二叉樹為B,已知T1,

7、T2,T3的結(jié)點(diǎn)數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有_ _個(gè)結(jié)點(diǎn)，右子樹中有_ _個(gè)結(jié)點(diǎn)13對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的二元樹，當(dāng)它為一棵_ _二元樹時(shí)具有最小高度，當(dāng)它為一棵_ _ 時(shí)，具有最大高度。 14含4個(gè)度為2的結(jié)點(diǎn)和5個(gè)葉子結(jié)點(diǎn)的二叉樹，可有_ _個(gè)度為1的結(jié)點(diǎn)。n1-1n2+n3完全二叉樹 單枝樹 0至多個(gè) 任意二叉樹，度為的結(jié)點(diǎn)個(gè)數(shù)沒限制。只有完全二叉樹，度為的結(jié)點(diǎn)個(gè)數(shù)才至多為1。232022-7-415利用樹的孩子兄弟表示法存儲(chǔ)，可以將一棵樹轉(zhuǎn)換為_ _ 16有一份電文中共使用 6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼

8、樹，則其加權(quán)路徑長(zhǎng)度WPL為_ _，字符c的編碼是_ _。17將二叉樹bt中每一個(gè)結(jié)點(diǎn)的左右子樹互換的C語言算法如下，其中 ADDQ(Q,bt), DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?zhí)顚懰惴ㄖ械每瞻滋?，完成其功能?80二叉樹001242022-7-4typedef struct node int data ; struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q; if (bt)ADDQ(Q,bt); while(!EMPTY(Q) p=DELQ(Q)

9、; q= _ _; p-rchild=(2)_ _ (3)_ _=q; if(p-lchild) (4)_ _; if(p-rchild) (5) _; / p-rchild p-lchild p-lchild ADDQ(Q,p-lchild) ADDQ(Q,p-rchild) 252022-7-418設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2;只有非空左兒子的個(gè)數(shù)NL;只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typedef struct nod

10、eint data; struct node *lchild,*rchild;node;int N2,NL,NR,N0;void count(node *t) if (t-lchild!=NULL) if (1)_ _ N2+; else NL+;else if (2)_ _ NR+; else (3) _ ;if(t-lchild!=NULL)(4)_ _ _; if (t-rchild!=NULL) (5)_ _; t-rchild!=null t-rchild!=null N0+ count(t-lchild)count(t-rchild)262022-7-419下面是求二叉樹高度的類C

11、寫的遞歸算法試補(bǔ)充完整 說明 二叉樹的兩指針域?yàn)閘child與rchild, 算法中p為二叉樹的根，lh和rh分別為以p為根的二叉樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最后返回。height(p)if (1)_ _) if(p-lchild=null) lh=(2)_; else lh=(3)_ _; if(p-rchild=null) rh=(4)_; else rh=(5)_ _; if (lhrh) hi=(6) _；else hi=(7)_; else hi=(8)_; return hi;/ p!=null0height(p-lchild)0height(p-rch

12、ild)lh+1rh+10272022-7-420下列是先序遍歷二叉樹的非遞歸子程序，請(qǐng)閱讀子程序填充空格，使其成為完整的算法。void example(b) btree *b; btree *stack20, *p； int top; if (b!=null) top=1; stacktop=b; while (top0) p=stacktop; top-; printf(“%d”,p-data); if (p-rchild!=null)(1)_ _; (2)_ _; if (p-lchild!=null) (3)_ ; (4) _; top+stacktop=p-rchildtop+sta

13、cktop=p-lchild282022-7-4第六章 樹和二叉樹(應(yīng)用題)1按下面要求解下圖中二叉樹的有關(guān)問題： (1)對(duì)此二叉樹進(jìn)行后序后繼線索化 ；(2)將此二叉樹變換為森林；(3)用后根序遍歷該森林，；寫出遍歷后的結(jié)點(diǎn)序列。 LJGIABEFKCDHMONP292022-7-4ABECFDKIGLJHMONP后續(xù)遍歷二叉樹: DCBIJHGFLPONMKEA302022-7-4MKLNPOIGEFHJCABD后續(xù)遍歷森林:BDCAIFJGHELOPMNK312022-7-42設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的編碼最短

14、。字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。其哈夫曼編碼如下A:0，B:100，C:11，D:101 322022-7-4第六章 樹和二叉樹(算法題)1二叉樹采用二叉鏈表存儲(chǔ)：（1）編寫計(jì)算整個(gè)二叉樹高度的算法（二叉樹的高度也叫二叉樹的深度）。（2）編寫計(jì)算二叉樹最大寬度的算法（二叉樹的最大寬度是指二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值）。332022-7-4int Height(btre bt)/求二叉樹bt的深度int hl,hr;if (bt=null) return(0);else hl=Height(bt-lch); hr=Height(bt-rch);if(hlhr) return (hl+1); else return(hr+1); 342022-7-4int Width(BiTree bt)/求二叉樹bt的最大寬度 if (bt=null) return (0); /空二叉樹寬度為0 else BiTree Q;/Q是隊(duì)列，元素為二叉樹結(jié)點(diǎn)指針，容量足夠大 front=1;rear=1;last=1;/front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置 temp=0; maxw=0; /temp記局部寬度, maxw記最大寬度