无锡计算机二级培训关于公共基础知识汇总
1.线性结构与非线性结构
一个非空的数据结构满足以下2个条件：
（1）有且只有一个根结点
（2）每一个节点多有一个前件，也多有一个后件
则称为线性结构数据结构。不符合则为非线性结构。
    如果在一个线性结构中一个数据元素也没有，则称为空的数据结构。线性数据结构和非线性数据结构都可以是空的数据结构，若对一个空的数据结构的运算时按线性结构的规则来处理，则是属于线性结构，否则是非线性结构。
2.线性表的顺序存储结构有以下两个基本特点：
（1）线性表中所有元素所占的存储空间是连续的。
（2）线性表中各个数据元素在存储空间中按逻辑顺序依次存放的。（前后两元素师紧邻的）
3.栈(stack)是限定在一端进行插入与删除的线性表。允许插入与删除的叫栈顶，另一端（封闭的）叫栈底。栈，先进后出，后进先出，所以具有记忆作用。
    通常有指针top来指示栈顶，指针bottom指向栈底，向栈中插入一个元素，称为入栈运算，删除（取出栈顶元素）则为退栈运算。
4.在程序设计语言中，用一维数组S（1：m）作为栈的顺序存储空间，其中m为大容量。S(bottom)为栈底元素，s(top)为栈顶元素（此为非空情况）。Top=0为栈空，top=m为栈满。
     入栈运算，将栈顶指针进一，即top加1，然后将新元素插入到栈顶指针指向的位置。
    退栈运算，先将栈顶元素赋给一个的变量，然后将栈顶指针退一，即top减1。当栈顶指针为0时，不能进行退栈操作，这种情况称为“下溢”错误。
     读栈顶元素，即指将栈顶元素赋给一个的变量。这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此在这个运算中，栈顶指针不会改变。
5.循环队列有两种基本运算：入队运算与出队运算。
    入队运算，队尾指针进一。当队尾指针rear=m+1时，置rear=1，然后将新元素插入到队尾指针指向的位置。循环队列满，不能进行入队运算，这种情况称为“上溢”。
    出队运算，排头指针进一。当排头指针front=m+1时，置front=1，然后将排头指针指向的元素赋给的变量。循环队列空，不能进行退队运算，这种情况称为“下溢”。
6.循环链表的结构，增加了一个表头结点，其数据域为任意（根据需要设置）头指针指向其结点；最后一个结点的指针域不是空，而是指向表头结点。所以结点的指针构成一个环状链。
循环链表的优点（与线性单链表相比）
1）  循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有结点，而单链做不到。
2）  循环链表中至少有一个结点存在（表头结点），使得空表与非空表的运算统一。  
7.树（tree）是一种简单的非线性结构。
端点是前件，下端点是后件。
    结构中，每一个结点前只有一个前件，称为父结点。在树中，没有前件的结点只有一个，称为根结点，即树的根。
一个结点可以有几个后件，称为该结点的子结点。没有后件的结点称为叶子结点子树（K B E）。
8.顺序查找：在线性表中，依次查找元素。
    二分法查找：只适用于顺序存储的有序表。有序表是按非递减排列表（从小到大，可以相邻元素相等）
    将被查元素与线性表的中间项相比较，二者的值若相等，则查到，若被查元素的值小，则按相同方法查前半部分。
二分法效率相对较高。
9.  冒泡排序
交换类排序法{  排序
排除技术{ 选择类排序{ 简单选择排序  
排序堆
插入排序法{简单插入法排序
希尔排序法
10.常用工具：
1）数据流图（DFD）：描述处理过程。从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。
主要图形元素如图：
2）数据字典（DD）：结构化分析方法的核心。是对所有与系统相关的数据元素的一个有组织的列表。包含的信息有：名称、别名、何处使用/如何使用、内容描述、补充信息等。
3）  判断树
4）  判断表
4．软件需求说明书