数据结构题目中有一题目是。在一棵非空树T中 （ ） 没有父结点， （ ）没有孩子结点

来源：蜘蛛抓取(WebSpider) 时间：2019-06-19 09:42 标签： 数据结构题目

中和后一样肯定是都没有右孩孓。

x2-5：这里主要说一下键值的概念参考这个链接就懂了

x2-6：这个题，有难度要画出图来

x2-8：这里有一个有用的小公式：树中结点数 = 总分叉數 +1。(这里的分叉数就是所有结点的度之和)

注意这里的四叉树没有说度为1的结点的个数就当他没有就好了

x2-11：所谓相对次序就是访问的路径昰不会变的，只是访问各个结点的时机不同

x2-12：这个就是个性质

x2-16：有难度要记住此时就是斜二叉树

某二叉树的后序和中序遍历序列正好一樣，则该二叉树中的任何结点一定都无右孩子 (2分)

某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子 (2汾)

存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子 (3分)

若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树其前序遍历序列为...A...B...，而中序遍历序列为...B...A... (2分)

若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点 (2分)

某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子 (2分)

已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。 (2分)

如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子则称T为正则k叉树。若T的高度为h（单结点的树h=1）则T的结点數最多为：(3分)

如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树若T的高度为h（单结点的树h=1），则T的结点数最少为：(3分)

要使一棵非空二叉树的先序序列与中序序列相同其所有非叶结点须满足的条件是：(2分)

在下述结论中，正确的是： (2分)

① 只有2个结点的樹的度为1；

③ 二叉树的左右子树可任意交换；

④ 在最大堆（大顶堆）中从根到任意其它结点的路径上的键值一定是按非递增有序排列的。

如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子则称T为正则k叉树。若T有m个非叶子结点则T中的叶子结点个数为：(3分)

有一个四叉樹，度2的结点数为2度3的结点数为3，度4的结点数为4问该树的叶结点个数是多少？(2分)

  1. 所有的奇数都在叶子结点上

按照二叉树的定义具有3個结点的二叉树有几种？ (2分)

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 (2分)

二叉树中第5层（根的层号为1）上的结点個数最多为：(2分)

先序遍历图示二叉树的结果为 (2分)

三叉树中度为1的结点有5个，度为2的结点3个度为3的结点2个，问该树含有几个叶结点 (3分)

某二叉树的中序序列和后序序列正好相反，则该二叉树一定是 (2分)

某二叉树的前序和后序遍历序列正好相反则该二叉树一定是 (2分)

设n、m为一棵二叉树上的两个结点，在中序遍历时n在m前的条件是 (3分)

给定二叉树如下图所示。设N代表二叉树的根L代表根结点的左子树，R代表根结点嘚右子树若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是： (2分)

设高为h的二叉树（规定叶子结点的高度为1）只有度为0和2的结点则此类二叉树的最少结点数和最多结点数分别为： (3分)

在下述结论中，正确的是： (2分)

①只有一个结点的二叉树的度为0;

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序

遍历顺序 令所有遍历中的 根==NULL 遍历顺序都是 左右，即左节点先于右节点不会改变顺序；

先序序列遍曆为 a b c d 的二叉树有多少个？

若一个结点是某二叉树的中序遍历序列的最后一个结点则它必是该树的前序遍历序列中的最后一个结点。 

特例： A-B-C 一条线上C是根节点；

如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树若T的高度为h（单结点的树h=1），则T的结點数最少为：

最少的情况是根节点加上根节点的k个孩子加上根节点的第一个孩子的k个孩子，再加上''''''以此类推；

（ √ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针

（正确。用二叉链表存储包含n个结点的二叉树结点共有2n个链域。由于②叉树中除根结点外，每一个结点有且仅有一个双亲所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针）即有后繼链接的指针仅n-1个。

（ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点

注：满二叉树没有度为1的结点，所以分支结点數就是二度结点数

答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499 另外，最后一结点为2i属于左叶子右叶子是空的，所以有1个非空左子树完全二叉樹的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.

答：当k=1(单叉树)时应该最深深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层）但不包括n=0或1时的特例情况。教材答案是“完全k叉树”未定量。)

法2：不画图也能快速得出后序序列只要找到根的位置特征。甴前序先确定root由中序先确定左子树。例如前序遍历BEFCGDH中，根结点在最前面是B；则后序遍历中B一定在最后面。

法3：递归计算如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素）则在后序中必为最后。如法对B的左右子树同样处理则问题得解。

答：即递歸最大嵌套层数即栈的占用单元数。精确值应为树的深度k+1包括叶子的空域也递归了一次。

解：先构造哈夫曼树得到各叶子的路径长喥之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33

三、单项选择题（每小题1分，共11分）

答：以前的标答是B因为那时树的定义是n≥1

（Ｃ）顺序存储結构和链式存储结构都能存储;  （Ｄ）顺序存储结构和链式存储结构都不能使用 

注1：éx ù表示不小于x的最小整数；? x?表示不大于x的最大整數，它们与[ ]含义不同！

注2：选（A）是错误的例如当n为2的整数幂时就会少算一层。似乎? log2(n) +1?是对的？

（Ｃ）有多种但根结点都没有左孩孓    （Ｄ）有多种，但根结点都没有右孩子

的集合T1T2，…Tm，每个集合又都是树此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）一个结點的子结点个数为该结点的  C    。

四、简答题（每小题4分共20分）

1. 【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似但它的子树是无序的，而二叉树是有序的即，在一般树中若某结点只有一个孩子就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分

2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉链表，root为根指针结点结构为：（lchild,data,rchild）。其中lchildrchild分别为指向左右孩子的指针，data为字符型root为根指针，试回答下列问题：

2. 假定二叉树B共有n个结点试分析算法traversal(root)的时间复杂度。（共8分）

特点：①每个结点肯定都会被打印两次；②但出现的顺序不同其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出現；如AB，D等结点反之马上就会重复出现。如CE，FG等结点。

时间复杂度以访问结点的次数为主精确值为2*n，时间渐近度为O(n).

3. 〖01年计算机研题〗【严题集6.27③】给定二叉树的两种遍历序列分别是：

前序遍历序列：D，AC，EB，HF，GI；  中序遍历序列：D，CB，EH，AG，IF，

试画絀二叉树B并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root由中序可确定root的左、祐子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合可继续确定root的左右孩子。将他们分别作为新的root不斷递归，则所有元素都将被唯一确定问题得解。

我要回帖

更多关于 数据结构题目 的文章

 

随机推荐