2026年电大数据结构期末复习材料

2026年电大数据结构期末复习材料同学们，期末考试的脚步临近，数据结构作为计算机相关专业的核心基础课程，其重要性不言而喻。这份复习材料旨在帮助大家系统梳理课程的核心知识点，巩固所学，提升应试能力。请结合教材、课堂笔记以及个人实践，合理利用这份材料，力求在期末取得理想成绩。一、数据结构基本概念1.1数据结构的定义与研究对象数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。其研究对象主要包括：*数据的逻辑结构：指数据元素之间的逻辑关系，独立于计算机，是从具体问题抽象出来的数学模型。主要分为线性结构（如线性表、栈、队列）和非线性结构（如树、图）。*数据的存储结构（物理结构）：指数据逻辑结构在计算机中的具体实现方式。常见的有顺序存储、链式存储、索引存储和散列存储（哈希存储）。*数据的运算：对数据施加的操作，如插入、删除、查找、修改、排序等。运算的实现依赖于具体的存储结构。1.2算法及其复杂度分析*算法：解决特定问题的有限指令序列，具有输入、输出、有穷性、确定性和可行性五大特性。*算法设计的基本要求：正确性、可读性、健壮性（鲁棒性）、高效率和低存储量需求。*时间复杂度：衡量算法执行时间随问题规模增长的量级。常用大O符号表示，关注最坏情况或平均情况。例如：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。分析方法：找出语句频度最高的那条语句作为基本操作，计算其执行次数的数量级。*空间复杂度：衡量算法在执行过程中所需存储空间随问题规模增长的量级。同样用大O符号表示，包括程序本身、输入数据和辅助变量所占用的空间。复习要点：深刻理解逻辑结构与存储结构的区别与联系；能够对简单算法进行时间和空间复杂度分析，尤其是循环嵌套情况下的时间复杂度。二、线性表2.1线性表的逻辑结构线性表是n个具有相同特性的数据元素的有限序列，数据元素之间存在一对一的线性关系。2.2线性表的顺序存储结构（顺序表）*定义：用一组地址连续的存储单元依次存储线性表中的数据元素。*特点：随机存取（通过下标直接访问）；存储密度高；插入和删除操作需要移动大量元素，效率较低。*基本操作实现：初始化、插入（按位/按值）、删除（按位/按值）、查找（按位/按值）、遍历、求表长等。重点掌握插入和删除时元素的移动方向和数量。2.3线性表的链式存储结构（链表）*定义：用一组任意的存储单元存储线性表中的数据元素，每个元素除了存储自身信息外，还需存储指示其后继（或前驱）元素位置的指针（或引用）。*特点：不需要连续的存储单元；插入和删除操作只需修改指针，效率较高；不能随机存取，查找需从头指针开始遍历；存储密度较低（需额外空间存储指针）。*单链表：每个节点包含数据域和一个指向下一节点的指针域。头指针是链表的起始地址。为简化操作，可引入头结点。*循环链表：最后一个节点的指针域指向头结点（或第一个节点），形成一个环。解决了单链表中从尾节点访问头节点需O(n)时间的问题。*双向链表：每个节点包含数据域、一个指向前驱节点的指针域和一个指向后继节点的指针域。可以方便地向前或向后遍历。*链表基本操作实现：初始化、创建（头插法、尾插法）、插入（指定位置前/后）、删除（指定节点）、查找（按值、按位）、遍历等。特别注意指针操作的顺序，避免断链。2.4顺序表与链表的比较与应用选择根据实际问题的需求，如对存取效率、插入删除频率、存储空间等方面的要求，选择合适的存储结构。复习要点：顺序表插入删除的元素移动计算；单链表的各种操作，尤其是指针的修改；能够比较两种存储结构的优缺点并进行选用。三、栈与队列3.1栈（Stack）*定义：一种限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶，表头称为栈底。*特点：后进先出（LIFO）。*存储结构：*顺序栈：用数组实现，需要设置栈顶指针（top）。注意栈空（top=-1或0，取决于初始化方式）和栈满的判断条件。*链栈：用单链表实现，通常以头结点或第一个节点作为栈顶，便于操作。*基本操作：初始化、入栈（Push）、出栈（Pop）、取栈顶元素（GetTop/Peek）、判空等。*应用：表达式求值（中缀转后缀、后缀表达式求值）、括号匹配、函数调用与递归实现、迷宫求解等。3.2队列（Queue）*定义：一种限定仅在表尾进行插入操作，在表头进行删除操作的线性表。表尾称为队尾，表头称为队头。*特点：先进先出（FIFO）。*存储结构：*顺序队列：用数组实现，设置队头指针（front）和队尾指针（rear）。易产生“假溢出”现象。*循环队列：将顺序队列的数组空间想象成一个首尾相接的圆环。通过取模运算来实现队头队尾指针的循环移动。关键是队空和队满的判断条件（通常牺牲一个单元，即(rear+1)%MaxSize==front时为满）。*链队列：用单链表实现，设置头指针（指向队头节点）和尾指针（指向队尾节点）。*基本操作：初始化、入队（EnQueue）、出队（DeQueue）、取队头元素（GetHead）、判空等。*应用：缓冲处理、广度优先搜索（BFS）、操作系统中的进程调度等。复习要点：栈和队列的LIFO、FIFO特性；顺序栈和循环队列的实现细节，特别是栈空栈满、队空队满的判断；栈在表达式求值中的应用。四、串4.1串的基本概念串（字符串）是由零个或多个字符组成的有限序列。空串、空格串、子串、主串、串的长度、串相等的概念。4.2串的存储结构*定长顺序存储：用固定长度的字符数组存储串。*堆分配存储：在堆区动态分配一块连续的存储空间来存储串，长度可变。*块链存储：用链表存储串，每个节点可以存放一个或多个字符。4.3串的模式匹配算法*朴素的模式匹配算法（BF算法）：从主串的第一个字符起，与模式串的第一个字符比较，若相等则继续比较后续字符；若不等，则从主串的下一个字符起重新与模式串的第一个字符比较。时间复杂度较高，最坏情况下为O(n*m)（n为主串长，m为模式串长）。*KMP算法：通过分析模式串本身，找出模式串中隐含的前后缀关系，从而当匹配过程中出现字符不相等时，可以利用这些信息跳过一些不必要的比较，提高匹配效率。核心是部分匹配表（Next数组）的计算。平均时间复杂度有较大改善。复习要点：理解串的基本概念；掌握BF算法的匹配过程；理解KMP算法的改进思想，能够手动计算简单模式串的Next数组。五、数组与广义表5.1数组的定义与存储结构*数组：是线性表的推广，其数据元素为具有相同类型的结构数据（可以是基本类型或构造类型）。n维数组可以看作是n-1维数组的线性表。*存储结构：通常采用顺序存储。*行优先顺序（以行序为主序）：将数组元素按行排列。*列优先顺序（以列序为主序）：将数组元素按列排列。*数组元素的地址计算：给定数组的基地址、每个元素占用的存储单元数以及各维的下界和上界，能够计算指定下标的数组元素的存储地址。5.2特殊矩阵的压缩存储*对称矩阵：元素满足a[i][j]=a[j][i]。只存储主对角线和下（上）三角部分的元素，通常按行优先或列优先存入一维数组。*三角矩阵：上（下）三角矩阵的下（上）三角部分元素均为常数（通常为零）。存储方式类似对称矩阵，额外存储一个常数。*对角矩阵（带状矩阵）：非零元素集中在主对角线及其附近几条对角线上。按一定方式（如对角线顺序）将非零元素存入一维数组，并记录其位置信息。5.3稀疏矩阵*定义：非零元素个数远小于零元素个数的矩阵。*压缩存储方法：*三元组表：每个非零元素用一个三元组（行标，列标，值）表示，再按一定顺序（如行优先）存储这些三元组。*十字链表：每个非零元素对应一个节点，节点中除了行标、列标、值外，还有两个指针域，分别指向同一行的下一个非零元素和同一列的下一个非零元素。5.4广义表（了解）广义表是线性表的进一步推广，其元素可以是单个元素（原子），也可以是广义表（子表）。具有递归性和共享性等特点。复习要点：掌握二维数组按行/列优先存储时元素地址的计算公式；理解对称矩阵、三角矩阵压缩存储的原理和地址计算；了解稀疏矩阵的三元组表示。六、树与二叉树6.1树的基本概念*树：n（n≥0）个节点的有限集。当n=0时为空树；当n>0时，有且仅有一个特定的称为根的节点，其余节点可分为m（m≥0）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树。*基本术语：节点的度、树的度、叶子节点（终端节点）、非叶子节点（非终端节点）、双亲、孩子、兄弟、祖先、子孙、节点的层次、树的深度（高度）、森林等。*树的逻辑结构特点：一对多关系，层次性，根节点无前驱，其他节点有且仅有一个前驱，可有零个或多个后继。6.2二叉树*定义：是n（n≥0）个节点的有限集，它或为空树（n=0），或由一个根节点和两棵互不相交的、分别称为根的左子树和右子树的二叉树组成。*特点：每个节点至多有两棵子树；子树有左右之分，次序不能颠倒（有序树）。*特殊二叉树：*满二叉树：深度为k且含有2^k-1个节点的二叉树。*完全二叉树：深度为k的二叉树，除第k层外，其余各层的节点数均达到最大个数，且第k层的节点都连续集中在最左边。完全二叉树具有良好的性质，便于顺序存储。*二叉排序树（BST）：左子树所有节点值小于根节点值，右子树所有节点值大于根节点值，左右子树也分别为二叉排序树。*平衡二叉树（AVL树）：左右子树的深度之差（平衡因子）的绝对值不超过1的二叉排序树。*二叉树的性质：*性质1：在二叉树的第i层上至多有2^(i-1)个节点（i≥1）。*性质2：深度为k的二叉树至多有2^k-1个节点（k≥1）。*性质3：对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。*性质4：具有n个节点的完全二叉树的深度为floor(log2n)+1或ceil(log2(n+1))。*性质5：完全二叉树中节点的父子关系（已知节点i，求父节点、左孩子、右孩子的编号）。6.3二叉树的存储结构*顺序存储结构：适用于完全二叉树。将节点按层序编号，依次存入数组。对于非完全二叉树，需补空节点，可能浪费空间。*链式存储结构（二叉链表）：每个节点包含数据域、左孩子指针域（lchild）和右孩子指针域（rchild）。n个节点的二叉链表共有n+1个空指针域。根据需要，还可以有三叉链表（增加双亲指针域）。6.4二叉树的遍历遍历是指按某种规律对树中所有节点进行访问且仅访问一次。是树结构中最基本的运算。*先序遍历（DLR）：访问根节点->先序遍历左子树->先序遍历右子树。*中序遍历（LDR）：中序遍历左子树->访问根节点->中序遍历右子树。*后序遍历（LRD）：后序遍历左子树->后序遍历右子树->访问根节点。*层序遍历：从根节点开始，按层次从上到下，同一层从左到右依次访问各节点。（通常借助队列实现）*遍历序列的应用：由遍历序列恢复二叉树（如已知先序和中序，或中序和后序）。6.5线索二叉树*定义：利用二叉链表中的空指针域，存放指向节点在某种遍历序列中的前驱和后继节点的指针（称为线索）。加上线索的二叉树称为线索二叉树。*作用：加快查找前驱和后继节点的速度，可在O(1)或O(logn)时间内找到，无需每次都遍历。*类型：先序线索二叉树、中序线索二叉树、后序线索二叉树。*线索化过程：实质是在遍历过程中修改空指针的过程。6.6树和森林*树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法（二叉树表示法，最常用，可将树和森林转换为二叉树）。*树与二叉树的转换：利用孩子兄弟表示法，树中节点的第一个孩子作为二叉树的左孩子，节点的右兄弟作为二叉树的右孩子。*森林与二叉树的转换：将森林中每棵树分别转换为二叉树，第一棵二叉树不动，从第二棵开始，依次将其根节点作为前一棵二叉树根节点的右孩子。*树和森林的遍历：树的先根遍历、后根遍历；森林的先序遍历、中序遍历（对应转换后二叉树的先序和中序遍历）。6.7哈夫曼树（最优二叉树）及其应用*哈夫曼树定义：给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，则称该