《数据结构第五章自测题及解答》由会员分享，可在线阅读，更多相关《数据结构第五章自测题及解答（4页珍藏版）》请在金锄头文库上搜索。
1、一、 概念题（每空1分，共53分）1树（及一切树形结构）是一种“_”结构。在树上，_结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的_。2由个结点所构成的二叉树有 种形态。3一棵深度为6的满二叉树有 个分支结点和 个叶子。4一棵具有个结点的完全二叉树，它的深度为 。5二叉树第i(i=1)层上至多有_个结点；深度为k(k=1)的二叉树至多有_个结点。6对任何二叉树，若度为2的节点数为n2，则叶子数n0=_。7满二叉树上各层的节点数已达到了二叉树可以容纳的_。满二叉树也是_二叉树，但反之不然。8设一棵完全二叉树有700个结点，则共有 个叶子结点。9.设一棵完全二叉树具有100
2、0个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。10.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度为 。11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。12.中序遍历的递归算法平均空间复杂度为 。13.二叉树通常有_存储结构和_存储结构两类存储
3、结构。14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1=in，则结点X无_且无_；否则，X的左孩子LCHILD(X)的编号为_。（3） 若2i+1n，则结点X无_；否则，X的右孩子RCHILD(X)的编号为_。15. 每个二叉链表的访问只能从_结点的指针，该指针具有标识二叉链表的作用。16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是_的指针，或者是_。17.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。18.二叉树有不同的链式存储结构，其中最常用的是_与_。19.若二叉树的一个叶子是某子树的中根遍
4、历序列中的第一个结点，则它必是该子树的后根遍历序列中的_个结点。20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为_和_，即使在结点只有一棵子树的情况下，也要明确指出该子树是_还是_。21.树的结点数目至少为_，二叉树的结点数目至少为_。22.树的主要遍历方法有_、_、_等三种。23.由_转换成二叉树时，其根结点的右子树总是空的。24.哈夫曼（Huffman）树是带权路径度_的树，通常权值较大的结点离根_。25.用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。二、 选择题（每空1分，共12分）（ ）1 不含任何结点的空树 。（）是一棵树;
5、（）是一棵二叉树; （）是一棵树也是一棵二叉树; （）既不是树也不是二叉树（ ）2二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使用 （ ）3. 具有n(n0)个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1（ ）4把一棵树转换为二叉树后，这棵二叉树的形态是 。（）唯一的 （）有多种（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子5. 树是结点的有限集合，它 A 根结点，记
6、为T。其余的结点分成为m（m0）个 B 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。一个结点的子结点个数为该结点的 C 。供选择的答案A： 有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交C： 权 维数 次数 序答案：A= B= C= 6. 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。供选择的
7、答案A： 是特殊的树 不是树的特殊形式 是两棵树的总称 有是只有二个根结点的树形结构 B: 左子结点 右子结点 左子结点或者没有右子结点 兄弟CD： 最左子结点 最右子结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= D 7. 以下说法错误的是 ( ) 一般在哈夫曼树中，权值越大的叶子离根结点越近哈夫曼树中没有度数为1的分支结点若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树三、 综合题（1-9每题3分，10-11每题4分,共35分）1给定二叉树的两种遍历序列，分别是：前
8、序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B。2825 3340 60 08 54 552. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。3试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。4. 把如图所示的树转化成二叉树。5. 编写递归算法，计算二叉树中叶子结点的数目。6. 写出求二叉树深度的算法。 7. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。8编写算法判别给定二叉树是否为完全二叉树。9. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0
9、.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。10. 试编写最小堆类的下滑调整算法成员函数。（注：程序头已给出，类定义略：已通过数组heap建堆）template void MinHeap:siftDown(int start, int m)11.Suppose you have a binary tree whose data fields are single characters. When the data fields of the nodes are output in inorder, the output is ABCDEFGHIJ, and when they are output in preorder, the output is ADBCJGFEHI. Draw the binary tree showing the data in each node and the pointers between nodes.参考答案
