二级考试公共基础知识.ppt

1、公共基础知识、数据结构和算法编程基础软件工程基础数据库设计基础、算法、算法的基本概念是解题方案的准确、完整描述。 对于一个问题，如果在一个计算机程序有限的存储空间中执行有限的时间可以获得正确的结果，则该问题可以通过算法解决。 算法不等于程序，也不等于计算方法。 算法、算法的基本特征的可行性：算法总是在一个特定的计算工具上执行，算法在执行中受到计算工具的限制，执行结果经常产生偏差。 示例：计算工具有七位有效数字，如果A=1012，B=1，C=-1012，则ab=0，B=1的确定性：算法步骤必须被明确定义，并且不允许模糊的解释或多义性。 算法、贫困性：算法必须在有限的时间内完成，算法必须在执行有限

2、的步骤后结束。 具有足够的信息、算法复杂度，主要是时间复杂度和空间复杂度算法的时间复杂度是算法执行所需的计算工作量。 算法工作负载：测量在算法中执行的基本运算的次数。 举例来说，鉴于两个矩阵的乘法，可将两个实数之间的乘法设为基本运算，且可忽略加法(或减法)运算。 算法执行的基本运算次数也与问题的规模相关，例如，如果将两个20次矩阵乘以两个10次矩阵，则所需的基本运算次数明显不同，在分析算法时还必须测量问题的规模。 算法执行的基本运算次数是问题规模的函数，即，算法的工作量=f(n )，其中，n是问题的规模，算法的时间复杂度，具体地说，如果分析一个算法的工作量，则在一定规模下，算法执行的基本运算次

3、数也是特定的输入实际上，在所有可能的情况下，还存在着不能列举算法执行的基本运算次数的问题。 例如，已经明确的是，当在长度为n的一维阵列中搜索值x的元素时，与从阵列的第一个元素开始的顺序所检查的值x相比较，只需要比较一次，如果第一个元素正好为x，则x是阵列的最后一个元素，或者如果x不在阵列中，则需要比较n次以获得结果。 因此，在该问题算法中，基本运算次数与具体的被检值x相关。 如果在算法的时间复杂性上、在相同规模的问题上执行算法所需的基本运算次数取决于特定输入，则可以用以下两种方法来分析算法的工作量。 1 .平均状态是使用在各种特定输入处的基本运算次数的加权平均来测量算法的工作量。 假设x是所有

4、可输入的特定输入，p(x )是x出现的概率，t(x )是算法在输入为x时执行的基本运算次数，则算法的平均状态定义为a(n)=，p(x)t(x)xdndn，问题规模为n时另外，算法的时间复杂度、2 .最坏的情况的复杂度是指，规模为n时，算法执行的基本运算的最大次数。 W(n)=maxt(x)xDn，该算法的空间复杂度是执行该算法所需的存储器空间。 算法占用的存储区域包括算法程序占用的区域、输入的初始数据占用的存储区域和执行算法所需的附加区域。 在许多实际问题上，为了减少算法所消耗的存储容量，通常采用压缩存储技术，以最大程度地减少不必要的容量。 数据结构、数据结构的基本概念是反映数据元素之间的关系

5、的数据元素的集合的表示。 指具有结构的数据元素的集合。 作为一种处理，其中的数据元素一般具有某些共同特征。 例如，春、夏、秋、冬这四个数据要素具有共同的特征，即季节名。一般地，在具有相同特征的数据元素的集合中，在每个数据元素之间存在一些关系(连接)，该关系反映该集合中的数据元素的固有结构。 在数据处理领域中，通常简单地以前后关系描述数据元素之间的这种固有关系。 例如，考虑到一年四季的顺序关系，春天是夏天的前件，夏天是秋天的前件等，考虑到家族的世代关系，父亲是儿子和女儿的前件，儿子和女儿是父亲的后件。 一般来说，数据元素之间的关系可以用上下文关系来描述。 数据结构和数据逻辑结构是指数据元素之间的

6、上下文关系。 数据元素之间的上下文关系是指逻辑关系，无论其在计算机上的位置如何。 数据的逻辑结构是反映数据元素之间的逻辑关系的数据结构。 逻辑结构的两个要素：一个是数据要素的集合，通常记为d，第二个是d上的关系，反映d中各数据要素数之间的前后关系，通常记为r。 逻辑结构可以表示为B=(D，r )例，一年四季的数据结构可以表示为B=(D，R)D=春、夏、秋、冬R=春、夏、秋)、(秋、冬) ，数据结构、数据的存储结构的各数据要素在计算机存储空间中的位置关系不一定数据的逻辑结构被存储在计算机的存储空间中的形式称为数据的存储结构(也称为数据的物理结构)。 在数据的存储结构中，不仅存储各数据要素的信息，

7、还需要存储各数据要素之间的上下文信息。 通常，数据逻辑结构可以按需要表示为多个存储结构，其通常具有存储结构，例如顺序、链路、索引等。 数据结构的图表显示，一个数据结构除了用二项关系表示以外，还可以用图表直观地表示。 例如，用图表显示一年四季的数据结构。 反映家庭间世代关系的数据结构的图形表示。 春、夏、秋、冬、父亲、儿子、女儿、线性结构和非线性结构、数据结构中，没有前件的节点称为根节点，没有后件的节点称为终端节点(叶节点)，其他节点称为内部节点。 根据数据结构中数据元素之间前后关系的复杂度，数据结构通常分为线性结构和非线性结构。 如果非空数据结构满足以下条件：只有一个根节点。 每个节点前件最多

8、1件，后件最多1件。 该数据结构是线性结构，也称为线性表。 当数据结构不是线性结构时，称为非线性结构。 如果数据结构内没有元素，则称为空数据结构。 用线性结构规则处理对一个空数据结构的运算属于线性结构，否则属于非线性结构。 线性表、线性表是由n(n0 )个数据元素a1，a2、an组成的有限数组，表中的各元素除最初外，都有前件，除最后外，只有一个后件。 也就是说，线性表或空表，或者可表示为： (a1、a2、ai、an )、线性表、非空线性表具有以下特征： (a1、a2、a1、a1、a2、a3、a3、a4、a5、a5、a6、a6、 n=0时，称为空表。 线性表的顺序记忆结构和线性表的顺序记忆结构有

9、两个基本特征。 线性表中的所有要素所占的记忆空间是连续的线性表中的各要素以逻辑的顺序依次被存储在记忆空间中。 在线性表的顺序存储结构中，其前后两个元素在存储空间中相邻，前面的元素必须存储在后面的元素之前。 编程通常定义表示线性表顺序存储区域的一维数组。线性表的插入运算一般来说，要在第I个元素之前插入新元素，首先从最后一个元素开始，第n-i 1个元素依次向后移动，移动结束后，第I个位置为空，新元素插入到第I个项目中。 平均地插入新元素需要移动表中的一半元素，效率很低。 线性表删除运算通常要删除第I个元素，从第I个元素开始，第n-i个元素按顺序向前移动一个元素。 平均来说，要从线性表中删除要素，需

10、要移动表的一半要素，效率很差。 堆栈、堆栈是仅限于一端插入和删除的线性表。 堆栈中，允许插入和删除的一侧称为堆栈顶部，不允许插入和删除的一侧称为堆栈底部。 堆栈按照“先进后出”或“后进先出”的原则来组织数据。 堆栈有记忆功能。 通常用指针top表示堆栈的顶部位置，用bottom表示堆栈的底部。 在堆栈中插入元素称为堆栈，从堆栈中删除元素(删除堆栈顶部的元素)称为取消堆栈。 堆栈顶部指针top动态地反映了堆栈中元素的变化。 例如，子弹夹子是堆栈，一端闭合，一端开放的容器也是堆栈。 在堆栈的顺序记忆和运算、进入堆栈顶部top，堆栈底部bottom，程序设计中，把一维数据组S(1:m )作为堆栈的顺

11、序记忆空间，把m作为堆栈的最大容量。 top=0表示堆栈空top=m表示堆栈满运算。 在堆栈的顶部插入新元素。 有两个基本的操作。 首先添加一个堆栈指针(top 1)，然后在堆栈指针指向的位置插入新元素。 “溢出”错误：如果堆栈上的指针已经指向存储空间的最后一个位置，则无法进入堆栈。 堆栈运算：取出堆栈的最上面的元素，分配给指定的变量。 有两个基本的操作。 首先将堆栈顶部元素指定给指定变量，然后返回一个堆栈顶部指针(top减1 )“下溢”错误： top=0，堆栈为空，不能再返回堆栈。 装入堆栈顶部元素：将堆栈顶部元素指定给指定变量。 这个运算中堆栈顶部的指针不变。 队列和基本运算，队列：在一端

12、插入，在另一端允许删除的线性表。 列尾：允许插入的一侧用rear指针指示，rear总是指向最后插入的元素的列头：允许删除的一侧用开头指针front指向开头元素的前一个位置。 矩阵是称为“先入先出”或“后出”的线性表，最初插入的元素被删除。 在编程中，把一维数组作为队列的顺序存储空间。 另外，在循环队列和运算，实际应用中，队列顺序存储结构一般采用循环队列的形式。 循环队列：将队列的最后一个位置旋转到第一个位置，形成逻辑环状空间，用于队列循环。 如果使用存储的最后一个位置，并且需要入队操作，则可以将元素添加到第一个位置，只要存储的第一个位置可用。 从开头指针front所指示的下一位置到队列的末尾指

13、针rear所指示的位置为止的所有要素都是队列内的要素。 Q(1:m )、rearm、前、1、2、循环队列和运算，图a是容量为8的循环队列，其中已经有6个元素。 图b表示在图a的循环队列中还有两个要素，而图c表示在图b的循环队列中有一个要素。Q(1:8 )、Q(1:8 )、87875431、87875431、rear、front、rear、front、rear、 (a )有六个元素的循环队列，(b )加入x、y后的队列，(c )退出一个元素后的循环队列，循环队列和运算，队列是空还是满的标志s，s=0队列为空，s=1，前端=rear，队列满。 循环队列初始状态为空，即rear=front=m循环队

14、列有两种操作，即将入队和入队：在循环队列的末尾添加新元素。 有两个基本的操作。 首先，将后退指针前进一个位置(rear=rear 1)，当rear=m 1时，设置rear=1，然后将新元素插入队列的最后一个指针指向的位置。溢出：如果循环队列不是空的，并且队列末尾的指针等于开头的指针，则表示队列已满，不能入队操作。 退出：在循环队列的第一个位置退出元素，并将其分配给指定的变量。 有两个基本的操作。 首先，使开头指针前进1个位置(front=front 1)，在front=m 1的情况下，使front=1，然后，将开头指针指定的要素分配给所指定的变量。 下溢：循环队列为空时，不能进行取消运算。 线

15、性链表，大的线性表，特别是元素波动频繁的线性表，采用链存储结构，而不是顺序存储结构。 在链式存储结构中，每个节点用于存储数据元素的值的部分、被称为数据域的部分、要求由两个部分组成的另一部分用于存储被称为指针字段的指针。 指针是用于指向该节点之前或之后的节点的。 在链型存储结构中，存储空间可以是不连续的，数据节点的存储顺序与数据元素的逻辑关系也可以不一致，并且数据之间的逻辑关系是不能在指针域中确定的。 线性链表：线性表的链存储结构。 在线性链表中，用专用的指针HEAD指定线性表中的第一个数据元素的节点，并且线性表的最后一个元素没有后续元素，指针字段为空(用空或0表示，表示链表结束)。 数据1、数

16、据2、数据nNULL、HEAD，线性链表，HEAD=NULL (或者0 )时称为空表。 堆栈和队列也是线性链表，也可以采用链式存储结构。 线性单链表：每个节点只有一个指针域，只能从该指针域中找到后续节点。 双向链表：在线性链表的各节点中设置两个指针，一个指前一个节点，指被称为左指针的一个后件节点，称为右指针。 链式堆栈：此链式堆栈称为可用堆栈，可以收集计算机存储空间中的所有可用存储节点。 链式队列、线性链表的基本运算、检索线性链表中指定的元素、在非线性链表中检索包含指定元素值x的前一个节点p的基本方法：从开头指针所指的节点开始，没有节点或下一个节点的数据填充以此方式被发现的节点p，如果在线性链

17、表中存在包括元素x的节点，那么被发现的p是链表中不存在包括元素x的节点，所述节点可以是包括第一次遇到的元素x的前一个节点号，并且被发现的p是链表中的最后的节点号。线性链表的基本运算，插入线性链表为了向线性链表中插入新元素，首先给该元素分配新节点，存储该元素的值。 新节点可从可用的堆栈中获得。 线性链表的删除首先从线性链表中找到该节点，将删除的节点返回可用的堆栈。循环链表、循环链表最后一个节点的指针字段不是空，而是指向开头节点。 在循环链表中，如果指定一个节点的位置，则可以访问表的所有其他节点，但是不能在线性链表中。 在循环链表中增加一个报头节点，其数据域是可选的，并且指针域指向线性表中的第一个

18、元素的节点。 在线性链表中，必须分别考虑对空表和第一个节点的处理，但是循环链表实现了空表和非空表的运算统一。 树和二叉树、树是简单的非线性结构，所有数据元素之间有明显的层次特性。 上端节点是前件，下端节点是后件。书、第一章、第二章、第三章、第四章、1.1节、1.2节、2.1节、2.2节、3.1节、树和二叉树、结构中，每个节点只有一个前件，称为父节点。 树中只有一个没有前件的节点，称为树的根节点，简称为根。 在结构中，每个节点可以有多个后缀，其被称为该节点的子节点。 没有后件的节点称为叶节点。 一个节点拥有的后件节点的数量称为该节点的度。 树是分层结构，根节点位于第一层，同一层上所有节点的子节点位于下一层。 树的最大水平叫做树的程度。树中，把某个节点的一个子节点作为根而构成的树称为该节点的一个子树。