学堂在线数据结构上5

第五章 二叉树
a树
1.下列哪种数据结构可以高效地兼顾静态操作和动态操作:树
解析:向量长于静态操作而列表长于动态操作,树则在某种程度上兼顾二者.

2.n个顶点的树有多少条边?n−1

3.树是:连通无环图

4.在一棵树中,顶点p是顶点v的父亲,则它们的高度的关系是
height(v) < height§

b.树的表示
1.用父节点+孩子节点的方法存储n个节点的树,需要的空间是:
O(n)

2.
以上树在计算机中表示如下:
第三行中parent[]的内容应该是:-1, 5, 5, 7, 0, 4, 5, 0, 0, 7

c.二叉树
1.高度为h的满二叉树有多少个节点?2^(h+1)−1
解析：满二叉树深度为i的节点有2i个，求和得出答案

2.一棵高度为h,节点数为n的真二叉树的特点是:
不存在只有一个孩子的节点

3.在长子-兄弟表示法中,树中某节点的长子相当于二叉树中的:左子

d.二叉树的实现
1.设二叉树有n个节点,高度为h.在其中插入一个新的节点,高度发生改变的节点个数为:O(h)
解析：新插入节点到根节点的路径上所有节点(即新节点的祖先)高度都有可能变化.

e1.先序遍历
1.对以下二叉树进行先序遍历:

刚访问完节点d时（迭代实现2）栈中的元素从栈顶到栈底依次为:f

2.二叉树是:半线性结构

3.若在先序遍历中规定访问完根节点后先访问右子树再访问左子树,则左、右子树的入栈顺序是：先左后右

4.先序遍历的顺序是:先自上而下访问左侧链上的节点,再自下而上访问它们的右子树

e2.中序遍历
1.中序遍历中第一个被访问的节点是:最左的节点

2.对以下二叉树进行中序遍历:

节点c刚被访问完毕时栈中的元素从栈顶到栈底为:d, f

e3.层次遍历
1.层次遍历的次序是:自上而下访问各个深度的节点,同样深度的节点中自左向右

2.对以下二叉树进行层次遍历:

节点F正欲出队时队列中的元素从队头到队尾为:F,G

e4.重构
1.后序遍历序列中最后一个节点是：根节点

本章测试
1.二叉树有n个节点，高度为h。在其中插入一个新的节点，高度发生改变的节点个数最多为：O(h)
解析：新插入节点到根节点的路径上所有节点(即新节点的祖先)高度都有可能变化

2.高度为 h 的完全二叉树可能有多少个节点?2^h
解析：高度为h的完全二叉树节点最多的情况即满二叉树，最少的情况比高度为h-1的满二叉树多1。

3.下列关于树的命题中错误的是：在树中删除任一条边得到的还是树。
解析：删除一条边后得到两个连通分量

4.并查集是一种用于表示不相交集合的数据结构，支持以下操作：一种基本的实现是将每一个集合中的元素组织成一棵有根树，集合中的元素即树中的节点，选取树根为该集合的代表元，而整个并查集就是由若干棵树组成的森林。接口实现的方法是：
例子：下图中的并查集原先有两棵表示集合的树{c,h,b,e}和{f,d,g}，调用Union(h, f)后得到了右边的树，如果此时再调用Find(e)会返回f。
并查集中的树最适合用什么方法表示：

答：父节点法
解析：父节点法能够高效定位父亲而不能高效地定位孩子，而并查集中的树只需要能够定位父节点。

5.从n个节点的二叉树的叶节点u逐个节点地上溯到根节点的过程中，以下说法中错误的是：
每上溯一层，当前节点的深度减小1，而高度增加1。
解析：每上溯一层，深度减小1，但高度的增加可能大于1，因为节点的高度由其左、右子树中较高者决定。

6.对二叉树进行中序遍历，节点v在中序遍历下的后继为（假设v的后继存在）：其右子树中第一个被访问的节点或v的某个祖先
解析：当v没有右子树时它的后继为某个祖先，具体地说是在沿着parent指针向上的过程中第一次向右的祖先。

7.与先序、中序遍历类似，以左子->右子->根节点的顺序来访问二叉树称为后序遍历。后序遍历中第一个被访问的节点是：
a.左侧链中最深的节点
b.根节点
c.右侧链中最深的节点
d.以上皆不是
答案为：d
解析：从根节点开始，对于中途每个节点，能往左就往左，不能往左就往右，若左右都无路可走，则该节点是后序遍历中第一个被访问的节点。

8.对二叉树进行先序遍历，u和v是左侧链上两个节点，且u是v的祖先，x、y分别是u和v的右子，试问这四个节点被访问的顺序是：
u,v,y,x

9.关于二叉树遍历序列之间关系的说法错误的是：已知先序遍历序列和后序遍历序列可以确定中序遍历序列
解析：已知先序遍历序列{1,2}和后序遍历序列{2,1}，无法确定2是1的左子还是右子，从而无法确定中序遍历序列。

10.借助队列对二叉树进行层次遍历时,任意时刻队列中的节点满足：
深度相差不超过1