资源简介

(共39张PPT)
课时1　数据结构与算法关系
第五章　数据结构与算法
1.理解算法与数据结构的关系，能根据数据结构设计合理的算法。2.能结合实例计算算法的时间复杂度和空间复杂度，并通过实例操作体会选择不同的数据结构对算法效率的影响。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.数据结构与算法的关系
(1)算法的设计和选择总是依赖于____________，算法设计的同时也伴随着____________的设计。
(2)算法是编程思想，____________则是算法思想的基础。
2.算法效率
算法效率的高低可由_______________来衡量。算法复杂度分为算法的_______________和_______________。
数据结构
数据结构
数据结构
算法复杂度
时间复杂度
空间复杂度
3.时间复杂度
(1)时间复杂度反映了算法执行所需要的______，常用大“O”来表示。
(2)算法中语句的____________作为时间复杂度度量标准。
(3)语句总的执行次数T(n)是关于问题规模n的函数。所谓问题规模(也称输入的大小)是指处理问题的大小，即用衡量输入数据量的整数。
(4)算法的_______________反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的______。
(5)常见的时间复杂度从高到低为：
O(1)时间
执行次数
时间复杂度
优劣
4.空间复杂度
(1)空间复杂度反映了算法执行所需要占用的____________。
(2)空间复杂度比较常用的有：O(1)、O(n)、O(n2)。
5.数据结构对算法效率的影响
选择不同的数据结构，算法的运行效率可能也会不同。
存储空间
例题精析
2
A.数据结构是指数据的组织、管理和存储格式
B.数据结构关注的是数据的逻辑结构、存储结构以及基本操作
C.数据结构中的线性存储结构有数组、链表、栈、队列、二叉树等
D.数据结构的存储包括线性存储结构和非线性存储结构
C
解析　数据结构中的线性存储结构有数组、链表、栈、队列等，而树、二叉树属于非线性存储结构，因此答案为C。
A.数据结构与算法的关系可表示为：程序＝算法＋数据结构
B.算法设计必须考虑到数据结构，算法设计不可能独立于数据结构
C.算法的设计同时伴有数据结构的设计，两者都是为最终解决问题服务的
D.数据结构是编程思想，算法则是这些思想的逻辑基础
解析　本题主要考查的是数据结构与算法的关系。算法是编程思想，数据结构则是这些思想的逻辑基础，答案为D。
D
例2 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天(第二天和第三天)里，每天收到两枚金币；之后三天(第四、五、六天)里，每天收到三枚金币；……这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N＋1天里，每天收到N＋1枚金币(N为任意正整数)。
现在骑士想知道，工作一定的天数后，他能获得的金币数量。小明写了3个Python自定义函数，完成了骑士的愿望。
def f1(day)： golds，i，s＝1，0，0 for j in range(day)： 　 　s＋＝golds 　　i＝(i＋1)%golds 　　if i＝＝0： 　　　golds＋＝1 　 return s def f2(day)：
golds，s＝1，0
while day＞＝golds：
　 　s＋＝golds*golds
　　day－＝golds
　　golds＋＝1
　 s＋＝golds*day
　 return s
def f3(day)： k＝int((2*day)**0.5＋1e－6) #1e－6表示10的－6次方 if k*(k＋1)＞2*day： 　 k－＝1 　 s＝k*(k＋1)*(2*k＋1)∥6＋(day－k*(k＋1)∥2)*(k＋1) 　 return s
这三个函数，从时间复杂度分析，程序效率从高到低依次是(　　)
A.f1>f2>f3 B.f2>f3>f1 C.f3>f2>f1 D.三者相同
解析　本题考查时间复杂度。f3没有用到循环，时间复杂度为O(1)，f1循环次数为day。f2循环条件为day>＝golds，golds每循环加1，累加的是连续N天，故f2算法效率大于f1。
C
变式训练　已知 s＝2＋4＋6＋8＋……＋2*n，为求得 s 小于 1500 时，n 的最大值，小明编写了如下三个自定义函数 f1、f2、f3，其语句总执行次数分别用 T1、T2、T3 表示，则它们之间的关系为(　　)
A.T1解析　本题考查语句执行次数。f3没有循环，次数最少；f1中每次加2，f2中每次加1，因此T1C
例3 随机产生100个0至99之间的随机数，存储在列表a中，采用下列算法进行升序输出：
for i in a：
　 b[i]＋＝1
t＝0
for i in range(100)：
　 for j in range(b[i])：
　t＋＝1
　print(str(i)，end＝″″)
该算法的时间复杂度为(　　)
A.O(n) B.O(n2) C.O(2n) D.O(log2n)
解析　本题考查时间复杂度。时间复杂度关键就是要分析循环结构的运行情况和次数。该程序有两个循环，第1个循环的循环次数是100次，第2个循环升序输出a列表中值，内循环的次数由b[i]决定，即循环总的次数是b列表中和，而b表示列表a中元素的个数，因此也是100。程序总共执行了2*n次。
A
变式训练　有如下Python程序代码：
C
n＝int(input(″n＝″))
ans1＝ans2＝0
for i in range(0，n，2)：
for j in range(n)：
ans1＝ans1＋1
ans2＝ans2＋ans1
print(″ans1＝″，ans1，″ans2＝″，ans2)
则该算法的时间复杂度为(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
随堂检测
3
1.算法的复杂度分为算法的时间复杂度和空间复杂度，其空间复杂度是指(　　)
D
解析　算法的复杂度分为算法的时间复杂度和空间复杂度，其空间复杂度是指程序执行时暂时存储中间数据所需要占用的内存空间，因此，答案为D。
A.程序存储时所需要占用的硬盘空间
B.程序存储时所需要占用的内存空间
C.程序执行时暂时存储中间数据所需要占用的硬盘空间
D.程序执行时暂时存储中间数据所需要占用的内存空间
A.同一个算法不一定能适用多种不同的数据结构
B.针对同一个数据结构设计不同的算法，算法的运行效率可能相同
C.使用链表存储和处理数据比使用数组效率更优
D.设计算法时，应根据实际问题选择合适的数据结构
C
解析　本题主要考查的是数据结构对算法效率的影响。使用链表或数组存储并处理数据时，它们有各自的优势，要根据实际情况判断。因此，答案为C。
3.有如下Python程序代码：
A
解析　本题程序只包含顺序结构和分支结构语句，因此，时间复杂度为O(1)，答案为A。
x＝input(″please input x：″)
y＝input(″please input y：″)
if x＋y>y＋x：
print(x＋y)
else：
print(y＋x)
则该程序的时间复杂度为(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
4.有如下Python程序代码：
C
解析　本题主要考查的是时间复杂度的计算。观察程序，可计算出t＝log2n，因此其时间复杂度O(log2n)，答案为C。
n＝int(input(″n＝″))
t＝1
while 2**tt＝t＋1
print(″t＝″，t)
则该算法的时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(2n)
4
巩固与提升
基础巩固
能力提升
A.数据结构是指带有结构特性的数据元素的集合
B.数据结构包括数据的逻辑结构和物理结构
C.数据结构按照数据的逻辑结构分类，分为线性结构和非线性结构两类
D.数据结构中的非线性结构就是指表中各个结点之间具有多个对应关系，如队列
D
解析　数据结构中的非线性结构就是指表中各个结点之间具有多个对应关系，如树、图等，而队列属于线性的数据结构。因此，答案为D。
A.同一个问题采用不同的算法，其算法效率可能不同
B.算法效率的高低可由算法复杂度来度量
C.评价算法效率优劣时，只需评价时间复杂度即可
D.算法的平均效率是指当输入规模为n时算法的平均效率
C
解析　评价算法效率优劣时，不仅要评价算法的时间复杂度，还要评价算法的空间复杂度，因此，答案为C。
A.常用的数据结构主要有：数组、链表、栈、队列、二叉树等
B.数组是一种线性表数据结构
C.若代码的执行时间不随问题规模n的增大而增长，则该代码的时间复杂度记作 O(n)
D.常见的时间复杂度比较为：O(1)C
解析　若代码的执行时间不随问题规模n的增大而增长，则该代码的时间复杂度记作 O(1)，因此，答案为C。
A.同一问题可用不同算法解决，不同算法的执行效率可能不同
B.对于同一个问题，如果选用不同的数据结构，则解决问题的算法可能也不同
C.高效的程序只与所使用的算法有关，与选择的数据结构无关
D.设计算法时，需要考虑选用何种数据结构
C
解析　算法的设计和选择总是依赖于数据结构，因此，高效的程序不仅与所使用的算法有关，还与选择的数据结构有关，故答案为C。
5.有如下Python程序代码：
A
解析　本程序只包含顺序结构，时间复杂度为O(1)，因此，答案为A。
s＝0
n＝int(input(″n＝″))
s＝n*(n＋1)∥2
print(″s＝″，s)
则该算法的时间复杂度为(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
6.有如下Python程序代码：
D
解析　本程序使用的是二重循环，时间复杂度为O(n2)，因此，答案为D。
n＝int(input(″please input n：″))
s1＝s2＝0
for i in range(n－1)：
for j in range(n)：
s1＝s1＋j
s2＝s2＋s1
print(″s＝″，s)
则该程序的时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(n2)
7.有如下Python程序代码：
count＝0
n＝int(input(″n＝″))
for i in range(2，n＋1)：
j＝2
flag＝True
while j<＝i－1：
if i % j＝＝0：
　　　　flag＝False
　　　　break
j＝j＋1
if flag：
print(i，end＝″″)
count＝count＋1
print(″count＝″，count)
A.该程序算法的时间复杂度为O(n2)
B.算法的功能是求区间[2，n]间的素数并统计素数的个数
C.将代码while j<＝i－1：修改为while j<＝int(i**0.5)，算法效率将更高
D.代码if flag：等价于if flag＝＝False：
解析　代码if flag：等价于if flag＝＝True：或if flag！＝False：，因此，答案为D。
D
8.有如下Python程序代码：
n＝int(input(″请输入n：″))
s，i＝0，1
while i<＝n：
s＝s＋i
i*＝2
print(″s＝″，s)
下列说法正确的是(　　)
A.该程序算法的时间复杂度为O(log2n)
B.若输入n的值为8，则输出的结果为21
C.交换语句s＝s＋i与i*＝2的位置，输出s的值将不变
D.该算法的功能是求1＋2＋4＋6＋8＋…＋2*n的和
A
解析　若输入n的值为8，则输出的结果为15，因此B选项错误；交换语句s＝s＋i与i*＝2的位置，将会影响s的值，因此C选项错误；该算法的功能是求1＋2＋4＋…＋2i的和，因此D选项错误；本题程序使用的是一重循环，但每次循环后，循环变量i的值变为i＝i*2，因此，时间复杂度为O(log2n)，也可以记为O(logn)，答案为A。
9.下列关于数据结构的说法正确的是(　　)
D
解析　A选项解决某问题，选择合适的数据结构可以提高算法效率。B选项数组采用下标访问数据，访问效率高。C选项撤销操作的原理是模拟栈的过程。D选项线性表是除了第一个和最后一个元素，每个元素只有一个前驱和一个后继。
A.用不同的数据结构解决同一个问题时，其算法效率是一样的
B.使用数组存储数据时，数据访问效率低，数据插入删除速度快
C.在 word 中执行“撤销键入”操作的原理与队列的特点相同
D.线性表是一种广泛使用的数据结构，常见的线性表有：字符串、队列、栈等
小明在学习了随机数模块后，编写了如下Python程序。请阅读该程序并回答第10～11题。
import random
n＝int(input(″n : ″))
st＝[0]* n
head，tail＝0，len(st)－1
p＝random.randint(5，8)*10＋random.randint(0，9)
while head<＝tail ：
p＝p＋random.randint(1，3)
if p%2＝＝0：
st[head]＝p
head＋＝1
else：
st[tail]＝p
tail－＝1
print(st)
10.该程序的时间复杂度为(　　)
C
解析　本题考查算法时间复杂度。p的初值为[50，89]之间的整数，接着产生的p是连续增加的值。建立长度为n的值均为0的队列，若产生的p是偶数则入队，否则将该值存入队尾，并进行出队操作，该算法循环n次。
A.O(1) B.O(n/2) C.O(n) D.O(2n)
11.若输入的n值为5，则该程序运行后的结果可能为(　　)
B
解析　st数组中偶数在前，奇数在后。A选项不可能有48。C选项77不可能介于两个偶数之间。D产生的数要连续递增，先产生83、85、87，不可能再产生81。
A.[48，84，81，79，77] 　　B.[88，92，95，91，87]
C.[76，77，82，84，79] 　　D.[80，81，87，85，83]课时1　数据结构与算法关系
课时目标
1.理解算法与数据结构的关系，能根据数据结构设计合理的算法。2.能结合实例计算算法的时间复杂度和空间复杂度，并通过实例操作体会选择不同的数据结构对算法效率的影响。
1.数据结构与算法的关系
(1)算法的设计和选择总是依赖于__________，算法设计的同时也伴随着____________的设计。
(2)算法是编程思想，____________则是算法思想的基础。
2.算法效率
算法效率的高低可由________________来衡量。算法复杂度分为算法的______________和____________。
3.时间复杂度
(1)时间复杂度反映了算法执行所需要的________，常用大“O”来表示。
(2)算法中语句的____________作为时间复杂度度量标准。
(3)语句总的执行次数T(n)是关于问题规模n的函数。所谓问题规模(也称输入的大小)是指处理问题的大小，即用衡量输入数据量的整数。
(4)算法的______________反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的________。
(5)常见的时间复杂度从高到低为：
O(1)4.空间复杂度
(1)空间复杂度反映了算法执行所需要占用的____________。
(2)空间复杂度比较常用的有：O(1)、O(n)、O(n2)。
5.数据结构对算法效率的影响
选择不同的数据结构，算法的运行效率可能也会不同。
例1 下列有关数据结构的描述中，不正确的是(　　)
A.数据结构是指数据的组织、管理和存储格式
B.数据结构关注的是数据的逻辑结构、存储结构以及基本操作
C.数据结构中的线性存储结构有数组、链表、栈、队列、二叉树等
D.数据结构的存储包括线性存储结构和非线性存储结构
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　下列有关数据结构与算法关系的描述中，错误的是(　　)
A.数据结构与算法的关系可表示为：程序＝算法＋数据结构
B.算法设计必须考虑到数据结构，算法设计不可能独立于数据结构
C.算法的设计同时伴有数据结构的设计，两者都是为最终解决问题服务的
D.数据结构是编程思想，算法则是这些思想的逻辑基础
例2 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天(第二天和第三天)里，每天收到两枚金币；之后三天(第四、五、六天)里，每天收到三枚金币；……这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N＋1天里，每天收到N＋1枚金币(N为任意正整数)。
现在骑士想知道，工作一定的天数后，他能获得的金币数量。小明写了3个Python自定义函数，完成了骑士的愿望。
def f1(day)： golds，i，s＝1，0，0 for j in range(day)： 　 　s＋＝golds 　　i＝(i＋1)%golds 　　if i＝＝0： 　　　golds＋＝1 　 return s def f2(day)： golds，s＝1，0 while day＞＝golds： 　 　s＋＝golds*golds 　　day－＝golds 　　golds＋＝1 　 s＋＝golds*day 　 return s
def f3(day)： k＝int((2*day)**0.5＋1e－6) #1e－6表示10的－6次方 if k*(k＋1)＞2*day： 　 k－＝1 　 s＝k*(k＋1)*(2*k＋1)∥6＋(day－k*(k＋1)∥2)*(k＋1) 　 return s
这三个函数，从时间复杂度分析，程序效率从高到低依次是(　　)
A.f1>f2>f3 B.f2>f3>f1 C.f3>f2>f1 D.三者相同
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　已知 s＝2＋4＋6＋8＋……＋2*n，为求得 s 小于 1500 时，n 的最大值，小明编写了如下三个自定义函数 f1、f2、f3，其语句总执行次数分别用 T1、T2、T3 表示，则它们之间的关系为(　　)
A.T1　　　　　　　　　　　　　
例3 随机产生100个0至99之间的随机数，存储在列表a中，采用下列算法进行升序输出：
for i in a：
　 b[i]＋＝1
t＝0
for i in range(100)：
　 for j in range(b[i])：
　t＋＝1
　print(str(i)，end＝″″)
该算法的时间复杂度为(　　)
A.O(n) B.O(n2) C.O(2n) D.O(log2n)
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下Python程序代码：
n＝int(input(″n＝″))
ans1＝ans2＝0
for i in range(0，n，2)：
for j in range(n)：
ans1＝ans1＋1
ans2＝ans2＋ans1
print(″ans1＝″，ans1，″ans2＝″，ans2)
则该算法的时间复杂度为(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
计算时间复杂度时，不考虑低价项和首项系数，如x(x－1)的量级与x2相同，其时间复杂度可表示成O(x2)。
1.算法的复杂度分为算法的时间复杂度和空间复杂度，其空间复杂度是指(　　)
A.程序存储时所需要占用的硬盘空间
B.程序存储时所需要占用的内存空间
C.程序执行时暂时存储中间数据所需要占用的硬盘空间
D.程序执行时暂时存储中间数据所需要占用的内存空间
2.下列有关数据结构对算法效率的影响的描述，不正确的是(　　)
A.同一个算法不一定能适用多种不同的数据结构
B.针对同一个数据结构设计不同的算法，算法的运行效率可能相同
C.使用链表存储和处理数据比使用数组效率更优
D.设计算法时，应根据实际问题选择合适的数据结构
3.有如下Python程序代码：
x＝input(″please input x：″)
y＝input(″please input y：″)
if x＋y>y＋x：
print(x＋y)
else：
print(y＋x)
则该程序的时间复杂度为(　　)
A.O(1) B.O(n) C.O(n2) D.O(2n)
4.有如下Python程序代码：
n＝int(input(″n＝″))
t＝1
while 2**tt＝t＋1
print(″t＝″，t)
则该算法的时间复杂度为(　　)
A.O(1) B.O(n) C.O(log2n) D.O(2n)
课时1　数据结构与算法关系
知识梳理
1.(1)数据结构　数据结构　(2)数据结构
2.算法复杂度　时间复杂度　空间复杂度
3.(1)时间　(2)执行次数　(4)时间复杂度　优劣
4.(1)存储空间
例题精析
例1　C　[数据结构中的线性存储结构有数组、链表、栈、队列等，而树、二叉树属于非线性存储结构，因此答案为C。]
变式训练　D　[本题主要考查的是数据结构与算法的关系。算法是编程思想，数据结构则是这些思想的逻辑基础，答案为D。]
例2　C　[本题考查时间复杂度。f3没有用到循环，时间复杂度为O(1)，f1循环次数为day。f2循环条件为day>＝golds，golds每循环加1，累加的是连续N天，故f2算法效率大于f1。]
变式训练　C　[本题考查语句执行次数。f3没有循环，次数最少；f1中每次加2，f2中每次加1，因此T1例3　A　[本题考查时间复杂度。时间复杂度关键就是要分析循环结构的运行情况和次数。该程序有两个循环，第1个循环的循环次数是100次，第2个循环升序输出a列表中值，内循环的次数由b[i]决定，即循环总的次数是b列表中和，而b表示列表a中元素的个数，因此也是100。程序总共执行了2*n次。]
变式训练　C　[本题主要考查的是时间复杂度的计算。本题中的程序为二重循环，语句的执行次数为n2，与量级n2相同，因此其时间复杂度O(n2)，答案为C。]
随堂检测
1.D　[算法的复杂度分为算法的时间复杂度和空间复杂度，其空间复杂度是指程序执行时暂时存储中间数据所需要占用的内存空间，因此，答案为D。]
2.C　[本题主要考查的是数据结构对算法效率的影响。使用链表或数组存储并处理数据时，它们有各自的优势，要根据实际情况判断。因此，答案为C。]
3.A　[本题程序只包含顺序结构和分支结构语句，因此，时间复杂度为O(1)，答案为A。]
4.C　[本题主要考查的是时间复杂度的计算。观察程序，可计算出t＝log2n，因此其时间复杂度O(log2n)，答案为C。]

展开更多......

收起↑