全国计算机二级公共基础知识--复习

全国计算机二级公共基础知识一、数据结构与算法数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构用来反映一个数据的内部构成，即一个数据由哪些成分构成、以什么方式构成、呈现什么样的结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映数据之间的逻辑关系，而物理上的数据结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式。算法是解题的步骤，是指令的有限序列.它们规定了解决某一特定类型问题的一系列运算,是对解题方案的准确与完整的描述。一个问题的解决方案要以算法为基础。1.1 概念介绍◆ 算法的时间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f（n)其中 n 是问题的规模. 例如，两个 n 阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为 n3，即计算工作量为 n3，也就是时间复杂度为 n3。◆ 算法的空间复杂度:算法的空间复杂度一般是指执行这个算法所需要的内存空间。◆数据的逻辑结构数据元素相互之间的关系，称为结构.数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。◆数据的存储结构数据的存储结构：是数据的逻辑结构在计算机存储空间中的存放形式。也称数据的物理结构.各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。同一种数据的逻辑结构可以根据需要表示成任意一种或几种不同的存储结构.数据的顺序存储方式：是将逻辑上相邻的结点存储在物理位置上亦相邻的存储单元里.也就是将所有存储结点相继存入在一个连续相邻的存储区里。数据的链式存储方式：是在存储每个结点信息的同时,增加一个指针来表示结点间的逻辑关系。该方式不要求逻辑上相邻结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。因此,链式存储结构中的每个结点都由两部分组成：一部分用于存储结点本身的信息，称为数据域；另一部分用于存储该结点的后继结点（或前驱结点）的存储单元地址，称为指针域。指针域可以包含一个或多个指针，这由结点之间的关系所决定.◆线性结构和非线性结构假如在一个线性结构中，一个数据元素都没有,则称该数据结构为空数据结构.线性结构的逻辑特征：在一个非空的数据结构中,除第一个数据元素只有一个后继没有前驱、最后一个数据元素只有一个前驱没有后继外，其他的每一个数据元素...