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