数据结构与算法（周测4-树与并查集）

判断题

1.某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。

     T      F

2.已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。

     T      F

3.在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。

     T      F

一个比较实用的判断方法是如果序列前一个元素比当前元素小，那么更新区间的最大值为当前元素；如果序列的前一个元素比当前元素大，那么更新区间的最小值为当前元素。之后的每一个元素必须在这个区间内。根据这个规则，当运行到70的时候区间已经是(70,80)，而下一个元素是59。

4.将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是：4、2、1、3、5、6。

     T      F

之前页面的第2题

5.一棵有124个结点的完全二叉树，其叶结点个数是确定的。

     T      F

完全二叉树完全可以确认

6.对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。

     T      F

之前页面的第1题

7.In a min-heap, all the keys along the path from the root to any leaf node must be in sorted (non-decreasing) order.

     T      F

最小堆从顶向下递增。

8.To find 63 from a binary search tree, one possible searching sequence is {39, 101, 25, 80, 70, 59, 63}.

     T      F

同第3题。

9.存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。

     T      F

设N为结点个数，N_n为拥有n个孩子的结点数量，则有总结点个数：$color{red}{N_{0}+N_{1}+N_{2} imes2+1}$，那么$color{red}{(2000-N_{0}) imes2+1=2000}$，N₀怎么看都不是整数，那么N₂也不用说了。

10.将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。

     T      F

11.在有N个元素的最大堆中，随机访问任意键值的操作可以在O(logN)时间完成。

     T      F

堆的左右孩子没有固定的顺序，无法像平衡二叉树那样顺着找下去。

12.对AVL树中的任一结点，其左子树的高度一定比其右子树的高度要高。

     T      F

13.完全二叉树中，若一个结点没有左孩子，则它必是树叶。

     T      F

14.完全二叉树的存储结构通常采用顺序存储结构。

     T      F

比如堆。

选择题

1.在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？

    A.1和-6
    B.4和-5
    C.8和-5
    D.8和-6

6和8合并就是集合{4,5,6}、{8,9}合并，大并小，所以{8,9}并入{4,5,6}，根结点是4，计数为-5。

2.The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are:

    A.1 and -6
    B.4 and -5
    C.8 and -5
    D.8 and -6

同第2题。

3.The array representation of a disjoint set is given by { 4, 6, 5, 2, -3, -4, 3 }. If the elements are numbered from 1 to 7, the resulting array after invoking Union(Find(7),Find(1)) with union-by-size and path-compression is:

    A.{ 4, 6, 5, 2, 6, -7, 3 }
    B.{ 4, 6, 5, 2, -7, 5, 3 }
    C.{ 6, 6, 5, 6, -7, 5, 5 }
    D.{ 6, 6, 5, 6, 6, -7, 5 }

按大小合并，所以集合{5,3,7}并入集合{6,2,4,1}，6是跟结点，树根大小为-7，又因为包含路径压缩，所以6成为原始集合元素2，4，1的直接父亲，并成为新假入集合根5的直接父亲，5也成为3和7的直接父亲。

4.The array representation of the disjoint sets is given by {2, –4, 2, 3, -3, 5, 6, 9, -2}. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(6)) with union-by-size, which elements will be changed in the resulting array?

    A.a. elements of index 2 and 5
    B.a. elements of index 2 and 6
    C.a. elements of index 4 and 5
    D.a. elements of index 4 and 6

类似与第一题。

5.In a disjoint set problem, given a set of m elements S = { 1, 2, 3, ..., m } and n ( 0<n<m ) distinct relations, the set S must have __ equivalence classes.

    A.at leatst m
    B.exactly n
    C.exactly m−n
    D.at least m−n

同一个集合的任意两个元素都可以构成等价类，最少的情况是同一个集合的所有元素构成一个等价类，个数为m-n。

6.已知不相交集合用数组表示为{ 4, 6, 5, 2, -3, -4, 3 }。若集合元素从1到7编号，则调用Union(Find(7),Find(1))（按规模求并，并且带路径压缩）后的结果数组为：

    A.{ 4, 6, 5, 2, 6, -7, 3 }
    B.{ 4, 6, 5, 2, -7, 5, 3 }
    C.{ 6, 6, 5, 6, -7, 5, 5 }
    D.{ 6, 6, 5, 6, 6, -7, 5 }

同第3题。

7.若并查集用树表示，其中有n个结点，查找一个元素所属集合的算法的时间复杂度为____。

    A.O(log₂n)
    B.O(n)
    C.O(n²)
    D.O(nlog₂n)

我认为这道题答案应该是O(1)，这里A最小，只能选A了。

8.设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？

    A.4
    B.6
    C.8
    D.10

结点总数：$color{red}{1 imes4+2 imes2+3 imes1+4 imes1+1=16}$，叶子结点数：$color{red}{16-4-2-1-1}$

9.三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？

    A.8
    B.10
    C.12
    D.13

参考第8题。

10.按照二叉树的定义，具有3个结点的二叉树有几种？

    A.3
    B.4
    C.5
    D.6

参考第8题。

11.二叉树中第5层（根的层号为1）上的结点个数最多为：

    A.8
    B.15
    C.16
    D.32

注意结点在左子树上和在右子树上不同。

12.先序遍历图示二叉树的结果为

    A.A，B，C，D，H，E，I，F，G
    B.A，B，D，H，I，E，C，F，G
    C.H，D，I，B，E，A，F，C，G
    D.H，I，D，B，E，F，G，A，C

13.AVL树是一种平衡的二叉搜索树，树中任一结点具有下列哪一特性：

    A.左、右子树的高度均相同
    B.左、右子树高度差的绝对值不超过1
    C.左子树的高度均大于右子树的高度
    D.左子树的高度均小于右子树的高度

14.已知关键字序列（5，8，12，19，28，20，15，22）是最小堆（小根堆），插入关键字3，调整后得到的最小堆是：

    A.3，5，12，8，28，20，15，22，19
    B.3，5，12，19，20，15，22，8，28
    C.3，8，12，5，20，15，22，28，19
    D.3，12，5，8，28，20，15，22，19

直接上滤。

15.由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：

    A.23
    B.37
    C.44
    D.46

之前页面的第2题

16.将{5, 2, 7, 3, 4, 1, 6}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：

    A.1, 2, 3, 4, 6, 7, 5
    B.1, 4, 2, 6, 3, 7, 5
    C.1, 4, 3, 2, 6, 7, 5
    D.5, 4, 3, 7, 6, 2, 1


17.在下述结论中，正确的是：
① 只有2个结点的树的度为1；
② 二叉树的度为2；
③ 二叉树的左右子树可任意交换；
④ 在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。

    A.①④
    B.②④
    C.①②③
    D.②③④

二叉树的度小于等于2，因为二叉树的定义要求二叉树中任意结点的度数小于等于2；堆就不允许交换

18.若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是：

    A.所有结点的平均查找效率是O(logN)
    B.最小值一定在叶结点上
    C.最大值一定在叶结点上
    D.中位值结点在根结点或根的左子树上

完全二叉树的最小值一定在叶节点上，是因为最左边的叶结点始终会拥有，但最大值就不好说了。

19.将 { 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7 } 逐个按顺序插入到初始为空的最小堆中，然后连续执行两次删除最小元素操作（DeleteMin），再插入4，16，此后堆顶的元素是什么？

    A.4
    B.5
    C.7
    D.9

这道题甚至不用建堆模拟，删掉最小的两个，再寻找加入了两个新元素后的最小值。

20.Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty min-heap. The preorder traversal sequence of the resulting tree is:

    A.1, 3, 2, 5, 4, 7, 6
    B.1, 2, 3, 4, 5, 7, 6
    C.1, 2, 5, 3, 4, 7, 6
    D.1, 3, 5, 4, 2, 7, 6


程序填空题

1.本题要求给出下列并查集操作执行后，集合数组内存储的结果。

union( find(4), find(6) )
union( find(2), find(7) )
union( find(0), find(4) )
union( find(7), find(6) )
union( find(7), find(1) )

注意：这里假设按规模求并（若两集合规模相等，则把第1个集合的根结点作为结果的根结点），并且用带路径压缩的查找。对所有的0≤i≤7，S[i]被初始化为−1。

i	0	1	2	3	4	5	6	7
S[i]	4			-1		-1	4

2.请填空完成下列代码，功能是实现并查集中的“查”，并且带路径压缩。

SetType Find ( ElementType X, DisjSet S )
{
    ElementType root, trail, lead;

    for ( root = X; S[root] > 0; ) ;
    for ( trail = X; trail != root; trail = lead ) {
        lead = S[trail] ;
       ;
    }
    return root;
}