《數(shù)據結構》期末復習題及參考答案第6章樹和二叉樹【HSH2013級】給學生

1、數(shù)據結構期末復習題及參考答案 - 第6章 樹和二叉樹一、 選擇題 1、在二叉樹的第I層(I1)上最多含有結點數(shù)為（ ） A. 2I B. 2I-1-1 C. 2I-1 D. 2I -12、深度為6的二叉樹最多有( )個結點 A64 B.63 C.32 D.313、一棵樹高為K的完全二叉樹至少有( )個結點 A.2k 1 B.2k-1 1 C.2k-1 D.2 k 4、有關二叉樹下列說法正確的是（ ）A. 二叉樹的度為2 B. 一棵二叉樹的度可以小于2 C. 二叉樹中至少有一個結點的度為2 D. 二叉樹中任何一個結點的度都為2 5、n個結點的線索二叉樹上含有的線索數(shù)為（ ）A. 2n B. nl

2、 C. nl D. n 6、線性表和樹的結構區(qū)別在于（ ）A前驅數(shù)量不同，后繼數(shù)量相同B前驅數(shù)量相同，后繼數(shù)量不同C前驅和后繼的數(shù)量都相同D前驅和后繼的數(shù)量都不同7、已知一算術表達式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，則其前綴形式為( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE8、設有一表示算術表達式的二叉樹（見下圖），EFDGAB/+*-C*它所表示的算術表達式是（ ）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*

3、B+C/D*E+F-G9、一棵具有 n個結點的完全二叉樹的樹高度（深度）(符號表示取不大于x的最大整數(shù))是（ ）A. B. C. D.10、利用二叉鏈表存儲樹，則根結點的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空11、已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 12、某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E 則前序序列是：AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不

4、對 13、若前序遍歷二叉樹的結果為序列A、B、C，則有_棵不同的二叉樹可以得到這一結果。A. 3 B. 4 C. 5 D. 6 14、已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 則它的前序遍歷是（ ）。 A. acbed B. decab C. deabc D. cedba 15、線索二叉樹是一種（ ）結構。A邏輯 B邏輯和存儲 C物理 D線性 二、填空題 1、對于任意一棵二叉樹，如果其葉子結點數(shù)為N0，度為1的結點數(shù)為N1，度為2的結點數(shù)為N2，則N0=_ N2 + 1_。2、具有256個結點的完全二叉樹的深度為_9_。3、一個深度為4的二叉樹，其結點至少有 4

5、個，至多有 15 個：4、深度為H 的完全二叉樹至少有_ 2H-1_個結點；至多有 2H-1_個結點；H和結點總數(shù)N之間的關系是 H=ëlog2Nû+1。5、若用鏈表存儲一棵二叉樹時，每個結點除數(shù)據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，N個結點的二叉樹共有_2N_個指針域，其中有_N-1_個指針域是存放了地址，有_N+1_個指針是空指針。6、設一棵赫夫曼樹有6個葉子結點，權值分別為3、4、7、14、15、20，則根結點的權值是_63_7、已知二叉樹的先序遍歷次序是 abdcef，中序遍歷次序是 bdaecf，則它的后序遍歷次序是： dbefca 。8、對

6、一棵完全二叉樹，設一個結點的編號為i，若它的左孩子結點存在，則其編號為 2i ；若右孩子結點存在，則其編號為 2i+1 ；而雙親結點的編號為 ë û 。 9、赫夫曼樹是帶權路徑長度 最小的 二叉樹，又稱最優(yōu)二叉樹，路徑上權值較大的結點離根較近。10、下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內容。typedef struct node int data; struct node *lchild;_ struct node *rchild _; BiTNode, *BiTree;void createBitree(BiTree &T) scanf(“%

7、c”, &ch);if(ch='#') T=NULL ;else T=( BiTNode *)malloc(sizeof(BiTNode); T->data=ch; createBitree(T->lchild)；_createBitree(T->rchild);11、二叉樹由_根結點_，_左子樹_，_右子樹_三個基本單元組成。12、樹的鏈表存儲結構常用的有三種，其中，雙親 表示法以一組連續(xù)空間存儲樹的結點，在每個結點中設一個指示器指示雙親結點的位置。孩子 表示法每個結點的孩子以單鏈表的形式存儲，n個結點有n個孩子鏈表，n個頭指針又組成一個線性表，并以

8、順序存儲結構存儲。孩子兄弟 表示法以二叉鏈表作為樹的存儲結構，鏈表中的結點的兩個指針分別指向該結點的第一個孩子結點和下一個兄弟結點。/P135-13613、利用樹的孩子兄弟表示法存儲，可以將一棵樹轉換為_二叉樹_。14、在二叉樹中，指針p所指結點為葉子結點的條件是_ p->lchild=NULL && p->rchlid=NULL _。15、樹的孩子兄弟表示法和二叉樹的二叉鏈表表示法，本質是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。16、樹和二叉樹邏輯上都是樹形

9、結構，但是二叉樹不是樹的特例，二叉樹與樹是兩個不同的概念。二叉樹的度 至多為2，樹無此限制；二叉樹有左右子樹之分，即使在只有一個分枝的情況下， 也必須指出是 左子樹還是右子樹，樹無此限制。三、簡答題 1、已知一棵二叉樹的前序遍歷的結果是ABKCDFGHIJ，中序遍歷的結果是KBCDAFHIGJ, 試畫出這棵二叉樹，并寫出后序遍歷結果。 答案：當前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時，逐步形成二叉樹的過程如下圖所示：這棵二叉樹的后序遍歷結果是：K D C B I H J G F A2、某通信電文由A、B、C、D、E、F六個字符組成，它們在電文中出現(xiàn)的次數(shù)（權值）分別是1

10、6，5，7，3，8，1。試畫出其哈夫曼樹，確定其對應的哈夫曼編碼，并計算其帶權路徑長度。為使結果唯一，請將權值較小的結點作為其雙親的左孩子，而將權值較大的結點作為其雙親的右孩子。答案：哈夫曼樹如下：對應的哈夫曼編碼如下：A: 0B: 101C: 110D: 1001E: 111F: 1000帶權路徑長度為: WPL=(1+3)*4+(5+7+8)*3+16*1=923、對下圖所示二叉樹分別按前序中序后序遍歷，給出相應的結點序列，同時給二叉樹加上中序線索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA （4）中序線索見圖中虛線箭頭所示。四、

11、算法分析題1、已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法，之后，對于如下所示的二叉樹：（1）畫出執(zhí)行下面算法后所建立的結構； （2）說明該算法的功能。typedef struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList； LinkList Leafhead = NULL； void Inorder ( BinTree T ) LinkList s； If(T) Inorder(T>lchild)； If (!T>lchild)&&(!T>rch

12、ild) s=(ListNode*)malloc(sizeof(ListNode)； s>data=T>data； s>next=Leafhead； Leafhead=s； Inorder(T>rchild); 答案：2、已知二叉樹中的結點類型BinTreeNode定義為:        struct BinTreeNode ElemType data;  BinTreeNode *left, *right;其中data為結點值域，left和right分別為指向左、右孩子

13、結點的指針域。下面函數(shù)的功能是從二叉樹BT中查找值為x的結點，若查找成功則返回結點地址，否則返回空。按標號填寫空缺的內容，要求統(tǒng)一填寫在算法后面的標記處。    BinTreeNode* BTF(BinTreeNode* BT，ElemType x)            if(BT=NULL) _ return NULL _;        else if

14、(BT->data=x) _ return BT  _;             else   BinTreeNode* t;                 if(t=BTF(BT->left, x) return t;    

15、0;            _ if(t=BTF(BT->right, x) return t   _;                 return NULL;            

16、;               3、由二叉樹的前序序列和中序序列能否唯一確定一棵二叉樹？由二叉樹的中序序列和后序序列能否唯一確定一棵二叉樹？由二叉樹的前序序列和后序序列能否唯一確定一棵二叉樹？請分別進行論述。答案： (1)給定二叉樹結點的前序序列和中序序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結點，該元素將二叉樹中序序列分成兩部分，左邊（設l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設r個元素）是右子樹，若為空，則右子樹為空。根據前序遍

17、歷中“根左子樹右子樹”的順序，則由從第二元素開始的l個結點序列和中序序列根左邊的l個結點序列構造左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構造右子樹。(2)由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。證明如下：當n=1時，只有一個根結點，由中序序列和后序序列可以確定這棵二叉樹。設當n=m-1時結論成立，現(xiàn)證明當n=m時結論成立。設中序序列為S1，S2，Sm,后序序列是P1,P2,，Pm。因后序序列最后一個元素Pm是根，則在中序序列中可找到與Pm相等的結點（設二叉樹中各結點互不相同）Si(1im)，因中序序列是由中序遍歷而得，所以Si是根結點，S1，S2，Si-

18、1是左子樹的中序序列，而Si+1,Si+2,Sm是右子樹的中序序列。若i=1，則S1是根，這時二叉樹的左子樹為空，右子樹的結點數(shù)是m-1,則S2，S3，Sm和P1，P2，Pm-1可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則Sm是根，這時二叉樹的右子樹為空，左子樹的結點數(shù)是m-1，則S1，S2，Sm-1和P1，P2，Pm-1唯一確定左子樹，從而也確定了二叉樹。最后，當1<i<m時，Si把中序序列分成S1，S2，Si-1和Si+1,Si+2,，Sm。由于后序遍歷是“左子樹右子樹根結點”，所以P1,P2,Pi-1和Pi,Pi+1,Pm-1是二叉樹的左子樹和右子樹的后序遍歷序列。因而由S1，S2，Si-1和P1，P2，Pi-1可唯一確定二叉樹的左子樹，由Si+1,Si+2,，Sm和Pi,Pi+1,，Pm-1可唯一確定二叉樹的右子樹 。(3)由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹。因為無法確定左右子樹兩部