抽象数据类型一轮复习课件-2025-2026学年浙江省高三信息技术选修一

抽象数据类型 1 知识过关 2 1. 数据类型 数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。每种程序设计语言都提供了一些内置数据类型,并为每个内置类型提供了一些操作,如Python语言中的语句: a=5　　　　 #定义了整型变量a并赋值 b=1.3　　 　#定义了浮点数变量b并赋值 c=a*2+b　　　#定义了浮点数变量c并通过表达式赋值 其中,整型、浮点数型等是Python中内置的数据类型,而运算“+”是定义在内置类型上的一种操作。这样的内置数据类型和操作在Python语言中还有很多。 3 2. 抽象数据类型 抽象数据类型(ADT)是一个数学模型及其定义在该模型上的一组操作。程序设计语言中的内置类型可以看作是一种抽象数据类型。如Python语言中的字符串类型就可以看作是一种抽象数据类型。在字符串数据类型中提供了一组可供编程者直接使用的操作。如Python语言中的语句: n=len(s)　#利用len操作获取字符串长度 抽象数据类型主要包括程序设计语言内置的数据类型(如整型)、程序设计语言的内建函数(如len)和自定义的数据类型和操作等。其中自定义的操作包括一个数据对象、数据对象各元素之间的关系及对数据元素的操作。 4 3. 抽象数据类型的描述 定义一个抽象数据类型,需要清晰地表述各方面的形式要求和功能要求。 (1)形式要求:类型的名称、操作的名字、参数的个数和类型。 (2)功能要求:操作所能完成的计算和产生的效果等,主要体现为一组可以对它们使用的操作。 具体格式如下: ADT 抽象数据类型名: Data 　　数据元素之间逻辑关系的定义 Operation 　　操作1 　　　　初始条件 　　　　操作结果描述 　　操作2 　　　　...... 　　操作n 　　　　...... endADT 5 4. 抽象数据类型的作用 抽象数据类型主要体现了程序设计中问题分解、抽象和信息隐藏的特征。主要表现为:能够使编写出来的程序结构清晰、层次分明、具有很好的可维护性、便于移植和重用;降低算法和程序设计的复杂度、编写的程序有较高的可靠性,容易优化算法和提高程序的运行效率。 6 典例精选 7 【例1】 下列关于抽象及抽象数据类型的说法,错. 误. 的是(　　) A. 抽象是指抽取出事物具有的普遍性本质,是对具体事物的一个概括,并隐藏了繁杂的细节 B. 使用抽象数据类型编写的程序具有模块化特点,但丧失了可维护性 C. Python程序设计语言的一个内置类型就可以看作一个抽象数据类型 D. 在Python语言中,字符串数据类型的“+”操作在字符串类中已经有定义 【解析】 Python的字符串类型(str)就是一个抽象数据类型,在字符串对象的内部提供了一组操作可供编程者使用,每个操作都有明确的抽象意义,编程者不必受制于操作内部的具体实现技术,在程序设计时可以直接使用,D符合题意。 D 【例2】 下面给出了字符串抽象数据类型的部分描述信息: ADT String: 　　String(self,sseq)　 #基于字符序列sseq建立一个字符串 　　is_empty(self)　　 #判断本字符串是否空串 　　len(self)　　　　　 #取得字符串的长度 　　char(self,index)　 #取得字符串中位置index的字符 　　substr(self,a,b)　 #取得字符串中[a:b]的子串,左闭右开区间 　　match(self,string) #查找串string在本字符串中第一次出现的位置 　　concat(self,string) #获得本字符串与另一个字符串string的拼接串 　　subst(self,str1,str2) #获得将本字符串里的子串str1替换为str2 现有一个字符串对象s,请回答下列问题: (1)根据字符串抽象数据类型的描述,若要获取字符串[m:n](左闭右闭)区间内容的子串, 正确的调用方式为____________________。若要将字符串中的“app”替换为“see”,正确的调用方式为________________________。  (2)当s=""时,is_empty(s)的返回值为True,则当s="Python 3"时,is_empty(s)的返回值为__________,len(s)的返回值为__________。  (3)当要调用match方法时,需要提供的参数个数为__________个。  【解析】 (3)根据文字说明可知,self是类方法中默认的参数,代表当前对象的地址,当要调用match方法时不必传入相应的参数,故只需要1个参数。 substr(s,m,n+1) subst(s,"app","see") False 8 1 自我检测 11 1. 下列关于抽象对象的作用的说法,正确的是(　　) A. 使用抽象数据类型编写出来的程序结构清晰、层次分明 B. 使用抽象数据类型编写出来的程序,其正确性得不到保障 C. 使用抽象数据类型编写出来的程序,移植性较差 D. 使用抽象数据类型编写程序,算法复杂度较高,一般情况下不建议使用 【解析】 本题考查抽象对象的作用。使用抽象数据类型编写出来的程序结构清晰、层次分明,便于程序正确性的证明和复杂度的分析,A正确,B错误。抽象数据类型的表示和实现都可以封装起来,便于移植和重用,C错误。使用抽象数据类型编写程序,降低了算法和程序设计的复杂度,有助于在开发过程中少出差错,保证编写程序有较高的可靠性,同时允许数据结构的自由选择,给了算法的优化空间,提高了程序运行的效率,D错误。 A 12 2. Python中有字典数据类型,下列不. 属. 于. 该类型内建函数的方法的是(　　) A. len() B. append() C. del D. values() 【解析】 append()是列表数据类型在尾部添加数据项的方法,字典中添加新的键值对的方法为dic[新键]=值,B符合题意。 B 13 3. 下面是一个判断三位数整数是否为水仙花数的简单ADT: class flower(): 　　def _ init _ (self,data): 　　　　#初始化属性data 　　　　self.data=data 　　def pdflowernum(self): 　　　　a=self.data∥100 　　　　b=self.data∥10%10 　　　　c=self.data%10 　　　　if a**3+b**3+c**3==self.data: 　　　　　　print(self.data,"是水仙花数") 　　　　else: 　　　　　　print(self.data,"不是水仙花数") # 创建实例: my_num=flower(153) my_num.pdflowernum() 14 下列关于该抽象数据类型(ADT)实例的说法,正确的是(　　) A. 创建的抽象数据类型名称为pdflowernum B. 程序代码执行后的结果为“153不是水仙花数” C. def pdflowernum(self)的功能是定义flower类的一个操作 D. flower为my_num类的一个对象 【解析】 本题考查定义一个抽象数据类型(ADT)。创建的抽象数据类型名称为flower,A错误。程序代码执行后的结果为“153是水仙花数”,B错误。my_num为flower类的一个对象,D错误。def pdflowernum(self)的功能是定义flower类的一个操作,C正确。 C 4. 下面是一个加减乘除四则运算的ADT,请回答下列问题: class operator(): 　def_init_(self,data1,data2,ch): 　　　self.data1=data1 　　　self.data2=data2 　　　①________________  　def cal(self): 　　　if self.ch=="+": 　　　　　c=self.data1+self.data2 　　　　　print(self.data1,"+",self.data2,"=",c) 　　　if self.ch=="－": 　　　　　c=self.data1－self.data2 　　　　　print(self.data1,"－",self.data2,"=",c) 　　　if self.ch=="*": 　　　　　c=self.data1*self.data2 　　　　　print(self.data1,"*",self.data2,"=",c) self. ch=ch 16 【解析】 本题考查定义一个抽象数据类型。(1)根据语句my_operator=operator(2,6,"*")可知,数据data1和data2进行乘法运算,因此输出结果为2*6=12。(2)①处的语句功能是初始化属性ch,因此填入的代码为self. ch=ch。②处代码表示data1和data2进行除法运算,结果存储在变量c中,因此,②处应填入的代码为c=self. data1/self. data2。 　　　if self.ch=="/": 　　　　　if self.data2 !=0: 　　　　　　②_______________________  　　　　　　print(self.data1,"/",self.data2,"=",c) 　　　　else: 　　　　　　print("分母不能为0") # 创建实例: my_operator=operator(2,6,"*") my_operator.cal() (1)程序运行后,输出的结果是__________。  (2)请在画线处填入合适的代码。 c=self. data1/self. data2 2*6=12 17 必备知识练 18 1. 下列关于抽象数据类型的说法,错. 误. 的是(　　) A. Python的字符串类型就是一个抽象数据类型 B. 抽象数据类型是指一个数学模型及定义在该模型上的一组操作 C. 抽象数据类型还可以是编程者在程序设计时使用的函数 D. 定义一个抽象数据类型,只需清晰地表述出各方面的形式要求即可 【解析】 本题考查对抽象数据类型的理解。定义一个抽象数据类型,需要清晰地表述出各方面的形式要求(如操作的名字、参数的个数和类型等)和功能要求(希望这个操作完成什么样的计算或产生什么效果等)。D符合题意。 D 19 2. 在Python程序设计语言中,有如下语句: a=13 b=10 c=a＋b print(c) 下列说法中,错. 误. 的是(　　) A. 语句“a=13”在给变量a赋值的同时也定义了其数据类型为整型 B. “＋”操作在整型类中已经定义,编程者不必关心计算机如何实现“＋”操作 C. 该编程语言中的其他数据类型的运算操作,都可以抽象出来 D. 语句“b=10”中的“=”操作在程序设计语言中没有定义,需要编程者自己编程实现 【解析】 同“＋”等操作一样,“=”操作在Python程序设计语言中已经定义,编程者不必自己编程实现,D符合题意。 D 20 3. 下面是一个简单的ADT: class jdage(): 　　def _ init_ (self,name,age): 　　　　#初始化属性name和age 　　　　self.name=name 　　　　self.age=age 　　def jd(self): 　　　　if self.age<18: 　　　　　　print(self.name＋"还未成年。") 　　　　else: 　　　　　　print(self.name＋"已成年。") my_stu=jdage(ˈPeterˈ,22) my_stu.jd() 21 下列关于该抽象数据类型实例的说法,错. 误. 的是(　　)  A. 创建的类名称为jdage B. my_stu为jdage类的一个对象 C. 代码执行后的结果为“Peter已成年。” D. def jd(self)的功能是定义jd函数 【解析】 本题考查抽象数据类型(ADT)的组成。def jd(self)的功能是定义jg操作,而不是函数,D符合题意。 D 4. 抽象数据类型的三个组成部分分别为(　　)  A. 数据项、数据元素和数据类型 B. 数据元素、数据类型和数据结构 C. 数据对象、数据关系和基本操作 D. 数据元素、逻辑结构和存储结构 【解析】 本题考查抽象数据类型(ADT)的知识。根据ADT的定义可知,抽象数据类型的三个组成部分分别为数据对象、数据关系和基本操作,C正确。 C 23 5. 下面给出了字符串抽象数据类型的部分描述信息: ADT String: 　　String(self,sseq)#基于字符串序列sseq建立一个字符串 　　is_empty(self)　　#判断字符串是否为空串 　　len(self)　　#取得字符串的长度 　　char(self,index)#取得字符串中位置在index的字符 　　substr(self,a,b)#取得字符串[a:b]的子串,左闭右开区间 　　…… 24 现有一字符串对象s,请回答下列问题: (1)根据字符串抽象数据类型的描述,若要获取字符串[x:y](左闭右闭)区间内容的子串,正确的调用方式为_________________。  (2)基于字符串序列sseq建立一个字符串的操作String(s,sseq),可以理解为对字符串s的初始化操作,初始值为__________。  (3)当s="" 时,is_empty(s)的返回值为True,则当s= "abc123"时,is_empty(s)的返回值为__________,len(s)的返回值为__________。  (4)当要调用char方法时,需要提供的参数个数为__________。  substr(s,x,y＋1) sseq False 6 2 【解析】 (1)根据ADT描述,从字符串中获取子串的操作为substr,需要三个参数,第一个为字符串本身s,第二、三个参数分别为子串的开始位置和结束位置的下一个位置。(2)由于操作String(s,sseq)的作用是基于字符串序列sseq建立一个字符串s,所以s的初值为sseq。 (3)操作is_empty(s)的作用是判断字符串是否为空,当字符串为空时返回True,非空时返回False;操作len(s)的作用是返回字符串s的长度,所以len(s)的结果为6。(4)根据ADT描述,操作char(self,index)调用时需要两个参数,第一个参数为字符串本身,第二个参数为位置。 关键能力练 27 6. 用抽象数据类型实现队列操作的代码如下,请回答下列问题: class Queue: def _ init _ (self): 　　self.queue=[] def isEmpty(self): 　　return self.queue==[] def enqueue(self,data):　#入队操作 　　①______________________________  def dequeue(self):　#出队操作 　　if len(self.queue): 　　　　②________________________  self. queue. insert(0,data) return self. queue. pop() def size(self):　　#测试队列长度 　　return len(self.queue) q=Queue() q.enqueue(8) q.enqueue(9) q.enqueue(10) while not q.isEmpty(): 　　print(q.dequeue(),end=" ") (1)程序运行后,输出的结果是__________。  (2)请在画线处填入合适的代码。 8 9 10 28 【解析】 本题考查用抽象数据类型表示队列操作。①队列的特点是先进先出,元素入队时是从队列的首部插入,故此处代码为self. queue. insert(0,data)。②此处代码为出队操作,通过pop()方法实现,将元素从队尾取出,故此处代码为return self. queue. pop()。 7. 创建一个ADT,实现如下功能:输入一个18位的公民身份号码,输出拥有该公民身份号码的人的性别。 判断方法:根据公民身份号码的第17位数字来判断,若是奇数,则表示为男士;若是偶数,则表示为女士。 程序运行界面如图所示: 请输入公民身份号码:330425198202261156 公民身份号码为:330425198202261156是位男士 30 实现上述功能的代码如下,请回答下列问题: class sexpd: def_init_(self,sfzcode): 　　self.code=sfzcode def isxb(self): 　　xbcode=int(self.code[16]) sfzcode=input("请输入公民身份号码:") sfz1=sexpd(sfzcode) sfz1.isxb() 31 (1)程序运行时,若输入的18位公民身份号码为“330425198002251269”,则输出结果为___________________________________________。  (2)完善isxb(self)操作中的程序代码。 【答案】 isxb(self)操作中的程序代码如下: if xbcode % 2==1: 　　print("公民身份号码为:",self. code,"是位男士") else: 　　print("公民身份号码为:",self. code,"是位女士") 【解析】 本题考查ADT的实际应用。(1)公民身份号码330425198002251269的第17位上的数字是6,是偶数,因此该公民身份号码的人的性别是位女士,参考输出示例可知,输出结果为“公民身份号码为:330425198002251269 是位女士”。(2)isxb(self)操作中的代码的功能是:根据公民身份号码的第17位上(索引位置为16)的数字的奇偶性来判断性别,因此使用if语句来实现,方法不唯一,只要输出结果正确即可。 身份证号码为:330425198002251269是位女士 32 $