資源簡介

(共41張PPT)
課時3　抽象數(shù)據(jù)類型
第四章　樹
1.理解抽象數(shù)據(jù)的概念，理解并體會抽象數(shù)據(jù)類型對數(shù)據(jù)處理的重要性。2.能用抽象數(shù)據(jù)類型表示棧、隊列、二叉樹，并定義其數(shù)據(jù)及基本操作，并嘗試編寫程序?qū)崿F(xiàn)，進(jìn)而提高學(xué)生的知識遷移能力。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.數(shù)據(jù)類型與抽象數(shù)據(jù)類型
(1)數(shù)據(jù)類型是指一組____________的值的集合及定義在此集合上的一些______的總稱。
(2)抽象數(shù)據(jù)類型是指一個____________及定義在該模型上的一組操作，即一個____________、數(shù)據(jù)對象中______________________________以及對_____________________。
性質(zhì)相同
操作
數(shù)學(xué)模型　
數(shù)據(jù)對象
各數(shù)據(jù)元素之間的關(guān)系
數(shù)據(jù)元素的操作
抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。
抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)是兩個不同的概念，不能混為一談。具體為：
①數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
②抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型及定義在該模型上的一組操作，“抽象數(shù)據(jù)類型”本質(zhì)是“數(shù)據(jù)類型”。我們可以用“抽象數(shù)據(jù)類型”來實(shí)現(xiàn)“數(shù)據(jù)結(jié)構(gòu)”。
2.抽象數(shù)據(jù)類型(ADT)的描述
(1)定義一個抽象數(shù)據(jù)類型(ADT)，需要清晰地表述出________________________(如操作的名字、參數(shù)的個數(shù)和類型等)和____________(這個操作完成什么樣的計算或產(chǎn)生什么效果等)。
(2)描述抽象數(shù)據(jù)類型的標(biāo)準(zhǔn)格式：
ADT 抽象數(shù)據(jù)類型名：
Data
數(shù)據(jù)元素之間邏輯關(guān)系的定義
Operation
各方面的形式要求
功能要求
操作1
　　　　 　初始條件
　　　　 　操作結(jié)果描述
操作2
　　　　　 ……
操作n
　　　　　 ……
end ADT
(3)線性表抽象數(shù)據(jù)類型
ADT List：
List(self)　　　#創(chuàng)建一個新表
is_empty(self)　#判斷self是否為一個空表
len(self)　　　　#返回列表的長度
prepend(self，elem)　 #在表頭插入元素elem
append(self，elem)　#在表尾插入元素elem
insert(self，elem，i)　#在表的第i個位置入元素elem
del_first(self)　#刪除第一個元素
del_last(self)　　　 #刪除最后一個元素
del (self，i)　　　　 #刪除第i個元素
search(self，elem)　#查找元素elem在表中第一次出現(xiàn)的位置
forall(self，op)　#對表中的每個元素執(zhí)行op操作
3.抽象數(shù)據(jù)類型的作用
(1)_________________________________，便于程序正確性的證明和復(fù)雜性的分析；
(2)因?yàn)槠鋉________的特點(diǎn)，在程序設(shè)計中容易糾正，具有很好的____________；
(3)由于抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，_____________________；
(4)_________算法與程序設(shè)計的復(fù)雜度，有助于在開發(fā)過程中少出差錯，保證編寫的程序有較高的_________，有益于算法的______，提高程序的____________。
程序結(jié)構(gòu)清晰、層次分明
模塊化
可維護(hù)性
便于移植和重用
降低了
可靠性
優(yōu)化
運(yùn)行效率
例題精析
2
例1 抽象數(shù)據(jù)類型的三個組成部分分別為數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和(　　)
B
解析　本題主要考查的是抽象數(shù)據(jù)類型的組成。抽象數(shù)據(jù)類型的三個組成部分分別為數(shù)據(jù)對象、數(shù)據(jù)對象中各數(shù)據(jù)元素之間的關(guān)系和對數(shù)據(jù)元素的操作，因此答案為B。
A.數(shù)據(jù)類型 B.基本操作 C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)元素
變式訓(xùn)練　下列有關(guān)抽象數(shù)據(jù)類型的說法，正確的是(　　)
解析　本題主要考查的是抽象數(shù)據(jù)類型的定義。抽象數(shù)據(jù)類型是由一種數(shù)據(jù)結(jié)構(gòu)和在其上的一組操作(運(yùn)算)所組成，因此A選項(xiàng)錯誤；抽象數(shù)據(jù)類型和其在計算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，因此B選項(xiàng)錯誤；定義一個抽象數(shù)據(jù)類型，不僅需要清晰表述出各方面的形式要求，還需要清晰表達(dá)出功能要求，因此D選項(xiàng)錯誤；Python的整型、字符串類型等也是一種抽象數(shù)據(jù)類型，因此答案為C。
C
A.抽象數(shù)據(jù)類型其實(shí)就是數(shù)據(jù)結(jié)構(gòu)
B.抽象數(shù)據(jù)類型和其在計算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)有關(guān)
C.Python的整型其實(shí)也是一種抽象數(shù)據(jù)類型
D.定義一個抽象數(shù)據(jù)類型，只需要清晰表述出各方面的功能要求即可
例2 創(chuàng)建一個簡單的ADT，如下所示：
class odd()：
def _ _init _ _(self，data)：
″″″初始化屬性data″″″
self.data＝data
def pd(self)：
if self.data % 2＝＝0：
　　　　print(self.data，″是偶數(shù)″)
else：
　　　　print(self.data，″是奇數(shù)″)
# 創(chuàng)建實(shí)例：
my_pro＝odd(12)
my_pro.pd()
解析　本題主要考查的是抽象數(shù)據(jù)類型(ADT)的組成。def pd(self)的功能是定義pd操作，而不是函數(shù)。因此，不正確的是B。
B
A.創(chuàng)建的類名稱為odd
B.def pd(self)的功能是定義pd函數(shù)
C.程序代碼執(zhí)行后的結(jié)果為“12是偶數(shù)”
D.my_pro為odd類的一個對象
變式訓(xùn)練　用抽象數(shù)據(jù)類型實(shí)現(xiàn)棧操作的代碼如下：
class Stack()：
def _ _init_ _(self)：
self.my_stack＝[]
def my_push(self)：　#入棧操作
　　________________________
def my_pop(self)：　 #出棧操作
return self.my_stack.pop()
def size(self)：　　 #測試棧長度
return len(self.my_stack)
def isEmpty(self)：　 #判斷棧是否為空
return self.my_stack＝＝[]
請在程序劃線處填入合適的語句。
答案　self.my_stack.append(data)
解析　本題主要考查的是用抽象數(shù)據(jù)類型表示棧操作。棧的特點(diǎn)是先進(jìn)后出，元素入棧時是從棧的首部插入，因此代碼為self.my_stack.append(data)。
隨堂檢測
3
1.下列關(guān)于抽象對象的作用的說法中，正確的是(　　)
A
解析　本題主要考查的是抽象對象的作用。使用抽象數(shù)據(jù)類型編寫出來的程序結(jié)構(gòu)清晰、層次分明，便于程序正確性的證明和復(fù)雜度的分析；抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，便于移植和重用；使用抽象數(shù)據(jù)類型編寫程序，降低了算法和程序設(shè)計的復(fù)雜度，有助于在開發(fā)過程中少出差錯，保證編寫程序有較高的可靠性，同時允許數(shù)據(jù)結(jié)構(gòu)的自由選擇，給了算法的優(yōu)化空間，提高了程序運(yùn)行的效率。因此，答案為A。
A.使用抽象數(shù)據(jù)類型編寫出來的程序結(jié)構(gòu)清晰、層次分明
B.使用抽象數(shù)據(jù)類型編寫出來的程序，其正確性得不到保障
C.使用抽象數(shù)據(jù)類型編寫出來的程序，移植性較差
D.使用抽象數(shù)據(jù)類型編寫程序，算法復(fù)雜度較高，一般情況不建議使用
A.len() B.append() C.del D.values()
B
解析　選項(xiàng)B的append()是列表數(shù)據(jù)類型在尾部添加數(shù)據(jù)項(xiàng)的方法，字典中添加新的鍵值對的方法為dic[新鍵]＝值。
3.下列是一個判斷三位數(shù)整數(shù)是否為水仙花數(shù)的簡單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，″是水仙花數(shù)″)
else：
　　　　print(self.data，″不是水仙花數(shù)″)
C
# 創(chuàng)建實(shí)例：
my_num＝flower(153)
my_num.pdflowernum()
下列有關(guān)該抽象數(shù)據(jù)類型(ADT)實(shí)例的說法中，正確的是(　　)
A.創(chuàng)建的抽象數(shù)據(jù)類型名稱為pdflowernum
B.程序代碼執(zhí)行后的結(jié)果為“153不是水仙花數(shù)”
C.def pdflowernum(self)的功能是定義flower類的一個操作
D.flower為my_num類的一個對象
解析　本題主要考查的是定義一個抽象數(shù)據(jù)類型(ADT)的。創(chuàng)建的抽象數(shù)據(jù)類型名稱為flower，因此A選項(xiàng)錯誤；程序代碼執(zhí)行后的結(jié)果為“153是水仙花數(shù)”，因此B選項(xiàng)錯誤；my_num為flower類的一個對象，因此D選項(xiàng)錯誤。def pdflowernum(self)的功能是定義flower類的一個操作，因此，正確的是C。
4.下列是一個加減乘除四則運(yùn)算的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)
if self.ch＝＝″/″：
　　　 　if self.data2 ?。?：
　　　　　　___________________
　　　　　　print(self.data1，″/″，self.data2，″＝″，c)
　　　　else：
　　　　　　print(″分母不能為0″)
# 創(chuàng)建實(shí)例：
my_operator＝operator(2，6，″*″)
my_operator.cal()
(1)程序運(yùn)行后，輸出的結(jié)果是__________________________________________。
(2)請在程序劃線處填入合適的語句。
答案　(1)2*6＝12　(2)①self.ch＝ch
②c＝self.data1/self.data2
解析　本題主要考查的是定義一個抽象數(shù)據(jù)類型。(1)根據(jù)語句my_operator＝operator(2，6，″*″)可知，數(shù)據(jù)data1和data2進(jìn)行乘法運(yùn)算，因此輸出結(jié)果為2*6＝12。(2)劃線①處的語句功能是初始化屬性ch，因此填入的代碼為self.ch＝ch。②處代碼表示data1和data2進(jìn)行除法運(yùn)算，結(jié)果存儲在變量c中，因此，②處應(yīng)填入的代碼為c＝self.data1/self.data2。
4
鞏固與提升
基礎(chǔ)鞏固
能力提升
A.抽象數(shù)據(jù)是指一個數(shù)學(xué)模型及定義在該模型上的一組操作
B.Python的一個內(nèi)置類型不是一個抽象數(shù)據(jù)類型
C.抽象數(shù)據(jù)類型是一種思想，也是一種技術(shù)
D.定義一個抽象數(shù)據(jù)類型(ADT)，目的是要定義一類計算對象，使它們具有某些特定的功能
B
解析　Python的一個內(nèi)置類型也可以看作是一個抽象數(shù)據(jù)類型，因此不正確的是B。
2.下列選項(xiàng)中屬于Python抽象數(shù)據(jù)類型(ADT)優(yōu)點(diǎn)的是(　　)
C
A.使用抽象數(shù)據(jù)類型編寫的程序結(jié)構(gòu)不清晰、層次不分明
B.抽象數(shù)據(jù)類型的模塊化特點(diǎn)，在程序設(shè)計中容易糾正，但不易維護(hù)
C.由于抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，便于移植和重用
D.使用抽象數(shù)據(jù)類型編寫程序，增加了算法復(fù)雜度，降低了程序運(yùn)行的效率
解析　使用抽象數(shù)據(jù)類型編寫的程序結(jié)構(gòu)清晰、層次分明，因此A選項(xiàng)錯誤；抽象數(shù)據(jù)類型的模塊化特點(diǎn)，在程序設(shè)計中容易糾正，具有良好的維護(hù)性，因此B選項(xiàng)錯誤；使用抽象數(shù)據(jù)類型編寫程序時，因?yàn)樗惴ㄔO(shè)計與數(shù)據(jù)結(jié)構(gòu)設(shè)計的隔開，降低了算法復(fù)雜度，同時允許數(shù)據(jù)結(jié)構(gòu)的自由選擇，給了算法的優(yōu)化空間，提高了程序運(yùn)行的效率，因此D選項(xiàng)錯誤；由于抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，便于移植和重用，是正確的。因此，答案為C。
3.下列是一個簡單的ADT：
class Sstring：
def _ _init _ _(self，str1)：
self.ss＝str1
def substr(self，a，b)：
return self.ss[a－1：b]
def concat(self，str2)：
return self.ss＋str2
sstr1＝Sstring(″Python″)　　　　
print(sstr1.substr(2，4))
print(sstr1.concat(″ is so easy！″))
D
解析　執(zhí)行代碼“print(sstr1.concat(″is so easy！″))”，輸出結(jié)果為“Python is so easy！”，因此，答案為D。
A.Sstring為抽象數(shù)據(jù)類型名
B.sstr1為Sstring類的一個對象
C.執(zhí)行代碼“print(sstr1.substr(2，4))”，輸出結(jié)果為“yth”
D.執(zhí)行代碼“print(sstr1.concat(″is so easy！″))”，輸出結(jié)果為“yth is so easy！”
4.下列是一個簡單的ADT：
class xcal：
def _ _init _ _(self，numx，numy)：
self.numx＝numx
self.numy＝numy
def xadd(self，another)：
numx＝self.numx*another.numx
numy＝self.numy*another.numy
return xcal(numx，numy)
def print(self)：
print(str(self.numx)＋'/'＋str(self.numy))
x＝xcal(2，3)
y＝x.xadd(xcal(4，5))
D
y.print()程序運(yùn)行后，輸出的結(jié)果為(　　)
A.6/20 B.15/8 C.10/12 D.8/15
解析　根據(jù)xadd操作中的語句可知，程序運(yùn)行后的結(jié)果為8/15，因此，答案為D。
5.用抽象數(shù)據(jù)類型實(shí)現(xiàn)隊列操作的代碼如下，請回答下列問題：
class Queue：
def _ _init _ _(self)：
self.queue＝[]
def isEmpty(self)：
return self.queue＝＝[]
def enqueue(self，data)：　#入隊操作
　　　　①________________
def dequeue(self)：　 #出隊操作
if len(self.queue)：
　　　__②________________
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)程序運(yùn)行后，輸出的結(jié)果是__________________________________________。
(2)請在程序劃線處填入合適的代碼。
答案　(1)8 9 10
(2)①self.queue.insert(0，data) ②return self.queue.pop()
解析　本題主要考查的是用抽象數(shù)據(jù)類型表示隊列操作。隊列的特點(diǎn)是先進(jìn)先出，元素入隊時是從隊列的首部插入，因此代碼為self.queue.insert(0，data)；②處代碼為出隊操作，通過pop()方法實(shí)現(xiàn)，將元素從隊尾取出，因此代碼為return self.queue.pop()。
6.創(chuàng)建一個ADT，實(shí)現(xiàn)如下功能：輸入一個18位的身份證號碼，輸出該身份證的人的性別。
判斷方法：根據(jù)身份證號的第17位上的數(shù)字來判斷，若是奇數(shù)，則表示是位男士；若是偶數(shù)，則表示是位女士。
程序運(yùn)行示例如圖所示：
請輸入身份證號：330425198202261156
身份證號為：330425198202261156是位男士。
實(shí)現(xiàn)上述功能的代碼如下，請回答下列問題：
class sexpd：
def _ _init _ _(self，sfzcode)：
　　　self.code＝sfzcode
def isxb(self)：
　　xbcode＝int(self.code[16])



sfzcode＝input(″請輸入身份證號：″)
sfz1＝sexpd(sfzcode)
sfz1.isxb()
(1)程序運(yùn)行時，若輸入的18位身份證號為“330425198002251269”，則輸出結(jié)果為____________________________。
(2)完善isxb(self)操作中的程序代碼。
答案　(1)身份證號為：330425198002251269 是位女士
(2)isxb(self)操作中的程序代碼如下：
if xbcode % 2＝＝1：
print(″身份證號為：″，self.code，″是位男士?！?
else：
print(″身份證號為：″，self.code，″是位女士。″)
解析　本題主要考查的是ADT的實(shí)際應(yīng)用。(1)身份證號330425198002251269的第17位上的數(shù)字是6，是偶數(shù)，因此該身份證號的人的性別是位女士，參考輸出示例可知，輸出結(jié)果為“身份證號為：330425198002251269 是位女士?！薄?2)isxb(self)操作中的代碼的功能是：根據(jù)身份證號的第17位上(索引位置為16)的數(shù)字的奇偶性來判斷性別，因此使用if語句來實(shí)現(xiàn)，方法不唯一，只要輸出結(jié)果正確即可。課時3　抽象數(shù)據(jù)類型
課時目標(biāo)
1.理解抽象數(shù)據(jù)的概念，理解并體會抽象數(shù)據(jù)類型對數(shù)據(jù)處理的重要性。2.能用抽象數(shù)據(jù)類型表示棧、隊列、二叉樹，并定義其數(shù)據(jù)及基本操作，并嘗試編寫程序?qū)崿F(xiàn)，進(jìn)而提高學(xué)生的知識遷移能力。
1.數(shù)據(jù)類型與抽象數(shù)據(jù)類型
(1)數(shù)據(jù)類型是指一組____________的值的集合及定義在此集合上的一些________的總稱。
(2)抽象數(shù)據(jù)類型是指一個________________及定義在該模型上的一組操作，即一個____________、數(shù)據(jù)對象中______________以及對________________。
抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。
抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)是兩個不同的概念，不能混為一談。具體為：
①數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
②抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型及定義在該模型上的一組操作，“抽象數(shù)據(jù)類型”本質(zhì)是“數(shù)據(jù)類型”。我們可以用“抽象數(shù)據(jù)類型”來實(shí)現(xiàn)“數(shù)據(jù)結(jié)構(gòu)”。
2.抽象數(shù)據(jù)類型(ADT)的描述
(1)定義一個抽象數(shù)據(jù)類型(ADT)，需要清晰地表述出____________________(如操作的名字、參數(shù)的個數(shù)和類型等)和____________(這個操作完成什么樣的計算或產(chǎn)生什么效果等)。
(2)描述抽象數(shù)據(jù)類型的標(biāo)準(zhǔn)格式：
ADT 抽象數(shù)據(jù)類型名：
Data
數(shù)據(jù)元素之間邏輯關(guān)系的定義
Operation
操作1
　　　　 　初始條件
　　　　 　操作結(jié)果描述
操作2
　　　　　 ……
操作n
　　　　　 ……
end ADT
(3)線性表抽象數(shù)據(jù)類型
ADT List：
List(self)　　　#創(chuàng)建一個新表
is_empty(self)　#判斷self是否為一個空表
len(self)　　　　#返回列表的長度
prepend(self，elem)　 #在表頭插入元素elem
append(self，elem)　#在表尾插入元素elem
insert(self，elem，i)　#在表的第i個位置入元素elem
del_first(self)　#刪除第一個元素
del_last(self)　　　 #刪除最后一個元素
del (self，i)　　　　 #刪除第i個元素
search(self，elem)　#查找元素elem在表中第一次出現(xiàn)的位置
forall(self，op)　#對表中的每個元素執(zhí)行op操作
3.抽象數(shù)據(jù)類型的作用
(1)________________________，便于程序正確性的證明和復(fù)雜性的分析；
(2)因?yàn)槠鋉_______的特點(diǎn)，在程序設(shè)計中容易糾正，具有很好的________；
(3)由于抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，__________________；
(4)________算法與程序設(shè)計的復(fù)雜度，有助于在開發(fā)過程中少出差錯，保證編寫的程序有較高的________，有益于算法的________，提高程序的____________。
例1 抽象數(shù)據(jù)類型的三個組成部分分別為數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和(　　)
A.數(shù)據(jù)類型 B.基本操作
C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)元素
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓(xùn)練　下列有關(guān)抽象數(shù)據(jù)類型的說法，正確的是(　　)
A.抽象數(shù)據(jù)類型其實(shí)就是數(shù)據(jù)結(jié)構(gòu)
B.抽象數(shù)據(jù)類型和其在計算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)有關(guān)
C.Python的整型其實(shí)也是一種抽象數(shù)據(jù)類型
D.定義一個抽象數(shù)據(jù)類型，只需要清晰表述出各方面的功能要求即可
例2 創(chuàng)建一個簡單的ADT，如下所示：
class odd()：
def _ _init _ _(self，data)：
″″″初始化屬性data″″″
self.data＝data
def pd(self)：
if self.data % 2＝＝0：
　　　　print(self.data，″是偶數(shù)″)
else：
　　　　print(self.data，″是奇數(shù)″)
# 創(chuàng)建實(shí)例：
my_pro＝odd(12)
my_pro.pd()
下列有關(guān)該抽象數(shù)據(jù)類型(ADT)實(shí)例的說法中，不正確的是(　　)
A.創(chuàng)建的類名稱為odd
B.def pd(self)的功能是定義pd函數(shù)
C.程序代碼執(zhí)行后的結(jié)果為“12是偶數(shù)”
D.my_pro為odd類的一個對象
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓(xùn)練　用抽象數(shù)據(jù)類型實(shí)現(xiàn)棧操作的代碼如下：
class Stack()：
def _ _init_ _(self)：
self.my_stack＝[]
def my_push(self)：　#入棧操作
　　________________________
def my_pop(self)：　 #出棧操作
return self.my_stack.pop()
def size(self)：　　 #測試棧長度
return len(self.my_stack)
def isEmpty(self)：　 #判斷棧是否為空
return self.my_stack＝＝[]
請在程序劃線處填入合適的語句。
1.下列關(guān)于抽象對象的作用的說法中，正確的是(　　)
A.使用抽象數(shù)據(jù)類型編寫出來的程序結(jié)構(gòu)清晰、層次分明
B.使用抽象數(shù)據(jù)類型編寫出來的程序，其正確性得不到保障
C.使用抽象數(shù)據(jù)類型編寫出來的程序，移植性較差
D.使用抽象數(shù)據(jù)類型編寫程序，算法復(fù)雜度較高，一般情況不建議使用
2.Python中有字典數(shù)據(jù)類型，以下不屬于該類型內(nèi)建函數(shù)的方法的是(　　)
A.len() B.append() C.del D.values()
3.下列是一個判斷三位數(shù)整數(shù)是否為水仙花數(shù)的簡單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，″是水仙花數(shù)″)
else：
　　　　print(self.data，″不是水仙花數(shù)″)
# 創(chuàng)建實(shí)例：
my_num＝flower(153)
my_num.pdflowernum()
下列有關(guān)該抽象數(shù)據(jù)類型(ADT)實(shí)例的說法中，正確的是(　　)
A.創(chuàng)建的抽象數(shù)據(jù)類型名稱為pdflowernum
B.程序代碼執(zhí)行后的結(jié)果為“153不是水仙花數(shù)”
C.def pdflowernum(self)的功能是定義flower類的一個操作
D.flower為my_num類的一個對象
4.下列是一個加減乘除四則運(yùn)算的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)
if self.ch＝＝″/″：
　　　 　if self.data2 ！＝0：
　　　　　　②________________
　　　　　　print(self.data1，″/″，self.data2，″＝″，c)
　　　　else：
　　　　　　print(″分母不能為0″)
# 創(chuàng)建實(shí)例：
my_operator＝operator(2，6，″*″)
my_operator.cal()
(1)程序運(yùn)行后，輸出的結(jié)果是__________________________________________。
(2)請在程序劃線處填入合適的語句。
課時3　抽象數(shù)據(jù)類型
知識梳理
1.(1)性質(zhì)相同　操作　(2)數(shù)學(xué)模型　數(shù)據(jù)對象　各數(shù)據(jù)元素之間的關(guān)系　數(shù)據(jù)元素的操作
2.(1)各方面的形式要求　功能要求
3.(1)程序結(jié)構(gòu)清晰、層次分明　(2)模塊化　可維護(hù)性　(3)便于移植和重用　(4)降低了　可靠性　優(yōu)化　運(yùn)行效率
例題精析
例1　B　[本題主要考查的是抽象數(shù)據(jù)類型的組成。抽象數(shù)據(jù)類型的三個組成部分分別為數(shù)據(jù)對象、數(shù)據(jù)對象中各數(shù)據(jù)元素之間的關(guān)系和對數(shù)據(jù)元素的操作，因此答案為B。]
變式訓(xùn)練　C　[本題主要考查的是抽象數(shù)據(jù)類型的定義。抽象數(shù)據(jù)類型是由一種數(shù)據(jù)結(jié)構(gòu)和在其上的一組操作(運(yùn)算)所組成，因此A選項(xiàng)錯誤；抽象數(shù)據(jù)類型和其在計算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，因此B選項(xiàng)錯誤；定義一個抽象數(shù)據(jù)類型，不僅需要清晰表述出各方面的形式要求，還需要清晰表達(dá)出功能要求，因此D選項(xiàng)錯誤；Python的整型、字符串類型等也是一種抽象數(shù)據(jù)類型，因此答案為C。]
例2　B　[本題主要考查的是抽象數(shù)據(jù)類型(ADT)的組成。def pd(self)的功能是定義pd操作，而不是函數(shù)。因此，不正確的是B。]
變式訓(xùn)練　self.my_stack.append(data)
解析　本題主要考查的是用抽象數(shù)據(jù)類型表示棧操作。棧的特點(diǎn)是先進(jìn)后出，元素入棧時是從棧的首部插入，因此代碼為self.my_stack.append(data)。
隨堂檢測
1.A　[本題主要考查的是抽象對象的作用。使用抽象數(shù)據(jù)類型編寫出來的程序結(jié)構(gòu)清晰、層次分明，便于程序正確性的證明和復(fù)雜度的分析；抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)都可以封裝起來，便于移植和重用；使用抽象數(shù)據(jù)類型編寫程序，降低了算法和程序設(shè)計的復(fù)雜度，有助于在開發(fā)過程中少出差錯，保證編寫程序有較高的可靠性，同時允許數(shù)據(jù)結(jié)構(gòu)的自由選擇，給了算法的優(yōu)化空間，提高了程序運(yùn)行的效率。因此，答案為A。]
2.B　[選項(xiàng)B的append()是列表數(shù)據(jù)類型在尾部添加數(shù)據(jù)項(xiàng)的方法，字典中添加新的鍵值對的方法為dic[新鍵]＝值。]
3.C　[本題主要考查的是定義一個抽象數(shù)據(jù)類型(ADT)的。創(chuàng)建的抽象數(shù)據(jù)類型名稱為flower，因此A選項(xiàng)錯誤；程序代碼執(zhí)行后的結(jié)果為“153是水仙花數(shù)”，因此B選項(xiàng)錯誤；my_num為flower類的一個對象，因此D選項(xiàng)錯誤。def pdflowernum(self)的功能是定義flower類的一個操作，因此，正確的是C。]
4.(1)2*6＝12　(2)①self.ch＝ch?、赾＝self.data1/self.data2
解析　本題主要考查的是定義一個抽象數(shù)據(jù)類型。(1)根據(jù)語句my_operator＝operator(2，6，″*″)可知，數(shù)據(jù)data1和data2進(jìn)行乘法運(yùn)算，因此輸出結(jié)果為2*6＝12。(2)劃線①處的語句功能是初始化屬性ch，因此填入的代碼為self.ch＝ch。②處代碼表示data1和data2進(jìn)行除法運(yùn)算，結(jié)果存儲在變量c中，因此，②處應(yīng)填入的代碼為c＝self.data1/self.data2。

展開更多......

收起↑