浙江版高中信息技术复习教学专题七数据的组织课件

第一部分信息技术

专题七数据的组织高考

技术浙江省专用考点一数组一、数组的概念与特征1.数组的概念数组是由相同类型的变量构成的一个序列。数组使用一个标识符(数组名)命名,并用

编号(下标或索引)区分数组内的各个变量。由数组名和下标组成数组的各个变量称

为数组的分量,也称为数组元素。常用的数组有一维数组和二维数组。2.数组的特性(1)数组元素的数据类型相同。(2)通过数组名和下标对数组元素的值进行访问。(3)存储空间固定不变。二、数组的基本操作1.数组的创建数组的创建实质是在系统内存中划分一块连续区域,用来保存数组所含的所有数据元

素。2.数组元素的访问通过数组名和下标直接访问数组元素。例如,a[0]表示一维数组a中的第一个元素。3.数组元素的插入与删除当需要在数组中某个位置插入一个新的数据时,必须先将该位置及其后的所有数据向后移动一个位置,在保证顺序不变的前提下保存这些数据,最后再修改该位置上的数

据为新数据,时间效率较低。在删除数组元素时,需要将被删除元素位置后的所有元素前移一个位置,同样有时间

效率低的问题,而且在删除比较多的元素后,数组中存储的有效数据减少,从而造成存

储空间的浪费。因此,在使用数组组织存储数据时应尽量避免数组元素的增删操作。考点二链表一、链表的概念与特性1.链表的概念链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结

构。链表中的每个节点一般由“数据区域”和“指针区域”两部分构成。链表可以

根据每个节点中指针的数量分为单向链表和双向链表。2.链表的特性(1)同一链表中每个节点的结构均相同;(2)每个链表必定有一个头指针,以实现对链表的引用和边界处理;(3)链表占用的空间不固定。二、链表的基本操作1.链表的创建创建链表时,首先要根据问题特点规划节点的数据域和指针域,然后根据规划创建一

个空链表。2.链表节点的访问与遍历链表只能通过头指针进行访问,其他节点通过节点间的指针依次访问。链表中的节点

通过指针相互链接,当需要访问某个位置的节点元素时,只能通过头指针进入链表并

通过节点间的链接关系逐个向下访问,直到找到指定位置节点。与数组相比,其节点的访问效率较低。3.链表节点的插入和删除链表节点的插入指的是根据新输入的实际数据形成节点,然后修改新节点与其前驱节

点的指针,将新节点插入到链表的正确位置。链表节点的删除,则通过将需要删除节点的前驱节点和其后继节点直接相连的方式实

现。三、数组与链表的区别1.存储结构数组使用一块连续的内存空间来存储一组数据,存储空间固定不变;链表不需要一块连续的空间,可通过“指针”将零散的空间联系起来。2.数据的运算数组通过下标可快速访问任一位置上的数据,但插入和删除数据的效率较低;链表需

通过节点间的链接关系依次访问,但插入和删除数据的效率较高。对于想要快速访问数据,又不经常插入和删除元素的情形,一般可选数组;对于需要经

常插入和删除元素,而对访问元素时的效率没有很高要求的情形,一般可选链表。考点三队列一、队列的概念队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队

首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队,从队列中删

除一个元素称为出队。如下图所示,元素a1最先入队,是队首元素;元素an最后入队,是队

尾元素。

1.先进先出、后进后出由队列的定义可知,队列具有“先进先出、后进后出”的特点。出队时,队首元素a1优

先出队,紧接着是a2,a3,…,an-1,队尾元素an最后出队。2.有限序列性队列是一种特殊的线性表结构,元素个数是有限的。队列可以是空的,也可以包含多

个元素。队列中所有元素呈现线性特征,队首元素只有一个后继点,队尾元素只有一

个前驱点,其他元素既有一个前驱点,又有一个后继点。三、队列的基本操作(一)队列的存储二、队列的特性1.队列一般按顺序结构存储,可以用数组来实现。如图所示,数组que中存储了一个队

列,共有4个元素,队首元素为a1,队尾元素为a4。head记录队首元素所在的位置,tail记录

队尾元素的下一个位置。

2.入队与出队的head、tail指针变化(1)入队

(2)出队

(3)队列的链式存储结构设置队首指针head记录链表的头节点,队尾指针tail记录链表的队尾节点。

空链队列

非空链队列(二)建队以数组形式存储队列为例,下面的Python程序中,用列表来实现创建队列。例如,有4个

字母“A”“B”“C”“D”按序入队、出队时,可以创建一个队列que,长度为4,初

始值空串。Python代码如下所示:head=0

tail=0que=[""]*4(三)入队、出队1.入队字母“A”“B”“C”“D”按序入队时,在队列que中,用tail指针变量跟踪各元素的

入队。如图所示。

入队的Python代码如下所示:que[tail]="A"#字母A入队tail=tail+1#tail=1que[tail]="B"#字母B入队tail=tail+1#tail=2que[tail]="C"#字母C入队tail=tail+1#tail=3que[tail]="D"#字母D入队tail=tail+1#tail=42.出队出队时,排在队首的元素依次出队,head指针变量依次加1,直至head值等于tail值时,队

列为空。

考点四栈一、栈的概念栈是一种操作受限的特殊线性表,仅允许在表的一端进行插入或删除。进行插入或删

除操作的一端称为栈顶,位于栈顶位置的元素称为栈顶元素;相应地,将表的另一端称

为栈底,位于栈底位置的元素为栈底元素。二、栈的特性1.先进后出、后进先出最后入栈的元素最先出栈,最先入栈的元素最后出栈。2.有限序列性同队列一样,栈中的元素也是有限的。栈可以是空的,也可以包含多个元素。栈中元

素呈线性关系,栈顶元素有一个前驱点,栈底元素有一个后继点,其他元素既有一个前

驱点,又有一个后继点。三、栈与队列的区别项目不同点相同点队列先进先出,后进后出有限序列性栈先进后出,后进先出考点五树一、树与二叉树1.树(Tree)可以描述为由n(n≥0)个节点(Node)构成的一个有限集合以及在该集合上定

义的一种节点关系。集合中的元素称为树的节点,节点的度是指该节点拥有的子树数

目,n=0的树称为空树。2.二叉树的概念二叉树是一个具有n(n≥0)个节点的有限集合,它的所有节点的度都小于或者等于2。

当n=0时,二叉树是一棵空树;当n≠0时,则是一棵由根节点和两棵互不相交的、分别称

作这个根节点的左子树和右子树组成的二叉树。3.二叉树的性质(1)二叉树的第k层上最多有2k-1(k≥1)个节点。(2)深度为k的二叉树最多有2k-1(k≥1)个节点。(3)在任意一棵二叉树中,若度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=

n2+1。二、二叉树的基本操作1.二叉树的建立(1)数组实现二叉树可以用数组来实现。对于完全二叉树,从二叉树的根节点开始,按从上而下、自左往右的顺序对n个节点进行编号,根节点的编号为0,最后一个节点的编号为n-1。

然后依次将二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一

对应。对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示,然

后将补全后的完全二叉树,从它的根节点开始,按从上而下、自左向右的顺序对n个节

点进行编号,根节点的编号为0,最后一个节点的编号为n-1。依次把完全二叉树中原二

叉树的节点用一维数组的各个元素来表示,节点编号与数组的下标一一对应。

(2)链表实现二叉树也可以采用链表来实现。二叉树的节点至少需要3个域:一个数据域和两个指

针域。数据域用于存放本节点的数据信息,两个指针域分别指向节点的左孩子和右孩

子。这两个指针分别称为左指针和右指针,这样得到的链表也称为二叉链表。当指针

不指向任何节点时,指针域用“^”表示。2.二叉树的遍历二叉树的遍历,是指按照一定的规则和次序访问二叉树中的所有节点,使得每个节点

都被访问一次且仅被访问一次。二叉树的遍历方式有很多,主要有前序遍历、中序遍

历和后序遍历等。三、抽象数据类型1.数据类型数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。每种

程序设计语言都提供了一些内置数据类型,并为每个内置类型提供了一批操作。2.抽象数据类型抽象数据类型是指一个数学模型及定义在该模型上的一组操作。程序设计语言的一

个内置类型可以看作是一个抽象数据类型。3.抽象数据类型的描述(1)形式要求:类型的名称、操作的名字、参数的个数和类型等。(2)功能要求:希望这个操作完成什么样的计算或产生什么效果等。(3)标准格式:ADT抽象数据类型名:Data数据元素之间逻辑关系的定义Operation操作1初始条件操作结果描述操作2……操作n……endADT考点六大数据时代的数据的组织一、实时查询系统中数据的组织1.实时查询系统中数据业务特点(1)能实现上千个请求的实时响应;(2)支持后续数据信息的更改。2.实时查询系统中的数据结构和算法设计(1)数组①查找,即在一个有序序列中查找新增元素的插入位置,可以采用二分查找算法,时间

复杂度为O(log2n)(n表示数组元素的总个数),速度比较快。②插入,即在找到可以插入的位置x后,将新元素插入到找到的位置x中,但必须先将位

置x到n之间的所有元素往后移一位,为新元素空出位置,这个时间复杂度就比较大,为

O(n)。当瞬间有上千名用户提出请求,同时进行上千个这样的处理时,时效性较差。(2)链表①插入,在一个链表中插入一个新元素,时间复杂度为O(1),大大优于采用数组时O(n)

的线性复杂度。②查找,链表虽然在插入操作时能确保O(1)的时间复杂度,但在进行查找时(查找新元

素的插入位置),却需要从链表的一端依次遍历查找,时间复杂度为O(n)。因此,采用链

表来存储数据,虽然整体复杂度有所下降,但O(n)的复杂度还是达不到现实的需求。(3)基于链表的数据结构和算法优化设计①减少查找插入位置过程中的比较次数;②借鉴二分查找算法的思想。3.其他数据组织与处理方式大部分的内存数据库主要从以下几个方面来提升数据的处理性能。减少对磁盘的访

问;对数据进行分级存储;采用改进后的数据结构来组织、存储数据。二、POI数据的组织与应用1.POI数据的概念POI(兴趣点)作为可以在电子地图中查询到的信息点要素,它描述了空间实体或者区域的空间位置、名称地址等信息。衡量POI数据价值的指标有空间位置的准确性和

覆盖率、空间位置的数量。2.POI数据的组织与表示POI数据一般以表记录或点状数据集的形式存在。POI数据的组织主要涉及空间索引

问题,空间索引是指依据空间对象的位置和形状或者空间对象之间的某种空间关系,

按一定的顺序排列的一种数据结构。考向一数组1.数组的创建(1)在Python中使用列表创建一维数组。例:学校元旦文艺汇演比赛时,现场有9位评委给各班节目打分,统计系统需要根据9位

评委的原始分计算平均分,作为各班表演节目的最终得分。创建保存评委原始分的一维数组s的程序如下:程序测试结果s=[0]*9print(s)[0,0,0,0,0,0,0,0,0](2)在Python中使用列表实现二维数组有两种方式:一是直接定义,适合创建规模较小

的二维数组。例如:保存棋盘信息的程序(直接定义)测试结果qp=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]foriinrange(4):#枚举行print(qp[i])[0,0,0,0][0,0,0,0][0,0,0,0][0,0,0,0]二是间接定义,适合创建规模较大的二维数组,例如:保存棋盘信息的程序(间接定义)测试结果qp=[[0foriinrange(4)]forjinrange(4)]foriinrange(4):print(qp[i])[0,0,0,0][0,0,0,0][0,0,0,0][0,0,0,0]2.Python列表中实现增加、删除数组元素的函数函数和方法功能实例len(list)统计列表list中元素个数list=[]print(len(list))输出为:0list.append(x)在列表list末尾添加元素xlist=[22,33,44]list.append(55)print(list)输出为:[22,33,44,55]list.insert(i,x)在列表list中下标为i的位置处插

入元素xlist=["A","B","D"]list.insert(2,"C")print(list)输出为:["A","B","C","D"]list.pop(i)将列表list中下标为i的元素删除;

若i不指定,默认为-1,即最后一个

元素list=["A","B","C","D"]list.pop(2)print(list)输出为:["A","B","D"]例1

(2022A9协作体返校考,12)有如下Python程序段:fromrandomimportrandomi=0a=[0]*6whilei<=5:a[i]=(int(random()*6+5))*(i%2+1)forjinrange(i):ifa[j]==a[i]:i=i-1breaki=i+1程序执行后,数组a中的数据可能是

(

)A.[6,12,5,18,8,10]B.[7,18,10,10,6,12]C.[8,15,6,16,7,12]D.[5,16,12,18,9,10]

解析

本题主要考查数组及随机数的使用。由代码可知,随机生成的数据,执行后面代码不会改变数据也不会移动位置。当i等于0、2、4时,生成的随机数为5~10,不会大

于10,所以D中的12错误;当i等于1、3、5时,生成的随机数要乘2,所以是10~20的偶数,

所以C中15错误;从代码ifa[j]==a[i]:i=i-1可知,数组a中不可能有相等的元素,所以B错误。

答案A1.(2022衢州期末,9)小萌编写Python程序批量处理“从身份证号码中提取出生年月

日”,将姓名和身份证号码存储在二维数组sfzh中,例如“周子夏”和“蔡佳杰”两人

的信息存储格式为:[["周子夏",],["蔡佳杰","3308812005040323

23"]]。程序代码如下:#将姓名和身份证号存储在二维数组sfzh的代码略foriinrange(len(sfzh)):s=

year=s[:4];month=s[4:6];day=s[6:]即练即清print("%s同学的生日是:%s年-%s月-%s日"%(sfzh[i][0],year,month,day))程序划线处填入的代码为

(

)A.sfzh[i][1][6:13]B.sfzh[i][1][6:14]C.sfzh[i][1]D.sfzh[i][0]答案

B

2.(2022杭嘉湖金月考,9)有如下Python程序段:importrandoma=[0]*6foriinrange(1,6):tmp=random.randint(5,24)iftmp%2==0ori%2==1:a[i]=a[i-1]+tmpprint(a)运行程序后,数组a的值可能是

(

)A.[0,9,29,50,0,20]B.[8,20,44,62,86,109]C.[0,8,14,21,39,0]D.[0,10,24,43,0,30]答案

A

考向二链表1.在Python中创建链表item=[]#空链表head=-1#表示头指针指向为空

2.链表节点的插入与删除(1)单向链表中插入新节点的过程

(2)单向链表中删除某一节点的过程

例2

(2022七彩阳光返校考,10)有如下Python程序段:defbianli(head):pt=headwhilept!=-1:print(data[pt][0],data[pt][1],"->",end='')pt=data[pt][1]print()data=[['A',1],['B',2],['C',3],['D',-1]]head=0bianli(head)#遍历链表,显示初始状态为"A1->B2->C3->D-1->"qt=headpt=data[qt][1]bianli(head)#遍历链表,显示最终状态为"A2->C1->B3->D-1->"执行该程序段后,链表遍历结果由初始状态变为最终状态,上述程序段中方框处可选

代码为:①data[data[qt][1]][1]=pt②data[qt][1]=data[pt][1]③data[pt][1]=data[data[pt][1]][1]则方框处代码的正确顺序是

(

)A.①②③B.①③②C.②①③D.②③①

解析

本程序主要考查的是链表的重新链接,程序实现的效果是A1->B2->C3->D-1->,变为A2->C1->B3->D-1->,qt表示前一指针,pt表示后一指针,故'A'要指向'C','B'要指向'D',然后'C'要指向'B'。

答案D1.(2022百校联考,9)采用列表模拟单向链表,data[p][0]为数据区域,data[p][1]为指针区

域。在单向链表指针为p的节点之后插入指针为s的节点,正确的操作是

(

)A.data[s][1]=pdata[p][1]=data[s][1]B.data[p][1]=sdata[s][1]=data[p][1]C.data[s][1]=data[p][1]data[p][1]=s即练即清D.data[p][1]=data[s][1]data[s][1]=p答案

C

2.(2024届百校起点调研考试,12)使用链表结构模拟某景区游玩路线,链表a中每一个节

点包含三个数据,第1个为景点名称,第2个为预计游玩时间(单位:分钟),第3个为下一个

景点指针。景区可以从多个景点的大门进入,但只能从"天梯"离开,输出显示各大门进

入路线及预计总时间的代码如下。a=[["迎客松",21,2],["激流勇进",40,2],["天空栈道",50,5],["一线天",30,4],["飞来峰",60,

5],["天梯",20,-1]]head=[0,1,3]foriinrange(len(head)):

(1)

s=a[p][1]whilea[p][2]!=-1:print(a[p][0],end="—>")

(2)

(3)

print(a[p][0])print("预计时间:",s,"分钟")上述程序划线处的可选代码有:①p=head②p=head[i]③s=s+a[p][1]④p=a[p][2]则(1),(2),(3)处代码依次为

(

)A.①③④B.①④③

C.②③④D.②④③答案D

考向三队列顺序存储结构与链式存储结构的比较1.顺序存储结构(1)空间利用率高。(2)存取某个元素速度快。(3)插入元素和删除元素存在元素移动,速度慢,耗时。(4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现“溢

出”问题,当元素个数远少于预先分配的空间时,空间浪费巨大。2.链式存储结构(1)占用额外的空间以存储指针(浪费空间)。(2)存取某个元素速度慢。(3)插入元素和删除元素速度快。(4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。3.顺序存储占用物理地址连续的一块空间来存储元素,元素之间的关系就是相邻元素

间的关系;链式存储占用的物理地址可连续可不连续,所以要找到某个元素的后继必

须用指针来指示。4.以查找为主采用顺序表,以插入和删除为主采用链表。5.在Python中实现队列的操作(1)顺序队列m=100#队列规模head=tail=0que=[""]*m#建队data=input("Pleaseinputdata:")i=0whiledata!="#":#输入#结束入队操作iftail==m:print("队列已满!")else:que[tail]=datatail+=1data=input("pleaseinputdata:")whilehead<tail:#出队操作print(que[head],end="")head+=1(2)循环队列m=100#队列规模head=tail=0que=[""]*m#建队data=input("Pleaseinputdata:")i=0whiledata!="#":#输入#结束入队操作if(tail+1)%m==head:print("队列已满!")else:que[tail]=datatail=(tail+1)%mdata=input("Pleaseinputdata:")whilehead<tail:#出队操作print(que[head],end="")head=(head+1)%m(3)链队列classQueue():def_init_(self):self.queue=[]defqueue_in(self,data):#data插入队列self.queue=[]defqueue_out(self,data):#取出队首元素iflen(self.queue):returnself.queue.pop()return

"队列已空"6.与队列有关的Python模块Python内建有queue模块,在这个模块内可以使用Queue()建立对象,然后可以使用下列

方法执行queue的操作。fromqueueimportQueueq=queue()foriinrange(3):q.put(i):whilenotq.empty():print(q.get())queue类中定义的方法方法功能描述put()在队尾插入数据get()在队首取出数据qsize()返回队列长度,即队列中的元素个数empty()判断队列是不是空,队列为空返回值为True,否则

为Falsefull()判断队列是不是满,队列为满返回值为True,否则

为False例3

(2023浙江1月选考,9,2分)有1个队列,队首到队尾的元素依次为8,3,2,9,5。约定:T

操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队。则经过TT-

TQTTQ系列操作后,队列中队首到队尾的元素依次为

(

)A.2,9,5B.2,5,8C.5,8,2D.8,3,2

解析

本题主要考查队列的基本操作。TTT后队列变为9,5,8,3,2。Q后变为5,8,3,2。TT后变为3,2,5,8。Q后变为2,5,8。

答案B1.(2023浙江6月选考,11,2分)列表q长度为20,q[0]至q[4]的值依次为'p','r','i','n','t',执行如

下程序段后,输出的最后一个字符为

(

)head,tail=0,5whilehead<tail:ifhead%3==0:print(q[head])else:q[tail]=q[head]即练即清tail+=1head+=lA.tB.nC.iD.r答案

D

2.(2024届A9协作体返校考,10)有如下Python程序段:s="abcxyz"q=[1,2,3]+[0]*10head,tail=0,3res=""foriins:c=chr((ord(i)-ord("a")+q[head])%26+ord("a"))res+=cq[tail]=q[head]head=head+1tail=tail+1print(res)执行该程序段后,输出的结果是

(

)A.bdfyacB.bdfxyzC.abcyacD.yacbdf答案A

考向四栈一、栈的结构与存储栈一般按顺序结构存储,可以用数组实现。由于栈顶元素在数组中的位置会发生改

变,因此使用top变量来记录栈顶元素在数组中的位置。如图所示,栈空时,top=-1;top=0

时,st[top]存储栈底元素“A”;top=1时,st[top]存储栈中第2个元素“B”;top=2时,st

[top]存储栈顶元素“C”。

栈的结构

栈的存储二、栈的创建在Python中,当要存储n个元素的栈时,可以用列表创建一个长度为n的栈。Python代码实现如下:n=4top=-1

st=[""]*n三、入栈、出栈1.入栈操作入栈又叫压栈操作,把数据元素压入栈顶。栈空时,top=-1,每次入栈时,栈顶指针变量

top值依次加1,再给st[top]赋值。字母“A”“B”“C”“D”按序入栈的过程如图所

示。

Python代码实现如下:top=top+1#top=0

st[top]="A"#字母A入栈top=top+1#top=1st[top]="B"#字母B入栈top=top+1#top=2st[top]="C"#字母C入栈top=top+1#top=3st[top]="D"#字母D入栈2.出栈操作出栈时把栈顶元素取出,同时top值减1。当栈中没有元素,即top=-1时,不能进行出栈操

作。

出栈过程3.在Python中,模拟栈操作a=[]#建栈a.append("data1")#入栈a.append("data2")#入栈a.append("data3")#入栈a.append("data4")#入栈print(a.pop())#出栈print(a.pop())#出栈print(a.pop())#出栈print(a.pop())#出栈四、建立stack类并进行栈操作classStack():

def

init

(self):#建栈self.my_stack=[]defpush(self,data):#入栈self.my_stack.append(data)defpop(self):#出栈returnself.my_stack.pop()defsize(self):#栈中元素数returnlen(self.my_stack)defisEmpty(self):#栈空判断returnself.my_stack==[]stack=Stack()a=["data1","data2","data3"]foritemina:#入栈stack.push(item)print("栈中元素个数为:",stack.size())whilenotstack.isEmpty():#出栈print(stack.pop())

例4

(2023浙江1月选考,12,2分)有如下Python程序段:importrandoma=['A','B','#','#','C','D','#']stk=[0]*len(a);top=-1foriinrange(len(a)):op=random.randint(0,1)#随机生成0或1ifop==1anda[i]!='#':top+=1;stk[top]=a[i]a[i]='#'elifop==0andtop!=-1anda[i]=='#':a[i]=stk[top];top-=1执行该程序段后,a的值不可能是

(

)A.['A','B','#','#','C','D','#']B.['#','#','#','#','#','#','#']C.['#','B','#','#','C','D','A']D.['#','#','A','B','C','D','#']

解析

本题主要考查栈相关知识。观察到A选项与原值相同,说明if与elif语句都不执行,即a[i]!='#'时,op==0,反之op==1;B选项均为#,则只运行if不运行elif即可,则op一直为1。观察C选项发现第1次与最后1次a值发生变化,则第1次op==1,最后1次op==0,其

他与A选项相同。D选项,a[0],a[1]的值均为#,表示A,B已经入栈,则出栈顺序为B,A,故D

不可能。

答案D1.(2023浙江6月选考,9,2分)栈s的最大长度为3,初始为空,经过一系列入栈、出栈操作,

若元素入栈的顺序是a,b,c,d,e,f,则可能的出栈序列为

(

)A.f,e,d,c,b,aB.c,b,a,f,e,dC.c,a,b,d,e,fD.c,e,d,b,a,f答案

B

2.(2024届A9协作体返校考,12)有如下Python程序段:tmps=[32,28,26,29]n=len(tmps);top=-1即练即清ans=[0]*nstk=