等考三级数据库考点分析：数据结构与算法

考点1数据结构的基本概念

1。数据
在计算机系统中，数据不仅包含通常的数值概念，还具有更广泛的含义。我们把计算机对客观事物进行识别、存储和处理的描述统称为数据。简而言之，数据是计算机化的信息。
数据的基本单位是数据元素。一个元素可以由一个或多个数据项组成。它是数据项的最小不可分单位，也称为键，其值可以决定一个数据元素的数据项。
2。数据结构
数据结构包括三个方面:数据之间的逻辑关系，数据在计算机中的存储方式，以及在这些数据上定义的操作集合。
(1)数据的逻辑结构。数据的逻辑结构与数据在计算机中的存储方式无关。它用于抽象地反映数据元素之间的逻辑关系。逻辑结构可分为线性结构和非线性结构。最常见的线性结构是线性表，最典型的非线性结构是树结构。
(2)数据的存储结构。数据的存储结构实现了数据在计算机中逻辑结构的存储问题，存储结构也叫物理结构。存储结构分为顺序存储结构和链式存储结构。
(3)数据的操作。数据的各种逻辑结构都有相应的操作，每个逻辑结构都有一组操作。数据操作主要包括搜索、排序、插入、更新和删除。

2考点的主要数据存储方式

数据的逻辑结构映射到计算机内存的方式有很多种。顺序存储结构和链式存储结构是两种最重要的存储方式。

1.顺序存储结构
顺序存储结构将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，节点之间的关系由存储单元的相邻关系决定。它主要用于存储线性数据。顺序存储结构的主要特征如下。
(1)由于节点之间的关系是由物理邻接关系决定的，所以一个节点中没有链接信息域，只有自己的信息域，在空之间存储密度高，利用率高。
(2)数据结构中第I个节点的内存地址B可以用下面的公式计算:
Li = l0+(I-1) × k
l0是第一个节点的内存地址，左边是每个节点占用的内存单元数。
(3)插入和删除操作会导致大量对应的节点移动。每个节点的物理地址是相邻的，每次插入和删除操作都会引起相应节点物理地址的重排。

2.链式存储结构
链式存储结构打破了计算机存储单元的连续性，两个逻辑上相邻的数据元素可以存储在物理上不相邻的存储单元中。链式存储结构的每个节点至少有一个节点域，反映了数据之间的逻辑联系。
链式存储结构的主要特点包括以下几个方面。
(1)一个节点除了自信任和自信任之外，还有一个表示链接信息的指针字段，所以存储密度低于顺序存储结构，存储空之间的利用率更低。
(2)洛基上的相邻节点不一定是物理相邻的，可以用于线性表、树、图等各种逻辑结构的存储表示。
(3)插人、删人等操作灵活方便，不需要移动很多节点，只需要修改节点的指针值即可。3测试中心算法的设计与分析

在计算机领域，算法本质上是在数据的逻辑结构和存储结构的基础上强加的操作，以满足所处理问题的需要。它是解决具体问题的方法。一个算法占用的计算机资源包括时间开销和空之间的开销。时间成本的含义是:当问题的规模在某个单位内从1增加到n时，算法求解问题的运行时间也在某个单位内从f( 1)增加到f(n)，所以算法的时间成本称为f(n)。
空之间的代价是指当问题的规模在某个单位内从1增加到N时，算法求解问题所占用的空在某个单位内也从g(1)增加到g(n)，因此算法的空之间的代价称为g(n)。

2。线性表

线性表的逻辑结构是n个数据元素的有限序列。线性表包含的元素个数称为线性表的长度。它是可变的。可以从线性表中添加或删除元素。线性表包括顺序表、链表、哈希表和字符串。
线性表的基本操作包括:设置表空、查找表长、读取表元素、插入人、删除、搜索。

4测试点序列表和一维数组

线性表的顺序存储是线性表最简单的存储结构。存储方法如下:在内存中为线性表打开一个连续的存储室空，存储室空中包含的存储单元个数大于等于线性表的长度，这样线性表的第一个元素存储在存储室空的第一个单元中，第二个元素存储在第二个单元中，其他元素依次存储。一般情况下，如果序列表的长度为n，土壤插入或删除的概率在任意位置都是相等的，元素移动的平均次数为n/2。

5考点链接列表

链表分为线性链表和非线性链表。线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。

1.线性链表
线性链表也叫单链表，每个节点只包含一个指针字段。插入或删除链表时，只需要改变节点中指针字段的值。
(1)在指针一p后插入指针9的关键操作步骤:
q ↑。链接:= p ↑。链接:
p ↑。链接:= q；
(2)删除指针P后面的节点Q的关键操作步骤:
Q: = p ↑。链接；
p↑。链接:=q↑。链接；
(3)在第一个节点(或头节点)前插入指针p的关键操作步骤:
p ↑。链接:=头；
头:两个p；
(4)删除表中头节点的关键操作步骤:
head: = head ↑。链接:

2.双向链表
在双向链表中，每个节点都有两个指针字段，分别用来指向它的前一个节点和后一个节点。Rlink指向节点的后继，llink指向节点的前任。这种结构便于向后和向前搜索。
(l)要删除双向链表中指针P指向的节点，只需修改它的前置rlink字段和后续Mink字段，如下:
p ↑。llink ↑。rlink: = p ↑。rlink
P↑T.rlink↑。llink:=P↑。llink
(2)如果要在指针P之后插入指针Q指向的新节点，只需要修改指针P指向的节点的rlink字段和原来的后续平均Ilink字段，重新设置Q指向的节点的Mink和rlink值，步骤如下:
q ↑。貂:= p:
q ↑。rlink:
P↑。rlink r . Rink:= q；
p↑。rlink:= q；
[br/]3。Available 空表
available空表的作用是管理链表中可以插入和删除的节点。当链表插入器需要一个新节点时，从available 空表中删除第一个节点。当从链表中删除一个节点时，它被插入到available 空表中第一个节点的前面。

6考点站

栈，也称栈，是一种特殊的线性表，操作有限。只能插入和删除表格的一端。桌子顶端可以操作，底端是另一端。表中没有任何元素的栈称为空栈。因为栈的插入和删除操作只在栈顶执行，后面进入栈的元素必须先删除，所以栈也叫“LIFO”表。
栈的基本操作有:
(1)push(S，X)。将新的顶部元素X插入(或推入)堆栈S，即推入堆栈。[br/](2)砰的一声.从堆栈中删除(或弹出)顶部的元素，即弹出堆栈。
(3)lop(S，X):将栈S的顶元素读入变量X，栈不变。
(4)空的.判断栈S是否是空栈，如果是，返回值为真。使成为空的.将堆栈设置为空。
由于栈是线性表，线性表的存储结构也适用于栈。堆栈通常存储在顺序存储器中。分配一个连续的存储区域来存储堆栈中的元素，并使用一个变量来指向当前堆栈的顶部。

7考点队列

队列简称队列。也是线性表，操作有限。队列的限制是只能插入表的一端，另一端可以删除。删除的结尾称为队列头，插入的结尾称为队列尾。
队列的基本操作有:
(1) enq(Q，X)。在队列的末尾插入一个新元素X，即人类队列。
(2)deq从队列Q中删除队列头元素，即出列。
(3)前端端口，x)将队列端口的队列头元素值读入变量x，队列保持不变。
(4)空(q)。判断队列是否坏，L口是否空，如果是，返回值为真。
(5)makempty将队列端口设置为空 queue。
和线性表一样，队列有两种存储方式:顺序存储和链式存储。队列在队列操作时，会产生假溢出。解决方案是将队列首尾相连，形成一个循环队列。

8烤点串

字符串是零个或多个字符的有限序列。零个字符的字符串是空字符串。字符串中的字符数就是字符串的长度。字符串中的字符可以是字母、数字或其他字符。
字符串存储也有两种:顺序存储和链式存储。按顺序存储时，可以使用非压缩模式或压缩模式。
字符串的基本操作包括连接、赋值、求长、同余比较、求子串、求子串位置和替换等。其中，寻找子串位置(或模式匹配)更为重要。

3.多维数组、稀疏矩阵和广义表

9多维数组在测试点的顺序存储

多维数组是一维数组的推广。多维数组的所有元素并不是按线性顺序排列的。要按顺序存储多维数组，所有元素都需要按一定顺序排列成线性序列。有两种常用的排序顺序:行优先级和列优先级。

测试站点10稀疏矩阵的存储

稀疏矩阵是指一个矩阵包含大量的0元素。稀疏矩阵可以压缩存储，即只存储其中的非零元素。如果非零元素的分布是有规律的，可以用顺序法存储非零元素。对于一般的稀疏矩阵，常用的存储方法有非元组法和交叉链表法，这里就不介绍了。

测试点11通用表的定义和存储

广义表(也叫列表)是线性表的另一种推广，线性表是由零个或多个单元素或子表组成的有限序列。它与线性表的区别在于，线性表中的所有元素都是结构上不可分的单个元素，而广义表中的元素可以是单个元素，也可以是结构化表。与线性表相比，广义表有以下三个特点。
(1)广义表的元素可以是子表，子表的元素也可以是子表。
(2)一个广义表可以被其他广义表引用。
(3)广义表可以是递归表，即广义表也可以是自身的子表。