华文慕课-数据结构树题库

1、给出一棵树的逻辑结构T=(N,R),其中：

N={A,B,C,D,E,F,G,H,I,J,K}

R={r}

r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}

试回答下列问题：

（1）哪个是F的父结点？

（2）哪些是B的子孙？

（3）以结点C为根的子树的深度是多少？

（注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此）

解析?

?答案： B EFGH 2

2、将下图的二叉树转换为对应的森林，按照后根次序列出其结点。

解析：

转化后的森林如下所示：

参考：?

后根深度优先遍历森林 = 按中序法遍历对应的二叉树（左根右）

后根次序列 ：EBFCDAIJKHGL

3、对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。

8-9 3-2 7-4 5-9 6-1 8-6 7-3 2-5 8-0 //右指向左

注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。

解析：（合并时，结点数少的指向结点数多的）

4、若一个具有N个顶点，K条边的无向图是一个森林（N>K且2K>=N），则该森林有多少棵树？

解析：

在一棵树中，结点比边多一个，即结点比边多几个就有几棵树。

答案： N-K

5、一棵完全三叉树，下标为121的结点在第几层？（注：下标号从0开始，根的层数为0）

解析：

第h层的下标是从(3^h-1)/2到(3^(h+1)-1)/2-1，

第5层的下标是从121到363。

答案： 5

?