无锡计算机二级培训关于公共基础知识汇总

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．软件需求说明书