VF二级公共基础知识-考点-已勾画

第1章数据结构和算法在调查了一些考生并总结和分析了近年来的实际问题后，书面部分经常检查算法的复杂性、数据结构的概念、堆栈、二叉树的遍历和二分法搜索。读者应该关注这一部分。专注于学习知识点的细节：1.算法的概念，算法时间复杂度和空间复杂度的概念2.数据结构定义、数据逻辑结构和物理结构定义3.栈的定义、操作和线性链表的存储方法4.树和二叉树的概念，二叉树的基本性质，完全二叉树的概念，二叉树的遍历5.二元搜索法6.气泡分选法1.1算法测试站点1算法的基本概念考试链接：考点1有30%的机会在笔试中被考试，主要是以填空题的形式，分数为2分。这个测试网站是用来记忆的。读者还应该知道算法中数据的基本计算。解决计算机问题的过程实际上是某些算法的实现，这些算法被称为计算机算法。1.该算法的基本特征：可行性、确定性、贫困和充足的信息。2.算法的基本元素：(1)算法中数据的操作和运算算法由两个基本元素组成：一是数据对象的操作和运算；第二是算法的控制结构。在一般的计算机系统中，基本操作和运算分为以下四类：算术运算、逻辑运算、关系运算和数据传输。(2)算法的控制结构：算法中每个操作的执行顺序称为算法的控制结构。描述算法的工具通常包括传统流程图、N-S结构化流程图、算法描述语言等。算法通常由三个基本控制结构组成：顺序、选择和循环。测试站点2算法的复杂性考试链接：考点2是笔试中经常被考查的内容。笔试出现的概率为70%，主要以选择的形式出现，得分为2分。这个测试网站侧重于记忆内容。读者还应该记住算法的时间复杂性和空间复杂性的概念。1.算法的时间复杂度算法的时间复杂度是指执行算法所需的计算工作量。相同的算法用不同的语言实现，或者由不同的编译器编译，或者在不同的计算机上运行，具有不同的效率。这表明以绝对时间单位来衡量算法的效率是不合适的。除了这些与计算机硬件和软件相关的因素外，可以认为特定算法的“运行工作量”的大小仅取决于问题的规模(通常用整数n表示)，这是问题规模的函数。也就是说，算法的工作量=f(n)2.算法的空间复杂度算法的空间复杂度是指执行算法所需的内存空间。算法占用的存储空间包括算法程序占用的空间、输入初始数据占用的存储空间以及算法执行过程中所需的额外空间。其中，额外空间包括算法程序执行过程中的工作单元和特定数据结构所需的额外存储空间。如果相对于问题的规模，额外空间的量是恒定的，则该算法被称为原地工作。在许多实际问题中，为了减少算法占用的存储空间，通常采用压缩存储技术来减少不必要的额外空间。故障排除：算法的工作量是多少？算法的工作量由算法执行的基本操作的数量来计算，算法执行的基本操作的数量是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模。1.2数据结构的基本概念测试站点3中数据结构的定义考试链接：考点3是笔试中经常被考查的内容。笔试出现的概率为70%，主要以选择的形式出现，得分为2分。这个测试网站是用来记忆内容的。读者还应该记住数据的逻辑结构和存储结构的概念。作为计算机的一门学科，数据结构主要研究(2)在处理数据元素时，计算机中每个数据元素的存储关系，即数据的存储结构；(3)对各种数据结构的操作。数据：它是客观事物的象征性表现。在计算机科学中，它指的是可以输入计算机并由计算机程序处理的所有符号。数据元素：它是数据的基本单位，通常在计算机程序中作为一个整体来考虑和处理。数据对象：它是具有相同属性的数据元素的集合，是数据的子集。数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以由一组数据元素和该组中定义的几个关系来表示。数据的逻辑结构有两个元素：一个是数据元素的集合，通常表示为D；第二个是D上的关系，它反映了数据元素之间的前后关系，通常表示为r乙=(丁，丙)其中b代表数据结构。为了反映数据元素之间的前后关系，它通常用二进制组来表示。计算机存储空间中数据逻辑结构的存储形式称为数据存储结构(也称为数据物理结构)。由于数据元素在计算机存储空间中的位置关系可能不同于逻辑关系，为了表示存储在计算机存储空间中的数据元素之间的逻辑关系(即前后关系)，在数据存储结构中，不仅需要存储每个数据元素的信息，还需要存储每个数据元素之间的前后关系的信息。数据的逻辑结构可以根据需要表示为多种存储结构。常见的存储结构包括序列、链接、索引等存储结构。不同存储结构的数据处理效率不同。因此，在处理数据时选择合适的存储结构非常重要。测试点4线性结构和非线性结构考试链接：在笔试中，虽然据说它不是考试中经常检查的内容，但读者还是对考试地点有所了解。笔试出现的概率为30%，主要以填空题的形式出现，得分为2分。考试地点是记忆内容。根据数据结构中数据元素前后关系的复杂性，数据结构一般分为两种：线性结构和非线性结构。如果非空数据结构满足以下两个条件：(1)只有一个根节点；(2)每个节点最多有一个前片和一个后片。然后数据结构被称为线性结构。线性结构也称为线性表。在线性结构中插入或删除任何节点后，它也应该是线性结构。如果一个数据结构不是线性结构，它被称为非线性结构。故障排除：空数据结构是线性的还是非线性的？空数据结构是属于线性结构还是非线性结构取决于具体情况。如果该数据结构的算法是根据线性结构的规则处理的，则属于线性结构。否则，它属于非线性结构。1.3堆栈和线性链表测试站点5堆栈及其基本操作考试链接：考点5是笔试的必备内容。笔试出现的概率为100%，主要以选择的形式出现，得分为2分。这个测试站点侧重于掌握内容，读者应该掌握堆栈操作。1.堆栈的基本概念堆栈是一个线性表，只在一端插入和删除。它通常被称为插入和删除末尾的堆栈顶部和另一端的堆栈底部。当表中没有元素时，调用空堆栈。堆栈的顶部元素总是后来插入的元素，因此它也是首先被删除的元素。堆栈底部的元素始终是要插入的第一个元素，因此也是要删除的最后一个元素。堆栈是根据“先进先出”或“后进先出”的原则组织的。2.堆栈顺序存储及其操作一维数组S (1: m)用作堆栈的顺序存储空间，其中m是最大容量。在堆栈的顺序存储空间S (1: m)中，S(底部)是堆栈底部元素，S(顶部)是堆栈顶部元素。Top=0表示堆栈为空；Top=m表示堆栈已满。有三种基本的栈操作：栈入口、栈出口和栈顶元素读取。(1)堆叠操作：堆叠操作是指在堆栈顶部插入新元素。首先，向堆栈的顶部指针添加一个(即top加1)，然后将新元素插入堆栈顶部指针所指向的位置。当堆栈的顶部指针指向存储空间的最后一个位置时，表示堆栈空间已满，不可能再有堆栈条目。这被称为堆栈“溢出”错误。(2)堆栈移除操作：堆栈移除指的是取出堆栈的顶部元素，并将其分配给指定的变量。首先，堆栈的顶部元素(顶部指针指向的元素)被分配给一个指定的变量，然后顶部指针被减一(即顶部减一)。当堆栈顶部的指针为0时，堆栈为空，不能被转储。这种情况称为堆栈下溢错误。(3)读取堆栈顶部元素：读取堆栈顶部元素是指将堆栈顶部元素分配给指定的变量。此操作不会删除堆栈的顶部元素，而是将其分配给一个变量，因此顶部指针不会改变。当堆栈顶部指针为0时，堆栈为空，无法读取堆栈顶部元素。提示：堆栈根据“先进先出”或“后进先出”的原则组织数据。然而，堆叠有许多选择，并且在试题中经常检查各种堆叠方法。测试站点6中线性链表的基本概念考试链接：笔试中出现测试站点6的概率为30%，主要以选择的形式出现，得分为2分。这个测试网站是用来记忆的。重点记忆节点的组成。在链存储模式中，每个节点需要由两部分组成：一部分用于存储数据元素值，称为数据字段，另一部分用于存储指针，称为指针字段。指针用于指向该节点的前一个节点或下一个节点(即前片或后片)。链式存储可以用来表示线性和非线性结构。(1)线性链表线性表的链式存储结构称为线性链表。在某些应用程序中，为线性链表中的每个节点设置了两个指针，其中一个称为左指针，指向它的前一个节点。另一个称为右指针，用于指向其后继节点。这种表被称为双链表。(2)带链堆叠栈也是一个线性表，也可以采用链式存储结构。链式堆栈可用于收集计算机存储空间中的所有空闲存储节点。这种链式堆栈称为可用堆栈。故障排除：存储空间位置和链结构中的逻辑之间有什么关系？在链式存储结构中，存储数据结构的存储空间可以是不连续的，每个数据节点的存储顺序可以与数据元素之间的逻辑关系不一致，数据元素之间的逻辑关系由指针字段决定。1.4树和二叉树测试站点7树和二叉树及其基本属性考试链接：考点7是笔试的必修内容。笔试中出现的概率是100%，这主要是形式的选择。有时它也会出现在填空题中，分数为2分。这个测试网站专注于掌握内容。专注于记忆树和二叉树的属性。错误警告：全二叉树也是全二叉树，而全二叉树通常不是全二叉树。应该注意两者之间的区别。1.树的基本概念树是一个简单的非线性结构。在树结构中，每个节点只有一个先行节点，称为父节点，只有一个没有先行节点的节点，称为树的根节点。每个节点可以有多个后继节点，称为节点的子节点。没有后者的节点称为叶节点。在树形结构中，一个节点拥有的后代的数量被称为节点的度。叶节点度为0。在树中，所有节点的最大度数被称为树的度数。2.二叉树及其基本性质(1)二叉树的定义二叉树是一种非常有用的非线性结构，具有以下两个特征：(1)非空二叉树只有一个根节点；(2)每个节点最多有两个子树，分别称为节点的左子树和右子树。从以上特征可以看出，在二叉树中，每个节点的最大度数是2，即所有的子树(左子树或右子树)都是二叉树，树结构中每个节点的度数可以是任意的。另外，二叉树中每个节点的子树明显分为左子树和右子树。在二叉树中，一个节点只能有一个左子树而没有右子树，或者只能有一个右子树而没有左子树。当节点既没有左子树也没有右子树时，该节点就是叶节点。(2)二叉树的基本性质二叉树具有以下属性：性质1:二叉树的K级上最多有2k-1个(k1)节点；属性2:深度为m的二叉树最多有2m-1个节点；属性3:在任何二叉树中，度为0的节点(即叶节点)总是比度为2的节点多一个。性质4:具有n个节点的二叉树，其深度至少为log2n 1，其中log2n表示log2n的整数部分。提示：在二叉树的遍历中，无论是前序遍历、中序遍历还是后序遍历，二叉树的叶节点的顺序都是相同的。3.全二叉树和全二叉树全二叉树指的是一种二叉树，其中除了最后一层之外，每层的所有节点都有两个子节点。在全二叉树中，每层上的节点数达到最大，即在全二叉树的第k层上有2k-1个节点，在深度为m的全二叉树上有2m-1个节点完全二叉树是指除最后一层之外，每一层的节点数达到最大的二叉树。最后一层只有右边的几个节点缺失。对于完整的二叉树，叶子节点只能出现在最大级别的两个级别上：对于任何节点，如果其右分支下的后代节点的最大级别是p，则其左分支下的后代节点的最大级别是p或p 1。完整的二叉树有以下两个属性：具有n个节点的属性5:的完整二叉树的深度是log2n 1。属性6:设置一个有n个节点的完整二叉树。如果从根节点开始，节点用自然数1，2，根据层次结构(在每层中从左到右)，对于编号为k(k=1 1，2，n):(1)如果k=1，则该节点是根节点，并且它没有父节点；如果为k1，则节点的父节点号为INT(k/2)。(2)如果2kn，节点号k的左子节点号为2k；否则，该节点没有左子节点(显然没有右子节点)。(3)如果2k 1n，节点号k的右子节点号为2k1否则，该节点没有正确的子节点。测试点8中二叉树的遍历考试链接：测试地点8的考试概率为30%，笔试成绩为2分。读者应该熟悉各种遍历的具体算法，并且能够从两次遍历的结果中推断出另一次遍历的结果。在遍历二叉树的过程中，通常先遍历左子树，再遍历右子树。在先左后右的原则下，二叉树遍历按照访问根节点的顺序可以分为三种类型：前序遍历、中序遍历和后序遍历。(1)前序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树；此外，当遍历左和右子树时，仍然首先访问根节点，然后遍历左子树，最后遍历右子树。(2)中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树；此外，当遍历左和右子树时，仍然首先遍历左子树，然后访问根节点，最后遍历右子树。(3)顺序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点；此外，当遍历左和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根节点。故障排除：树和二叉树有什么区别？在二叉树中，每个节点的最大度数是2，即所有子树(左子树或右子树)都是二叉树，树结构中每个节点的度数可以是任意的。1.5搜索技术考试中心9依次搜索考试链接：考试地点9有30%的机会参加笔试。一般来说，选择题得2分。读者应该掌握顺序搜索的算法。查找是指在给定的数据结构中查找指定的元素。从线性表的第一个元素开始，将线性表中的元素按顺序与搜索到的元素进行比较