高中信息技术选择性必修一 数据与数据结构 线性结构 核心知识清单

高中信息技术选择性必修一数据与数据结构线性结构核心知识清单一、学科定位与核心素养锚点【基础】【背景铺垫】本清单对应的是高中信息技术选择性必修课程模块一“数据与数据结构”。在高中信息技术课程体系中，本模块旨在从学科核心素养的角度，深化学生对数据本质的认识，提升利用数据结构解决实际问题的能力。线性结构作为数据结构中最基础、最常用的一类逻辑结构，是构建更复杂数据组织和算法的基石。掌握线性结构，不仅是理解计算机程序如何组织与管理数据的关键，更是培养计算思维，特别是抽象、建模与高效解决问题能力的重要环节。【非常重要】【学科核心素养渗透】学习线性结构，并非仅仅是记忆概念与代码，其深层目标是达成以下核心素养的落地：●信息意识：能够敏锐地意识到现实世界中的大量问题（如排队、撤销操作、通讯录管理）本质上都涉及具有“先后次序”的数据关系，从而主动寻求用线性结构建模。●计算思维：能够对问题进行抽象，定义其数据逻辑结构（如线性表、栈、队列）；能够基于逻辑结构选择或设计合适的物理存储结构（顺序存储或链式存储）；能够针对不同的存储结构，设计算法实现对数据的增、删、改、查等操作，并初步分析算法效率。●数字化学习与创新：能够运用Python等编程语言实现线性结构，并将其作为数字化工具，创造性地解决如任务调度、表达式求值、文本处理等实际问题。●信息社会责任：理解数据结构设计对信息系统性能和安全的影响，例如，理解栈在保障程序运行（如函数调用）中的关键作用，树立严谨、高效的工程思维。二、线性结构总览：从逻辑到存储的抽象之旅【基础】【概念建立】（一）数据的逻辑结构数据的逻辑结构是指数据元素之间客观存在的相互关系，它是面向问题的，是用户视图。线性结构是其中一类，其特点是：存在唯一的一个被称为“第一个”的数据元素，存在唯一的一个被称为“最后一个”的数据元素，除第一个元素外，每个元素都有且只有一个直接前驱；除最后一个元素外，每个元素都有且只有一个直接后继。这种“一对一”的关系构成了一个线性序列。（二）数据的物理结构（存储结构）【重要】【难点辨析】物理结构是指逻辑结构在计算机存储器中的表示（又称映像），它是面向计算机的，是实现视图。同一种逻辑结构，可以有不同的物理实现方式。线性结构主要包含两种基本的存储结构：●顺序存储结构：用一组地址连续的存储单元依次存储线性表中的各个元素。在Python中，列表（list）数据类型就是典型的顺序存储结构实现。●链式存储结构：用一组任意的存储单元存储线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。在存储每个元素的同时，还需要存储一个指向其后继（或前驱）元素位置的指针（或称链接、引用）。【高频考点】【易错点】考生务必清晰地区分“逻辑结构”与“物理结构”。例如，“线性表”是一种逻辑结构，它既可以用“顺序表”（顺序存储）实现，也可以用“链表”（链式存储）实现。考题中常会问“某操作在顺序表和链表上的时间复杂度有何不同”，这正是在考察存储结构对操作性能的影响。三、基础核心：线性表及其操作【非常重要】【核心概念】线性表是由n（n≥0）个类型相同的数据元素构成的有限序列。当n=0时，称为空表。（一）线性表的抽象数据类型定义【基础】一个完整的抽象数据类型（ADT）定义包括数据对象、数据关系和基本操作。对于线性表，其基本操作构成了后续所有应用的基础。...据对象：D={a_i|a_i属于ElemType,i=1,2,...,n,n≥0}...据关系：R={<a_i,a_{i+1}>|a_{i+1}是a_i的直接后继,i=1,2,...,n1}●【高频考点】【操作核心】基本操作（以Python风格描述）：1.init()：初始化一个空的线性表。2.is_empty()：判断线性表是否为空。3.length()：获取线性表中数据元素的个数。4.get(i)：读取并返回表中第i个位置的元素。★★★5.insert(i,e)：在表的第i个位置前插入一个新元素e。★★★6.delete(i)：删除表中第i个位置的元素。★★★7.locate(e)：查找元素e在线性表中的位置，若存在则返回其序号，否则返回0或1。8.traverse()：遍历整个线性表，对每个元素执行某种操作。（二）顺序表（顺序存储的实现）【重要】【实现原理】●定义：将线性表中的元素依次存放在一段地址连续的存储单元中。在Python中，最直接的体现就是列表。●【高频考点】【算法与复杂度】核心操作的算法实现与时间复杂度分析：1.查找（按位查找）：如get(i)，由于顺序表是随机存取结构，只要知道起始地址和每个元素所占存储空间，就可以直接计算出第i个元素的地址。因此时间复杂度为O(1)。这也是顺序表最大的优势。2.插入操作（insert(i,e)）：a.从最后一个元素开始，到第i个元素，依次将它们向后移动一个位置。b.将新元素e写入第i个位置。c.表长加1。【难点】【易错点】插入操作的时间主要耗费在移动元素上。在长度为n的线性表中，平均需要移动n/2个元素，因此平均时间复杂度为O(n)。若插入位置在表尾（i=n+1），则不需要移动元素，时间复杂度为O(1)；若在表头（i=1），则需要移动所有n个元素，时间复杂度为O(n)。3.删除操作（delete(i)）：a.将第i+1个到第n个元素依次向前移动一个位置。b.表长减1。c.时间复杂度与插入类似，平均需要移动(n1)/2个元素，为O(n)。删除表尾元素为O(1)，删除表头元素为O(n)。4.按值查找（locate(e)）：需要从第一个元素开始，依次将元素值与e进行比较，直到找到匹配项或遍历完整个表。平均比较次数为(n+1)/2，时间复杂度为O(n)。（三）链表（链式存储的实现）【重要】【实现原理】●定义：用一组任意的存储单元存储数据元素。为了表示每个元素与其后继的逻辑关系，除了存储元素本身的信息（数据域）外，还需存储一个指示其直接后继的引用（指针域）。这两部分信息组成一个“结点”。●【高频考点】【核心】单链表的结点结构：|数据域|指针域|(在Python中，引用即变量名，指针域就是存储下一个结点的变量名)●【非常重要】【算法实现】核心操作的算法思想与时间复杂度分析：1.查找（按位查找）：链表不具有随机存取特性，只能从头结点开始，沿着指针域逐个结点顺序访问（顺序存取）。查找第i个元素，必须从头开始走i步，时间复杂度为O(n)。2.插入操作（在结点p之后插入新结点s）：s.nextp.nexts.next=p.nextb.p.next=s【易错点】这两步的顺序绝对不能颠倒。如果先执行p.next=s，那么p原本的后继结点信息就会丢失，导致无法正确链接s与原后继。对于已知插入位置指针的情况，插入操作本身（指针修改）的时间是O(1)。但在实际应用中，往往需要先花费O(n)的时间找到插入位置的结点。3.删除操作（删除结点p的后继结点q）：a.q=p.nextb.p.next=q.next(即p.next=p.nex)c.如果使用的是需要手动管理内存的语言，还需释放结点q的内存（Python有垃圾回收机制，可省略此步）。同样，删除操作本身的时间是O(1)，但找到被删结点的前驱通常需要O(n)的时间。4.建立链表：a.头插法：新结点始终插入到头结点之后。特点是输入顺序与链表逻辑顺序相反。b.尾插法：新结点始终插入到链表尾部。需要额外一个尾指针来记录最后一个结点的位置。●【难点】【顺序表vs链表对比总结】1.存储方式：顺序表连续；链表离散（可能不连续）。2.存取方式：顺序表随机存取；链表顺序存取。3.空间利用率：顺序表需预分配空间，可能造成浪费或溢出；链表动态分配，按需生长，但每个结点需额外存储指针，有结构性开销。4.时间复杂度：操作顺序表链表（在给定指针位置操作时）按位查找O(1)O(n)插入/删除O(n)（主要耗时在移动元素）O(1)（仅修改指针）【考向】选择题或简答题常考：一个应用场景，如“频繁在中间插入删除”、“主要操作是按序号访问”，分别应该选用哪种存储结构？四、受限的线性表：栈与队列【非常重要】【应用核心】栈和队列是操作受限的线性表，即对它们的插入和删除操作的位置做了限制。这种限制使得它们成为解决特定类型问题的强大工具。（一）栈（Stack）——后进先出●【基础】定义：限定仅在表尾（称为栈顶）进行插入和删除操作的线性表。表头称为栈底。遵循“后进先出”（LIFO）原则。●【核心操作】（牢记英文术语）1.push(e)：向栈顶插入一个元素（入栈、压栈）。2.pop()：移除并返回栈顶元素（出栈、弹栈）。3.peek()/top()：读取栈顶元素，但不删除。4.is_empty()：判断栈是否为空。●【高频考点】【经典应用】1.函数调用与递归：系统使用一个调用栈来保存每次函数调用的返回地址、局部变量等信息。递归函数的层层调用与返回，完美契合栈的后进先出特性。2.括号匹配检验：编译器在检查程序中的括号（如“{[()]}”）是否匹配时，会使用一个栈。遍历字符串，遇到左括号则压栈，遇到右括号则检查栈顶是否为其对应的左括号，若匹配则弹栈，否则报错。3.【难点】表达式求值：将人们习惯的“中缀表达式”（如3+5(24)）转换为计算机更容易处理的“后缀表达式”，并利用栈进行求值。a.中缀转后缀算法：遍历中缀表达式，遇到数字直接输出，遇到运算符则与栈顶运算符比较优先级。若栈空或当前运算符优先级高于栈顶，则压栈；否则，弹出栈顶运算符并输出，直到满足压栈条件。括号单独处理（左括号直接压栈，遇到右括号则弹栈直到左括号）。b.后缀表达式求值：遍历后缀表达式，遇到数字压栈，遇到运算符则从栈中弹出两个数字进行计算，再将结果压栈。最终栈顶即为结果。4.浏览器的前进后退功能：使用两个栈实现。每次访问新页面，压入栈A；点击后退，从栈A弹出页面压入栈B；点击前进，从栈B弹出页面压入栈A。（二）队列（Queue）——先进先出●【基础】定义：限定在一端（队尾）进行插入，在另一端（队头）进行删除的线性表。遵循“先进先出”（FIFO）原则。●【核心操作】（牢记英文术语）1.enqueue(e)：在队尾插入一个元素（入队）。2.dequeue()：移除并返回队头元素（出队）。3.front()：读取队头元素，但不删除。4.is_empty()：判断队列是否为空。●【高频考点】【经典应用】1.操作系统进程/打印任务调度：为了公平地为多个请求服务，操作系统使用队列来管理需要占用CPU时间片的进程或等待打印的文档。先到先得。2.消息队列：在分布式系统或应用程序中，用于异步通信，生产者将消息放入队列，消费者从队列中取出消息进行处理。3.广度优先搜索（BFS）：在图或树的遍历算法中，使用队列来记录待访问的结点，保证按距离起始点的远近逐层访问。4.【热点】循环队列：为了克服“假溢出”现象（即顺序队列中，队尾指针已到数组末尾，但数组前部因出队操作仍有空闲空间），将顺序队列在逻辑上视为一个环。通常需要牺牲一个存储单元来区分队空和队满状态。队空条件：front==rear；队满条件：(rear+1)%maxsize==front。五、字符串：特殊的线性表【重要】【高频应用】字符串（简称串）是内容受限的线性表，其每个数据元素只能是单个字符。它是非数值计算中处理的主要对象。（一）基本概念●空串：长度为0的串。●空格串：由一个或多个空格字符组成的串。●子串与主串：串中任意连续字符组成的子序列称为该串的子串，包含子串的串称为主串。●【基础】比较操作：串的比较是通过组成串的字符之间的编码（如ASCII或Unicode）来进行的。例如，在Python中，"abc"<"abd"为True，因为前两个字符相同，第三个字符'c'的编码小于'd'。（二）【高频考点】【核心操作与算法】●【考向】字符串的基本操作在各种编程语言中都已封装好，考试重点在于对算法思想的理解，而非代码默写。尤其是：1.模式匹配：a.朴素模式匹配算法（BF算法）：将主串中与模式串长度相同的子串逐个与模式串比较。最坏时间复杂度为O(nm)，其中n和m分别为主串和模式串长度。b.【难点】KMP算法：一种改进的模式匹配算法。其核心思想是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数。关键在于求解模式串的“部分匹配表”（next数组），使得当某一字符失配时，模式串能够向右“滑动”尽可能远的一段距离。KMP算法将时间复杂度降为O(n+m)。六、算法与综合应用【综合】【高阶思维】（一）迭代与递归这是实现算法求解的两种基本思路，常与线性结构结合考察。●迭代：重复执行一系列指令，每次迭代处理一个数据元素。对线性表进行遍历、查找等操作，通常用循环结构（for、while）实现，这都属于迭代思想。●递归：一个函数在其定义中直接或间接调用自身。递归的思想与栈密不可分。【高频考点】【经典递归案例】1.计算阶乘n=n(n1)!。递归实现简洁，但效率往往低于迭代。2.遍历链表：可以设计一个递归函数，先处理当前结点，再递归调用处理下一个结点，实现链表的正向或逆向输出。3.【难点】汉诺塔问题：完美体现了递归的分治思想，将n个盘子的移动问题分解为(n1)个盘子的移动问题。【易错点】递归必须有明确的递归结束条件（基例），否则会导致栈溢出错误。每次递归调用，系统都会在栈上分配空间来保存状态，递归深度过大时会有风险。（二）查找与排序（线性结构上的应用）在掌握了线性结构的基本操作后，我们可以在其上实现更复杂的算法。●【高频考点】查找：1.顺序查找：从头到尾遍历线性表，适用于任何线性结构（顺序表、链表），时间复杂度O(n)。2.二分查找（折半查找）：【重要】【前提条件】必须采用顺序存储结构，且表中的元素必须按关键字有序排列（如升序排列）。【算法思想】每次取中间元素与待查关键字比较，若相等则成功；若待查关键字小于中间元素，则在左半区继续查找；否则在右半区查找。【时间复杂度】O(log2n)。效率远高于顺序查找。3.【考向】给定一个有序序列，手工模拟二分查找的过程（确定mid，比较，缩小区间），直到找到或确定不存在。●【高频考点】排序（线性结构上的经典算法）：1.冒泡排序：重复遍历要排序的列表，比较每对相邻元素，如果顺序错误就交换它们。每轮遍历会将最大（或最小）的元素“浮”到列表的一端。时间复杂度O(n^2)。2.插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度O(n^2)，但对于基本有序的序列效率很高。3.选择排序：每次从未排序的序列中找出最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找，直到所有元素均排序完毕。时间复杂度O(n^2)。4.【考向】给出一组数据，写出经过某排序算法每一趟排序后的结果。（三）解题步骤与易错点归纳【非常重要】【应试指南】●解题步骤：1.建模：从实际问题中抽象出数据的逻辑关系。问自己：“这些数据是按照什么顺序组织的？”“是否存在先进先出或后进先出的需求？”从而确定使用线性表、栈还是队列。2.选型：基于对操作性能的要求，选择合适的存储结构。如果需要频繁按位访问，选顺序表；如果需要频繁在中间插入删除，选链表；如果需要动态增长且不确定大小，链表更灵活。3.实现：用Python等语言将核