计算机二级公共基础知识总结-

第1章数据结构与算法1.1算法的复杂度1.算法的基本概念1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。*算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。（1）算法的基本特征算法一般具有4个基本特征：可行性、确定性、有穷性、拥有足够的情报。注:&确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；&有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；*算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。（2）*算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。（3）*算法的3种基本控制结构是：顺序结构、选择结构、循环结构。（4）算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。（5）指令系统:指的是一个计算机系统能执行的所有指令的集合。2.算法复杂度*算法复杂度包括时间复杂度和空间复杂度。注意两者的区别，无混淆，见表1-1。表1-1算法复杂性★★★名称描述时间复杂度执行算法所需要的计算工作量空间复杂度执行这个算法所需要的内存空间1.2数据结构1.2.1逻辑结构和存储结构1.数据结构的基本概念（1）*数据结构:指相互有关联的数据元素的集合。(2)数据结构研究的三个方面：Ⅰ、数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；Ⅱ、在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；Ⅲ、对各种数据结构进行的运算。2.逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成：B=(D,R)3.存储结构数据的存储结构有顺序、链接、索引等。注：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。*：数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构（也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。1.2.2线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。（1）如果一个非空的数据结构满足下列两个条件：*①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。可以用执行算法的过程中所需基本运算的执行次数来度量。则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串、线性链表等都为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。1.2.3线性表及其顺序存储结构线性表的存储结构主要分为顺序存储结构和链式存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。*线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：查找、插入、删除3种。1.3栈（重点）1.栈的基本概念（栈（stack）是一种特殊的线性表）栈是限定在一端进行插入与删除运算的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照“先进后出”（FILO）或“后进先出”(LIFO)的原则组织数据的。栈具有记忆作用。注：用top表示栈顶位置，用bottom表示栈底。当表中没有元素时称为空栈2.栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。计算栈的个数：栈底–栈顶+11.4队列(重点)1.队列的基本概念队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。2.队列运算入队运算是往队列队尾插入一个数据元素；退队运算是从队列的队头删除一个数据元素。队列的顺序存储结构一般采用队列循环的形式。循环队列s=0表示队列空；s=1且front=rear表示队列满。计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。队列是一种特殊的线性表，循环队列是队列的顺序存储结构。1.5链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。线性链表，HEAD称为头指针，HEAD=NULL（或0）称为空表，如果是两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。线性链表的基本运算：查找、插入、删除。1.6树与二叉树★★★★★1、树的基本概念树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。2、二叉树及其基本性质二叉树是一种很有用的非线性结构，具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。基本性质：性质1在二叉树的第k层上，最多有个结点。性质2深度为m的二叉树最多有个个结点。性质3在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。性质4具有n个结点的二叉树，其深度至少为，其中表示取的整数部分3.满二叉树与完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。注意：深度为m的满二叉树最多有个个结点完全二叉树具有以下两个性质：性质1：具有n个结点的完全二叉树的深度为。性质2：设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1，2，……，n给结点进行编号，则对于编号为k（k=1，2，……，n）的结点有以下结论：①若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT（k/2）；②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）；③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储4、二叉树的遍历★★★★二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种(1)前序遍历(DLR)：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。(2)中序遍历(LDR)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。(3)后序遍历(LRD)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点.1.7查找技术查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找成功/查找失败在下列两种情况下也只能采用顺序查找：①如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。查找分为:顺序查找二分法查找二分法查找只适用于顺序存储的有序表(能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。)对于长度为n的有序线性表，最坏情况只需比较次，而顺序查找需要比较n次。注：“有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。下一节排序中，有序的含义也是如此1.8排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。1、交换类排序法（冒泡排序，快速排序）2、插入类排序法（简单插入排序，希尔排序）3、选择类排序法（简单选择排序，堆排序）冒泡排序法,快速排序法,简单插入排序法,简单选择排序法,最坏需要比较的次数为n(n-1)/2希尔排序,最坏需要比较的次数为堆排序,最坏需要比较的次数为相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。（本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。）第2章程序设计基础2.1程序设计的方法与风格清晰第一、效率第二已成为当今主导的程序设计风格。形成良好的程序设计风格需注意：1、源程序文档化；2、数据说明的方法；3、语句的结构；4、输入和输出。注释分序言性注释和功能性注释。语句结构清晰第一、效率第二。2.2结构化程序设计1、结构化程序设计方法的四条原则是：1.自顶向下；2.逐步求精；3.模块化；4.限制使用goto语句。2、结构化程序的基本结构及特点：(1)顺序结构：一种简单的程序设计，最基本、最常用的结构；(2)选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；(3)循环结构：又称重复结构，可根据给定条件，判断是否需要重复执行某一相同或类似的程序段。结构化程序设计的特点：只有一个入口和出口2.3面向对象方法面向对象的程序设计：以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。面向对象方法的优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。*：面向对象的程序设计主要考虑的是提高软件的可重用性。对象是属性和方法的封装体。*：一个对象由对象名、属性和操作三部分组成。面向对象的基本特点：继承性，多态性，封装性*：信息隐蔽是通过对象的封装性来实现的。对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息，操作描述了对象执行的功能，是对象的动态属性，操作也称为方法或服务。对象的基本特点：（1）标识惟一性；（2）分类性；（3）多态性；（4）封装性；（5）模块独立性好。类是指具有共同属性、共