《考研计算机－习题精炼和重点回顾 树和二叉树 》由会员分享，可在线阅读，更多相关《考研计算机－习题精炼和重点回顾 树和二叉树 （30页珍藏版）》请在金锄头文库上搜索。
1、下列叙述中，树形结构最适合用来描述 您的答案是：【未答】 正确答案是：【C】解析：树形结构是一种层次结构，最适合用来数据元素之间具有层次关系的数据。2对一棵具有 n 个结点的树，其中所有度之和等于 您的答案是：【未答】 正确答案是：【B】解析：在一棵树中，度之和=分支数，而分支数=结点数按照二叉树的定义,具有 3 个结点的二叉树有几种形态？不考虑数据信息的组合情况） 您的答案是：【未答】 正确答案是：【D】解析：如果不考虑结点数据信息的组合情况，具有 3 个结点的二叉树有 5 种形态。其中，只有一棵二叉树具有度为 2 的结点（即为一颗都为 2 的二叉树），其余 4棵二叉树的度均为 1。4以下说
2、法中正确的是 子结点的双亲的左兄弟（如果存在）一定不是叶子结点 子结点数为度为 2 的结点数减 1 i 个结点的左孩子（如果存在）的编号为 2i 您的答案是：【未答】 正确答案是：【A】解析：本题主要考查二叉树的性质以及完全二叉树的定义。其中选项 A 正确；选项 的结点数加 1；选项 C 二叉树可以用顺序结构存储；选项 D 成立的前提是二叉树是完全二叉树。5设二叉树中有 度为 2 的结点，有 度为 1 的结点，有 度为 0 的结点，则该二叉树中空指针的数目为 n1+您的答案是：【未答】 正确答案是：【D】解析：每个度为 1 的结点有 1 个空指针，每个度为 0 的结点有 2 个空指针，度为 2
3、 的结点没有空指针。所以结果为 的树有 8 个度为 1 的结点，有 7 个度为 2 的结点，有 6 个度为 3的结点，有 5 个度为 4 的结点，有 4 个度为 5 的结点，有 3 个度为 6 的结点，有 2 个度为 7 的结点，该树一共拥有的叶子结点的数目是 您的答案是：【未答】 正确答案是：【D】解析：度为 7 的树应该有 1叶结点（与度为 1 的结点的个数无关）。因此，如 示叶结点的个数，则应该有7+26+35+44+53+62=78。（示度为 i 的结点数目）7有 n（n0）个结点的二叉树的深度的最小值是 A. B. C. D. 您的答案是：【未答】 正确答案是：【C】解析：8若某完全
4、二叉树的深度为 h，则该完全二叉树中至少拥有的结点数目是 A. B. C. +1 D. 您的答案是：【未答】 正确答案是：【D】解析：若某完全二叉树的深度为 h，则前 h1 层一定有 2h1 1 个结点，由于第 h 层至少有一个结点，加上前 h1 层的结点总数，得到（2 h1 1）12 h1 个结点，即深度为 h 的完全二叉树中至少有 2h1 个结点。9已知完全二叉树的第 7 层有 10 个叶子结点，则整个二叉树的结点数最多是 您的答案是：【未答】 正确答案是：【C】解析：本题没说明完全二叉树的高度，但根据题意，求二叉树的结点数最多的情况，因此此二叉树只能是 8 层。第 7 层共有 274 个
5、结点，已知有 10 叶子结点，其余 54 个结点均为分支结点。它在第 8 层上有 108 个叶子结点。所以该二叉树的结点数最多可达（2 708）=235。10将有关二叉树的概念推广到三叉树，则一棵有 244 个结点的完全三叉树的高度是 您的答案是：【未答】 正确答案是：【C】解析：由有 n 个结点的完全三叉树的高度为11若用一维数组保存一个深度为 5、结点个数 10 的二叉树，数组的长度至少为 您的答案是：【未答】 正确答案是：【C】解析：本题主要考查二叉树的性质和二叉树的顺序存储方法。由于二叉树的顺序存储是按完全二叉树来存储，根据二叉树的性质：深度为 k 的二叉树最多有 2结点，深度为 5
6、的二叉树最多有 31 个结点，所以存储这些结点需要数组的长度至少为 31，答案应为 n 个结点的二叉树采用二叉链表存储结构，链表中空的指针域的数目是 您的答案是：【未答】 正确答案是：【C】解析：具有 n 个结点的二叉树采用二叉链表存储结构，则该链表中共有 2n 个指针域，其中，有 n1 个指针域存放指向孩子结点的地址，剩余的 n1 个指针域为空。13某二叉树 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，编号为1，2，n，具有如下性质：要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中。其左孩子的编号小于其右孩子的编号，可采用的遍历形式是 您的答案是：【未答】 正确
7、答案是：【C】解析：对照后序遍历的先后关系（左右子树的大小关系，双亲和孩子结点的相对关系），可以很容易判断出该编号是后序遍历。14若非空二叉树的先序序列与后序序列的次序正好相反，则该二叉树一定是 您的答案是：【未答】 正确答案是：【D】解析：先序遍历序列是“根左右”，后序遍历序列是“左右根”，若要两个序列相反，只有当二叉树中分支结点的度都为 1 时，即任一分支结点只有左孩子或是只有右孩子，先序遍历与后序遍历的次序正好相反。本题的选项 A、B、C 都符合要求但都不完整。15若非空二叉树的先序序列与中序序列的次序正好相反，则该二叉树一定是 您的答案是：【未答】 正确答案是：【D】解析：先序遍历序列
8、是“根左右”，中序遍历序列是“左根右”，若要两个序列相反，说明对于任何分支结点都没有右子树，即其中任一结点无右孩子。16若非空二叉树的中序序列与后序序列的次序正好相同，则该二叉树一定是 您的答案是：【未答】 正确答案是：【D】解析：中序遍历序列是“左根右”，后序遍历序列是“左右根”，若要两个序列相同，说明对于任何分支结点都没有右子树，即其中任一结点无右孩子。17任何一棵非空二叉树中的叶子结点在先序遍历、中序遍历与后序遍历中的相对位置 您的答案是：【未答】 正确答案是：【B】解析：无论是先序遍历（是中序遍历（或是后序遍历（对于叶子结点而言，被访问的先后次序都是先左后右，因此，叶子结点在先序遍历、
9、中序遍历与后序遍历中的相对位置都不会发生改变。18已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为A、B、C、D、E、F、G、H、I、J，该完全二叉树的后序遍历序列为 您的答案是：【未答】 正确答案是：【A】解析：先根据二叉树的顺序存储结构将二叉树恢复，然后对二叉树进行后序遍历即可。19二叉树的先序遍历序列为 序遍历序列为 后序遍历序列为 您的答案是：【未答】 正确答案是：【B】解析：根据二叉树的先序序列和中序序列可以唯一地恢复二叉树，原则是：在先序序列中确定根结点的信息（任何一个二叉树/子树的先序序列中第一个结点为根结点），而中序序列中提供了由根结点将整个序列分为左、右子树的信
10、息。因此，本题先根据先序序列和中序序列将二叉树恢复出来，然后对二叉树进行后序遍历，即可得到后序序列。20已知某二叉树的先序序列为 可能的中序序列为 您的答案是：【未答】 正确答案是：【A】解析：二叉树的先序序列可以分为连续的 3 个部分：第一个是根结点，后面分别是左子树部分和右子树部分。中序遍历也可分为 3 个部分：左子树部分、根结点、右子树部分。题目给出的先序序列为 知 A 为根结点，选项 A 给出中序序列表示 左子树部分，右子树部分，和先序序列不矛盾，是可能的中序序列。选项 B 给出的序列表示 左子树，右子树，这两个部分在先序序列 不连续，说明不是可能的中序序列。同理，选项 C 和选项D
11、也不是可能的中序序列。21n 个结点的线索二叉树上含有的线索数为 您的答案是：【未答】 正确答案是：【C】解析：线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有 n1 个空链域。22线索二叉树与一般的二叉树相比，它更容易找到二叉树中结点的 您的答案是：【未答】 正确答案是：【D】解析：线索二叉树的作用即方便查找前驱和后继。23一棵左右子树均不为空的二叉树在先序线索化后，其中空链域的个数是 您的答案是：【未答】 正确答案是：【C】解析：对于一棵左右子树均不为空的二叉树，先序线索化后只有一个空链域，即先序序列的最后结点的右指针为空。24下面有关在中序线索树中查找指定结点的先序后继的问题
12、中，下列说法错误的是 指定结点有左孩子，则左孩子是它的先序后继，若指定结点没有左孩子，则右孩子是它的先序后继 指定结点是“某结点 X”的左子树中按先序遍历列出的最后一个结点，则该结点 X 又有右孩子，则指定结点的先序后继就是该结点 X 的右孩子 指定结点虽然是“某结点 X”的左子树中按先序遍历列出的最后一个结点，但该结点 X 没有右孩子，则指定结点没有先序后继 指定结点不是任何结点的左子树中按先序遍历列出的最后一个结点，则指定结点的先序后继为根结点 您的答案是：【未答】 正确答案是：【D】解析：选项 D 中，因为根结点必然为第一个访问结点，所以无论如何，叶子结点的后继都不会是根结点。25对于非空满 k 叉树，其分支结点数目为 n，则该树中叶子结点的数目为 A.n( D.n（1 您的答案是：【未答】 正确答案是：【D】解析：本题主要考查满 k 叉树叶子结点个数的计算。设树的深度为 t+1，则叶子结点的个数为 有，其分支结点数目为 n，所以n=1+k1+k (叶子结点的个数为 n（126设二叉树是由森林变换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点有
