数据结构第二单元练习题答案.doc

数据结构第二单元练****题答案一、选择 1. 树最适合用来表示() A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2. 在下述结论中,正确的是() ①只有一个结点的二叉树的度为 0;②二叉树的度为 2;③二叉树的左右子树可任意交换;④深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A. ①②③ B. ②③④ C. ②④ D. ①④ 3. 以下说法正确的是() A. 任何一棵二叉树中至少有一个结点的度为 2 B. 任何一棵二叉树中每个结点的度都为 2 C. 任何一棵二叉树的度肯定等于 2 D. 任何一棵二叉树的度可以小于 2 4. 在下列情况中,可称为二叉树的是() A. 每个结点至多有两棵子树的树 B. 哈夫曼树 C. 每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E. 以上答案都不对 5. 深度为 h 的满 m 叉树的第 k 层有() 个结点(1=<k=<h) k-1 k -1 h-1 h -1 6. 在一棵高度为 k 的满二叉树中,结点总数为() k-1 k -1 D. ? log2 k?+1 7. 在一棵三元树中度为 3 的结点数为 2 个,度为 2 的结点数为 1 个,度为 1 的结点数为 2 个,则度为 0 的结点数为()个 8. 具有 10 个叶结点的二叉树中有() 个度为 2 的结点。 9. 二叉树有 n 个结点,则其深度为( ) A. n-1 C. (log 2 n) +`1 D. 无法确定该题是二叉树不是完全二叉树由二叉树结点的公式: n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1 , 因为 n=1001, 所以 1002=2n0+n1, 在完全二叉树树中, n1 只能取 0或 1, 在本题中只能取 0,故 n=501 , 因此选 E。 10. 一个具有 1025 个结点的二叉树的高 h为() B. 10C. 11至 1025 之间 至 1024 之间 11. 一棵具有 n 个结点的完全二叉树的深度是() A. ? log 2n ?+1 2 n+1 C. ? log 2n ? 2 n-1 12. 将有关二叉树的概念推广到三叉树,则一棵有 244 个结点的完全三叉树的高度() 13. 将一棵有 100 个结点的完全二叉树从根结点这一层开始,每一层上从左到右依次对结点编号,根结点的编号为 1 ,则编号为 49 的结点的左孩子编号为( ) A. 98 利用二叉树的性质 5 14. 在完全二叉树中,若一个结点是叶结点,则它没() A. 左子结点 B. 右子结点 C. 左子结点和右子结点 D. 左子结点,右子结点和兄弟结点 15. 当一棵有 n 个结点的二叉树按层次从上到下,同层次从左到右将数据存放在一维数组 A[l..n] 中时,数组中第 i 个结点的左孩子为() [2i](2i=<n) [2i+1](2i+1=<n) [i/2] D. 无法确定 16. 在下列存储形式中, ()