作业13-树与森林

柔情只为你懂 2022-12-26 09:15 210阅读 0赞

1-1  
对于一个有N个结点、K条边的森林，不能确定它共有几棵树。(F)  
\[解析\]设边的数目 EdgeNum, 树的数目为 TreeNum  
根据 NodeNum - 1 = EdgeNum  
所以 (NodeNum1 - 1) + … + (NodeNumi - 1) = K  
即 N - TreeNum = K

2-2  
若森林F有15条边、25个结点，则F包含树的个数是：©  
A.8  
B.9  
C.10  
D.11  
\[解析\]运用1-1得到的公式可求出树的个数  
TreeNum = N - K = 25 - 15 = 10

2-3  
将森林转换为对应的二叉树，若在二叉树中，  
结点u是结点v的父结点的父结点，则在原来的森林中，  
u和v可能具有的关系是：(B)

1.  父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系  
    A.只有2  
    B.1和2  
    C.1和3  
    D.1、2和3  
    \[解析\]注意,题目给出的条件是在二叉树中的父子关系,  
    并非原森林中的结点之间的父子关系  
    以u为根节点做一棵层数为3的满二叉树(结点u本应在一棵完整的  
    二叉树中,但是可以单独拿出来分析),结点v出现在第三层中,  
    在二叉树的第三层中,所有位置能够产生的关系  
    依次为 (1)父子关系(爷爷-孙子), (2)父子关系,  
    (3)结点v的父亲节点和u是兄弟 (4)v和u互为兄弟  
    这里单独讨论第三种可能具有的关系:  
    若情况为(1)则u的父结点与v的父结点 是 父子爷孙关系  
    若情况为(2)则u的父结点与v的父结点 是 父子关系  
    若情况为(3)则u的父结点与v的父结点 也是 父子关系  
    若情况为(4)则u的父结点与v的父结点 是 同一个人  
    综上 第三种关系不存在

2-4  
对于一个有N个结点、K条边的森林，共有几棵树？(A)  
A.N−K  
B.N−K+1  
C.N−K−1  
D.不能确定  
\[解析\]公式忘了,再推一次吧  
一棵树: NodeNum - 1 = EdgeNum  
一个森林: N - TreeNum = K

2-5  
设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M2  
和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是：©  
A.M1  
B.M1+M2  
C.M2+M3  
D.M3  
\[解析\]二叉树的根节点是M1的根节点,右子树是由M2和M3组成的  
所以结点个数就是M2 + M3

2-6  
由若干个二叉树组成的森林F中，叶结点总个数为N，  
度为2的结点总个数为M，则该集合中二叉树的个数为：(B)  
A.M−N  
B.N−M  
C.N−M−1  
D.无法确定  
\[解析\]设二叉树的数目为TreeNum  
一棵树: n0 = n2 + 1  
森林: N = M + TreeNum

2-7  
已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，  
则该完全二叉树的结点个数最多是：©  
A.39  
B.52  
C.111  
D.119  
\[解析\]这题我记得上一次作业做过,  
第七层是最后一层, 第六层是满的.  
最多的时候, 第六层倒数第 9 个 结点有两个结点  
(从第一个到倒数第九个结点都有两个子节点)  
此时结点的个数 MaxNum = 2^(6) - 1 + (2^(6-1) - 8) \* 2

2-8  
在一个用数组表示的完全二叉树中，如果根结点下标为1，  
那么下标为17和19这两个结点的最近公共祖先结点在哪里(数组下标)？  
(注:两个结点的“公共祖先结点”是指同时都是这两个结点祖先的结点)(B)  
A.8  
B.4  
C.2  
D.1  
\[解析\]注意 二叉树求父亲节点是 除2 下取整.  
17 /2 = 8 /2 = 4  
19 /2 = 9 /2 = 4

2-9  
具有65个结点的完全二叉树其深度为(根的深度为1)：(B)  
A.8  
B.7  
C.6  
D.5  
\[解析\] 2^6 - 1 == 63, 2^7 - 1 = 127  
只有六层装不下

2-10

下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是：(B)  
\[解析\]先求出后序遍历序列, 依次找到结点, 若左子树为空,则左子树存前驱  
若右子树为空,则右子树存后继  
后序序列的第一个结点和最后一个节点有可能出现指针指向NULL的情况

4-1  
已知一个森林的先序遍历序列为BEFKLCGDHIJ，  
中序遍历序列为EKLFBGCHIJD，该森林的叶子数为(3)  
\[解析\]森林的先序遍历 对应到二叉链表的先序遍历  
森林的中序遍历 对应到二叉链表的中序遍历

4-2  
已知一颗树的先根序遍历序列为ABHCEFGD，  
后根序遍历序列为HBEGFCDA，这颗树的深度为()

\[解析\]一棵普通树的先根遍历对应二叉链表的先序遍历  
一棵普通树的后根遍历 对应二叉链表的 中序遍历  
由此可以得到原 二叉链表的 结构  
注意 此时得到的是 二叉链表 不是原树的 结构  
需要在还原会原来 的树  
进而得到 原树的深度 是4

7-2 家谱处理(不会写也不想写)