二级公共基础知识(基本版).ppt

全国计算机排名考试，第二次公共基础知识，第一章数据结构和算法(30%)，考试大纲1。算法的基本概念；算法复杂性的概念和重要性(时间复杂性和空间复杂性)。数据结构的定义；数据的逻辑结构和存储结构数据结构的图形表示；线性结构和非线性结构的概念。定线表格的定义；线性表格的顺序储存结构以及插入和删除作业。堆栈和队列的定义；堆栈和队列序列存储结构以及基本运算。5.线性单列表、双向列表和循环列表的结构和基本运算。树的基本概念；二叉树定义和存储结构；二叉树的前导、中间和结尾遍历。顺序搜索和二分法搜索算法；默认排序算法(交换类排序、选择类排序、插入类排序)。知识点推导，算法的基本概念所谓算法，是指对问题解决方案的准确、完整的说明。严格地说，算法必须有5个主要特征。也就是说，有限的确定性可行性输入和输出，即算法是严格定义运算顺序的一系列规则，每个规则在有效、明确、有限的次数上终止。算法的基本概念，算法的组件算法中数据的运算和操作算法的控制结构算法设计基本方法枚举方法递归递归递归反递归回溯，算法的复杂性，算法的复杂性可以分为时间复杂性和空间复杂性，测量算法的优缺点。1.算法的时间复杂性算法的时间复杂性表示运行算法所需的工作量。通常，算法中基本操作重复执行的次数是问题大小n的函数f(n)之一。算法的时间测量值用T(n)=O(f(n)表示，随着问题规模n的增加，算法运行时间的增长率与f(n)的增长率相同，这称为算法的(渐进)时间复杂性。算法的复杂性，如何估计算法的时间复杂性？任何算法都由一个控制结构和多个“原始操作”组成，因此，可以将一个算法的执行时间视为所有原始操作的执行时间之和(原始操作(I)的执行次数原始操作(I)的执行时间)。该算法与所有原始操作的执行次数成正比。为算法正在研究的问题选择默认操作的原始操作。使用此默认操作在算法中重复执行的次数作为算法时间复杂性的基础。这种效率测量不是时间的量，而是增长趋势的尺度。揭示了算法本身执行效率的优缺点，与硬件和软件环境无关。算法的复杂性，算法的空间复杂性算法的空间负噪声表示运行此算法所需的内存空间。空间复杂性是算法所需存储空间的尺度，以S(n)=O(g(n)的形式记录。其中n表示随着问题的增长，运行算法所需的存储容量的增长率与g(n)的增长率相同。数据结构，使用计算机进行数据处理是计算机应用的重要领域。数据结构主要研究和讨论数据的逻辑结构，即数据集中数据元素之间的逻辑关系。处理数据时，计算机中每个数据元素的存储关系，即数据的存储结构。各种数据结构的运算。数据的逻辑结构，是对数据元素之间逻辑关系的描述，可以表示为一组数据元素和此集合中定义的多个关系。与数据在计算机上的存储位置无关，与计算机无关。数据存储结构、数据存储结构是数据元素及其在计算机内存中的关系的表示。存储结构的主要内容是在存储空间中使用存储节点存储数据元素，在存储空间中建立存储节点之间的关联以表示数据元素之间的逻辑关系。典型存储结构：顺序存储结构链存储结构索引存储结构散列存储结构、线性和非线性结构、线性结构数据元素的非空有限集合中线性结构的逻辑特征如下：有一个唯一的数据元素，称为“第一个”。有一个唯一的数据元素，称为“最后一个”。集合中的每个数据元素在一个直接前面有最后一个数据元素，而集合中的每个数据元素在一个直接后面有非线性结构的非线性结构的逻辑特征是一个节点可以有多个直接前缀和直接后缀，树和图形都属于非线性结构。线性表，通常按以下n个数据元素的顺序显示：(a1，a2，ai、an)序列中数据元素的数目n由线性表中的表长度定义。N=0时，路线表称为空表。I在线性表中称为ai的位顺序。线性表的顺序存储，线性表的顺序存储结构按顺序存储线性表的数据元素，以连续存储一系列地址。也就是说，“存储位置相邻”表示“位顺序中两个数据元素之间的前导和后续关系”，并使用表中第一个元素的存储位置作为线性表(称为线性表的主地址)的起始地址。所有数据元素的存储位置由第一个数据元素的存储位置决定，ADR (ai)=ADR (a1) (I-1) c基本地址数据元素的存储容量，线表的插入和删除操作，插入操作是将新节点添加到线表中的指定位置的操作。通常，要在I(1In)元素之前插入新元素，请先从最后一个元素开始，在I元素之间将n-i 1元素总计向后移动一个位置，然后在I项目中插入新元素。删除操作是取消结构中的节点。通常，如果要删除I(1In)个元素，则从I 1元素开始，到第n个元素，n-i的总元素依次向前移动一个位置。堆叠、堆叠是线性表格，仅在表格的一端限制插入和删除作业。允许插入和删除的一端称为堆栈顶部，另一端称为堆栈底部。堆栈顶部元素始终是最后插入的、最先删除的元素。堆栈底部的元素始终是最先插入、最后删除的元素。因此，堆栈是后进先出的线性表。通常，堆栈顶部的位置表示为指针top，堆栈底部的位置表示为指针bottom。堆栈的顺序存储和计算，使用一维阵列S(1:m)作为堆栈的顺序存储空间，m是堆栈的最大容量。Top=0表示堆栈为空，top=m表示堆栈已满。使用堆栈：在堆栈顶部位置插入新元素，在堆栈顶部指针的顶部添加1。堆叠：移除堆叠顶部元素，并将值指定给指定的变数。堆栈顶部指针top减去1。选取堆叠顶部元素：将堆叠顶部元素的值指定给指定变数，不删除堆叠顶部元素，堆叠顶部指标保持不变。堆栈，如果堆栈的堆栈顺序为ABCDEF，则堆栈顺序不能是()a、DCEFBAB、ABCDEFC、EDFCABD或CBAEDF，因为只能在表格的一端插入元素(团队结束)，而在另一端删除元素(团队头)通常，头指针front定义指向团队头元素的以前位置，而尾部指针rear定义指向团队尾元素的位置。队列是先进先出数据结构。将元素插入伫列末端的作业称为排入伫列或从伫列标头删除元素。循环队列，将队列存储空间的最后一个位置绕过第一个位置，形成逻辑环空间。循环队列的初始状态为空。也就是说，front=rear=m。入队操作中，如果rear加1，rear=m 1，则rear=1；在后退操作中，向front添加1，如果front=m 1，则设置front=1。如果循环队列为空或已满，则具有front=rear，因此需要设置标志s以进行分隔。如果队列为空，则定义s=0，如果队列不为空，则定义s=1。，单个链接表、线性表的链存储结构的特点是将线性表的数据元素存储为所有存储单元集(可以连续也可以不连续)，对于数据元素ai，除了存储自身信息(数据域)外，还必须存储后续子元素的存储位置信息(指针域)，以表示每个数据元素ai及其直接后续子元素ai 1之间的逻辑关系。存储在“指针”字段中的信息称为指针或链，n个节点链接到链接表，这是线性表的链存储结构。节点仅包含一个指针字段，因此称为单个链接。单个链接列表，通常是单个链接列表中第一个数据元素的存储地址，称为标题指针的单个链接列表。整个连接列表的保存(按顺序访问)必须从头开始，头指针指示连接列表中第一个节点的存储位置。最后一个数据元素没有直接后缀，其指针字段为空。插入和删除单个链接列表、双向链接列表和循环链接列表，以及双向链接表的节点有两个指向直接后继者的指针字段。循环链接表的特点是指向表中最后一个节点的指针字段指向第一个节点，并且整个链接表成为链指针连接的一个环。因此，表格中的所有节点都可以找到表格中的其他节点。指向第一个元素节点的指针字段和指向头节点的标题节点将添加到循环链接表格中。树及其基本概念，树是一种简单的非线性结构，所有数据元素之间具有明显的层次关系。树是任意非空树中(n0)节点的有限集合。(1)只有一个特定节点称为根节点。(2)对于n1，剩馀节点是m个不相交的子集t1，T2，可以分为TM。其中，每个有限子集本身是另一棵树，称为根的子树。收藏空的树简称为空树。树中的元素称为节点。树的主要术语，节点的度：节点拥有的子树的数量。叶节点(端子节点):零度节点。父节点、子节点和同级节点：节点的子树的根节点称为该节点的子节点，此节点称为子节点的父节点。同一个双亲节点的孩子叫彼此兄弟。层次：节点的层次从根开始定义，根是第一层，根是第二层。深度(depth):树中节点的最大层级称为树的深度或高度。二进制树，二进制树是n(n0)个数据元素的有限集，或空集，或包含名为root的唯一元素，其馀元素分为两个不相交的子集，每个子集本身也是一个二进制树，称为root的左侧子树和右侧子树。二进制树是另一种树结构，其特征是每个节点最多有两个子树，二进制树的子树有左右两个子树，顺序不能随机颠倒。二进制树的基本特性，特性1为2到1节点(i1)特性2深度为k的二进制树的最大2k-1节点(k1)特性3对任意二进制树t，终端节点数为n0，度为2的节点数为N2:n0=N2 1特性4为最小也就是说，每个层的节点数达到最大值。也就是说，整个二进制树的级别k具有节点2k-1，深度为m的整个二进制树具有节点2m-1。除了整个二叉树的最后一层以外，每个层的节点数达到最大值，最后一层中右侧的部分节点丢失。具有n个深度为log2n 1的节点的完整二进制树。如上定义所示，整个二叉树也是完整的二叉树。否则，情况并非如此。对于二进制树的基本属性，具有属性5 n节点的完整二进制树(深度为log2n 1的节点)，序列(层1到层log2n 1，每个层从左到右)从1开始编号，编号为I的节点(1In)如果为I1，则父节点parent(i)的编号为i/2。(2)如果为2in，编号为I的节点没有左边的孩子(编号为I的节点是叶节点)。否则，左侧子节点lChild(i)的编号为2i。(3)如果是2i 1n，编号I的节点没有右边的孩子；否则，右侧子节点rChild(i)的编号为节点2i 1。二进制树的链存储结构，二进制树的链存储结构中的每个节点存储三个域：数据域、左指针域和右指针域，两个指针域分别存储指针，即左侧和右侧子根节点的存储位置。二进制树的链存储结构，二进制树的遍历，二进制树的遍历意味着不重复访问二进制树的所有节点。从二进制树的结构定义可以看出，二进制树导航分为三个部分：“根节点”、“左侧子树”和“右侧子树”。左侧子树和右侧子树导航可分解为三个子任务：“根节点访问”、“遍历左侧子树”和“遍历右侧子树”，遍历二叉树，第一次遍历顺序：ABDEGHCFIJ遍历中间顺序：DGHEBJIFCA，遍历二进制树，如果一棵树的第一次遍历顺序是ABDEGHCFIJ，中间顺序遍历顺序是DBGEHACIJF，则绘制此树，然后构建下一个顺序序列。如果一个树的中间顺序遍历序列是BDACFE最后一个顺序遍历序列是DBFECA，二进制树遍历，1，二进制树的前一顺序遍历节点访问顺序是ABDGCEFH，中间顺序遍历节点访问顺序是DGBAECHF，则最后顺序遍历的节点访问顺序是2，已知二进制树的中间和最后一个根序列是BDCEAFHG和DECBHGFA。二进制树遍历、查找和查询是指在指定数据结构中查找指定元素。顺序查找顺序查找通常是在直线表中查找指定元素的基本方法，从直线表中的第一个元素开始，将直线表中的元素依次与查找的元素进行比较，如果相同，则查找成功。如果线型表格中的所有元素都不等于要查找的元素，查找将失败。如果线性表格是未排序的表格(即表格的元素排序未排序)，则无论线性表格是顺序储存还是链储存，都必须使用顺序查询。线性表格是顺序的，但是如果使用链存储结构，则还必须使用顺序查询。查找、查找二等分(查找二等分)查找二等分方法仅适用于按顺序保存的排序表格。确定目标元素所在的范围(地块)，然后逐渐缩小范围，直到找到元素，或者缩小范围，直到目标元素缩小到零。在查找过程中，给定的值首先与要检查的部分“中间位置”的关键字进行比较，如果相同，搜索成功，否则缩小到“前半部分间隔”或“后半部分间隔”，然后继续查找。降级、平分、排序、排序是按值的升序或降序排列未排序序列的顺序(本章都适用增量规则)。排序可以在各种存储结构(即排序对象)中实现，在编程语言中，按顺序存储排列表(一维数组)的算法。排序的算法种类很多，如交换类排序、插入类排序、选择类排序等。类排序、冒泡排序基本思路：从标头开始，进行线型表扫描，在扫描过程中对两个相邻元素的大小进行依次比较，如果前面的元素大于后面的元素，则交换其位置。显然，在扫描过程中，相邻元素之间较大的元素继续向后移动，最后，直线表中最大的元素移动到标签上。然后在扫描过程中依次比较两个相邻元素的大小，如果后面的元素小于前面的元素，则交换位置，就像从后面向前扫描其馀的线性表一样。在扫描过程中，连续向前移动相邻元素之间较小的元素，最后将线性表中最小的元素移动到表头。对其馀路线表重复以上过程，直到剩馀路线表为空。，气泡对齐示例，第一个通路(从前到后)，第一个通路(从前到后)，第二个通路(从前到后)，第