二级公共基础知识

《二级公共基础知识》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、二级公共基础知识第1章数据结构与算法1.1算法和数据结构的基本概念1.算法的定义算法是指解题方案的准确而完整的描述。2.算法的复杂度（1）算法的时间复杂度：是指执行算法所需要的计算工作量。（2）算法的空间复杂度：一般是指执行这个算法所需要的内存空间。1.2数据结构的基本概念1.数据结构的定义（1）数据结构是指相互关联的数据元素的集合。（2）数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（3）数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。常用的存储结构有顺序、链接。索引等存储结构。2.线性结构和非线性结构如果一

2、个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件。也最多有一个后件。1.3线性表及其顺序存储结构1.线性表的基本概念线性表是有n(n≥0)个数据元素a1,a2,……an组成的一个有限序列，表中的每一个数据元素，除第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。2.线性表的顺序存储结构（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。3.顺序表的删除运算在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行。即删除第n个元素，则不需要移动表中

3、的元素；如果要删除线性表中的第1个元素，则需要移动表中所有的元素。1.4栈和队列1.栈的特点栈是一种特殊的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈是按照“先进后出”（FILO----FirstInLastOut）或“后进先出”（LIFO----LastInFirstOut）的原则组织数据的。2.队列的特点（1）队列（queue）是指允许在一端进行插入、而在另一端进行删除的线性表。队列又称为“先进先出”（FILO----FirstInFirstOut）或“后进后出”（LILO---LastInLastOut）的线

4、性表。（2）循环队列的特点所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。1.5树与二叉树1.树的基本概念树（tree）是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特征。1.二叉树的定义（1）非空二叉树只是一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。3.二叉树的遍历（1）前序遍历（DLR）首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。（2）中序遍历(LDR)

5、首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历(LRD)首先遍历左子树，然后遍历左子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。1.6查找技术1.顺序查找在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。在平均情况

6、下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。2.二分法查找二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列。对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较log2n次，而顺序查找需要比较n次。1.7排序技术1.交换类排序法交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。2.插入类排序法插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中，包括简单插入排序法和希尔排序法。3.选择类排序法选择排序法的基本思想

7、是扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置），然后对剩下的子表采用同样的方法，直到子表空为止。包括简单选择排序法和堆排序法。第2章程序设计基础2.1程序设计方法与风格程序设计的方法和技术，主要经过了结构化程序设计和面向对象的程序设计阶段。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。要形成良好的程序设计风格，应注重和考虑这些因素；源程序文档化、数据说明的方法、语句的结构、输入和输出。2.2结构化程序设计结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。结构化程序设计的三种

8、基本结构分别为：顺序结构、选择结构和循环结构。2.3面向对象的程序设计1.关于面