公共基础知识考点分析

1、。第1章数据结构和算法经过对一些考生的调查以及对近年来实际问题的总结和分析，笔试部分经常要考查算法的复杂性、数据结构的概念、堆栈、二叉树的遍历以及二分法搜索，所以读者应该关注这一部分。专注于学习知识点的细节：1.算法的概念、算法的时间复杂度和空间复杂度2.数据结构、数据逻辑结构和物理结构的定义3.堆栈的定义和操作，以及线性链表的存储方式4.树和二叉树的概念，二叉树的基本性质，完全二叉树的概念和二叉树的遍历5.二元搜索法6.气泡分选法1.1算法测试点1算法的基本概念考试链接：笔试第一考点的考试概率为30%，主要以填空题的形式出现，得分为2分。这个测试站点是记忆内容的，读者也应该了解算法中数据的基

2、本操作。事实上，计算机解决问题的过程就是实现一种算法，这就是所谓的计算机算法。1.该算法的基本特征是：可行性、确定性、有限性和足够的智能性。2.算法的基本要素：(1)算法中数据的运算和运算算法由两个基本元素组成：一是数据对象的操作和运算；第二是算法的控制结构。在一般的计算机系统中，有四种基本操作：算术运算、逻辑运算、关系运算和数据传输。(2)算法的控制结构：算法中操作之间的执行顺序称为算法的控制结构。描述算法的工具通常包括传统流程图、N-S结构化流程图、算法描述语言等。通常，算法可以由三种基本控制结构组成：顺序、选择和循环。测试点2的算法复杂度考试链接：考点2是笔试中经常被考查的内容，概率为7

3、0%，主要以选择的形式出现，得分为2分。这个测试站点是关键的记忆内容，读者还应该记住算法时间复杂度和空间复杂度的概念。1.算法的时间复杂度算法的时间复杂度是指执行算法所需的计算工作量。相同的算法用不同的语言实现，由不同的编译器编译，或者在不同的计算机上运行，这具有不同的效率。这表明用绝对时间单位来衡量算法的效率是不合适的。除了这些与计算机硬件和软件相关的因素之外，可以认为特定算法的“运行工作量”的大小仅取决于问题的规模(通常用整数n表示)，这是问题规模的函数。也就是说，算法的工作量=f(n)2.算法的空间复杂性算法的空间复杂度是指执行算法所需的内存空间。算法占用的存储空间包括算法程序占用的空间

4、、输入初始数据占用的存储空间以及算法执行过程中所需的额外空间。额外空间包括执行算法程序过程中的工作单元和某个数据结构所需的额外存储空间。如果相对于问题的大小，额外空间的量是恒定的，则该算法被称为在原地工作。在许多实际问题中，为了减少算法占用的存储空间，通常采用压缩存储技术来最小化不必要的额外空间。故障排除：算法的工作量是多少？算法的工作量由算法执行的基本操作的数量来计算，算法执行的基本操作的数量是问题大小的函数，即算法的工作量=f(n)，其中n是问题的大小。1.2数据结构的基本概念测试中心3数据结构的定义考试链接：考点3是笔试中经常检查的内容，概率为70%，主要以选择的形式出现，得分为2分。这

5、个测试网站是记忆内容，读者也应该记住数据的逻辑结构和存储结构的概念。作为一门计算机学科，数据结构主要研究和讨论以下三个方面：(1)内在的逻辑关系(2)处理数据元素时，计算机中各数据元素的存储关系，即数据的存储结构；(3)对各种数据结构的操作。数据：它是客观事物的象征性表现。在计算机科学中，它指的是可以输入计算机并由计算机程序处理的所有符号的总称。数据元素是数据的基本单位，通常在计算机程序中作为一个整体来考虑和处理。数据对象：它是具有相同属性的数据元素和数据子集的集合。数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以由一组数据元素和该组中定义的几个关系来表示。数据的逻辑结构有两个元素：一个

6、是数据元素的集合，通常记录为d；第二，d上的关系反映了数据元素之间的先行关系，通常记录为r。数据结构可以表示为乙=(丁，丙)其中b代表数据结构。为了反映数据元素之间的先行关系，一般用二元组来表示。计算机存储空间中数据逻辑结构的存储形式称为数据存储结构(也称为数据物理结构)。因为数据元素在计算机存储空间中的位置关系可能不同于逻辑关系，所以为了表示存储在计算机存储空间中的数据元素之间的逻辑关系，不仅每个数据元素的信息，而且其先前关系的信息都应该存储在数据存储结构中。数据的逻辑结构可以根据需要表示为各种存储结构，常用的存储结构包括顺序存储结构、链接存储结构、索引存储结构等。不同存储结构的数据处理效率

7、不同。因此，在处理数据时选择合适的存储结构非常重要。测试点4线性结构和非线性结构考试链接：笔试中的考点4，虽然不是考试中经常被考查的内容，但读者对这个考点还是有一定了解的，笔试中出现的概率为30%，主要以填空题的形式出现，得分为2分。这个测试网站是记忆内容。根据数据结构中数据元素之间先行关系的复杂性，数据结构一般分为两类：线性结构和非线性结构。如果非空数据结构满足以下两个条件：(1)只有一个根节点；(2)每个节点最多有一个前部和一个后部。数据结构被称为线性结构。线性结构也称为线性表。在线性结构中插入或删除任何节点后，它也应该是线性结构。如果一个数据结构不是线性的，它被称为非线性结构。故障排除：

8、空数据结构是线性的还是非线性的？空数据结构是属于线性结构还是非线性结构取决于具体情况。如果数据结构的算法是按照线性结构的规则处理的，则属于线性结构；否则，它属于非线性结构。1.3堆栈和线性链表测试中心5栈及其基本操作考试链接：考试中心5是笔试中的一个必考内容。笔试出现的概率为100%，主要以选拔的形式出现，得2分。这个测试中心侧重于掌握内容，读者应该掌握堆栈操作。1.堆栈的基本概念堆栈是一个线性表，只有一端用于插入和删除，通常称为堆栈顶部和堆栈底部。当表中没有元素时，调用空堆栈。堆栈顶部的元素总是后来插入的元素，所以它也是首先被删除的元素；堆栈底部的元素始终是要插入的第一个元素，因此也是要删除

9、的最后一个元素。堆栈根据“先进先出”或“后进先出”的原则组织数据。2.堆栈顺序存储及其操作一维数组S(1m)用作堆栈的顺序存储空间，其中M是最大容量。在堆栈的顺序存储空间S(1m)中，S(底部)是底部元素，S(顶部)是顶部元素。Top=0表示堆栈为空；Top=m表示堆栈已满。有三种基本的栈操作：栈入口、栈出口和栈顶元素读取。(1)堆栈操作：堆栈操作是指在堆栈顶部插入一个新元素。首先，向顶部指针添加一个(即顶部加一)，然后将新元素插入顶部指针所指向的位置。当堆栈的顶部指针指向存储空间的最后一个位置时，这意味着堆栈空间已满，无法再次进入堆栈。这种情况称为堆栈“溢出”错误。(2)回堆操作：回堆指的是

10、取出堆栈的顶部元素，并将其分配给指定的变量。首先，将顶部元素(顶部指针指向的元素)赋给指定的变量，然后从顶部指针中减去一个(即从顶部减去一个)。当堆栈的顶部指针为0时，意味着堆栈为空，并且无法执行堆栈退出操作。这种情况被称为堆栈的“下溢”错误。(3)读取顶层元素：读取顶层元素意味着将顶层元素分配给指定的变量。此操作不会删除顶部元素，但会将其分配给一个变量，因此顶部指针不会改变。当堆栈顶部指针为0时，意味着堆栈为空，并且无法读取堆栈顶部元素。提示：堆叠根据“先进先出”或“后进先出”的原则组织数据，但是堆叠方法有许多选择，并且在试题中经常检查各种堆叠方法。测试点6线性链表的基本概念考试链接：笔试中

11、出现6号考点的概率为30%，主要以选拔的形式出现，得分为2分。这个测试网站是记忆内容。重点记忆节点的组成。在链存储模式中，每个节点需要由两部分组成：一部分用于存储数据元素值，称为数据字段，另一部分用于存储指针，称为指针字段。其中指针用于指向该节点的前一个或后一个节点(即前一个或后一个)。链式存储可以用来表示线性和非线性结构。(1)线性链表线性表的链式存储结构称为线性链表。在某些应用中，线性链表中的每个节点都有两个指针，一个叫做左指针，用来指向它的前一个节点；另一个叫做右指针，用来指向它后面的节点。这样的表被称为双链表。(2)带链堆叠栈也是一个线性表，也可以采用链式存储结构。带链栈可以用来收集计

12、算机存储空间中所有空闲的存储节点，称为可用栈。故障排除：链结构中存储空间的位置和逻辑关系是什么？在链式存储结构中，用于存储数据结构的存储空间可以是不连续的，并且每个数据节点的存储顺序可以与由指针字段确定的数据元素之间的逻辑关系不一致。1.4树和二叉树测试中心7树和二叉树及其基本性质考试链接：考试中心7是笔试的必修内容，笔试出现的概率为100%，主要以选择题的形式出现，有时以填空题的形式出现，得分为2分。这个测试中心是掌握内容的关键。专注于记忆树和二叉树的属性。误解警告：完整的二叉树也是完整的二叉树，而完整的二叉树通常不是完整的二叉树。应该注意他们之间的差异。1、树的基本概念树是一个简单的非线性

13、结构。在树形结构中，每个节点只有一个前因，称为父节点，只有一个没有前因的节点，称为树的根节点。每个节点可以有多个后件，这些后件被称为节点的子节点。没有后缀的节点称为叶节点。在树形结构中，一个节点拥有的后继者的数量被称为该节点的度。叶节点度为0。在树中，所有节点的最大度数被称为树的度数。2.二叉树及其基本性质(1)二叉树的定义二叉树是一种有用的非线性结构，具有以下两个特征：(1)非空二叉树只有一个根节点；每个节点最多有两个子树，分别称为节点的左子树和右子树。从以上特征可以看出，在二叉树中，每个节点的最大度数是2，即所有的子树(左子树或右子树)也是二叉树，树结构中每个节点的度数可以是任意的。另外，

14、二叉树中每个节点的子树明显分为左子树和右子树。在二叉树中，一个节点只能有一个左子树而没有右子树，或者一个右子树而没有左子树。当一个节点既没有左子树也没有右子树时，该节点就是叶节点。(2)二叉树的基本性质二叉树具有以下属性：性质1:二叉树的第k级上最多有2k-1个(k1)节点；属性2:深度为m的二叉树最多有2m-1个节点；属性3:在任何二叉树中，0度的节点(即叶节点)总是比2度的节点多一个。性质4:具有n个节点的二叉树，其深度至少为log2n 1，其中log2n表示log2n的整数部分。提示：在二叉树的遍历中，二叉树的叶节点的顺序是不变的，无论是前序遍历、中序遍历还是后序遍历。3.全二叉树和全二

15、叉树完整的二叉树指的是每层上的所有节点都有两个子节点(除了最后一个)的二叉树。在全二叉树中，每层的节点数达到最大，即全二叉树的第k层有2k-1个节点，深度为m的全二叉树有2m-1个节点。完全二叉树指的是这样一种二叉树：除最后一层外，每层的节点数达到最大值；在最后一层，只有右边的几个节点丢失了。对于一个完整的二叉树，叶子节点只能出现在两个层次最大的层次上：对于任何节点，如果其右分支下的后代节点的最大层次是P，其左分支下的后代节点的最大层次是P或p 1。完整的二叉树有以下两个属性：属性5:具有n个节点的完整二叉树的深度是log2n 1。属性6:假设完整的二叉树有n个节点。如果从根节点开始，节点用自

16、然数1，2，根据层次结构(在每个层次结构中从左到右)，对于编号为k(k=1，2，n):(1)如果k=1，则该节点是根节点，并且它没有父节点；如果为k1，则该节点的父节点号为INT(k/2)。(2)如果2kn，编号为k的节点的左子节点的数目为2k；否则，该节点没有左子节点(显然，它也没有右子节点)。如果2k 1n，编号为k的节点的右子节点号为2k1否则，该节点没有正确的子节点。测试中心8中二叉树的遍历考试链接：笔试中测试中心8的考试概率为30%，得2分。读者应该掌握各种具体的遍历算法，并能够从两个遍历结果中推导出另一个遍历结果。在遍历二叉树的过程中，我们通常先遍历左子树，然后遍历右子树。根据访问

17、根节点的顺序，二叉树的遍历可以分为三类：前序遍历、中序遍历和后序遍历。(1)序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树；此外，当遍历左右子树时，我们仍然先访问根节点，然后遍历左子树，最后遍历右子树。(2)中间顺序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树；此外，当遍历左和右子树时，我们仍然先遍历左子树，然后访问根节点，最后遍历右子树。(3)后序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点；此外，当遍历左和右子树时，我们仍然先遍历左子树，然后遍历右子树，最后访问根节点。故障排除：树和二叉树有什么区别？在二叉树中，每个节点的最大度数是2，也就是说，所有的子树(左子树或右子树)也是二叉树，树结构中每个节点的度数可以是任意的。1.5搜索技术测试站点9顺序搜索考试链接：测试中心9在笔试中的评估概率为30%。一般来说，在选择题中，分数是2分。读者应该掌握顺序搜索的算法。搜索是指在给定的数据结构中查找指定的元素。从线性表的第一个元素开始，将线性