问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

麻烦你能不能给我也发一份2011年二级C的公共基础知识呢,我明年也要考。。。谢谢了。。

发布网友 发布时间:2022-04-28 12:31

我来回答

1个回答

热心网友 时间:2023-10-09 04:54

经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。

1.算法的概念、算法时间复杂度及空间复杂度的概念

2.数据结构的定义、数据逻辑结构及物理结构的定义

3.栈的定义及其运算、线性链表的存储方式

4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历

5.二分查找法

6.冒泡排序法

1.1算法

考点1 算法的基本概念

考试链接

考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。

计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。

1.算法的基本特征可行性、确定性、有穷性、拥有足够的情报。

2.算法的基本要素

算法中对数据的运算和操作

一个算法由两种基本要素组成一是对数据对象的运算和操作;二是算法的控制结构。

在一般的计算机系统中,基本的运算和操作有以下4类算术运算、逻辑运算、关系运算和数据传输。

算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

考点2 算法复杂度

考试链接

考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。

1.算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法运行工作量的大小,只依赖于问题的规模,它是问题规模的函数。即

算法的工作量=f

2.算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数,则称该算法是原地工作的。在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的额外空间。

疑难解答算法的工作量用什么来计算?

算法的工作量用算法所执行的基本运算次数来计算,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量=f,其中n是问题的规模。

1.2数据结构的基本概念

考点3 数据结构的定义

考试链接

考点3在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为识记内容,读者还应该识记数据的逻辑结构和存储结构的概念。

数据结构作为计算机的一门学科,主要研究和讨论以下三个方面

数据集合中个数据元素之间所固有的逻辑关系,即数据的逻辑结构;

在对数据元素进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;

对各种数据结构进行的运算。

数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合,是数据的一个子集。

数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成

B=

其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系,在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,选择合适的存储结构是很重要的。

考点4 线性结构与非线性结构

考试链接

考点4在笔试考试中,虽然说不是考试经常考查的内容,但读者还是对此考点有所了解,在笔试考试中出现的几率为30%,主要是以填空题出现的形式出现,分值为2分,此考点为识记内容。

根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件

有且只有一个根结点;

每一个结点最多有一个前件,也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构,则称之为非线性结构。

疑难解答空的数据结构是线性结构还是非线性结构?

一个空的数据结构究竟是属于线性结构还是属于非线性结构,这要根据具体情况来确定。如果对该数据结构的算法是按线性结构的规则来处理的,则属于线性结构;否则属于非线性结构。

1.3栈及线性链表

考点5 栈及其基本运算

考试链接

考点5在笔试考试中,是一个必考的内容,在笔试考试中出现的几率为100%,主要是以选择的形式出现,分值为2分,此考点为重点掌握内容,读者应该掌握栈的运算 。

1.栈的基本概念

栈是限定只在一端进行插入与删除的线性表,通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。栈是按照先进后出或后进先出的原则组织数据的。

2.栈的顺序存储及其运算

用一维数组S作为栈的顺序存储空间,其中m为最大容量。

在栈的顺序存储空间S中,S为栈底元素,S为栈顶元素。top=0表示栈空;top=m表示栈满。

栈的基本运算有三种入栈、退栈与读栈顶元素。

入栈运算入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈上溢错误。

退栈运算退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素赋给一个指定的变量,然后将栈顶指针减一。当栈顶指针为0时,说明栈空,不可进行退栈操作。这种情况称为栈的下溢错误。

读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素,只是将它赋给一个变量,因此栈顶指针不会改变。当栈顶指针为0时,说明栈空,读不到栈顶元素。

小技巧栈是按照先进后出或后进先出的原则组织数据,但是出栈方式有多种选择,在考题中经常考查各种不同的出栈方式。

考点6 线性链表的基本概念

考试链接

考点6在笔试考试中出现的几率为30%,主要是以选择的形式出现,分值为2分,此考点为识记内容。重点识记结点的组成。

在链式存储方式中,要求每个结点由两部分组成一部分用于存放数据元素值,称为数据域,另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点。

链式存储方式既可用于表示线性结构,也可用于表示非线性结构。

线性链表

线性表的链式存储结构称为线性链表。

在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。

带链的栈

栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。

疑难解答在链式结构中,存储空间位置关系与逻辑关系是什么?

在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。

1.4树与二叉树

考点7 树与二叉树及其基本性质

考试链接

考点7在笔试考试中,是一个必考的内容,在笔试考试中出现的几率为100%,主要是以选择的形式出现,有时也有出现在填空题中,分值为2分,此考点为重点掌握内容。重点识记树及二叉树的性质。

误区警示

满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。应该注意二者的区别。

1、树的基本概念

树(tree是一种简单的非线性结构。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点。每一个结点可以有多个后件,它们称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0。在树中,所有结点中的最大的度称为树的度。

2、二叉树及其基本性质

二叉树的定义

二叉树是一种很有用的非线性结构,具有以下两个特点

①非空二叉树只有一个根结点;

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

由以上特点可以看出,在二叉树中,每一个结点的度最大为2,即所有子树也均为二叉树,而树结构中的每一个结点的度可以是任意的。另外,二叉树中的每个结点的子树被明显地分为左子树和右子树。在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即为叶子结点。

二叉树的基本性质

二叉树具有以下几个性质

性质1在二叉树的第k层上,最多有2k-1个结点;

性质2深度为m的二叉树最多有2m-1个结点;

性质3在任意一棵二叉树中,度为0的结点总是比度为2的结点多一个。

性质4具有n个结点的二叉树,其深度至少为〔log2n〕+1,其中〔log2n〕表示取log2n的整数部分。

小技巧在二叉树的遍历中,无论是前序遍历,中序遍历还是后序遍历,二叉树的叶子结点的先后顺序都是不变的。

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

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

完全二叉树是指这样的二叉树除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。

完全二叉树具有以下两个性质

性质5具有n个结点的完全二叉树的深度为〔log2n〕+1。

性质6设完全二叉树共有n个结点。如果从根结点开始,按层次用自然数1,2,,n给结点进行编号,则对于编号为k的结点有以下结论

①若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点编号为INT。

②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点。

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。

考点8 二叉树的遍历

考试链接

考点8在笔试考试中考核几率为30%,分值为2分,读者应该熟练掌握各种遍历的具体算法,能由两种遍历的结果推导另一种遍历的结果。

在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。在先左后右的原则下,根据访问根结点的次序,二叉树的遍历分为三类前序遍历、中序遍历和后序遍历。

前序遍历先访问根结点、然后遍历左子树,最后遍历右子树;并且,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。

中序遍历先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。

后序遍历先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。

疑难解答树与二叉树的不同之处是什么?

在二叉树中,每一个结点的度最大为2,即所有子树也均为二叉树,而树结构中的每一个结点的度可以是任意的。

1.5查找技术

考点9 顺序查找

考试链接

考点9在笔试考试中考核几率在30%,一般出现选择题中,分值为2分,读者应该具体掌握顺序查找的算法。

查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;若线性表中所有的元素都与被查找元素进行了比较但都不相等,则表示查找失败。

在下列两种情况下也只能采用顺序查找

如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找。

即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。

考点10 二分法查找

考试链接

考点10在笔试考试中考核几率为30%,一般出现填空题中,分值为2分,考核比

热心网友 时间:2023-10-09 04:54

经过对部分考生的调查以及对近年真题的总结分析,笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,读者应对此部分进行重点学习。

1.算法的概念、算法时间复杂度及空间复杂度的概念

2.数据结构的定义、数据逻辑结构及物理结构的定义

3.栈的定义及其运算、线性链表的存储方式

4.树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历

5.二分查找法

6.冒泡排序法

1.1算法

考点1 算法的基本概念

考试链接

考点1在笔试考试中考核的几率为30%,主要是以填空题的形式出现,分值为2分,此考点为识记内容,读者还应该了解算法中对数据的基本运算。

计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。

1.算法的基本特征可行性、确定性、有穷性、拥有足够的情报。

2.算法的基本要素

算法中对数据的运算和操作

一个算法由两种基本要素组成一是对数据对象的运算和操作;二是算法的控制结构。

在一般的计算机系统中,基本的运算和操作有以下4类算术运算、逻辑运算、关系运算和数据传输。

算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

考点2 算法复杂度

考试链接

考点2在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念。

1.算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。

同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行,效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素,可以认为一个特定算法运行工作量的大小,只依赖于问题的规模,它是问题规模的函数。即

算法的工作量=f

2.算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数,则称该算法是原地工作的。在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的额外空间。

疑难解答算法的工作量用什么来计算?

算法的工作量用算法所执行的基本运算次数来计算,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量=f,其中n是问题的规模。

1.2数据结构的基本概念

考点3 数据结构的定义

考试链接

考点3在笔试考试中,是一个经常考查的内容,在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分,此考点为识记内容,读者还应该识记数据的逻辑结构和存储结构的概念。

数据结构作为计算机的一门学科,主要研究和讨论以下三个方面

数据集合中个数据元素之间所固有的逻辑关系,即数据的逻辑结构;

在对数据元素进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;

对各种数据结构进行的运算。

数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合,是数据的一个子集。

数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成

B=

其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系,在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,选择合适的存储结构是很重要的。

考点4 线性结构与非线性结构

考试链接

考点4在笔试考试中,虽然说不是考试经常考查的内容,但读者还是对此考点有所了解,在笔试考试中出现的几率为30%,主要是以填空题出现的形式出现,分值为2分,此考点为识记内容。

根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件

有且只有一个根结点;

每一个结点最多有一个前件,也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构,则称之为非线性结构。

疑难解答空的数据结构是线性结构还是非线性结构?

一个空的数据结构究竟是属于线性结构还是属于非线性结构,这要根据具体情况来确定。如果对该数据结构的算法是按线性结构的规则来处理的,则属于线性结构;否则属于非线性结构。

1.3栈及线性链表

考点5 栈及其基本运算

考试链接

考点5在笔试考试中,是一个必考的内容,在笔试考试中出现的几率为100%,主要是以选择的形式出现,分值为2分,此考点为重点掌握内容,读者应该掌握栈的运算 。

1.栈的基本概念

栈是限定只在一端进行插入与删除的线性表,通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。栈是按照先进后出或后进先出的原则组织数据的。

2.栈的顺序存储及其运算

用一维数组S作为栈的顺序存储空间,其中m为最大容量。

在栈的顺序存储空间S中,S为栈底元素,S为栈顶元素。top=0表示栈空;top=m表示栈满。

栈的基本运算有三种入栈、退栈与读栈顶元素。

入栈运算入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈上溢错误。

退栈运算退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素赋给一个指定的变量,然后将栈顶指针减一。当栈顶指针为0时,说明栈空,不可进行退栈操作。这种情况称为栈的下溢错误。

读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素,只是将它赋给一个变量,因此栈顶指针不会改变。当栈顶指针为0时,说明栈空,读不到栈顶元素。

小技巧栈是按照先进后出或后进先出的原则组织数据,但是出栈方式有多种选择,在考题中经常考查各种不同的出栈方式。

考点6 线性链表的基本概念

考试链接

考点6在笔试考试中出现的几率为30%,主要是以选择的形式出现,分值为2分,此考点为识记内容。重点识记结点的组成。

在链式存储方式中,要求每个结点由两部分组成一部分用于存放数据元素值,称为数据域,另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点。

链式存储方式既可用于表示线性结构,也可用于表示非线性结构。

线性链表

线性表的链式存储结构称为线性链表。

在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。

带链的栈

栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。

疑难解答在链式结构中,存储空间位置关系与逻辑关系是什么?

在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。

1.4树与二叉树

考点7 树与二叉树及其基本性质

考试链接

考点7在笔试考试中,是一个必考的内容,在笔试考试中出现的几率为100%,主要是以选择的形式出现,有时也有出现在填空题中,分值为2分,此考点为重点掌握内容。重点识记树及二叉树的性质。

误区警示

满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。应该注意二者的区别。

1、树的基本概念

树(tree是一种简单的非线性结构。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点。每一个结点可以有多个后件,它们称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0。在树中,所有结点中的最大的度称为树的度。

2、二叉树及其基本性质

二叉树的定义

二叉树是一种很有用的非线性结构,具有以下两个特点

①非空二叉树只有一个根结点;

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

由以上特点可以看出,在二叉树中,每一个结点的度最大为2,即所有子树也均为二叉树,而树结构中的每一个结点的度可以是任意的。另外,二叉树中的每个结点的子树被明显地分为左子树和右子树。在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即为叶子结点。

二叉树的基本性质

二叉树具有以下几个性质

性质1在二叉树的第k层上,最多有2k-1个结点;

性质2深度为m的二叉树最多有2m-1个结点;

性质3在任意一棵二叉树中,度为0的结点总是比度为2的结点多一个。

性质4具有n个结点的二叉树,其深度至少为〔log2n〕+1,其中〔log2n〕表示取log2n的整数部分。

小技巧在二叉树的遍历中,无论是前序遍历,中序遍历还是后序遍历,二叉树的叶子结点的先后顺序都是不变的。

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

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

完全二叉树是指这样的二叉树除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。

完全二叉树具有以下两个性质

性质5具有n个结点的完全二叉树的深度为〔log2n〕+1。

性质6设完全二叉树共有n个结点。如果从根结点开始,按层次用自然数1,2,,n给结点进行编号,则对于编号为k的结点有以下结论

①若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点编号为INT。

②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点。

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。

考点8 二叉树的遍历

考试链接

考点8在笔试考试中考核几率为30%,分值为2分,读者应该熟练掌握各种遍历的具体算法,能由两种遍历的结果推导另一种遍历的结果。

在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。在先左后右的原则下,根据访问根结点的次序,二叉树的遍历分为三类前序遍历、中序遍历和后序遍历。

前序遍历先访问根结点、然后遍历左子树,最后遍历右子树;并且,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。

中序遍历先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。

后序遍历先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。

疑难解答树与二叉树的不同之处是什么?

在二叉树中,每一个结点的度最大为2,即所有子树也均为二叉树,而树结构中的每一个结点的度可以是任意的。

1.5查找技术

考点9 顺序查找

考试链接

考点9在笔试考试中考核几率在30%,一般出现选择题中,分值为2分,读者应该具体掌握顺序查找的算法。

查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;若线性表中所有的元素都与被查找元素进行了比较但都不相等,则表示查找失败。

在下列两种情况下也只能采用顺序查找

如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找。

即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。

考点10 二分法查找

考试链接

考点10在笔试考试中考核几率为30%,一般出现填空题中,分值为2分,考核比
声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
脚崴了挂什么科、急急急 linux 解压缩工具--tar命令 生日祝福语闺蜜 简短独特暖心 QQ有哪些隐藏的图标??他们分别是什么??怎么样点亮?? QQ业务的各种图标怎么点亮? qq怎么点亮图标和名字 诗中书万象=求下联 大爱如山藏万象下联 中国电子展:电位器和可调电阻的区别是什么?这四点很明显 电位器的接线方法是什么 电位器的工作原理如何 想考计算机二级c语言, #运营主管#现在的运营主管,日常工作一般在做什么工作,项目偏向内容营销,市场营销,还是产品运营 京东的运作主管是干嘛的,有人应聘过吗?是不是就是快递分拣员? 公司的首席运营官是做什么的,运营主管/经理的工作内容有什么 运营主管是做什么的呀 梦见跟爸妈一起抓鸡是什么预兆? 运营主管是干什么的 已婚女人梦到抓鸡兔子鱼好不好 电子商务运营主管的主要工作 梦到抓了好多秧鸡,有什么征兆 影城运营主管干什么的? 梦见在水里抓鸡是什么意思? 我在淘宝上定的东西太多了,都已经收到了,我想把物流信息删掉,怎么删 昨晚梦到别人在抓鸡抓不到后来被我抓到了一只母鸡好不好? 请问超市里的运营主管是做什么的? 永泰能源这个股票怎样?永泰能源预计能涨到多少?永泰能源股票有分红吗? 手机充电口坏了能修吗? 永泰能源股票可以长久持有吗?永泰能源业绩预告是利好还是利空?永泰能源属于什么板块的股? 永泰能源长期持有吗?永泰能源股票历史价格详情?永泰能源发生什么股票大跌? 永泰能源现在还能买入和加仓吗?永泰能源怎么股价这么低呢?永泰能源怎么样行情怎么样? 2011年9月全国计算机二级VB公共基础知识 王者荣耀法师英雄嬴政铭文怎么搭配,怎么出装 求计算机二级公共基础知识 如何判断一个数据库表是否满足一个给定的函数依赖? 算法的复杂度... 递归算法要有哪两个要素? 成都购买的社保,在老家生小孩可以报吗? 成都生完孩子最迟多久能报社保 怎么样才能破解手机卡获得免费上网流量 联通限速后怎么破解 监控录像误删如何恢复怎么操作 你好 我家里安装监控在手机上 手机里的录像被删了怎么找回 把定向流量破解为通用流量容易吗 5s怎么破解使用移动4g 怎样破解手机卡无限流量上网 监控的录像删除了,能不能恢复 联通流量超40g被限制了,有没有破解方法 监控器录像被删除了如何恢复?? 谁知道如何破解手机卡无限流量上网 家里的监控摄像头被删除了。试图调出五个月前的监控录像。有办法恢复吗? 苹果5破解移动4g