资源简介

(共37张PPT)
课时28 数据结构与算法效率
一、数据结构设计
1. 在计算机程序设计中，根据问题　　　　的需要，对数据进行有效的整理和
　　　　，并以一定的形式加以存储和表示的过程称为数据结构的设计。
2. 数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物　　　　，既确保数据处理的正确性，又提高编程实现和数据处理的效率。
3.算法+　　　　=程序。
求解
逻辑
组织
数据结构
1.数据元素。
（1）数据项：也称为字段、域，是具有独立含义的　　　　数据表示单位。
（2）数据元素：是数据的　　　　，有些情况下也称为元素、节点、顶点、记录等。有时一个数据元素可以由若干个　　　　组成。
最小
基本单位
二、数据结构的概念
数据项
类型 说明
基本数据类型 也称为原子数据类型，由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python中的整型、实型、布尔型等
结构数据类型 在程序设计时利用基本数据类型构造出的、复合的新类型，由用户根据实际需要定义，能较好地描述数据元素的数据项组成以及数据元素之间的逻辑关系，方便用户根据数据之间逻辑关系的特点进行数据处理，如很多编程语言中提供的记录类型、集合等
2.数据类型。
（1）数据类型指的是具有相同　　　　的计算机数据的集合以及在这个数据集合上的一组操作。
（2）分类。
性质
3.数据结构。
（1）数据结构指的是数据之间的相互关系，即数据的组织形式。
①数据元素之间的　　　　关系，也称为数据的逻辑结构。
②数据元素及其关系在计算机存储器内的表示，也称为数据的　　　　 或物理结构。
③数据的　　　　，即对数据施加的操作。
（2）实际应用中数据结构设计主要考虑数据对象之间的逻辑关系，所以数据结构一般指数据的　　　　。
逻辑　
存储结构
运算
逻辑结构
1.数组。
（1）使用条件：描述数据对象本身，以及数据所处的位置或者数据之间的
　　　　 顺序关系。
（2）特点：既可以快速地通过　　　　精确地访问序列中的某个数据元素，又可以方便地通过　　　　后面的下标依次按顺序遍历序列中的每个数据元素。
（3）分类。
①一维数组：存储一批性质和类型相同，具有线性特征的数据序列。
②二维数组：存储二维空间内，行列之间都有逻辑关系的一批数据。可以使用一对行号和列号来唯一地　　　　。
前后
下标
三、常见的数据结构
变量名
定位　
2.链表。
（1）适用条件：不关心数据实际所处的具体位置，只需要知道数据之间相互
　　　　的顺序。
（2）设置头指针 head 指向头节点，链表非空时，头指针指向第一个节点，链表为空时，头指针指向为-1。
（3）链表的分类。
链接
3.队列。
（1）数据“　　　　”，在序列两端分别进行，一端（队首）只可出队，另一端（队尾）只可入队，中间不可“插队”。
（2）图示。
4.栈。
（1）数据序列只有一端开放，数据的进、出栈操作只能在开放的一端（栈顶）进行。
（2）数据进、出栈的规律是“　　　　 ，后进先出”。
（3）图示。
先进先出　　
先进后出
5.树。
（1）表示　　　　结构的数据，特点是除根之外，一个数据元素前面（或上面）只有一个元素，而后面（或下面）有 0个或多个元素相邻。
（2）图示。
非线性　
1. 设计算法解决问题离不开数据结构。根据数据之间的关系特点，基于不同的数据结构来设计算法并解决问题，可以减少设计算法及编写程序时的工作量，提高编程实现和数据处理的效率。
2. 不同数据结构会导致处理效率的　　　　。例如，解决同一问题，基于数组和链表两种数据结构分别设计算法，在程序实现效率上两者会有不同的表现，数据项越多，程序实现效率的差距会越大。
不同
四、数据结构的作用
1. 算法效率的高低可由算法复杂度来度量。算法复杂度又分为算法的时间复杂度和空间复杂度。
　　　　复杂度反映了算法执行所需要的时间，　　　　复杂度反映了算法执行所需要占用的存储空间。
2.时间复杂度。
（1）一般将算法中语句的　　　　作为时间复杂度的度量标准。
（2）语句总的执行次数 T(n)是关于问题规模 n 的函数。
（3）问题规模：也称为输入的大小，是指处理问题的大小，即用来衡量输入数据量的整数。
（4）时间复杂度常用符号 O 表示，不包括 T(n)函数的低阶项和首项系数，如 1/2
n(n-1)的量级与 n2相同，其时间复杂度可表示成 O(n2)。
（5）推导大 O 阶的方法。
①用常数 1 取代运行时间中的所有加法常数。
②在修改后的运行次数函数中，只保留最高阶项。
③若最高阶项存在且不是 1，则去除与这个项相乘的常数。
（6）常见的时间复杂度耗费时间的比较：O(1)< O(log2n)（7）算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣。
时间
五、算法效率
空间
执行次数
1. 数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的操作，提高算法处理数据的效率。
2. 解决同一个问题时，从不同角度可以抽象出不同的数据结构特征，不同的数据结构决定了数据运算集合的不同，最终导致算法效率的不同。
3. 解决实际问题时，需要根据问题的需要选择、设计不同的算法和数据结构，选择、设计算法与数据结构往往根据算法效率展开。
（1）当实际需要程序运行速度较快时，可以通过分析　　　　复杂度来改进算法，必要时需要用空间换取时间的优化。
（2）当实际需要程序占用较小的存储空间时，就需要分析空间复杂度来减少存储空间的占用，甚至可以用时间来换取空间的优化。
时间
六、数据结构对算法效率的影响
典例 1 有如图所示的二维数据表，下列说法不正确的是 （　　）
A.①处是一条记录即一个数据元素
B.②处是数据元素的一个数据项
C.数据元素是具有独立含义的最小数据表示单位
D.数组的元素和链表节点都可以称为数据元素
C
√
题型导向一　数据结构的概念
胜券点拨1
明考向 本题主要考查数据元素
审关键 数据元素和数据项的概念与区别
考场思 维快闪 数据元素是数据的基本单位，可由若干个数据项（也称为字段、域）组成，数据项是具有独立含义的最小数据表示单位。图中所示的二维表中，每一行实际内容（也称为一条记录）就是数据元素，而每个数据元素又由5个数据项（条形码、物品名称、单位、进价、库存）组成
典例 2 下列关于数据结构的说法，正确的是（　　）
A.整数数据类型仅仅指计算机系统所能表示的整数组成
B.结构数据类型可以由用户根据实际需要定义
C.数据结构是指数据的逻辑结构和存储结构
D.数据的运算是指数据元素及其关系在计算机计算器内的表示
B
√
胜券点拨2
明考向 本题主要考查数据类型与结构
审关键 提取选项中与特征有联系的关键词
考场思维快闪 A 整数数据类型既是指计算机系统所能表示的整数组成，又是指在这个整数集合上可以进行的算术运算操作
B 结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，由用户根据实际需要定义
C 数据结构包括数据的逻辑结构、存储结构和运算
D 数据的运算是指对数据施加的操作；数据元素及其关系在计算机存储器内的表示称为数据的存储结构或物理结构
典例 3 下列关于队列和栈的说法，不正确的是 （　　）
A.队列不允许插队
B.栈是“先进后出”的数据结构
C.栈只有一端可以进行数据操作
D.当队列中只有一个数据的时候，则可以从序列两端出队
D
√
题型导向二　常见数据结构及其作用
胜券点拨3
明考向 本题主要考查队列和栈的特点
审关键 队列和栈的特点
考场思维快闪 A 队列和栈都不允许“插队”
B 栈的特点是“先进后出，后进先出”
C 栈只允许在一端进行数据出、入栈的操作
D 任何情况下，队列的一端只可入队，另一端只可出队
典例 4 下列关于一维数组和二维数组的说法，正确的是 （　　）
A.存放某个年级所有班级各门学科的平均分适合使用一维数组
B.二维数组可以由若干个一维数组组成
C.由行号可以确定二维数组中的一个数据项
D.一维数组和二维数组在数据处理过程中的效率相同
B
√
胜券点拨4
明考向 本题主要考查数组的相关知识
审关键 一维数组与二维数组在组织与处理数据时的异同
考场思维快闪 A 存放某个年级所有班级需要一个一维数组，各门学科各需要一个一维数组，且每一组一维数组之间有逻辑关系，适合使用二维数组
B 二维数组中每一行或每一列可以看作一个单独的一维数组
C 由一对行号和列号才能确定二维数组中唯一的一个数据项
D 在不同的问题中使用一维数组和二维数组组织处理数据的效率不同
典例 5 下列情况中，适合用链表组织数据的是 （　　）
A.经常需要在序列表中进行插入和删除操作
B.经常需要在序列表中查询元素
C.存储空间能表示数据之间的关系
D.存储非线性数据
A
√
胜券点拨5
明考向 本题综合考查数据结构
审关键 链表的数据存储方式、处理方式
考场思维快闪 A 在链表中进行数据插入和删除操作只需要改变部分节点的指针
B 在链表中查询元素需要先从链表的头部进入链表，逐个遍历，效率较低
C 链表占用的存储空间不连续也不固定，无法表示数据之间的关系
D 链表只能存储线性结构数据
典例 6 下列关于数据结构的说法，正确的是 （　　）
A.不同数据结构的处理效率是相同的
B.链表能使用数据的位置信息访问任意节点
C.计算机中的文件夹管理采用“树形”结构
D.队列是一种“先进后出”的数据结构
C
√
胜券点拨6
明考向 本题主要考查数据结构
审关键 链表、树、队列的特性
考场思维快闪 A 不同数据结构的处理效率是不同的
B 数组能使用数据的位置信息访问任意节点
D 栈是一种“先进后出”的数据结构，队列是一种“先进先出”的数据结构
典例 7 ［2025 嘉兴联考］下列关于数据结构的说法，正确的是 （　　）
A.队列和栈都是操作受限的线性表
B.链表必定有 1 个头指针和 1 个尾指针
C.字符串中不能存储空格字符
D.数组元素的数据类型可以不一致
A
√
胜券点拨7
明考向 本题主要考查数据结构
审关键 队列、栈、链表、字符串、数组的特性
考场思维快闪 B 单向链表通常只有头指针，双向链表可能有头指针和尾指针
C 字符串中可以存储空格字符
D 数组元素的数据类型必须一致
典例 8 下列关于数据结构与算法的关系的说法，正确的是 （　　）
A.随着问题规模 n 的增大，T(n)函数值增长较快的算法较优
B.时间复杂度为 O(1)的算法，其语句执行次数与问题规模 n 无关
C.同一种数据结构在不同的算法中，时间复杂度相同
D.一般而言，对数阶的时间复杂度要大于指数阶的时间复杂度
B
√
题型导向三　数据结构与算法效率
胜券点拨8
明考向 本题主要考查数据结构与算法的关系
审关键 不同数据结构与算法效率的关系
考场思维快闪 A 通常情况下，随着问题规模n的增大，函数值增长较慢的算法较优
B 常量阶时间复杂度为O(1)，其算法中语句的执行次数与问题规模n无关
C 同一种数据结构在不同的算法中，时间复杂度不同，为了满足不同问题的需求，要选择合适的数据结构
D 常见时间复杂度的耗时比较：O(1)典例 9 有如下 Python 程序段：
def func(n):
s=0;i=1
while i<=n:
s+=i
i+=1
return s
n=int(input("n="))
print(func(n))
其时间复杂度为 （　　）
A.O(n)
B.O(n2)
C.O(log2n)
D.O(nlog2n)
A
√
胜券点拨9
明考向 本题主要考查时间复杂度
审关键 语句执行次数
考场思 维快闪 函数func(n)中，while循环执行了n次，实现计算1+2+…+n的值，因此该算法的时间复杂度为O(n)
数据结构 常用操作的时间复杂度
访问 插入 删除
数组 O(1) O(n) O(n)
链表 O(n) O(1) O(1)
通法一　数组和链表常用操作的算法效率对比
链式存储 顺序存储
①占用额外的存储空间存储指针 ②查找元素速度慢 ③插入和删除元素效率高 ④没有空间限制，存储元素的个数只与内存空间大小有关 ①查找元素速度快
②插入和删除元素时会造成其他元素的移动，效率低
③有空间限制，当需要存储的元素个数多于顺序表的长度时，会出现“溢出”问题；当存储的元素个数远小于顺序表的长度时，空间利用率低
当数据以查找操作为主时，一般采用顺序表；当数据以插入和删除操作为主时，一般采用链表
通法二　链式存储结构与顺序存储结构的比较
程序 时间复杂度
算法1 n=int(input()) #执行1次 s=n**2//3 #执行1次 print(s) #执行1次 语句执行总次数为3次，语句的执行次数与问题规模n无关，时间复杂度为O(1)，称为常量阶
算法2 n=int(input()) #执行1次 s=1 #执行1次 #执行n次 for i in range(1,n+1): s=s*i #执行n次 print(s) #执行1次 语句执行总次数为2n+3次，语句的执行次数与问题规模n呈线性增大关系，时间复杂度是O(n)，称为线性阶
算法3 n=int(input()) #执行1次 s=0 #执行1次 x=0 #执行1次 #执行 n 次 for i in range(0,n): #执行n*n次 for j in range(0,n): x=x+1 #执行n*n次 s=s+x #执行n*n次 print(s) #执行1次 语句执行总次数为3n2+n+4次，语句的执行次数与问题规模n呈平方增大关系，时间复杂度为O(n2)，称为平方阶
算法4 …… 算法的时间复杂度还有对数阶O(log2n)、指数阶O(2n)等
通法三　常见算法的时间复杂度
1.下列关于数据结构的说法，不正确的是 （　　）
A.计算机程序设计的本质是算法与数据结构的设计
B.数据结构就是数据之间的相互关系，即数据的组织形式
C.数据结构包含数据元素、数据类型和数据运算三个方面
D.数据结构的设计既要保证数据处理的正确性，又要考虑数据处理的效率
数据结构主要包括数据的逻辑结构、数据的存储结构（物理结构）和数据的运算三个方面。
一、数据结构的概念
C
√
2.数据在计算机存储空间内的存放不是随意的，而是要求选择某种最恰当的数据结构来组织和存储数据。下列关于数据结构的说法，正确的是 （　　）
A.栈与队列在数据处理过程中的操作一致，存储方式不一致
B.链表是非线性数据结构，可以快速进行数据插入操作
C.使用数组存储数据，则数组中的数据不允许被修改
D.非线性结构数据可以用树结构来存储
栈与队列在数据处理过程中操作不一致，栈的操作原则是“先进后出”，队列的操作原则是“先进先出”，存储方式可以有链表或数组等，根据实际需要选择。链表存储线性结构数据。使用数组存储数据，仍可以对数组中的数据进行修改等操作。
D
√
二、常见数据结构及其作用
3.下列关于算法效率的说法，正确的是 （　　）
A.算法效率指的就是算法的时间复杂度
B.通常，随着问题规模n的增大，时间复杂度的函数值增长较慢的算法较优
C.时间复杂度常用符号T表述，如2*n*(n-1)，其时间复杂度可以表示为T(n2)
D.常见时间复杂度耗费时间的大小关系为：常数阶<对数阶<指数阶<平方阶
B
√
算法效率的高低可由算法复杂度来度量，算法复杂度又分为算法的时间复杂度和空间复杂度。时间复杂度常用符号O表述。常见时间复杂度耗费时间的大小关系为：常数阶<对数阶<平方阶<指数阶。
三、数据结构与算法效率
4.有如下Python程序段：
n=int(input("请输入一个数："))
s=1
for i in range(1,n+1):
s*=i
print(s)
该程序段的时间复杂度是 （　　）
A.常量阶 B.线性阶
C.对数阶 D.平方阶
B
√
该算法总的执行次数为2n+3次，故其时间复杂度是O(n)，为线性阶。
5.下列关于数组和链表的说法，不正确的是 （　　）
A.在链表中删除数据需要移动其他数据的存储位置
B.在链表中查找数据的效率一般低于数组
C.在数组中插入数据，有时不必移动其他数据的存储位置
D.使用数组和链表解决同一问题的效率一般不同
在链表中删除数据不需要移动其他数据的存储位置，只需要修改待删除数据的前驱节点的指针即可。
A
√
6.下列关于栈和队列的说法，正确的是 (　　)
A.队列的插入和删除操作分别在两端进行，而栈的插入和删除操作均在栈顶进行
B.栈和队列都是线性数据结构，且栈的删除操作可以在任意位置进行
C.栈的运算规则是先进先出，队列的运算规则是后进先出
D.栈和队列都可以直接访问中间元素，但无法访问首尾元素
栈的删除操作只能在栈顶进行。队列的运算规则是先进先出，栈的运算规则是后进先出。栈和队列都不可以直接访问中间元素，栈只能访问栈顶元素，队列只能访问队首和队尾元素。
A
√
7.存储某个公司的部门从属关系，最合适的数据结构是 （　　）
A.二维数组
B.一维数组
C.链表
D.树
D
一个公司的部门从属关系一般是一个大部门对应多个小部门，小部门之后又有更细化的分组，是非线性结构的数据，且元素之间具有分支层次的关系，适合使用树结构来存储。
√
8.在对数据进行组织和处理的过程中，第一步即是为数据选择一项数据结构。下列说法正确的是 （　　）
A.使用不同的数据结构处理数据，设计算法的思路是一样的
B.一般采用链表和树结构来存储非线性结构数据
C.设计算法的过程中只能使用一种数据结构
D.不同的数据结构之间可以进行相互转换
D
选择不同的数据结构组织数据需要设计不同的算法。链表用来存储线性结构数据。设计算法的过程中可以选择多种数据结构。
√
9.下列关于数据结构的说法，正确的是 （　　）
A.在程序设计中，数据结构设计时主要考虑对象之间逻辑关系的实现
B.数组是一种适合于组织、存储涉及频繁插入与删除的数据结构
C.常见的线性关系数据结构有数组、队列、栈、树和图等
D.链表在访问、插入和删除元素时，算法效率比数组高
A
√
链表是一种适合于组织、存储涉及频繁插入与删除的数据结构。树和图是非线性数据结构。链表在访问元素时，算法效率比数组低。
10.下列程序段中，时间复杂度耗时最大的是 （　　）
B
选项A的时间复杂度是O(n)，为线性阶。选项B的时间复杂度是O(2n)，为指数阶。选项C的时间复杂度是O(n2)，为平方阶。选项D的时间复杂度是O(1)，为常量阶。时间复杂度最大的是指数阶。
A.for i in range(n): print(" "*(10-i),end=" ") print("*"*(2*i-1)) B.i=1 s=0 while i<=4**n: s=s+i i=i+1 C.total=0 a=[] for i in range(n): for j in range(n): if j%2==1 and j%3==2: a.append(j) total+=1 D.if 5>n:
c=5/n
else:
c=n/5
√
11.有如下Python程序段：
arr=[1,1,2,3,3]
d=[]
n=len(arr)
for i in range(n):
for j in range(i+1,n):
if arr[i]==arr[j] and arr[i] not in d:
d.append(arr[i])
print(d)
该程序段的时间复杂度为 （　　）
A.O(log2n) B.O(n)
C.O(1) D.O(n2)
D
√
在该程序段中，有两个嵌套的for循环。外层的for循环将会执行n次，内层的for循环将会执行n-1次、n-2次、…、2次、1次，故总的执行次数可以近似表示为：(n-1)+(n-2)+…+2+1=n(n-1)/2。在大O记法中，通常忽略常数项和低阶项，因此将其简化为O(n2)。
阅读下列材料，回答第12至13题：
　　国家外汇管理局统计数据显示，2025年1月，中国外汇市场（不含外币对市场，下同）累计成交22.34万亿元人民币（等值3.11万亿美元）。其中，银行对客户市场成交4.03万亿元人民币（等值0.56万亿美元），银行间市场成交18.31万亿元人民币（等值2.55万亿美元）；即期市场累计成交7.94万亿元人民币（等值1.11万亿美元），衍生品市场累计成交14.40万亿元人民币（等值2.00万亿美元）。
　　2024年1~12月，中国外汇市场累计成交293.01万亿元人民币（等值41.14万亿美元）。
12.下列关于数字和数值的说法，不正确的是 （　　）
A.数值和数字都是数据的表现形式
B.数字本身没有意义，只有在具体情境中才具有实际意义
C.数字数据可以在计算机中直接被处理
D.数值具有量的意义，可以进行算术运算
C
√
计算机不能理解孤立的数字是一个符号还是数值，需要人们事先给予界定并以某种方式告诉计算机。
阅读下列材料，回答第12至13题：
　　国家外汇管理局统计数据显示，2025年1月，中国外汇市场（不含外币对市场，下同）累计成交22.34万亿元人民币（等值3.11万亿美元）。其中，银行对客户市场成交4.03万亿元人民币（等值0.56万亿美元），银行间市场成交18.31万亿元人民币（等值2.55万亿美元）；即期市场累计成交7.94万亿元人民币（等值1.11万亿美元），衍生品市场累计成交14.40万亿元人民币（等值2.00万亿美元）。
　　2024年1~12月，中国外汇市场累计成交293.01万亿元人民币（等值41.14万亿美元）。
13.若要对材料中的数据进行整理，下列数据结构中，最适合的是 （　　）
A.一维数组
B.二维数组
C.链表
D.树
B
√
各市场存储在一个一维数组中，各项成交额存储在另一个一维数组中，两个一维数组之间存在逻辑关系，故适合使用二维数组来存储。

展开更多......

收起↑