6.1 实时查询系统中数据的组织（教学设计）信息技术浙教版2019选择性必修1

6.1 实时查询系统中数据的组织 1课时（教学设计） 年级 高二年级 授课时间 2课时 课题 6.1 实时查询系统中数据的组织 教学 目标 1.通过典型案例的剖析，使学生能感受、理解数据结构设计的迭代思想。 2.通过典型案例的剖析，使学生了解对于大规模数据的典型数据组织与处理方式。 教学 重难点 重点： 1.实时查询系统中数据的组织方式。 2.常用的数据组织方法及其优缺点 难点： 1.如何根据实时查询系统的需求选择合适的数据组织方式。 2.如何优化数据组织结构以提高查询效率。 教学 准备 多媒体课件、多媒体教室、课本教材 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.情境导入：（1）展示图片：查话费、查流量的截图 （2）操作与体验： 网购平台购物，如何查询和选择商品? 思考:打开京东购物商城，解决以下问题： 要购买一本有关信息技术的书籍，预算在35元以内？ 想要知道目前哪本信息技术书籍最畅销？ 想要知道哪个店铺的好评率最高？ 人们经常会提出实时查询各种信息的请求，如电信业务中实时话费与剩余网络流量的查询、网购用户对特定商品的各种信息查询等。面对这种实时访问，系统必须在瞬间给出结果并呈现给用户。 大数据背景下，全部数据的组织、存储和处理，仅凭单个服务器和数据库的数据组织与存储方式，无论从存储容量还是处理速度上都不能满足实际应用的需求。 此时，采用分布式存储技术，将所有数据分别保存在不同的服务器中，需要时从中提取并进行合并，就可以满足海量数据的存储与处理需求。 以生活实际为例，吸引学生参与课堂，抛出问题，让学生思考并观看教师的PPT课件上的图片提示，从而引出本堂课的主题。 通过学生的实际操作与体验，网购平台购物，如何查询和选择商品?提出相关的要求，在学生的实际操作中引出本堂课的内容。 新 知 讲 授 一、实时查询系统中的数据业务特点 1.拓展链接 分布式存储系统：分布式存储系统利用分布在不同物理位置的服务器来分担系统存储任务，既能提高数据存储的安全性，又能提升系统数据访问的速度，同时也具有较好的可扩展性。当用户提出访问请求时，系统根据元数据服务器（进行数据访问索引的服务器）将访问定位到目标数据的服务器上。 2.实时查询系统的两个特殊性： （1）能实现上千个请求的实时响应 网站应能做到“即点即现”，即当某用户选择一种查询方式后，系统能马上呈现结果，而且同一时刻可能有上千名用户提出了查询请求。 （2）支持后续商品信息的更改 当用户选择了某种查询后，可能马上又有另一名用户提出其他方式的查询请求，而此时恰好网站中更改了某个商品的属性，也或者是删除、增加了商品，那么这个修改信息应该体现在最新的查询结果中。 面对这种查询业务，如果直接从数据库中提取查询结果，特别是在上千名用户同时发出请求的情况下，系统需频繁地读取计算机硬盘并访问数据库。 ①一方面将增加系统的负担，甚至在访问量增大的瞬间出现系统崩溃； ②另一方面，会造成用户较长的等待时间，结果导致用户的流失。 为了减轻磁盘数据库访问的负担，可事先将数据库中的商品信息读取出来并保存在内存中，这样用户的查询就能直接面对内存进行，大大提高数据读取的速度。 3.用某种数据结构组织并存储数据： (1)能体现数据间的逻辑关系 (2)能为后续查询提供算法支持 二、实时查询系统中的数据结构和算法设计 1.基于数据间线性关系的数据结构设计 （1）数组 ①体现商品间的有序线性关系； ②数据读取到数组后，先按各属性（销量、信用、价格等）进行排序并分类存储。 查询过程中涉及的主要操作： 数据查找 在一个有序序列中查找新增元素的插入位置，可以采用二分查找算法，时间复杂度为〇(log2n)（n表示数组元素的总个数），速度比较快； 二分查找、 〇(log2n) 数据插入 在找到可以插入的位置x后，将新元素插入到找到的位置x中，但必须先将位置x到n之间的所有元素往后移一位，为新元素空出位置，这个时间复杂度就比较大，为〇(n)。当瞬间有上千名用户提出请求，同时进行上千个这样的处理时，时效性较差。 插入位置x到n中的元素均后移一位、〇(n)、上千名用户提出请求时，时效性较差 例如：新增商品时，需要插入一个新数据并维持数组元素继续有序。 （2）链表 ①链表替换数组 在数组中插入新元素时引起的数据移动低效的问题 在一个链表中插入一个新元素，时间复杂度为〇(1)，大大优于采用数组时〇(n)的线性复杂度。 ②插入操作主要涉及查找和插入两个关键操作 查找 需从链表的一端依次遍历、〇(n) 插入 〇(1) 整体复杂度有所下降，但还是达不到现实的需求。 只在查找过程低效。 （3）探讨与讨论 除了数组和链表，是否还有其他的数据结构来组织并存储数据？ 非线性数据：树结构 链表的数据结构和算法优化设计 各种数据结构是人们在用计算机解决问题的过程中，根据数据特点不断研究、探索所得到的。因此，随着数据业务的发展，既有的数据结构就得以不断改进，甚至演变出新的数据结构。 由于基于链表的处理，只是在查找时效率较低，而插入操作却完全能满足要求，所以可以在链表的基础上继续加以改进，以解决顺序查找导致的低效问题。 （1）减少查找插入位置过程中的比较次数 链表结构数据主要消耗在插入位置的查找中，可减少查找过程中的数据两两比较的次数来优化数据结构。 （2）借鉴二分查找算法的思想 二分查找算法之所以效率较高，首先是因为数据是有序的，其次是利用有序性进行跨区间、跳跃性的比较，从而避免低效的逐个依次比较。 ①数据进行有序化处理 ②确定比较的关键节点 关键节点：对每个节点采用抛硬币的方法确定是否放在关键节点中 （3）例如：查找元素6 抛硬币的次数越多，其正反的概率越趋向于1/2 从整体效率分析：增设关键节点后，查找速度是原来的2倍 ①建立二级索引 插入数据元素6 原一级索引的比较次数减少一半，数据多，还可增设三、四级索引 总体来说,通过对链表改进可实现〇(log2n) 因为数据序列在不断地变化，所以需要对关键节点进行动态的调整，即数据增加时增设关键节点，而数据减少时删除关键节点。对各级索引表中的关键节点进行增加和删除的实现方法如下： ①增设关键节点。随着数据元素的增加，原链表会变得越来越长，结果导致区间内查找效率降低。为了解决这个问题，可以考虑对新增元素基于“抛硬币”原则的选拔，以确定是否把新增元素提升为上一层的关键节点，并且逐层进行。 若新增元素为24，通过“抛硬币”发现需要提升为关键节点，则新的链表组织结构如下图所示。 将新增元素24所在节点提升为关键节点 若通过“抛硬币”发现不需要提升为关键节点，则新的链表组织结构如下图所示（新增元素只在原链表中出现）。 新增元素24所在节点不提升为关键节点 ②删除关键节点。随着原链表中数据元素的不断删除，各级索引中的关键节点也需要随之删除。删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。若原来链表的状态如下图所示，现在要删除原链表中的元素10，则从顶层索引开始，依次往下删除各层的元素10。 删除元素10之前的链表状态 二级索引中删除元素10所在的节点后，因为只剩下一个关键节点，对于区间划分和提高查找效率没有任何意义，所以将剩下一个节点也删除，得到的最终状态如下图所示。 删除元素10之后的链表状态 因为上述数据结构是在一个有序链表中通过索引表跳跃着进行查找，所以称为“跳跃表”，跳跃表是威廉 · 皮尤（William Pugh）于1990年发明并提出的一种数据结构。 数组→链表→跳跃表 一个切合实际的数据结构和算法不是一蹴而就的，而是根据问题中数据及其关系的特点，通过迭代逐步优化得到的。 3.探讨与讨论 “跳跃表”是立足链表，是借鉴二分思想形成的数据结构。能否立足数组，借鉴链表的思想构造一种新的数据结构来解决数组数据移动的低效问题？ 参考方向：将原来一个数组中的数据均匀地分解存储到k个数组中，这样就将原来(𝑛)的移动复杂度降为(n/k)，虽然数量级没变，但至少是原来的k倍速度 三、其他数据组织与处理方式 单纯采用传统的磁盘数据库来组织、处理海量的数据，其固有的数据组织、存取、处理等模式无法适应当今很多数据业务对实时数据管理和查询的需求。于是，人们针对磁盘数据库存在的瓶颈，发明了内存数据库，并于1994年推出了第一个商业化的、实际应用的内存数据库。 推出内存数据库： 1.减少对磁盘的访问 2.对数据进行分级存储 3.采用改进后的数据结构来组织、存储数据 AVL树、Sorted-set技术 探讨与讨论 （1）若数据库中有10万条记录以链表形式有序存放，先要在原链表基础上增设关键节点创建索引，若以二分的形式创建每一级索引，则最多需要创建索引的级数是（ ） A.8 B.17 C.100 D.1000 （2）若使用跳跃表查询，则对于下图所示的链表： 四、课堂小练 五、小结 1.实时查询系统中的数据业务特点 （1）能实现上千个请求的实时响应。 （2）支持后续商品信息的更改。 2.实时查询系统中的数据结构和算法设计 （1）基于数据间线性关系的数据结构设计 ①数组②链表 （2）基于链表的数据结构和算法优化设计 ①减少查找插入位置过程中的比较次数 ②借鉴二分查找算法的思想 3.其他数据组织与处理方式 (1)减少对磁盘的访问 (2)对数据进行分级存储 (3)采用改进后的数据结构来组织、存储数据 通过拓展链接，引入分布式存储系统，让学生们先了解什么是分布式存储系统，在后面的课堂中，将该概念更好的融入到教学中。 提出实时查询系统的两个特殊性，从两个方面对比性的进行讲解，让学生能更好的去理解实时查询系统。 再通过对实际案例的对比分析后，学生 对实时查询系统有了基本的理解。 有了对实时查询系统中的初步理解，现在从其数据结构来讲解，同样也是在对比中进行讲解，先通过之前学过的数组来讲解，然后引出链表，体现两个在实际应用中的不同。 通过课堂练习，加深同学们对基于数据间线性关系的数据结构设计的理解。 引入实际案，对链表的数据结构和算法优化设计的讲解，比如在查找元素6，通过之前的理论讲解，现在在案例中来讲解，让学生能够更更好的理解。 图形化的讲解和展示，让学生更能够循序 渐进的学习和掌握知识点。 通过案例的讲解，同学们已经有了一个逐步递进的学习过程，从数组→链表→跳跃表，从这三个方面来更好的理解本节课的内容：实时查询系统中数据的组织。 通过课堂练习，加深同学们对跳跃表的理解。 课 堂 练 习 （有题有答案有解析） 1. 利用分布在不同物理位置的服务器来分担系统存储任务，既能提高数据存储的安全性，又能提升系统数据访问的速度，同时也具有较好的 。 2.实时查询系统的两个特殊性： 、 。 3.针对在数组中插入新元素时引起的数据移动低效的问题，可以考虑用 代替 。 4.数据序列在不断地变化，所以需要对关键节点进行动态的调整，即数据增加时增设 ，而数据减少时删除 。 5.某班级的同学制作了一个以“加油吧高考”为主题的网站，现在他想让别人来共同分享欣赏他们的作品，那么可以通过()方式来发布。 ①在网上邻居中发布 ②保存到电子邮箱中 ③在因特网上发布 ④在本机上发布， A.①②③ B.①②④ C.①③④ D.②③④ 6.如图所示，此网站发布方式属于() A.因特网上发布 B.局域网内发布 C.本机发布 D.网上邻居发布 7.下列关于数据结构的说法正确的是() A.同一数据元素中各数据项的数据类型一定相同 B.跳跃表是立足链表、借鉴二分查找的思想而形成的数据结构 C.若入栈序列为abcd，则出栈序列可能为dbca D.在浏览器中执行“后退”、“前进”操作的原理与队列的特点相同 8.下列选项中可以看出都是文本文件的选项是() A.学习强国.doc、lover.SWF B.湖北省12月计算机调考成绩.xls、校运会 成绩排序.exe C.算法代码.txt、九九乘法表.docx D.Python.exe、21.swf 9.关于结构化程序设计所要求的基本结构，以下描述错误的是() A.重复(循环) B.选择(分支) C.goto 跳转 D.顺序 10.一个数组的第一个元素的存储位置为1000(表示在第1000个字节处)，每个元素所占空间大小为8个字节，则第5个元素的位置是（ ）? A.1000 B.1040 C.1032 D.1256 参考答案： 1.分布式存储系统、可扩展性。 2.能实现上千个请求的实时响应、支持后续商品信息的更改。 3.链表、数组 4.关键节点、关键节点 5.【答案】C [解析]本题考查信息发布的方式，信息发布的类型多种多样，大致可分为两种:一种是借用现成的网络工具和资源发布信息，另一种是建立自己的网站发布信息。题目中的1和3是借助网络进行发布，4在本机建立自己的网站进行发布，故通过1、3、4都能实现让别人来分享自己他们的作品。故选:C。 6.【答案】C [解析]在因特网上发布网站:①申请网站空间:ISP:互联网服务提供商②上传网站:常用的FTP工具:CuteFTP、LeachFTP、WebPublisher等维护和宣传网站包括:①内容的更新，如文字、图片、动画等信息的校对、增加和修改等②根据信息发布活动的需求，阶段性地调整网站的整体风格，如更换版面结构，颜色搭配等。通过图片可知，是在本地的D盘上发布的，故选:C. 7.【答案】B [解析]跳跃表(SkipList)是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(log N)。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。故选项B说法错误。故选:B。 8.【答案】C [解析]文本文件主要包括:txt(所有文字处理软件或编辑器都可打开)、doc(word及wps等软件可打开)、hlp (adobe acrobat reader可打开)、wps(wps软件可打开)、rtf(word及wps等软件可打开)、html(各种浏览器可打开、用写字板打开可查看其源代码)、pdf(adobe acrobat reader和各种电子阅读软件可打开)等.A:doc为电子文档;SWF是基于矢量的Flash动画[3]文件格式，A错误;B: xls是电子表格;exe是可执行文件[4]，B错误;C:txt是文本文档;docx是电子文档，C正确;D:exe是可执行文件，swf是基于矢量的Flash动画文件格式，D错误.故选C. 9.【答案】C [解析]本题主要考查程序基本结构。结构化程序设计所要求的基本结构，包括三种:重复(循环)、选择(分支)和顺序结构，故本题选C选项。 10.【答案】C [解析]第五个元素的存储地址为1000+8×（5-1）=1032 课 堂 小 结 课堂小结 一、实时查询系统中的数据业务特点 1.能实现上千个请求的实时响应。 2.支持后续商品信息的更改。 二、实时查询系统中的数据结构和算法设计 1.基于数据间线性关系的数据结构设计 （1）数组（2）链表 2.基于链表的数据结构和算法优化设计 （1）减少查找插入位置过程中的比较次数 （2）借鉴二分查找算法的思想 三、其他数据组织与处理方式 1.减少对磁盘的访问 2.对数据进行分级存储 3.采用改进后的数据结构来组织、存储数据 作 业 设 计 1.某算法的时间复杂度是〇(n),表明该算法()。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 2.递归算法的函数调用时,处理参数和返回地址,通常使用的数据结构是（） A.数组 B.链表 C.队列 D.栈 3.算法的时间复杂度是指什么?() A.算法执行所需的时间 B.算法中语句的数量 C.算法所需内存空间 D.算法执行所需时间随输入规模增长的趋势 4.若数据库中有10万条记录以链表形式有序存放,现要在原链表基础上增设关键节点创建索引,若以二分的形式创建每一级索引,则最多需要创建索引的级数是() A.8 B.17 C.100 D.1000 5.有如下Python程序段: a=[[0]*4]*3 b=[[0]*4 for i in range(3)] a[2][3]=8 b[2][3]=8 则程序执行后，下列说法正确的是( ) A.a[0][3]的值为0,b[0][3]的值为0 B.a[0][3]的值为0,b[0][3]的值为8 C.a[0][3]的值为8,b[0][3]的值为0 D.a[0][3]的值为8,b[0][3]的值为8 6.有如下 Python程序代码: s=0 n=int(input( "n=")) s=n*(n+1)//2 print("s=",s) 则该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n2） D.〇(2n) 7.阿福将我国部分省份及其省会城市存储到二维数组中，并依次输出各省及其省会名称，例如“湖南省的省会是长沙市”。相关代码如下: a=[["浙江省","杭州市"]，["吉林省","长春市"],["湖南省","长沙市"],["湖北省","武汉市"],["江苏省","南京市"],["广东省","广州市"]] for p in a: print(f"{ }的省会是{ }") 则划线①和②处分别应填写的代码为( ) A.①p[1];②p[0] B.①p[0];②p[1] C.①a[p][0];②a[p][1] D.①p[1];②p[2] 8.通过以下 Python 程序段,转换为原链表的逆序链表,即头指针 head=1,L=[[30,2],[10,3],[20,-1]，[15,4],[21 ,0]]。 q=-1 p = head #head 为原链表头指针 while p!=-1: tmp =L[p][1] head = q 上述程序段中方框处可选的语句为: ①p = tmp ③L[p][1] =q ②q=p 则方框处语句依次为 A.③②① B.③①② C.①③② D.①②③ 9.使用Python的二维列表来模拟单向链表，如下代码创建一个拥有4个节点的链表a a = [[“cat“，1],[“dog“，2],[“pig“，-1],[“rabbit“，0]] head =3 依次输出各节点数据域的值，内容为( ) A.“cat“，“dog“，“pig“，“rabbit“ B.“pig“，“rabbit“，“cat“，“dog“ C.“pig“，“dog“，“cat“，“rabbit“ D.“rabbit“，“cat“，“dog“，“pig“ 10.arr=[1,3,4,5,6,8,9,12,15,0] #0表示该位置未存储元素 num=int(input("输入需要插入的数据:")) for i in range(len(arr)): if arr[i]>num: for j in range(len(arr)-1,i-1,-1): arr[j]=arr[j-1] arr[i]=num break else: arr[-1]=num print(arr) 执行该程序段后,输入数字9,则位置下标发生改变的数据个数是() A.3 B.2 C.1 D.0 11.下列Python程序的功能是在数据有序的链表中插入一个整数，使链表中的数据仍保持有序. a=[[8,3],[6,0],[2,1],[11,4],[15,-1]] n-int(input("请输入一个整数:")) p=q=head=2 if n<=a[head][0]: a.append([n,head]) ① else: while p!=-1 and ②: q=p p=a[p][1] a.append([n,p]) a[q][1]=1en(a)-1 划线处应填入的代码是() A.①head=a[p][1] ②n>a[p][0] B.①head=a[p][1] ②n>a[q][0] C.①head=len(a)-1 ②n>a[p][0] D.①head=len(a)-1 ②n>a[q][0] 参考答案： 1.【答案】D [解析]算法的时间复杂度是〇(n),这是设定问题规模为n的分析结果,所以A、B都不对;它也不表明执行时间等于n,它只表明算法的执行时间T(n)≤cXn(c为比例常数)。有的算法,如nXn矩阵的转置,时间复杂度为〇(n),不表明问题规模是n。 2.【答案】D [解析]本题主要考查的是递归算法。计算机在执行递归程序时，是通过栈结构的调用来实现的，因此答案为D。 3.【答案】A [解析]所谓算法的时间复杂度，是指执行算法所需要的计算:工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程叶，所需基本运算的执行次数米度量.算法的工作量。故选:A。 4.【答案】B [解析]二分查找最多的查找次数为[log2n]+1。 5.【答案】C [解析]本题主要考查的是二维数组创建与访问。数组a为间接创建方式，当某个元素值改变时，对应的该列所有值改变，数组b使用的是列表生成式创建,各个元素独立。 6.【答案】A [解析]本程序只包含顺序结构，时间复杂度为〇(1),因此,答案为A。 7.【答案】B [解析]考查数组的基本知识。遍历a数组的元素，p[0]获取省份,p[1]获取城市,因此①、②处分别应填写的代码为p[0],p[1]。 8.【答案】A [解析]考查数据结构中链表的知识。将原链表转换为逆序链表,需要将原链表遍历一遍,记录链表指向,并进行交换逆向输出。观察代码,head为原链表头指针且p=head,当P值不为1即链表不为空时，执行tmp=L[p][1],将当前链表位指向临时放人p 并给其赋值为q,再将p赋值给q,然后将tmp赋值给p,准备下一轮赋值给q。如此循环,直到原链表的最后一位结束,最后 head 就是最后一次的位置。因此方框中可选的语句顺序是:L[p][1]=q-->q=p-->p =tmp。故选 A。 9.【答案】D [解析]根据引用域的排列顺序可知[“rabbit“，0][“cat“，1],[“dog“，2],[“pig“，-1]，列表是这样的顺序。故选:D。 10.【答案】B [解析]当数组arr中的元素arr[i]大于新数据num时,则将位置i及其之后的数据都向后移动,所以当输入的数字为9时,12大于num,则12和15的位置下标将发生改变。 11.【答案】C [解析]本题考查Python程序。首先分析程序逻辑，程序要在有序链表中插入一个整数n并保持有序。如果n小于等于表头元素的值，就在表头插入。否则，通过循环找到合适的插入位置。对于①处，如果n小于等于表头元素，要更新表头指针，应将表头指针指向新插入元素，即head=len(a)-1。对于②处，在循环中要判断n是否大于当前指针所指元素的值，即n>a[p][0]。故答案为: C。 反 思 评 价 本堂课讲解的是理论实践方面的知识，比较枯燥难懂，只有通过大量的举例来充实课堂。通过典型案例的剖析，使学生能感受、理解实时查询系统中数据的组织的思想。通过典型案例的剖析，使学生了解实时查询系统中数据的组织。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$