mooc 第五章 习题

Q1

Q2

Q3

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。

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

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

Q5

1. Q6

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

   其右子树中第一个被访问的节点 其左子树中第一个被访问的节点 其右子树中第一个被访问的节点或v的某个祖先 其右子树中第一个被访问的节点或其左子树中的某个节点
     您已经提交0次，共有2次提交机会。

2. Q7

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

   左侧链中最深的节点 根节点 右侧链中最深的节点 以上皆不是
     您已经提交0次，共有2次提交机会。

3. Q8

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

   y,v,x,u x,y,v,u u,v,y,x 无法确定
     您已经提交0次，共有2次提交机会。

4. Q9

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

   已知先序遍历序列和中序遍历序列可以确定后序遍历序列 已知中序遍历序列和后序遍历序列可以确定先序遍历序列 已知中序遍历序列和后序遍历序列可以确定层次遍历序列 已知先序遍历序列和后序遍历序列可以确定中序遍历序列
     您已经提交0次，共有2次提交机会。

5. Q10

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

   均位于从根节点到当前节点的路径上 均是当前节点的后代 高度相差不超过1 深度相差不超过1
     您已经提交0次，共有2次提交机会。