第七章 树
PROBLEM 1 (2/3 分) 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)} Given a logical structure of a tree, T=(N, R), and 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)} 试回答下列问题： Please answer these questions: （1） 哪个是根结点？which is the root node? A A - 正确 A （2） 哪些是F的孩子？which are the child nodes of Node F? GH GH - 正确 GH （3） 结点K的层次是多少？ 5 5 - 不正确 5 3 （注：根的层数为0，独根树深度为0，高度为1，其他题目同样如此；同一个选项的答案如果有多个字母，按照字典序排列，且不要以空格分隔） (P.S. the level of the root node is 0, the depth of a tree, which only has a root node, is 0, and its height is 1. Other problems have the same regulations. If there are several alphabets in one question, order them by lexicographical order, and do not add spaces.)
PROBLEM 2
(1/1 分)
一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0） There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.)
k^(h-1) (k^h-1)/(k-1) Explanation 层数---节点数
number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is：
1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1)
k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确
PROBLEM 3
(1/1 分)
2-3树是一种特殊的树，它满足两个条件：
（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；
如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。 (多项) 2-3 tree is a special kind of tree, it satisfy:
（1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node.
If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确
4
5
6
7
Explanation
倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。 倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。
If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node.
If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes
PROBLEM 4
(1/1 分)
设F是由T1,T2,T3三棵树组成的森林，其中T1,T2,T3的结点数分别为n1,n2和n3，与F对应的二叉树为B，则二叉树B的左子树中有_____________个结点(单选）
Assume that F is a forest, made up of tree T1, T2, T3, and the node numbers of T1, T2, T3 are n1, n2, n3. Let B be the corresponding binary tree of F, then B's left sub-tree will has __________ nodes. (There is only one correct answer)
n1-1 n1-1 - 正确 Explanation
解释：B的根是T1的根，左子树是从T1根结点的子树组成的森林转换成的二叉树。换句话，B左子树的结点数=T1后代结点数=n1-1
B's root node is T1's root node, and B's left sub-tree is a binary tree, corresponding to the forest F'={T1}. So, the number of nodes of B's left sub-tree equals to the number of offspring nodes of T1, namely, n1-1.
n2-1 n3-1 n2
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库北大PKU 慕课 EDX 数据结构与算法 第七章图 quiz答案与解析在线全文阅读。
相关推荐：