计算机二级C语言公共公共基础知识部分

把这些看懂,背会,二级c基础部分30分可以完全得到。

第1章数据结构与算法

1.1算法

1．算法的概念：是指解题方案的准确而完整的描述

2．算法的基本特征：可行性、确定性、有穷性(有限的时间)、拥有足够的情报

3．算法的复杂度：时间复杂度和空间复杂度

(1)时间复杂度：算法所需要的计算工作量（算法所执行的基本运算次数）

(2)空间复杂度：执行这个算法所需要的内存空间

1.2数据结构的基本概念

1．数据结构研究的三个问题

(1)逻辑结构：指反应数据元素之间逻辑关系的数据结构

(2)存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。

(3)对各种数据结构进行的运算

2．数据结构定义：是指带有结构的数据元素的集合。所谓结构就是指数据元素之间的前后件关系。

在数据结构中，没有前件的结点称为根结点，没有后件的结点为终端结点（也叫叶子结点）。

3．空的数据结构：一个元素都没有的数据结构。

4．数据结构的种类：线性结构与非线性结构。

线性结构：有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。

非线性结构：如果一个数据结构不是线性结构，则称之为非线性结构。

1.3线性表及其顺序存储

1．线性表是最简单、最常用的一种线性结构。

2．非空线性表的结构特征：

(1)有且只有一个根结点，无前件

(2)有且只有一个终端（叶子）结点，无后件

(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

在线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。

3．线性表顺序存储结构的基本特点：

(1)所有元素所占的存储空间是连续的

(2)各元素在存储空间中是按逻辑顺序依次存放的

4．在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素的平均个数是为n/2。

1.4栈和队列

1．栈：限定在一端进行插入与删除的线性表。

2．栈的结构特点： 先进后出 或 后进先出

3．栈的基本运算：入栈运算、退栈运算、读栈顶元素

(1)上溢：当栈空间已满，不能再入栈时，称为“上溢”。

(2)下溢：当栈空间已空，不能再出栈时，称为“下溢”。

4．队列：允许在一端进行插入、而在另一端进行删除的线性表

5．队列的结构特点： 先进先出 或 后进后出