全国计算机二级公共基础知识
一、数据结构与算法
数据结构指的是数据之间的相互关系，即数据的组织形式。
数据结构用来反映一个数据的内部构成，即一个数据由哪些成分构成、以什么方式构成、呈现什么样的结构。数据结构有逻辑上的数据结构和物理上的数据
结构之分。逻辑上的数据结构反映数据之间的逻辑关系，而物理上的数据结构反映数据
在计算机内部的存储安排。数据结构是数据存在的形式。
算法是解题的步骤，是指令的有限序列。它们规定了解决某一特定类型问题的一系
列运算，是对解题方案的准确与完整的描述。一个问题的解决方案要以算法为基础。
概念介绍
◆ 算法的时间复杂度：
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
算法的工作量=f(n) 其中n是问题的规模。
例如，两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n3，即计算工作量为n3，也就是时间复杂度为n3。
◆ 算法的空间复杂度：
算法的空间复杂度一般是指执行这个算法所需要的内存空间。 ◆数据的逻辑结构
数据元素相互之间的关系，称为结构。
数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。 ◆数据的存储结构
数据的存储结构：是数据的逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构。
各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构。
数据的顺序存储方式：是将逻辑上相邻的结点存储在物理位置上亦相邻的存储
单元里。也就是将所有存储结点相继存入在一个连续相邻的存储区里。
数据的链式存储方式：是在存储每个结点信息的同时，增加一个指针来表示结
点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。因此，链式存储结构中的每个结点都由两部分组成：一部分用于存储结点本身的信息，称为数据域；另一部分用于存储该结点的后继结点(或前驱结点)的存储单元地址，称为指针域。指针域可以包含一个或多个指针，这由结点之间的关系所决定。
◆线性结构和非线性结构
如果在一个线性结构中，一个数据元素都没有，则称该数据结构为空数据结构。
线性结构的逻辑特征：在一个非空的数据结构中，除第一个数据元素只有一个
后继没有前驱、最后一个数据元素只有一个前驱没有后继外，其他的每一个数据元素仅有一个前驱和一个后继。线性结构也称为线性表。
注：某个元素直接相邻的前一个元素称为此元素的前驱、直接相邻的后一个元素称为此元素的后继。
非线性结构的逻辑特征：在一个非空的数据结构中，某数据元素可能有多于一
个前驱或后继。如树型结构等。
习题：
（一）选择题(单选)
1. 算法的时间复杂度是指（D） A) 算法的执行时间 B) 算法所处理的数据量
C) 算法程序中的语句或指令条数
D) 算法在执行过程中所需要的基本运算次数
线性表
线性表是由同一类型的数据元素构成的一种线性的数据结构。是一种最基本、最常用的数据结构。线性表常用的存储方式有两种：顺序存储方式和链接存储方式。
线性表的数学定义：
L=(a1,a2,a3,…,an) 说明：
线性表是具有相同类型的n(n≥0)个数据元素组成的有限序列。 L：为表的名称。
ai(i=1,2, …,n)：为表的元素，也称为线性表中的一个结点。它可以是一个数、一个字符、一个字符串，也可以是一条记录，还可以是复杂的数据对象。a1是a2的前驱、a2是a1的后继， a2是a3的前驱、a3是a2的后继，…，依次类推。
n：为线性表的长度(元素个数)，当n=0时称线性表为空表。
线性表的特点：
在非空的线性表中：存在唯一的一个“第一个元素”(根结点)。存在唯一的一个“最后一个元素”(终端结点)。除第一个元素外，其他的元素均有唯一的前驱。除最后一个元素外，其他的元素均有唯一的后继。
栈和队列
栈和队列本质上也是线性表，只是它们的操作受到了限制。