二级公共基础第一章

数据结构与算法全国计算机等级考试二级公共基础·第一章Contents本章目录数据结构与算法核心章节概览，涵盖从基础理论到关键技术的完整知识体系。01算法基础与复杂度分析02线性结构：线性表、栈、队列与链表03树与二叉树04查找与排序技术CHAPTER01算法基础与复杂度分析从算法的定义、特征到复杂度评估方法ALGORITHMFUNDAMENTALS算法的定义与基本特征算法是解题方案的准确而完整的描述，不等于程序或计算方法。程序编制不可能优于算法设计，算法具有可行性、确定性、有穷性和拥有足够情报四大特征，这是理解一切算法问题的基础。可行性算法中每一步操作都必须是实际可执行的，能在有限时间内通过基本运算完成，确保方案具有实践意义可执行确定性每一步骤都必须有明确定义，不允许模棱两可的解释和多义性，保证相同输入必然得到相同输出无歧义有穷性算法必须在有限步骤内终止，包含合理执行时间的含义，区别于无限循环或死循环的程序错误有限步拥有足够情报算法需要具备必要的输入数据才能正确运行，输入信息不足将导致算法无法给出正确结果输入完备AlgorithmDesign算法的设计方法与控制结构算法设计有列举、归纳、递推、递归、回溯等经典方法，而所有算法的控制流程都可分解为顺序、选择、循环三种基本结构。列举与归纳列举法逐一检验所有可能解，归纳法从特殊案例推导一般规律，两者都是最基础也是最直觉的设计思路。基础直觉递推与递归递推通过已知条件逐步推导结果，递归通过函数自调用将大问题分解为小问题，数学计算中应用广泛。分解推导回溯法搜索中遇到死路时退回上一步重新选择，适用于求解组合问题和路径规划类问题。路径搜索控制结构分为顺序、选择、循环三种，任何复杂算法都可由这三种基本结构组合而成。3种结构ALGORITHMCOMPLEXITY算法的时间复杂度与空间复杂度算法复杂度是衡量算法效率的核心指标，分为时间复杂度与空间复杂度。两者之间没有必然联系，需特别注意辨别。时间复杂度衡量执行算法所需计算工作量，用基本运算执行次数表示O(1)<O(logn)<O(n)空间复杂度衡量执行算法所需内存空间，包括程序代码、输入数据和辅助变量三部分辅助空间设计权衡时间与空间复杂度之间没有必然联系，存在灵活的设计权衡策略时空互换常见误区空间复杂度并非程序所占存储空间，实际只考虑算法运行过程中额外需要的辅助空间额外空间CHAPTER02线性结构：线性表、栈、队列与链表从顺序存储到链式存储，掌握四种核心线性结构的操作特性Fundamentals数据结构的基本概念与分类数据结构研究数据的逻辑结构、存储结构和运算三个层面。按逻辑关系分为线性结构与非线性结构：线性结构要求有唯一根结点且每个结点最多一个前件一个后件，不满足此条件的即为非线性结构（如树、图）。01逻辑结构与存储结构逻辑结构关注数据元素间的固有关系，存储结构关注数据在计算机中的物理表示，常见存储方式有顺序、链接和索引三种02线性结构判定条件有且只有一个根结点，且每个结点最多有一个前件（前驱）、最多有一个后件（后继），两者缺一不可03非线性结构不满足线性条件，典型代表有树结构（一个结点可有多个后件）和图结构（结点间关系更加复杂）04存储方式的选择同一逻辑结构可采用不同存储方式，例如线性表既可用顺序存储也可用链式存储，但操作效率和适用场景会发生变化DATASTRUCTURE线性表及其顺序存储结构线性表由一组数据元素构成，元素位置仅取决于序号。顺序存储结构要求所有元素占用连续存储空间且按逻辑顺序依次存放，支持随机访问但插入删除效率较低，是理解后续栈和队列的基础。数据元素与记录线性表中数据元素位置仅取决于序号，复杂线性表中的数据元素由若干数据项组成称为记录，多个记录构成文件。序号定位顺序存储特点所有元素占用连续存储空间，各元素按逻辑顺序依次存放，可通过下标直接计算地址实现随机访问。随机访问插入与删除操作插入操作需将插入位置后的所有元素后移，删除操作需将被删元素后的所有元素前移，平均移动量为n/2。n/2移动适用场景判断适用于数据量相对固定、查找操作频繁的场景；若频繁进行插入删除操作，应考虑链式存储结构。链式替代DATASTRUCTURE栈的基本概念与运算栈是限定仅在栈顶一端进行插入与删除操作的线性表，遵循先进后出（FILO）原则。栈底固定不动，所有操作均在栈顶完成，元素个数公式为bottom-top+1。栈广泛应用于子程序调用、表达式求值、括号匹配等场景。01核心特征先进后出（FILO），最后入栈的元素最先出栈。栈底指针bottom固定不动，所有插入删除操作均在栈顶指针top处进行，体现"后进先出"的核心逻辑。FILO02元素计数栈中元素个数计算公式：num=bottom−top+1。当top>bottom时栈为空状态；当top等于bottom时栈中仅有一个元素，需特别注意边界条件。bottom−top+103基本运算栈支持三种核心操作：入栈（push）将元素压入栈顶、退栈（pop）移除栈顶元素、读栈顶元素（peek）获取但不移除。每次操作前必须进行溢出判断：入栈判满、退栈判空，确保操作安全。Push·Pop·Read04典型应用栈在计算机科学中应用广泛：支持子程序调用与递归实现、表达式求值与括号匹配验证、进制转换算法，以及深度优先搜索（DFS）中的路径记忆与回溯功能。DFSDataStructure·Queue队列的基本概念与循环队列队列是允许在队尾插入、队头删除的线性表，遵循先进先出（FIFO）原则。为解决普通队列的空间浪费问题，实际采用循环队列实现，元素个数计算需区分rear>front和rear<front两种情况，这是考试中的计算题高频考点。01FIFO与双指针机制：队列核心特征为先进先出，rear指针指向队尾用于插入，front指针指向队头用于删除，与栈的FILO形成对比FIFO02假溢出问题与循环方案：普通队列在元素出队后队头前部空间无法复用，循环队列通过将数组首尾相连解决空间浪费假溢出03元素个数计算公式：当rear>front时num=rear−front；当rear<front时num=rear+n−front（n为队列容量）rear+n−front04判空与判满条件：判空条件为front=rear，判满条件为(rear+1)%n=front，即牺牲一个存储单元来区分空和满的状态(r+1)%n=fDataStructure线性链表及其变体每个结点包含数据域和指针域，存储空间可不连续，逻辑关系由指针确定。双向链表和循环链表是其两种重要变体。链条结构—线性链表的物理类比环形首饰—循环链表的类比SinglyLinkedList单链表结构01每个结点由数据域（存储元素值）和指针域（存放下一个结点地址）组成，存储空间可以不连续02查找须从头指针顺序遍历，不支持随机访问；插入删除仅需修改指针，无需移动元素Doubly&Circular双向链表与循环链表01双向链表每个结点增加前驱指针，可同时向前和向后遍历，适用于双向查找场景02循环链表将尾结点指针指回头结点形成环状，从任一结点出发均可遍历整个链表DATASTRUCTURE栈与队列的对比分析栈和队列都是操作受限的线性表，核心区别在于操作规则：栈遵循先进后出（FILO）仅在栈顶操作，队列遵循先进先出（FIFO）在两端分别操作。两者的应用场景截然不同，理解其本质差异是解题的关键。核心差异对比01栈仅在栈顶一端进行插入和删除，遵循先进后出（FILO），最后入栈的元素最先被访问。02队列在队尾插入、队头删除，遵循先进先出（FIFO），最早入队的元素最先被处理。03栈的操作使元素具有"记忆"效果，队列的操作使元素保持"公平排队"的访问顺序。典型应用场景04栈适用于子程序调用、递归实现、表达式求值、括号匹配和深度优先搜索等需要回溯的场景。05队列适用于操作系统任务调度、缓冲区管理、打印排队和广度优先搜索等排队处理的场景。06循环队列是队列在实际工程中的主流实现方式，有效避免了普通队列的假溢出问题。堆叠盘子：栈的FILO操作模式直观类比Chapter03树与二叉树从树的基本概念到二叉树的性质、存储与遍历DataStructure树的基本概念与术语树是一种非线性结构，具有层次特性。根结点是唯一无前件的结点，叶子结点是度为0的结点。结点的度指其拥有的子树个数，树的度是所有结点度的最大值，树的深度是最大层次数。01根结点与叶子结点根结点没有前件，位于树的顶端；叶子结点度为0，位于末端。顶端·末端02结点的度与树的度结点的度是拥有的子树个数；树的度是所有结点度的最大值。分支程度03树的深度树的最大层次数，根为第一层，依次递增，反映纵向规模。纵向规模04层次关系与森林父子、兄弟结点描述层次关系；森林是多棵互不相交的树的集合。互不相交自然大树的分支层次——树的层次结构类比数据结构·树与二叉树二叉树的定义与基本性质二叉树是每个结点最多有两棵子树且左右子树有序的树结构。其核心性质包括：第k层至多2^(k-1)个结点，深度m至多2^m-1个结点，叶子结点数n0=n2+1。这些性质是二叉树计算题的理论基础，几乎每年必考。01左右有序每个结点最多有两棵子树，分别称为左子树和右子树，且左右子树有序不可颠倒，即使只有一个子树也需区分左右。左右不可颠倒02层与深度容量第k层至多有2^(k-1)个结点（k≥1），深度为m的二叉树至多有2^m−1个结点，这是二叉树的最大容量公式。2m−103叶子结点公式对任意二叉树，叶子结点数n₀与度为2的结点数n₂满足n₀=n₂+1，此公式是结点计算题的核心依据。n₀=n₂+104结点与分支总结点数n=n₀+n₁+n₂，总分支数=n−1=n₁+2×n₂，结合n₀=n₂+1可求解各类结点数量问题。n=n₀+n₁+n₂数据结构·树与二叉树满二叉树与完全二叉树满二叉树每层结点数均达最大值，完全二叉树仅最后一层可不满且结点靠左排列。满二叉树必为完全二叉树，反之不然。完全二叉树的层序编号规律（左孩子2i、右孩子2i+1、父结点⌊i/2⌋）是解决相关计算题的关键工具。01满二叉树·结点最大值每一层结点数都达到该层最大值，第k层有2k−1个结点，深度为m时总结点数为2m−1。02满二叉树·度与叶子所有叶子结点都在最后一层，所有非叶子结点的度均为2，不存在度为1的结点。03完全二叉树·结构约束除最后一层外其余各层结点数达最大值，最后一层结点从左向右连续排列，可以不满但不能有空缺。04完全二叉树·层序编号编号i的结点左孩子为2i、右孩子为2i+1、父结点为⌊i/2⌋，便于数组存储和快速定位。金字塔的完美对称结构，类比满二叉树每层结点数均达最大值的理想形态DATASTRUCTURES二叉树的遍历方法二叉树遍历分为前序、中序、后序三种深度优先方式和层序遍历。中序遍历二叉搜索树可得到有序序列，是该知识点的典型应用。前序遍历根-左-右：先访问根结点，再前序遍历左子树，最后前序遍历右子树，根结点总在子树访问之前根优先中序遍历左-根-右：先中序遍历左子树，再访问根结点，最后中序遍历右子树，对二叉搜索树可得到有序序列有序输出后序遍历左-右-根：先后序遍历左子树，再后序遍历右子树，最后访问根结点，根结点总在子树访问之后根最后层序遍历从上到下、从左到右按层次访问，借助队列实现，属于广度优先遍历，与前三种深度优先方式形成对比BFS队列核心考点二叉树遍历计算与解题技巧前序+中序或后序+中序可唯一确定一棵二叉树，但前序+后序不能。完全二叉树n个结点时叶子数为⌈n/2⌉，度为1的结点最多1个。01前序+中序可唯一确定二叉树：前序的第一个元素是根，在中序中找到根将序列分为左右子树，递归求解02后序+中序同理可唯一确定：后序的最后一个元素是根，在中序中定位根后划分左右子树递归构造03完全二叉树性质：有n个结点时叶子结点数为⌈n/2⌉，度为1的结点最多1个（n为偶数时恰好1个，奇数时0个）04解题建议：遇到复杂题目先画树形图辅助分析，利用n₀=n₂+1和n=n₀+n₁+n₂联立求解，避免纯记忆公式出错CHAPTER04查找与排序技术掌握经典查找算法与排序算法的原理、性能与适用场景查找算法顺序查找与二分查找顺序查找逐个比较、不要求数据有序，时间复杂度O(n)；二分查找每次将搜索范围缩小一半、要求数据有序，时间复杂度O(logn)。二分查找效率远高于顺序查找，但必须以数据预排序为前提。顺序查找从表头开始逐个比较，找到目标即成功，遍历完未找到则失败，不要求数据有序二分查找（折半查找）每次取中间元素与目标比较，根据大小关系将搜索范围缩小一半，前提是数据必须有序ALGORITHMS常用排序算法原理与比较冒泡排序、直接插入排序和简单选择排序的时间复杂度均为O(n²)，适用于小规模数据；快速排序平均时间复杂度O(nlogn)，是实际应用最广泛的高效排序算法。排序算法的稳定性也是考试的重要考点。冒泡排序通过相邻元素两两比较和交换实现排序，每轮将极值"冒泡"到末尾，最坏和平均时间复杂度均为O(n²)O(n²)快速排序选取基准元素将数据划分为两部分递归排序，平均时间复杂度O(nlogn)，最坏情况退化为O(n²)O(nlogn)直接插入排序将每个元素插入已排序序列的正确位置，对基本有序数据效率高，时间复杂度O(n²)但常数因子小O(n²)排序稳定性相等元素的相对顺序是否保持不变：冒泡、插入、归并排序是稳定的，快速、选择、堆排序是不稳定的稳定vs不稳定AlgorithmComparison查找与排序算法性能对比查找算法中二分查找效率远优于顺序查找但要求数据有序；排序算法中O(nlogn)级别的快速、归并、堆排序适用于大规模数据，而稳定性差异直接影响算法选择。全面对比各算法的性能指标是考试复习的高效方法。常用算法性能对比表算法名称平均时间复杂度最坏时间复杂度稳定性顺序查找O(n)O(n)—二分查找O(logn)O(logn)—冒泡排序O(n²)O(n²)稳定快速排序O(nlogn)O(n²)不稳定直接插入排序O(n²)O(n²)稳定简单选择排序O(n²)O(n²)不稳定堆排序O(nlogn)O(nlogn)不稳定归并排序O(nlogn)O(nlogn)稳定O(nlogn)级别排序算法适用于大规模数据，稳定性是选择排序算法的重要考量因素CHAPTERREVIEW本章核心考点总结第一章高频考点集中在四个维度：算法复杂度的概念辨析、栈与队列的操作特性及计算、二叉树的性质公式与遍历方法、查找与排序算法的性能对比。算法复杂度时间复杂度与空间复杂度无必然联系，注意"以空间换时间"的设计策略常见复杂度排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)O(1)→O(2ⁿ)栈与队列栈先进后出、队列先进先出，循环队列元素个数计算需分两种情况给出入栈序列判断可能的出栈序列是经典题型，注意卡特兰数规律LIFO/FIFO二叉树核心公式n₀=n₂+1，完全二叉树叶子数⌈n/2⌉，第k层最多2^(k-1)个结点前序+中序或后序+中序可唯一确定二叉树，三种遍历序列必须熟练手写n₀=n₂+1查找与排序二分查找要求有序表、时间O(logn)；快速排序平均O(nlogn)但不稳定稳定排序：冒泡、插入、归并；不稳定排序：快速、选择、堆排序O(nlogn)APPLICATIONSCENARIOS数据结构的实际应用场景数据结构并非抽象的理论概念，而是软件系统的底层基石。从浏览器的后退按钮（栈）到打印任务管理（队列），从文件系统目录（树）到数据库索引（B树），每种数据结构都有其最佳适用场景。浏览器双栈导航后退/前进功能使用双栈实现，访问页面入栈，后退时弹出当前页并压入前进栈，完美体现先进后出特性。双栈打印与消息队列操作系统打印队列和消息队列采用队列结构，保证任务按提交顺序公平处理，循环队列避免内存浪费。FIFO文件系统目录文件系统目录结构是典型的树形结构，每个目录可包含多个子目录和文件，遍历算法实现全局搜索。树形数据库索引数据库索引采用B树或B+树结构，保持有序的同时降低树的高度，使磁盘I/O最小化，实现高效范围查找。B+树SUPPLEMENTARY补充知识点与易忽略细节指令系统、基本运算分类、链式存储的适用范围等细节知识点虽非核心考点，但在选择题中常作为干扰选项或独立考点出现。全面掌握这些边缘知识点可以有效避免在简单题上失分。指令系统与基本运算指令系统是计算机能执行的所有指令的集合，基本运算分为算术、逻辑、关系和数据传输四类。理解各类运算的特点和应用场景有助于快速识别题目考点。4OPERATIONS链式与顺序存储链式存储既可表示线性也可表示非线性结构，顺序存储主要用于线性结构。两者在插入删除效率、空间利用率等方面存在明显差异，是常见辨析点。CHAINvsSEQ回溯法与减治递推回溯法遇死路时退回上一步重新选择，减治递推逐步减小问题规模求解。两者均为重要算法策略，需明确区分其适用场景和实现特点。BACKTRACK存储结构三方式顺序、链接、索引三种基本存储方式，同一逻辑结构可采用不同方式但操作效率差异显著。选择合适存储方式是优化算法性能的关键考量。3MODESCHAPTER01·EXAMSTRATEGY考试技巧与常见