5.1数据结构与算法效率 学案 - 浙教版2019 高中 信息技术 选修1 学案

| 4页
| 142人阅读
| 1人下载
精品

学科网 zxxk.com学科网 zxxk.com

 5.1数据结构与算法效率 导学案

学科

高中信息技术

教材版本

浙教版2019选修1

课题

5.1数据结构与算法效率

一、【学习目标】

1.理解数据结构与算法的关系。(重点)(学科核心素养:信息意识、计算思维)

2.认识算法效率高低的主要的两个方面:时间复杂度与空间复杂度,及这两个方面的表示与计算。(难点)(学科核心素养:信息意识、计算思维)

3.逐步自觉将算法的效率应用在算法程序设计中,根据问题选择合适的数据结构,提高算法效率。(学科核心素养:信息意识)

二、【自主探究】

任务一:学生自主学习课本,完成下列题目:

1.算法效率的高低可由          来度量。算法复杂度又分为算法的       和      ,其中时间复杂度反映了          所需要的时间,而空间复杂度反映了算法执行所需要占用的         。

2.算法的       反映了程序执行时间随问题规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣。

任务二:

def ct(n):

s=0

while   n>0:

s+=n%2

n//=2

return  s

n=int(input("输入一个正整数:")

ans=ct(n)

print(ans)

请回答下列问题:

(1)程序运行后,输入整数23,自定义函数ct(n)中语句“s+=n%2”执行的次数是     。page number 0

原创精品资源学科网独家享有版权,侵权必究!

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


学科网 zxxk.com学科网 zxxk.com

(2)该算法的时间复杂度为         (单选,填字母:A.O(n)/B.O(log₂n))。

任务三:小华规划自驾游路线,出发地为杭州,目的地为北京,途径地为上海、苏州、南京、济南、石家庄。用数组来实现其更改过程。

0

1

2

3

4

5

6

杭州

上海

苏州

南京

济南

石家庄

北京

          

(1)小华想要查询第5个到达的城市,如何编程实现      时间复杂度为       。 

(2)小华计划有变决定直接从上海出发,不从杭州出发,如何编程实现?时间复杂度为       。

a=["杭州","上海","苏州","南京","济南","石家庄","北京"]  

n=ien(a)

q=0

for i in range(q,n-1):

 

  1. pop()

print(a)

任务四:比较数组和链表两种不同的数据结构对算法的影响并填写表格。

 

 

page number 1

原创精品资源学科网独家享有版权,侵权必究!

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。