数据结构课后习题答案第六章.doc

数据结构课后****题答案第六章第六章树和二叉树(下载后用阅读版式视图或 web 版式可以看清****题一、选择题 1. 有一“遗传”关系:设x是y 的父亲,则x 可以把它的属性遗传给 y 。表示该遗传关系最适合的数据结构为()。 A. 向量 D. 二叉树 2 .树最合适用来表示()。 A. 有序数据元素 B 元素之间具有分支层次关系的数据 C 无序数据元素 D. 元素之间无联系的数据 3 .树 B 的层号表示为 la, 2b, 3d, 3e, 2c ,对应于下面选择的()。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c) 4. 高度为 h 的完全二叉树至少有() 个结点,至多有() 个结点。 A. 2h_l C. 2h-1 D. 2h 5. 在一棵完全二叉树中,若编号为 f 的结点存在右孩子,则右子结点的编号为()。 A. 2i B. 2i-l C. 2i+l D. 2i+2 6. 一棵二叉树的广义表表示为 a(b(c) , d(e( , g(h)) , f)) ,则该二叉树的高度为()。 7. 深度为 5 的二叉树至多有() 个结点。 A. 31 B. 32 C. 16 D. 10 8. 假定在一棵二叉树中, 双分支结点数为 15, 单分支结点数为 30个, 则叶子结点数为() 个。 A. 15 B. 16 C. 17 D. 47 9. 题图 6-1 中, () 是完全二叉树, () 是满二叉树。 10. 在题图 6-2 所示的二叉树中: (1)A 结点是 A. 叶结点 B 根结点但不是分支结点 C 根结点也是分支结点 D. 分支结点但不是根结点(2)J 结点是 A. 叶结点 B .根结点但不是分支结点 C 根结点也是分支结点 D. 分支结点但不是根结点(3)F 结点的兄弟结点是 C .空 (4)F 结点的双亲结点是 (5) 树的深度为 (6)B 结点的深度为 (7)A 结点所在的层是 11. 在一棵具有 35 个结点的完全二叉树中,该树的深度为()。 12. 一棵有 124 个叶结点的完全二叉树,最多有() 个结点。 A. 247 B. 248 C. 249 D. 250 13. 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组 R[1?n] 中,结点 R[i] 若有左子树,则左子树是结点()。 A. R[2i+l] B. R[2i] [i/2] D. R[2i-1] 14. 在一非空二叉树的中序遍历序列中,根结点的右边()。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 15. 一棵度为 m 的树中,有 ni 个度为 1 的结点,有 n2 个度为 2 的结点?? ,有 nm 个度为 m 的结点,则该树的叶结点数为()。 A. n1+n2+...+nm B. (m-l) nm+...+n2 +1 +n2+1 D. nl-n2 16. 已知某二叉树的中序遍历序列是 debac ,后序遍历序列是 dabec , 它的前序遍历序列是()。 A. acbed B. decab C. deabc D. cedba 17. 在一棵二叉树的二叉链表中,空指针域等于所有非空指针域数加()。 D.-1 18. 线索二叉树是一种() 结构。 A. 逻辑 B .逻辑和存储 C .物理 D. 线性 19. 由权值分别是 8,7,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为()。 A. 23 B. 37C. 46 D. 43 20. 设T 是哈夫曼树,具有 5 个叶结点,树 T 的高度最高可以是()。 二、填空题 1. 对于一棵具有 n 个结点的树,该树中所有结点的度数之和为____ 。 2. 在树型结构中, 树根结点没有____ 结点, 其余每个结点有且只有____ 个前驱结点:叶子结点没有____ 结点,其余每个结点可以有____ 后继结点。 3. 有一棵树如题图 6-3 所示,回答下面的问题。这棵树的根点是____ ;叶子结点是____ ;结点 k3 的度是____ ;结点 k3的子女是____ ; 结点 k3 的父结点是____ ; 这棵树的度为____ ; 这棵树的深度是____ 。 4. 假定一棵树的广义表表示为 A(B(E) , C(F(H ,I,J, G), D),