《树和二叉树习题及答案.docx》由会员分享，可在线阅读，更多相关《树和二叉树习题及答案.docx（6页珍藏版）》请在三一文库上搜索。
1、树和二叉树习题及答案一、 填空题1、 不相交的树的聚集称之为森林。2、从概念上讲 , 树与二叉树就是两种不同的数据结构 , 将树转化为二叉树的基本目的就是 _树 可 采 用 孩 子 - 兄弟 链表 ( 二叉 链表 ) 做 存 储 结 构 , 目 的 就 是利用二 叉树 的已 有算 法 解决 树的 有关 问题 。3、 深 度 为 k 的完 全二 叉树 至少 有 2 k-1 个 结点 。 至 多有 2 k -1 个 结点 , 若按自 上而 下 , 从 左到 右次 序给 结点 编 号 ( 从 1 开始 ), 则 编 号最 小的叶子结 点的 编号 就是 2 k-2 +1。4、在 一 棵二 叉树 中 ,
2、 度为 零 的结 点 的 个数 为 n 0 , 度 为 2 的 结点 的个数为 n 2 , 则有 n 0 = n 2+1。5、 一 棵 二叉 树的 第 i(i 1) 层 最多 有 2 i-1个 结点 ; 一 棵 有 n(n0)个结点的 满二 叉树 共有 (n+1)/2个叶子 与 (n-1) /2个非终端 结 点。6. 现有按 中序 遍历 二叉 树 的结 果为 abc, 问 有 5 种不 同形 态的 二 叉树可以得 到这 一遍 历结 果 。7、 哈夫曼树就是带权路径最小的二叉树。8、 前缀编码就是指任一个字符的编码都不就是另一个字符编码的前缀的一种编码方法 , 就是设计不等长编码的前提。9、以给
3、定的数据集合 4,5,6,7,10,12,18为结点权值构造的Huffman 树的加权路径长度就是165。10、 树被定义为连通而不具有回路的 ( 无向 ) 图。11、 若一棵根树的每个结点最多只有两个孩子 , 且孩子又有之分 , 次序不能颠倒 , 则称此根树为二叉树。12、 高度为 k, 且有个结点的二叉树称为二叉树。左、右2k-1满13、带权路径长度最小的二叉树称为最优二叉树, 它又被称为树。Huffman14、 在一棵根树中 , 树根就是为零的结点 , 而为零的结点就是结点。入度出度树叶树和二叉树习题及答案15、 Huffman 树中 , 结点的带权路径长度就是指由到之间的路径长度与结点
4、权值的乘积。结点树根16、 满二叉树就是指高度为 k, 且有个结点的二叉树。二叉树的每一层 i 上,最多有个结点。2 k-12i-1二、单选题1、 具有 10 个叶结点的二叉树中有 (B)个度为 2 的结点。(A)8(B)9(C)10(D)112. 对二叉树的结点从 1 开始进行连续编号 , 要求每个结点的编号大于其左右孩子的编号 , 同一结点的左右孩子中 , 其左孩子的编号小于其右孩子的编号 , 则可采用 _(3) 次序的遍历实现编号。(1) 先序(2)中序(3) 后序(4)从根开始按层遍历3、 由 2、 3、4、7 作为结点权值构造的树的加权路径长度B。A、33B、30C、36D、404、
5、 高度为 6 的满二叉树 , 总共有的结点数就是B。A、15B、63C、20D、255、 下面描述根树转换成二叉树的特性中, 正确的就是 C。A 、根树转换成的二叉树就是唯一的 , 二叉树的根结点有左、右孩子。B 、根树转换成的二叉树就是不唯一的 , 二叉树的根结点只有左孩子。C 、根树转换成的二叉树就是唯一的 , 二叉树的根结点只有左孩子。D 、根树转换成的二叉树就是不唯一的 , 二叉树的根结点有左、 右孩子。6、 如图所示的 4 棵二叉树中 , 不就是完全二叉树的就是。A、B、 树和二叉树习题及答案C、D、C7、某二叉树先序遍历的结点序列就是则其后序遍历的结点序列就是 dgbaechf,a
6、bdgcefh,D中序遍历的结点序列就是。A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca8、 已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK,按后序遍历所得到的结点序列为DCEGBFHKJIA,按先序遍历所得到的结点序列为ABCDGEIHFJK。9、 设 n,m 为一棵二叉树上的两个结点, 在中序遍历时 ,n 在 m前的条件就是C 。A、n 在 m右方B、 n 就是 m祖先C、n 在 m左方D、 n 就是 m子孙10、 二叉树第 i 层结点的结点个数最多就是( 设根的层数为 1) :AA)2 i-1B)2i -1C)2iD) 2i-111、 树的
7、后根遍历序列等同于该树对应的二叉树的: BA)先序序列B)中序序列C)后序序列12、树最适合用来表示_C_。A 、有序数据元素B 、无序数据元素C 、 元素之间具有分支层次关系的数据D、 元素之间无联系的数据13、 由于二叉树中每个结点的度最大为2, 所以二叉树就是一种特殊的树, 这种说法 _B_。A、 正确B 、 错误14、 假定在一棵二叉树中 , 双分支结点数为15, 单分支结点数为30 个 , 则叶子结树和二叉树习题及答案点数为B个。A.15B.16C.17D.4715、 按照二叉树的定义 , 具有 3 个结点的不同形状的二叉树有_C_种。A 、 3B 、 4C、 5D 、 616、 深
8、度为 5 的二叉树至多有 _C_个结点。A 、 16B 、 32C、 31D、 1017、 对一个满二叉树 ,m 个树叶 ,n 个结点 , 深度为 h, 则_D_ 。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-118、任何一棵二叉树的叶结点在先序、 中序与后序遍历序列中的相对次序_A_。A、不发生改变B 、发生改变C、不能确定D、以上都不对19、如果某二叉树的前根次序遍历结果为stuwv, 中序遍历为 uwtvs, 那么该二叉树的后序为 _C_。A、uwvtsB、vwutsC、wuvtsD、wutsv20、 二叉树的前序遍历序列中, 任意一个结点均处在其子女结点的前面, 这种说法
9、 _A_。A、 正确B 、 错误21、 在一非空二叉树的中序遍历序列中, 根结点的右边 _A_。A 、 只有右子树上的所有结点B 、 只有右子树上的部分结点C、 只有左子树上的部分结点D 、 只有左子树上的所有结点22、已知某二叉树的后序遍历序列就是dabec, 中序遍历序列就是debac, 它的前序遍历序列就是 _D_。A 、 acbedB 、 decabC 、 deabcD、 cedba23、实现任意二叉树的后序遍历的非递归算法而不使用栈结构, 最佳方案就是二叉树采用 _C_存储结构。树和二叉树习题及答案A、二 叉 链表B、广 义表 存储 结构C、三叉 链 表D、顺 序存储结构24、 在线
10、索化二叉树中 ,t所指结点没有左子树的充要条件就是A 、 t left=NULL_B_。B 、 tltag=1C 、t ltag=1且 t left=NULLD、 以上都不对25、 二叉树按某种顺序线索化后, 任一结点均有指向其前驱与后续的线索, 这种说法 _B_。A、 正确B 、 错误26、树的基本遍历策略可分为先根遍历与后根遍历; 二叉树的基本遍历策略可分为先序遍历、中序遍历与后序遍历。这里, 我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_A_就是正确的。A 、树的先根遍历序列与其对应的二叉树的先序遍历序列相同B 、树的后根遍历序列与其对应的二叉树的后序遍历序列相同C、树的先根遍
11、历序列与其对应的二叉树的中序遍历序列相同D、以上都不对6、42 统计二叉树中叶子结点的个数 ( 先序遍历 )Void CountLeaf( B iTree T, int & count) if( T) if( ( ！ T -Lchild ) & & (！T -Rchild ) )Count+ ; / 计数器加1CountLeaf ( T -Lchild , count );CountLeaf ( T -Rchild , count);2、编写算法实现求以二叉链表表示的二叉树的深度的递归算法。Int Depth(BiTree T)if(！ T)return 0;else h1=Depth( T -Lchild);h2=Depth( T -Rchild);if(h1=h2)return h1+1;else return h2+1;/Depth6、43 交换所有结点的左右子树void Bitree_Revolute(Bitree T)树和二叉树习题及答案if(T)T-lchildT-rchild; / 交换左右子树if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bitree_Revolute(T-rchild);/左右子树再分别交换各自的左右子树/Bitree_Revolute