计130121第次作业.doc

数据结构与算法 上机作业 第四次作业 一、选择题 1、具有n(n1)个结点的完全二叉树中，结点i(2in)的左孩子结点是 D 。 A. 2i B. 2i+1 C. 2i-1 D. 不存在 2、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为 D 。 A. 46 B. 47 C. 90 D. 91 3、在结点数为n的堆中插入一个结点时，复杂度为 C 。 A. O(n) B. O(n2) C. O(log2n) D. O(logn2) 4、两个二叉树是等价的，则它们满足 D 。 A. 它们都为空 B. 它们的左右子树都具有相同的结构 C. 它们对应的结点包含相同的信息 D. A、B和C 5、包含n个元素的堆的高度为 C 。（符号「a表示取不小a最小整数） A. n B. 「log2n C. 「log2(n+1) D. n+1 6、以下说法错误的是 B 。 A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同 B. 二叉树是树的特殊情形 C. 由树转换成二叉树，其根结点的右子树总是空的 D. 在二叉树中只有一棵子树的情形下，也要指出是左子树还是右子树 7、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中没有右孩子的结点有 C 个。 A. n-1 B. n C. n+1 D. n+2 8、将一棵树T转换为二叉树B，则T的后根序列是B的 B 。 A. 先根序列 B. 中根序列 C. 后根序列 D. 层次序列 9、设树T的度为4，其中度为1, 2, 3, 4的结点个数分别为4, 2, 1, 1，则T中的叶结点的个数为 D 。 A. 5 B. 6 C. 7 D. 8 10、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1, M2, M3。与森林F对应的二叉树根结点的右子树上的结点个数为 D 。 A. M1-1 B. M1+M2 C. M2 D. M2+M3 11、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C 。 A. 二叉排序树 B. 哈夫曼树 C. 堆 D. 线索二叉树 12、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是 B 。 A. 32 B. 33 C. 34 D. 15 二、填空题 1、如果一颗完全二叉树的任意一个非终结结点的元素都 不小于 其左儿子结点和右儿子结点(如果有的话)的元素，则称此完全二叉树为最大堆。 2、堆是一种特殊形式的 完全 二叉树，对于最大堆而言，其根结点的元素的值应该是所有结点元素中 最大 的。 3、二叉树的复制是指按照一棵已知的二叉树复制一个副本，使两者 等价 。复制二叉树最长用的方法是 后根遍历递归算法 。 4、在定义堆时，通常采用 结构体 方式定义相应的二叉树，这样可以很容易实现其相关操作。 5、在构建选择树时，根据孩子结点的获胜者确定他们双亲结点所得到的选择树称为 胜者树 。根据孩子结点的失败者确定他们双亲结点所得到的选择树称为 败者树 。 6、树的表示方法包括 数组 、 邻接表 和 左右链 。 7、表达式(a+b*(c-d))-e/f的波兰式(前缀式)是 -+a*b-cd/ef ，逆波兰式(后缀式)是 abcd-*+ef/- 。 8、设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。已知T1, T2, T3的结点数分别为n1, n2和n3，则二叉树B的左子树中有 n1-1 个结点，二叉树B的右子树中有 n2+n3 个结点。 9、设二叉树的中根序列为ABCDEFG，后根序列为BDCAFGE。则该二叉树的先根序列为 EACBDGF 。该二叉树对应的森林中包含 2 棵树。 10、先根次序遍历森林等同于按 先根 遍历对应的二叉树，后根次序遍历森林等同与按 中根