1、以下图所示的4棵二叉树中，不是完全二叉树的是〔 〕
A
B
C
D
2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法〔 〕。
A、正确 B、错误 C、不肯定
3、某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是〔 〕。
A、acbed B、decab C、deabc D、cedba
4、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的〔 〕。
A、前序 B、中序 C、后序 D、层次序
5、深度为5的二叉树至多有〔 〕个结点。
A、16 B、32 C、31 D、10
6、在一个非空二叉树的中序遍历序列中，根结点的右边〔 〕。
A、只有右子树上的全部结点 B、只有右子树上的局部结点
C、只有左子树上的局部结点 D、只有左子树上的全部结点
7、树最适合用来表示〔 〕。
A、有序数据元素 B、无序数据元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据。
8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序〔 〕。
A、不发生改变 B、发生改变 C、不能确定 D、以上都不对
9、完成任意二叉树的后序遍历的非递归算法而不使用栈结构，最正确方案是二叉树采纳〔 〕存储结构。
A、二叉链表 B、广义表存储结构 C、三叉链表 D、顺序存储结构
10、对一个满二叉树，m个树叶，n个结点，深度为h，则〔 〕。
A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1
11、设n，m为二叉树上的两个结点，在中序遍历时，n在m前的条件是〔 〕。
A、n在m右方 B、n是m祖先 C、n在m左方 D、n先序中序后序遍历二叉树是m子孙
12．一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
A
B
+
C
*
E
F
D
G
+
*
-
/
13. 设有一表示算术表达式的二叉树〔见右图〕，
它所表示的算术表达式是〔 〕
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-G
14. 在下述结论中，正确的选项是〔 〕
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
15. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是〔 〕
A．m-n B．m-n-1 C．n+1 D．条件缺乏，无法确定
16．假设一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是〔 〕
A．9 B．11 C．15 D．不确定
17．一棵完全二叉树上有1001个结点，其中叶子结点的个数是〔 〕
A． 250 B． 500 C．254 D．505 E．以上答案都不对
18. 一个具有1025个结点的二叉树的高h为〔 〕
A．11 B．10 C．11至1025之间 D．10至1024之间
19．深度为h的满m叉树的第k层有〔 〕个结点。(1=<k=<h)
A．mk-1 B．mk-1 C．mh-1 D．mh-1
20. 利用二叉链表存储树，则根结点的右指针是〔 〕。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空
21．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采纳( )次序的遍历完成编号。
A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
22．假设二叉树采纳二叉链表存储结构，要交换其全部分支结点左、右子树的位置，利用( )遍历方法最适宜。
A．前序 B．中序 C．后序 D．按层次
23．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树肯定满足〔 〕
A．全部的结点均无左孩子 B．全部的结点均无右孩子
C．只有一个叶子结点 D．是任意一棵二叉树
24. 假设X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
的双亲的右子树中最左的结点
的左子树中最右结点的左子树中最右叶结点
25. 线索二叉树是一种〔 〕结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D．线性
26．n个结点的线索二叉树上含有的线索数为〔 〕
A．2n B．n－l C．n＋l D．n
27．下面几个符号串编码集合中，不是前缀编码的是〔 〕。
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. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 ]中时，数组中第i个结点的左孩子为〔 〕
A．A[2i](2i=<n) B. A[2i+1](2i+1=< n) C．A[i/2] D．无法确定
29、高度为h的完全二叉树至少有多少个结点?至多有多少个结点?
解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。
30、在什么样的情况下，等长编码是最优的前缀码?
答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。
31.假设在树中，结点x是结点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)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?
(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?
(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?
答：这是测试我们对树的根本概念的掌握情况。
a是根结点；mndfjkl是叶结点；c是g的双亲；c,a是g的祖先；
j,k是g的孩子；imn是e的子孙；d是e的兄弟，g,h是f的兄弟；
b的层次是2，n的层次是5；树的深度是5；以c为根的子树深度是3；
树的度数是3。
32、试出分别满足下面条件的全部二叉树：
(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；
(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。
答：
(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。
(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。
(3) 前序序列和后序序列相同的二叉树是：只有根结点的二叉树。
(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。
33、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
解： A
/ \
B C
/ \ \
D E F
/ \ /
G H I
\
J
34、对以下图所示的森林：
(1)求各树的前序序列和后序序列；
(2)求森林的前序序列和后序序列；
(3)将此森林转换为相应的二叉树；
(4)给出(a)所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?
解：
(1) (a)的前序序列：ABCDEF 后序序列：BDEFCA
(b)的前序序列：GHIJK 后序序列：IJKHG
(c)的前序序列：LMPQRNO 后序序列：QRPMNOL
(2) 此森林的前序序列： ABCDEFGHIJKLMPQRNO
此森林的后序序列： BDEFCAIJKHGQRPMNOL
(3)略
(4)略
35．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为 。
答：⎣n/2⎦
36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(1) ,则该二叉树对应的树林包含 (2) 棵树。
答：(1)EACBDGF 〔2〕2
37．具有n个结点的满二叉树，其叶结点的个数是______。
答：(n+1)/2
设内部节点数为a，叶节点数为b，明显有a+b=n (1)，非空满二叉树中全部节点的出度正好等于入度，每个内部节点出度为2，叶节点出度为0，全部节点的出度和为2a；根节点入度为
0，其他节点的入度为1，全部节点的入度和为a+b-1;因此有2a=a+b-1 (2)。由(1)(2)得b=(n+1)/2，a=(n-1)/2。其它可得b=a+1，也就是说，非空满二叉树的叶节点数正好比内部节点数多1。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论