两个计算机基础知识(计算机两大基础）

计算机二级公共基础知识

1算法的基本概念

1.通常，算法应该具有以下基本特征：可行性、确定性、有穷性、拥有足够的情报.

算法是对求解方案准确完整的描述，是一组严格定义运算顺序的规则，每条规则都是有效的、清晰的，并且这个顺序会在有限的次数内终止。

2.算法的基本要素。

(1)算法中数据的运算和操作。通常有四类：算术运算，逻辑运算，关系运算和数据传输.

(2)算法的控制结构。算法的功能不仅取决于所选择的操作，还取决于操作之间的执行顺序和算法的控制结构。

3.算法设计的基本方法。

算法设计的基本方法是列举法、归纳法和递推法、递归法和减半递推技术.

4.算法的复杂度(在算法正确的前提下，评价算法的标准)

(1)算法的时间复杂度

算法的时间复杂度是指执行算法所需的计算工作量。算法的工作量由算法执行的基本操作的数量来衡量，它是问题规模的函数。

(2)算法的空间复杂度

算法的空间复杂度一般是指执行这个算法需要的内存空间。算法占用的存储空间包括算法程序占用的空间、输入初始数据占用的存储空间、算法执行过程中需要的额外空间。

数据结构，直接影响算法的选择和效率。数据结构包括两个方面，即数据的逻辑结构和数据的存储结构。

数据之间的关系称为逻辑结构。它通常分为四种基本的逻辑结构，即集合、线性结构、树形结构和图状结构或网状结构.内存结构图是内存中逻辑结构的图像，它包含数据元素的图像和关系的图像。计算机中有两种存储结构，即顺序存储结构和链式存储结构.

时间复杂度和空间复杂度没有必然的关系。

2数据结构基本概念

1.数据结构是指反映数据元素之间若干年的数据元素集合的表示。

2.数据的逻辑结构是指映射的数据元素之间的逻辑关系的数据结构。数据的逻辑结构有两个元素：一个是数据元素的集合；第二是数据元素之间的关系。

3.每个数据元素在计算机存储空间中的位置关系不一定与它们的逻辑关系相同。数据的逻辑结构在计算机存储空间中的存储形式称为数据存储结构(也称数据的物理结构)。

3线性表和线性链表

1.线性结构和非线性结构

根据数据结构中数据元素之间关系的复杂程度，数据结构一般分为线性结构和非线性结构两种。如果非空数据结构满足以下两个条件：

(1)只有一个根节点。(2)每个节点最多有一个前部和一个后部。

那么数据结构就不是线性结构，就叫非线性结构。

如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键字，则称其为本关系的外关键字

2.线性表的基本概念

线性表由n(n