(一)计算机二级公共基础知识考前培训班课件.ppt

全国计算机等级考试，二级公共基础知识，第一章数据结构和算法(30% )，考试大纲1 .算法基本概念算法的复杂性概念和意义(时间复杂性和空间复杂性)。 2 .数据结构定义数据的逻辑结构和存储结构数据结构的图形表示线性结构和非线性结构的概念。 3 .定义线性表线性表的顺序存储结构及其插入和删除运算。 4 .堆栈和队列定义堆栈和队列的顺序存储结构及其基本运算。 5 .线性单链表、双向链表和循环链表的结构及其基本运算。 6 .树的基本概念追溯二叉树的定义及其记忆结构二叉树的前序、中序、后序。 7 .序贯搜索和二分法搜索算法基本排序算法(交换类排序、选择类排序、插入类排序)。 知识点摘要、算法的基本概念算法是问题解决方案的正确完整描述。 严格地说，一个算法必须具有以下五个主要特征：可行性确定性具有贫困性输入输出，算法是严格定义运算顺序的一组规则，而且每个规则都是有效和明确的，该顺序以有限次数结束。 算法的基本概念、算法的组成部分算法中数据运算和操作算法的控制结构算法的设计基本方法的列举法归纳法递归半衰递归递归回归法、算法复杂性、算法复杂性分为时间复杂性和空间复杂性1 .算法的时间复杂度算法的时间复杂度是算法执行所需的工作量。 通常，算法中的基本操作被重复执行的次数是具有问题规模n的函数f(n )。 算法的时间量度被表示为T(n)=O(f(n ) )，表明随着问题规模n变大，算法的执行时间的增加率与f(n )的增加率相同，且被称为算法的(渐进的)时间复杂度。 如何估计算法的复杂性和算法的时间复杂性？ 因为任何算法都由一个“控制结构”和几个“原操作”构成，所以一个算法的执行时间可以看作是所有原操作的执行时间之和(原操作(I )的执行次数原操作(I )的执行时间)，算法的执行时间与所有原操作的执行次数之和成比例。 针对所研究的问题，从算法中选择基本操作的原始操作，将该基本操作在算法中反复执行的次数作为算法的时间复杂性的依据。 这个测定效率的方法不是时间量，而是测定成长倾向的方法。 无论硬件和软件环境如何，只暴露算法本身执行效率的优劣。 算法的复杂度、算法的空间复杂度算法的空间复杂度是执行该算法所需要的存储器空间。 将空间复杂度表示为S(n)=O(g(n ) )作为算法所需的存储空间的尺度。 这里，n是问题的规模，随着问题的规模变大，表示算法执行所需的存储容量的增加率与g(n )的增加率相同。 数据结构、计算机数据处理是计算机应用的重要领域。 该数据结构主要研究和讨论数据集合中每个数据元素之间的逻辑关系，即数据的逻辑结构。 在处理数据的情况下，各数据要素在计算机中的存储关系，即数据的存储结构。 针对不同数据结构的运算。 另外，数据的逻辑结构、数据逻辑结构是数据元素之间存在的逻辑关系的描述，并且可以用数据元素集合及其定义的一些关系来表示。 无论数据在计算机中的存储位置如何，它都独立于计算机。 另外，数据的存储构造、数据的存储构造，是将数据要素及其关系表示在计算机存储器中的构造。 存储结构的主要内容是在存储空间中使用一个存储节点来存储一个数据元素，在各存储空间中建立各存储节点之间的关联以表示数据元素之间的逻辑关系。典型的存储结构：序列存储结构链存储结构索引存储结构散列存储结构，线性结构和非线性结构，线性结构位于数据元素的非空有限集合中，线性结构的逻辑特征如下：存在唯一称为“第一”的数据元素， 集合中的每个数据元素，除了存在仅称为“最后”的数据元素的集合中的每个数据元素仅在一个直接前面被去除之外，一个直接的非线性结构的非线性结构的逻辑特征是，一个节点可以直接连接到多个直接的前驱，树和图都属于非线性结构当(a1，a2，ai，an )序列中的数据元素的数目n定义为线性表的表长度时，线性表一般被称为空表，其中n由下列n个数据元素序列表示： I称为线性表中的ai的顺序。 线性表的顺序存储、线性表的顺序存储结构用一系列地址连续的存储单元依次存储线性表中的数据要素，用“存储位置相邻”表示“顺序连续的2个数据要素之间的前驱和后续的关系，将表中的第一个要素的存储位置作为线性表的起始地址，称为线性表的基础地址。 此外，所有数据要素的存储位置是，从最初的数据要素的存储位置开始，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。 取消堆栈：检索堆栈顶部元素，将其分配给指定的变量，然后从堆栈顶部指针顶部减去1。 栈顶元素：将栈顶元素的值分配给指定变量。 不删除堆栈顶部元素，并且不更改堆栈顶部指针。 队列、队列是高级路线表，只能在表的一端插入元素(队列的末尾)，在另一端删除元素(队列的开头)。 通常，头指针front指向队列头元素的前面，并定义尾指针rear指向队列头元素的位置。 队列是一种先进的数据结构。 在队列末尾插入元素的操作称为排入队列，从队列开头删除元素的操作称为取消。 进而在队列中循环，将队列存储空间的最后位置转到第一位置以形成逻辑环形空间。 循环队列的初始状态为空，即front=rear=m。 在入队操作时，如果rear=1，rear=m 1，则对rear=1的取消操作用前端加1，如果front=m 1，则前端加1。 如果循环队列为空或已满，则由于front=rear，因此设置标志s来区分，如果定义s=0，则队列为空，s=1表示队列不为空。 单链表和线性表的链存储结构的特征在于，用一系列任意存储装置(可以是连续的或者不连续的)存储线性表的数据元素，并且为了表示各个数据元素ai与其直接的后续元素ai 1之间的逻辑关系，在数据元素ai中，除了其自身的信息(数据域)以外，还存储其后续元素的存储位置信息(数据域)存储在指针字段中的信息称为指针或链，是线性表的链存储结构，其中n个节点链接到一个链路表。 由于节点只包含一个指针域，因此称为单链路表。 链接列表的第一数据元素的存储地址通常被称为链接列表的地址，并且被称为头指针。 整个链路表的存储必须从第一个指针开始(依次访问)，第一个指针指示该链路表中第一节点的存储位置。 最后一个数据元素不能直接继续。 指针字段为空。 还有，单链路表的插入和删除，双向链路表和循环链路表，双向链路表的节点包含两个指针域，一个指的是直接的后继者，另一个指的是直接的先驱者。 循环链路表的特征在于，表的最后一个节点的指针域指向第一个节点，整个链路表成为用链路指针链接的环。 这使得能够从显示中的任何节点找到显示中的其它节点。 报头节点被添加到循环链表中，其指针域指向第一个元素节点，报头指针指向报头节点。 树及其基本概念，树为简单的非线性结构，树中所有数据元素之间存在明显的层次关系。 树是(n0 )个节点的有限集合，在任意一根非空树中，(1)只将某个特定节点称为根节点。 (2)当n-1时，其馀节点被划分成m个互不相交的子集T1、T2、 TM，其中的有限子集本身还是树形的，并且称之为根子树。 集合把空树简称为空树，把树中的要素称为节点。 树的主要术语，节点度：节点具有的子树数。 叶节点(终止节点):度为0的节点。 父母、孩子、兄弟：将节点的子树的根节点称为该节点的孩子，将该节点称为孩子节点的父母节点。 同父母节点的孩子们互称兄弟。 层次：节点的层次由根定义，根是第一层次，根的子项是第二层次。 深度：树中节点的最大级别称为树的深度或高度。 二叉树、二叉树是n(n0 )个数据元素的有限集合，它们是空集合，或包含唯一的称为根的元素，其馀元素分为相互不交叉的两个子集合，各个子集合本身也是一个二叉树，分别是称为根的左子树和右子树。 二叉树是另一种树型结构，每个节点最多有两个子树，而二叉树的子树具有左右两部分的特征，其顺序不能任意颠倒。 二叉树的基本性质，性质1在二叉树的第I层至多2i-1个节点(I1 )性质2深度k的二叉树最多为2k-1个节点(k1 )性质3对的任意一根二叉树t，如果其终端节点数为n0、度为2的节点数为n2，则n0=n2 1性质4为具有n个节点的二叉树， 其深度至少为log2n 1，满二叉树和完全二叉树除最后一层外，各层的所有节点都有两个子节点，即各层的节点数达到最大值，即满二叉树的第k层有2k-1个节点，深度为m的满二叉树有2m-1个节点完全二叉树除最后一层外，各层的节点数达到最大值，最后一层只缺少右边的几个节点。 具有n个节点的完全二叉树，其深度为log2n 1。 由以上定义可知，满二叉树也是完全二叉树，否则不然。 二叉树的基本性质，对具有性质5n个节点的完全二叉树(其深度为log2n 1)的节点按层次(从第1层到第log2n 1层，每层从左到右)进行编号，对任意编号为I的节点(1in )，3360 (1) I (2)如果是2合，则在编号为I的节点处不存在左边的子节点(编号为I的节点是叶节点)，否则，其左边的子节点lChild(i )的编号为2i。 (如果2-I1- n，则第I号节点不具有右边的子节点，否则其右边的子节点rChild(i )的编号是节点2i 1。在二叉树的连锁存储结构，二叉树的连锁存储结构中，每个节点存储3个域，即数据域、左指针域和右指针域，2个指针域分别存储左右子树的根节点的存储位置，即指针。 二叉树的连锁记忆结构，二叉树的扫描，二叉树的扫描，不会反复访问二叉树的所有节点。 由二叉树的结构定义可知，二叉树由“根节点”、“左子树”和“右子树”三部分构成，横断二叉树的操作可分解为“访问根节点”、“横断左子树”、“横断右子树”三个子操作，由二叉树的递归定义可知，横断左子树和横断右子树二叉树扫描，第一次扫描： ABDEGHCFIJ中的扫描： DBGEHACIJF后的扫描： DGHEBJIFCA，检索是指在特定的数据结构内检索特定的要素。 逐次搜索顺序搜索一般是搜索线性表中指定的元素，基本方法是从线性表的第一个元素起按顺序比较线性表的元素与所搜索的元素，如果匹配则指示搜索成功，如果匹配则指示搜索成功的线性表的所有元素不等于要搜索的元素如果路线表是无序表，也就是说，如果表中的元素数组是无序的，则无论路线表是顺序存储还是链存储，都必须使用顺序搜索。 如果路线表是规则的并且采用了链式存储结构，则还必须使用顺序搜索。 搜索、二分搜索(二分搜索)二分搜索方法仅适用于顺序存储的规则表。 首先，确定检索对象要素存在的范围(区间)，阶段性地缩小范围直到找到该要素，或者即使将检索区间缩小为0也找不到对象要素。 在检索中，规定值首先与处于检查等待区间“中间位置”的关键字进行比较，在相等的情况下检索成功，否则将检索区间缩小为“前半区间”或“后半区间”继续检索。 半搜索、二进制搜索、排序和排序是按升序或降序按值组织无序序列的顺序(本章中全部采用升序规则)。 排序可以通过各种记忆结构来实现，本章介绍的算法以顺序记忆的线性表为排序对象，在编程语言中是一维排列。 排序算法种类繁多，主要有交换类排序、插入类排序、选择类排序等。 交换类排序、冒泡排序的基本思想：从报头扫描线性表，在扫描过程中依次比较相邻的两个要素的大小，前面的要素比后面的要素大时，交换它们的位置。 在扫描过程中，相邻元素之间的大元素始终向后移动，最后线性表中的最大元素移动到表的末尾。 然后，从后向前扫描剩馀的线性表，同样地在扫描的过程中依次比较相邻的两个要素的大小，在后面的要素比前面的要素小的情况下调换位置。 在扫描期间，将相邻元素之间的小元素逐个向前移动，最后将线性表中的最小元素移动到标题。 对于剩馀的线型表，重复上述步骤，直到剩馀的线型表变空为止，线型表变得规则。 泡排序的例子包括：第一次(从前到后)、第一次(从后到前)、第二次(从前到后)、第二次(从后到前)、快速排序、基本思想：从线性表中选择一个要素作为t，在线性表后面移动小于t的要素，在线性表后面移动大于t的要素作为后面移动， 把线性表放在边界线的位置上称为线性表的分割，一次把线性表以t为界分成两个子表，前面的子表的要素都在t以下，接着子表的要素都在t以上。 根据上述原则，如果继续分割子表直到子表为空，则整个线性表变得规则。 快速排序和操作步骤：首先从表的第一个元素、最后一个元素和中间元素中选择中值，设置P(k )，将P(k )指定给t，然后将表的第一个元素移动到P(k )的位置。使两个指针I、j分别朝向表的开头和最后的位置，逐渐减小j，依次比较P(j )和t直到找到一个P(j)T，并且将P(i )移动到P(j )的位置，这两个步骤重复。 上述两个阶段的操作交替进