大学生计算机考试二级公共基础知识总结.docVIP

PAGE 9 二级公共基础知识总结 第一章 数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 算法的基本特征： （1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性。算法中每一步骤都必须有明确的定义，不允许有模棱两可的解释，不允许有多义性。 （3）有穷性。算法必须在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。 （4）拥有足够的情报。 *：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 算法复杂度包括：时间复杂度和空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。可以用执行算法的过程中所需基本运算的执行次数来度量。 算法空间复杂度是指执行算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构是指相互有关联的数据元素的集合。 数据结构研究的三个方面 （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。 数据的逻辑结构包含： （1）表示数据元素的信息。 （2）表示各数据元素之间的前后件关系。 （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。数据的存储结构有顺序、链接、索引等。 （3）对各种数据结构进行的运算。 数据结构分为两大类型：线性结构和非线性结构。 （1）线性结构（非空的数据结构）条件：1）有且只有一个根结点；2）每一个结点最多有一个前件，也最多有一个后件。 *：常见的线性结构有线性表、栈、队列和线性链表等。 （2）非线性结构：不满足线性结构条件的数据结构。 *：常见的非线性结构有树、二叉树和图等。 1.3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）有且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外其它所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。 1.4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”或“后进先出”组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算： （1）插入元素称为入栈运算； （2）删除元素称为退栈运算； （3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进行插入，而在另一端（队头）进行删除的线性表。 rear指针指向队尾，front指针指向队头。 队列是“先进先出”或“后进后出”的线性表。 队列运算包括： （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。 循环队列及其运算：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素均为队列中的元素。 循环队列：s=0表示队列空，s=1且front=rear表示队列满。 1.5 线性链表 数据结构中每一个结点对应于一个存储单元，这种存储单元称为存储结点，也称结点。 结点由两部分组成：（1）用于存储数据元素值，称为数据域； （2）用于存放指针，称为指针域，用于指向前一个或后一个结点。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式既可用于表示线性结构，也可用于表示非线性结构。 线性链表：head称为头指针，head=NULL（或0）空表，如果是两指针：左指针指向前件结点，右指针指向后件结点； 线性链表的基本运算：查找、插入、删除。 1.6 树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为