数据结构二叉树习题含答案.doc

第６章树与二叉树

1.选择题

(1）把一棵树转换为二叉树后,这棵二叉树得形态就是（).

Ａ。唯一得Ｂ.有多种

C．有多种，但根结点都没有左孩子Ｄ．有多种,但根结点都没有右孩子

(2）由３个结点可以构造出多少种不同得二叉树？（）

Ａ。２Ｂ．３C。４Ｄ

（3)一棵完全二叉树上有1０01个结点,其中叶子结点得个数就是（）。

A。2５0B．５00Ｃ.254D．５01

(4)一个具有1025个结点得二叉树得高h为().

A。11Ｂ。10C．11至10２５之间D

（5）深度为ｈ得满m叉树得第k层有（)个结点。(1＝〈k=h)

A。mk-1B。ｍｋ-1C．mh－１D。m

（6)利用二叉链表存储树,则根结点得右指针就是（）。

A．指向最左孩子B.指向最右孩子C。空Ｄ.非空

（7)对二叉树得结点从1开始进行连续编号，要求每个结点得编号大于其左、右孩子得编号，同一结点得左右孩子中，其左孩子得编号小于其右孩子得编号,可采用()遍历实现编号。

A。先序Ｂ、中序C、后序Ｄ、从根开始按层次遍历

（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树得位置,利用（）遍历方法最合适。

A．前序B.中序C。后序D。按层次

（9)在下列存储形式中,（）不就是树得存储形式？

A.双亲表示法B．孩子链表表示法C.孩子兄弟表示法D．顺序存储表示法

（1０)一棵非空得二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足（)。

A.所有得结点均无左孩子Ｂ．所有得结点均无右孩子

Ｃ.只有一个叶子结点D.就是任意一棵二叉树

(11)某二叉树得前序序列与后序序列正好相反，则该二叉树一定就是（)得二叉树。

A。空或只有一个结点B.任一结点无左子树

C.高度等于其结点数D．任一结点无右子树

(１２）若X就是二叉中序线索树中一个有左孩子得结点，且X不为根，则X得前驱为()。

A.X得双亲B。X得右子树中最左得结点

C.Ｘ得左子树中最右结点D.X得左子树中最右叶结点

(13）引入二叉线索树得目得就是（)。

Ａ．加快查找结点得前驱或后继得速度B.为了能在二叉树中方便得进行插入与删除

Ｃ.为了能方便得找到双亲D。使二叉树得遍历结果唯一

（14）线索二叉树就是一种（）结构。

A。逻辑B。逻辑与存储C。物理D．线性

（15）设F就是一个森林，Ｂ就是由F变换得得二叉树.若F中有n个非终端结点,则Ｂ中右指针域为空得结点有（)个.

A．n-１B。nC.n+１Ｄ.n+2

2.应用题

（1）试找出满足下列条件得二叉树

=1\＊GB3①先序序列与后序序列相同=2\*GB３②中序序列与后序序列相同

=3\＊ＧＢ３③先序序列与中序序列相同=4\*ＧB3④中序序列与层次遍历序列相同

先序遍历二叉树得顺序就是“根—左子树-右子树”，中序遍历“左子树—根—右子树”,后序遍历顺序就是：“左子树—右子树―根＂,根据以上原则,本题解答如下:

(1）?若先序序列与后序序列相同,则或为空树,或为只有根结点得二叉树

（2）?若中序序列与后序序列相同，则或为空树,或为任一结点至多只有左子树得二叉树．

(３）?若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树得二叉树．

（４）?若中序序列与层次遍历序列相同，则或为空树,或为任一结点至多只有右子树得二叉树

（２）设一棵二叉树得先序序列:ＡＢＤFCＥGH，中序序列：BＦＤAGEHC

=１\*GB３①画出这棵二叉树。

=2\*ＧＢ３②画出这棵二叉树得后序线索树。

=3\＊GB3③将这棵二叉树转换成对应得树（