mooc 第五章 习题

Q1

某二叉树有n个节点，高度为h。在其中插入一个新的节点，高度发生改变的节点个数最多为：

O(1)O(n)O(h)O(hlog2(n))

  您已经提交0次，共有2次提交机会。

Q2

高度为h的完全二叉树可能有多少个节点?

2h+12h2h−1−12h−1

  您已经提交0次，共有2次提交机会。

Q3

下列关于树的命题中错误的是：

顶点数为n的树的边数为n-1。树中任意两顶点之间存在唯一路径。在树中添加任一条边都会破坏树的结构。在树中删除任一条边得到的还是树。

  您已经提交0次，共有2次提交机会。

Q4

并查集是一种用于表示不相交集合的数据结构，支持以下操作：

• Union(x, y): 将元素x和y所在的集合合并
• Find(x): 返回元素x所在集合（实际上是返回该集合的一个代表元）

一种基本的实现是将每一个集合中的元素组织成一棵有根树，集合中的元素即树中的节点，选取树根为该集合的代表元，而整个并查集就是由若干棵树组成的森林。接口实现的方法是：

• Union(x, y): 将x所在树的根节点的父亲设为y所在树的根节点，从而将它们合并成一棵树
• Find(x): 返回节点x所在树的根节点。

例子：下图中的并查集原先有两棵表示集合的树{c,h,b,e}和{f,d,g}，调用Union(h, f)后得到了右边的树，如果此时再调用Find(e)会返回f。

并查集中的树最适合用什么方法表示：

父节点法孩子节点法长子-兄弟法邻接表法

  您已经提交0次，共有2次提交机会。

Q5

从n个节点的二叉树的叶节点u逐个节点地上溯到根节点的过程中，以下说法中错误的是：

经过的节点都是u的祖先。最坏时间复杂度为O(n)经过的路径是唯一确定的每上溯一层，当前节点的深度减小1，而高度增加1。

  您已经提交0次，共有2次提交机会。

1. Q6

   对二叉树进行中序遍历，节点v在中序遍历下的后继为（假设v的后继存在）：

   其右子树中第一个被访问的节点其左子树中第一个被访问的节点其右子树中第一个被访问的节点或v的某个祖先其右子树中第一个被访问的节点或其左子树中的某个节点

     您已经提交0次，共有2次提交机会。

2. Q7

   与先序、中序遍历类似，以左子->右子->根节点的顺序来访问二叉树称为后序遍历。后序遍历中第一个被访问的节点是：

   左侧链中最深的节点根节点右侧链中最深的节点以上皆不是

     您已经提交0次，共有2次提交机会。

3. Q8

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

   y,v,x,ux,y,v,uu,v,y,x无法确定

     您已经提交0次，共有2次提交机会。

4. Q9

   关于二叉树遍历序列之间关系的说法错误的是：

   已知先序遍历序列和中序遍历序列可以确定后序遍历序列已知中序遍历序列和后序遍历序列可以确定先序遍历序列已知中序遍历序列和后序遍历序列可以确定层次遍历序列已知先序遍历序列和后序遍历序列可以确定中序遍历序列

     您已经提交0次，共有2次提交机会。

5. Q10

   借助队列对二叉树进行层次遍历时,任意时刻队列中的节点满足：

   均位于从根节点到当前节点的路径上均是当前节点的后代高度相差不超过1深度相差不超过1

     您已经提交0次，共有2次提交机会。