高中 CSP初试精讲精练 第二节 数据结构（基础）

CSP-J/S初赛知识点精讲精练第二讲

数据结构基础04九月2024线性表线性结构在数据元素存在非空有限集中：存在唯一的一个被称为“第一个”的数据元素。存在唯一的一个被称为“最后一个”的数据元素。除了第一个外，集合中每个数据元素都只有一个前趋元素。除了最后一个外，集合中每个数据元素都只有一个后继元素。线性表线性表有n个数据元素的有限序列，同一个线性表中的元素必定有相同特性，元素之间存在序偶关系。线性表中的元素个数n(n>=0)定义为该表的长度，当n==0时称为空表，非空表中每个数据元素都有一个确定的位置。线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。线性表线性表(List)有n个数据元素的有限序列，同一个线性表中的元素必定有相同特性，元素之间存在序偶关系。线性表中的元素个数n(n>=0)定义为该表的长度，当n==0时称为空表，非空表中每个数据元素都有一个确定的位置。线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。依据存储结构不同的分类顺序存储结构的顺序表链式存储结构的链表（单链表、静态链表、循环链表、双向链表）线性表线性表的特点：1.数据元素的个数n定义为表的长度。2.n=0时为空表。3.将非空的线性表(n>0)记作：(a1,a2,…an)4.数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同情况下不同。5.同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。线性表是典型的线性结构。顺序表概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。特点：逻辑上相邻的数据元素，物理次序也是相邻的。只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。顺序表的优缺点优点：无须为表中元素之间的逻辑关系而增加额外的存储空间；可以快速存取表中任一位置元素。缺点：插入和删除操作需要移动大量元素；当线性表长度较大时，难以确定存储空间的容量；造成存储空间的“碎片”。链表在链式结构中，除了要存储数据元素的信息外，还要存储它的后继元素的存储地址。因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。例题一链表不具有的特点是（

）A.插入删除不需要移动元素B.不必事先估计存储空间C.所需空间与线性表长度成正比D.可随机访问任一元素D栈与队列栈（Stack）支持push与pop两种操作的数据结构。从顶端放入，从顶端取出。最后入栈的数据最先被取出，被称为LastInFirstOut，简称LIFO表。栈顶：栈最顶端的元素。栈底：栈最底端的元素。栈与队列栈（Stack）<stack>头文件stack<int>a声明int型栈aa.push(x)往栈顶前添加一个元素x。a.pop(

)从栈顶弹出（删除）一个元素。a.top(

)返回栈顶的值。a.empty(

)返回是否为空。（1为空，0为非空）a.size(

)返回栈里的元素个数。例题二某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（

）A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2C栈与队列队列（Queue）支持push与pop两种操作的数据结构。从队尾放入，从队首取出。最初放入的数据最先被取出，被称为FirstInFirstOut，简称FIFO表。队首/队头：队列的第一项。队尾：队列的最后一项。栈与队列队列（Queue）<queue>头文件queue<int>a声明int型队列aa.push(x)往队尾后添加一个元素x。a.pop()从队首弹出（删除）一个元素。a.front()返回队首的值。a.back()返回队尾的值。a.empty()返回是否为空。（1为空，0为非空）a.size()返回队列里的元素个数。树树是n（n>=0）个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：有且仅有一个特定的称为根的结点。当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。树父亲（parentnode）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。根结点没有父结点。祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。子结点（childnode）：如果u是v的父亲，那么v是u的子结点。子结点的顺序一般不加以区分，二叉树是一个例外。在分支结点中,每个结点的分支数就是该结点的度。度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。结点的深度（depth）：到根结点的路径上的边数。树的高度（height）：所有结点的深度的最大值。兄弟（sibling）：同一个父亲的多个子结点互为兄弟。后代（descendant）：子结点和子结点的后代。子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。二叉树二叉树：所有结点的子节点个数都不超过二的树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。完整二叉树（full/properbinarytree）：每个结点的子结点数量均为0或者2的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。完全二叉树（completebinarytree）：只有最下面两层结点的度数可以小于2，且最下面一层的结点都集中在该层最左边的连续位置上。完美二叉树（perfectbinarytree）：所有叶结点的深度均相同，且所有非叶节点的子节点数量均为2的二叉树称为完美二叉树。例题三一棵二叉树如图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标2i+1处），则该数组的最大下标至少为（

）。A.6B.10C.15D.12CDFS深度优先搜索深度优先搜索算法（DepthFirstSearch，简称DFS）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。二叉树的DFS包括：先序遍历、中序遍历、后序遍历DFS深度优先搜索DFS：先序遍历按照根，左，右的顺序遍历二叉树。DFS深度优先搜索DFS：中序遍历按照左，根，右的顺序遍历二叉树。DFS深度优先搜索DFS：后序遍历按照左，右，根的顺序遍历二叉树。例题四DFS反推根据先序遍历，写出其余两种遍历。先序遍历：ABDEHCFGI

例题四DFS反推根据先序遍历，写出其余两种遍历。BFS广度优先从树根开始，严格按照层次来访问节点。BFS过程中也可以顺便求出各个节点的深度和父亲节点。树的层序遍历树层序遍历是指按照从根节点到叶子节点的层次关系，一层一层的横向遍历各个节点。根据BFS的定义可以知道，BFS所得到的遍历顺序就是一种层序遍历。但层序遍历要求将不同的层次区分开来，所以其结果通常以二维数组的形式表示。下图的树的层序遍历的结果是[[1],[2,3,4],[5,6]]（每一层从左向右）图图(graph)是一个二元组G=(V(G),E(G))。其中V(G)是非空集，称为点集(vertexset)，对于V中的每个元素，我们称其为顶点(vertex)或节点(node)，简称点；E(G)为V(G)各结点之间边的集合，称为边集(edgeset)，对于E中的每个元素，我们称其为边(Edge)。常用G=(V,E)表示图。图完全图：任意两点都有边相连，一个n个节点完全图的边数为Cn2简单路径：两点之间通过不重复的边相连。连通图：任意两点都