二级公共基础部分.doc

数据结构与算法 算法 1、算法是指解题方案的准确而完整的描述。算法不等于程序，也不等计算方法算法的基本特征（1）可行性 （2）确定性（3）有穷性算法必须在有限的时间内算法复杂度时间复杂度和空间复杂度 （1）算法时间复杂度是指执行算法所需要的计算工作量算法空间复杂度是指执行这个算法所需要的内存空间。 线性表及其顺序存储结构 1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。2、非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 3、线性表是一种存储结构，它的存储方式：顺序和链式。 4、线性表的顺序存储结构具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 栈是限定在一端进行插入与删除的线性表允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”组织数据。栈的基本运算：1）插入元素称为入栈运算；2）删除元素称为退栈运算；3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。指针Rear）指向队尾，指针front）指向。front rear 队列是“先进出”或“后进后出”的线性表。队列运算包括1）入队运算：从队尾插入一个元素2）退队运算：从队头删除一个元素。 树与二叉树 1、树的基本概念 树是一种简单的非线性结构所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 （2）二叉树的基本性质 下图a表示的是满二叉树，下图b表示的是完全二叉树： 4、 在计算机中，二叉树通常采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历 （1）前序遍历（DLR）（2）中序遍历（LDR） （3）后序遍历（LRD）次。 *：对于。 排序技术 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列 1、交换类排序法插入类排序法选择类排序法n(n-1)/2 快速排序 选择基准元素，通过交换，划分成两个子序列 n(n-1)/2 插入类 简单插入排序 待排序的元素看成一个有序表和一个无序表，将无序表中元素插入到有序表中 n(n-1)/2 希尔排序 分割成若干个子序列分别进行直接插入排序 O(n1.5) 选择类 简单选择排序 扫描整个线性表，从中选出最小的元素，将它交换到表的最前面 n(n-1)/2 堆排序 选建堆，然后将堆顶元素与堆中最后一个元素交换，再调整为堆 O(nlog2n) 程序设计基础 程序设计风格序言性注释和功能性注释结构化程序设计 1、结构化程序设计方法的原则自顶向下逐步求精自顶向下逐步求精结构化程序的基本结构： 1）顺序结构一种简单的程序设计，最基本、最常用的结构 2）选择结构又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列 3）重复结构又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。面向对象的程序设计对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强注意当使用“对象”这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是，当使用“实例”这个术语时，必然是指一个具体的对象。 例如：Integer是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，而一个具体的整数“123”是类Integer的实例。 由类的定义可知，类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。 继承是面向对象的方法的一个主要特征计算机软件是包括程序、数据及相关文档的完整集合。 成本、质量、生产率等问题。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序