云题海 - 专业文章范例文档资料分享平台

当前位置:首页 > 国家二级C语言公共基础知识要点及历年真题

国家二级C语言公共基础知识要点及历年真题

  • 62 次阅读
  • 3 次下载
  • 2025/7/5 18:37:18

c.树具有明显的层次关系,即树是一种层次结构。 d.数的最大层次称为树的深度。

第5页,共 26 页

f.在树中,叶子结点没有子树。

A E B F C G H D I K L J 如左图中, 1、A 为根结点; 2、E、F、J、H、K、L、 M 为叶子结点。 3、树中A、I 都有 3 个子 结点,故树的度为 3。 M 4、 整个树中, 总共分为4 层,故树的深度为 4。 树形表示法 二叉树 6.2 二叉树及其基本性质

1.什么是二叉树:

二叉树是一种很有用的非线性结构。 二叉树具有以下两个特点: a.非空二叉树只有一个根结点;

b.每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。

由以上特点可以看出,在二叉树中,每一个结点的度最大为2。 2.二叉树的基本性质:(重要)

a.在二叉树的第 k 层上,最多有 2k-1(k>=1)个结点。

b.深度为 m 的二叉树最多有 2m-1 个结点。深度为 m 的二叉树是指二叉树共有 m 层。 c.在任意一棵二叉树中,度为 0 的结点(即叶子结点)总是比深度为 2 的结点多一个。

d.具有 n 个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取 log2n 的整数部分。

A、 第四层中,最多有 24-1=23=8 个结点。 B、树的深度为 4,最多有 24-1=16-1=15 个

结点。 C、度为 0 的结点有 8 个, 度为2 的结点有7

个。

3.满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

a.满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。这就是说,在满二叉树中,每一层上的 结点数都达到最大值,即在满二叉树的第k 层上有 2k-1 个结点,且深度为 m 的满二叉树有 2m-1 个结点。

b.完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。 注意:满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。 完全二叉树还具有以下性质:

a.具有 n 个结点的完全二叉树的深度为log2n] +1。 完全二叉树

满二叉树 非满二叉树 6.3 二叉树的存储结构

在计算机中,二叉树通常采用链式存储结构。 6.4 二叉树的遍历:(重要)

在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、中序遍历、后序遍

第6页,共 26 页

历。

a.前序遍历:首先访问根结点,然后遍历左子树,最后遍历右子树。 b.中序遍历:首先遍历左子树,然后访问根结点,最后遍历右子树。 c.后序遍历:首先遍历左子树,然后遍历右子树,最后访问根结点。

F 1 5 F C 2 E 6 2 C G 7 6 E F 9 C 4 8 G E 8 A 3 D 4 1 A 4 D A 1 D 3 G 7 H 5 B 5 H 8 P 9 3 B 7 H 9 P B 2 P 6 前序:FCADBEGHP 中序:ACBDFEHGP 后序:ABDCHPGEF

注意:在树结构中,每一个结点都代表一棵子树。前序遍历中一定以根结点开头,后序遍历一定以根结点结尾, 而中序遍历中,根结点前面的为树的左子树,而其后面的为树的右子树。

历届的考题:

1、在深度为 7 的满二叉树中,叶子结点的个数为()[2006.4]

A)32 B)31 C)64 D)63 2、对下图 1 所示二叉树

图 1 图 2 进行中序遍历的结果是________。[2006.9]

A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG

3、对如下图 2 所示二叉树,进行后序遍历的结果为()[2006.4]

A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA

4、某二叉树中,度为 2 的结点有 18 个,则该二叉树中有___个叶子结点。[2005.4] 5、一棵二叉树第六层(根结点为第一层)的结点数最多为____个。[2005.9]

1.7 查找技术

7.1 顺序查找:

顺序查找的方法是:用被查元素与线性表中的元素逐一比较, 直到找出相等的元素, 则查找成功;或者找遍

所有元素都不相等,则查找失败。

顺序查找的优点: 对线性表的元素的逻辑次序无要求 (不必对元素进行排序) , 对线性表的存储结构无要求(顺

序存储、链接存储皆可)。

顺序查找的效率很低,但在以下情况下,只能采用顺序查找:

a.如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。 b.即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。 7.2 二分法查找:

第7页,共 26 页

  • 收藏
  • 违规举报
  • 版权认领
下载文档10.00 元 加入VIP免费下载
推荐下载
本文作者:...

共分享92篇相关文档

文档简介:

c.树具有明显的层次关系,即树是一种层次结构。 d.数的最大层次称为树的深度。 第5页,共 26 页 f.在树中,叶子结点没有子树。 A E B F C G H D I K L J 如左图中, 1、A 为根结点; 2、E、F、J、H、K、L、 M 为叶子结点。 3、树中A、I 都有 3 个子 结点,故树的度为 3。 M 4、 整个树中, 总共分为4 层,故树的深度为 4。 树形表示法 二叉树 6.2 二叉树及其基本性质 1.什么是二叉树: 二叉树是一种很有用的非线性结构。 二叉树具有以下两个特点: a.非空二叉树只有一个根结点; b.每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。

× 游客快捷下载通道(下载后可以自由复制和排版)
单篇付费下载
限时特价:10 元/份 原价:20元
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219
Copyright © 云题海 All Rights Reserved. 苏ICP备16052595号-3 网站地图 客服QQ:370150219 邮箱:370150219@qq.com