第一部分信息技術(shù)

專題七數(shù)據(jù)的組織高考

技術(shù)浙江省專用考點一數(shù)組一、數(shù)組的概念與特征1.數(shù)組的概念數(shù)組是由相同類型的變量構(gòu)成的一個序列。數(shù)組使用一個標識符(數(shù)組名)命名,并用

編號(下標或索引)區(qū)分數(shù)組內(nèi)的各個變量。由數(shù)組名和下標組成數(shù)組的各個變量稱

為數(shù)組的分量,也稱為數(shù)組元素。常用的數(shù)組有一維數(shù)組和二維數(shù)組。2.數(shù)組的特性(1)數(shù)組元素的數(shù)據(jù)類型相同。(2)通過數(shù)組名和下標對數(shù)組元素的值進行訪問。(3)存儲空間固定不變。二、數(shù)組的基本操作1.數(shù)組的創(chuàng)建數(shù)組的創(chuàng)建實質(zhì)是在系統(tǒng)內(nèi)存中劃分一塊連續(xù)區(qū)域,用來保存數(shù)組所含的所有數(shù)據(jù)元

素。2.數(shù)組元素的訪問通過數(shù)組名和下標直接訪問數(shù)組元素。例如,a[0]表示一維數(shù)組a中的第一個元素。3.數(shù)組元素的插入與刪除當需要在數(shù)組中某個位置插入一個新的數(shù)據(jù)時,必須先將該位置及其后的所有數(shù)據(jù)向后移動一個位置,在保證順序不變的前提下保存這些數(shù)據(jù),最后再修改該位置上的數(shù)

據(jù)為新數(shù)據(jù),時間效率較低。在刪除數(shù)組元素時,需要將被刪除元素位置后的所有元素前移一個位置,同樣有時間

效率低的問題,而且在刪除比較多的元素后,數(shù)組中存儲的有效數(shù)據(jù)減少,從而造成存

儲空間的浪費。因此,在使用數(shù)組組織存儲數(shù)據(jù)時應(yīng)盡量避免數(shù)組元素的增刪操作?？键c二鏈表一、鏈表的概念與特性1.鏈表的概念鏈表指的是將需要處理的數(shù)據(jù)對象以節(jié)點的形式,通過指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)

構(gòu)。鏈表中的每個節(jié)點一般由“數(shù)據(jù)區(qū)域”和“指針區(qū)域”兩部分構(gòu)成。鏈表可以

根據(jù)每個節(jié)點中指針的數(shù)量分為單向鏈表和雙向鏈表。2.鏈表的特性(1)同一鏈表中每個節(jié)點的結(jié)構(gòu)均相同;(2)每個鏈表必定有一個頭指針,以實現(xiàn)對鏈表的引用和邊界處理;(3)鏈表占用的空間不固定。二、鏈表的基本操作1.鏈表的創(chuàng)建創(chuàng)建鏈表時,首先要根據(jù)問題特點規(guī)劃節(jié)點的數(shù)據(jù)域和指針域,然后根據(jù)規(guī)劃創(chuàng)建一

個空鏈表。2.鏈表節(jié)點的訪問與遍歷鏈表只能通過頭指針進行訪問,其他節(jié)點通過節(jié)點間的指針依次訪問。鏈表中的節(jié)點

通過指針相互鏈接,當需要訪問某個位置的節(jié)點元素時,只能通過頭指針進入鏈表并

通過節(jié)點間的鏈接關(guān)系逐個向下訪問,直到找到指定位置節(jié)點。與數(shù)組相比,其節(jié)點的訪問效率較低。3.鏈表節(jié)點的插入和刪除鏈表節(jié)點的插入指的是根據(jù)新輸入的實際數(shù)據(jù)形成節(jié)點,然后修改新節(jié)點與其前驅(qū)節(jié)

點的指針,將新節(jié)點插入到鏈表的正確位置。鏈表節(jié)點的刪除,則通過將需要刪除節(jié)點的前驅(qū)節(jié)點和其后繼節(jié)點直接相連的方式實

現(xiàn)。三、數(shù)組與鏈表的區(qū)別1.存儲結(jié)構(gòu)數(shù)組使用一塊連續(xù)的內(nèi)存空間來存儲一組數(shù)據(jù),存儲空間固定不變;鏈表不需要一塊連續(xù)的空間,可通過“指針”將零散的空間聯(lián)系起來。2.數(shù)據(jù)的運算數(shù)組通過下標可快速訪問任一位置上的數(shù)據(jù),但插入和刪除數(shù)據(jù)的效率較低;鏈表需

通過節(jié)點間的鏈接關(guān)系依次訪問,但插入和刪除數(shù)據(jù)的效率較高。對于想要快速訪問數(shù)據(jù),又不經(jīng)常插入和刪除元素的情形,一般可選數(shù)組;對于需要經(jīng)

常插入和刪除元素,而對訪問元素時的效率沒有很高要求的情形,一般可選鏈表?？键c三隊列一、隊列的概念隊列是一種先進先出的線性表,允許插入的一端稱為隊尾,允許刪除的一端稱為隊

首。隊列中的數(shù)據(jù)元素稱為隊列元素。在隊列中插入一個元素稱為入隊,從隊列中刪

除一個元素稱為出隊。如下圖所示,元素a1最先入隊,是隊首元素;元素an最后入隊,是隊

尾元素。

1.先進先出、后進后出由隊列的定義可知,隊列具有“先進先出、后進后出”的特點。出隊時,隊首元素a1優(yōu)

先出隊,緊接著是a2,a3,…,an-1,隊尾元素an最后出隊。2.有限序列性隊列是一種特殊的線性表結(jié)構(gòu),元素個數(shù)是有限的。隊列可以是空的,也可以包含多

個元素。隊列中所有元素呈現(xiàn)線性特征,隊首元素只有一個后繼點,隊尾元素只有一

個前驅(qū)點,其他元素既有一個前驅(qū)點,又有一個后繼點。三、隊列的基本操作(一)隊列的存儲二、隊列的特性1.隊列一般按順序結(jié)構(gòu)存儲,可以用數(shù)組來實現(xiàn)。如圖所示,數(shù)組que中存儲了一個隊

列,共有4個元素,隊首元素為a1,隊尾元素為a4。head記錄隊首元素所在的位置,tail記錄

隊尾元素的下一個位置。

2.入隊與出隊的head、tail指針變化(1)入隊

(2)出隊

(3)隊列的鏈式存儲結(jié)構(gòu)設(shè)置隊首指針head記錄鏈表的頭節(jié)點,隊尾指針tail記錄鏈表的隊尾節(jié)點。

空鏈隊列

非空鏈隊列(二)建隊以數(shù)組形式存儲隊列為例,下面的Python程序中,用列表來實現(xiàn)創(chuàng)建隊列。例如,有4個

字母“A”“B”“C”“D”按序入隊、出隊時,可以創(chuàng)建一個隊列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值時,隊

列為空。

考點四棧一、棧的概念棧是一種操作受限的特殊線性表,僅允許在表的一端進行插入或刪除。進行插入或刪

除操作的一端稱為棧頂,位于棧頂位置的元素稱為棧頂元素;相應(yīng)地,將表的另一端稱

為棧底,位于棧底位置的元素為棧底元素。二、棧的特性1.先進后出、后進先出最后入棧的元素最先出棧,最先入棧的元素最后出棧。2.有限序列性同隊列一樣,棧中的元素也是有限的。?？梢允强盏?也可以包含多個元素。棧中元

素呈線性關(guān)系,棧頂元素有一個前驅(qū)點,棧底元素有一個后繼點,其他元素既有一個前

驅(qū)點,又有一個后繼點。三、棧與隊列的區(qū)別項目不同點相同點隊列先進先出,后進后出有限序列性棧先進后出,后進先出考點五樹一、樹與二叉樹1.樹(Tree)可以描述為由n(n≥0)個節(jié)點(Node)構(gòu)成的一個有限集合以及在該集合上定

義的一種節(jié)點關(guān)系。集合中的元素稱為樹的節(jié)點,節(jié)點的度是指該節(jié)點擁有的子樹數(shù)

目,n=0的樹稱為空樹。2.二叉樹的概念二叉樹是一個具有n(n≥0)個節(jié)點的有限集合,它的所有節(jié)點的度都小于或者等于2。

當n=0時,二叉樹是一棵空樹;當n≠0時,則是一棵由根節(jié)點和兩棵互不相交的、分別稱

作這個根節(jié)點的左子樹和右子樹組成的二叉樹。3.二叉樹的性質(zhì)(1)二叉樹的第k層上最多有2k-1(k≥1)個節(jié)點。(2)深度為k的二叉樹最多有2k-1(k≥1)個節(jié)點。(3)在任意一棵二叉樹中,若度為2的節(jié)點數(shù)量為n2,葉子節(jié)點(度為0的節(jié)點)數(shù)為n0,則n0=

n2+1。二、二叉樹的基本操作1.二叉樹的建立(1)數(shù)組實現(xiàn)二叉樹可以用數(shù)組來實現(xiàn)。對于完全二叉樹,從二叉樹的根節(jié)點開始,按從上而下、自左往右的順序?qū)個節(jié)點進行編號,根節(jié)點的編號為0,最后一個節(jié)點的編號為n-1。

然后依次將二叉樹的節(jié)點用一組連續(xù)的數(shù)組元素來表示,節(jié)點編號與數(shù)組的下標一一

對應(yīng)。對于非完全二叉樹,先將它補全為一棵完全二叉樹,補上的節(jié)點及分支用虛線表示,然

后將補全后的完全二叉樹,從它的根節(jié)點開始,按從上而下、自左向右的順序?qū)個節(jié)

點進行編號,根節(jié)點的編號為0,最后一個節(jié)點的編號為n-1。依次把完全二叉樹中原二

叉樹的節(jié)點用一維數(shù)組的各個元素來表示,節(jié)點編號與數(shù)組的下標一一對應(yīng)。

(2)鏈表實現(xiàn)二叉樹也可以采用鏈表來實現(xiàn)。二叉樹的節(jié)點至少需要3個域:一個數(shù)據(jù)域和兩個指

針域。數(shù)據(jù)域用于存放本節(jié)點的數(shù)據(jù)信息,兩個指針域分別指向節(jié)點的左孩子和右孩

子。這兩個指針分別稱為左指針和右指針,這樣得到的鏈表也稱為二叉鏈表。當指針

不指向任何節(jié)點時,指針域用“^”表示。2.二叉樹的遍歷二叉樹的遍歷,是指按照一定的規(guī)則和次序訪問二叉樹中的所有節(jié)點,使得每個節(jié)點

都被訪問一次且僅被訪問一次。二叉樹的遍歷方式有很多,主要有前序遍歷、中序遍

歷和后序遍歷等。三、抽象數(shù)據(jù)類型1.數(shù)據(jù)類型數(shù)據(jù)類型是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。每種

程序設(shè)計語言都提供了一些內(nèi)置數(shù)據(jù)類型,并為每個內(nèi)置類型提供了一批操作。2.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是指一個數(shù)學模型及定義在該模型上的一組操作。程序設(shè)計語言的一

個內(nèi)置類型可以看作是一個抽象數(shù)據(jù)類型。3.抽象數(shù)據(jù)類型的描述(1)形式要求:類型的名稱、操作的名字、參數(shù)的個數(shù)和類型等。(2)功能要求:希望這個操作完成什么樣的計算或產(chǎn)生什么效果等。(3)標準格式:ADT抽象數(shù)據(jù)類型名:Data數(shù)據(jù)元素之間邏輯關(guān)系的定義Operation操作1初始條件操作結(jié)果描述操作2……操作n……endADT考點六大數(shù)據(jù)時代的數(shù)據(jù)的組織一、實時查詢系統(tǒng)中數(shù)據(jù)的組織1.實時查詢系統(tǒng)中數(shù)據(jù)業(yè)務(wù)特點(1)能實現(xiàn)上千個請求的實時響應(yīng);(2)支持后續(xù)數(shù)據(jù)信息的更改。2.實時查詢系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(1)數(shù)組①查找,即在一個有序序列中查找新增元素的插入位置,可以采用二分查找算法,時間

復(fù)雜度為O(log2n)(n表示數(shù)組元素的總個數(shù)),速度比較快。②插入,即在找到可以插入的位置x后,將新元素插入到找到的位置x中,但必須先將位

置x到n之間的所有元素往后移一位,為新元素空出位置,這個時間復(fù)雜度就比較大,為

O(n)。當瞬間有上千名用戶提出請求,同時進行上千個這樣的處理時,時效性較差。(2)鏈表①插入,在一個鏈表中插入一個新元素,時間復(fù)雜度為O(1),大大優(yōu)于采用數(shù)組時O(n)

的線性復(fù)雜度。②查找,鏈表雖然在插入操作時能確保O(1)的時間復(fù)雜度,但在進行查找時(查找新元

素的插入位置),卻需要從鏈表的一端依次遍歷查找,時間復(fù)雜度為O(n)。因此,采用鏈

表來存儲數(shù)據(jù),雖然整體復(fù)雜度有所下降,但O(n)的復(fù)雜度還是達不到現(xiàn)實的需求。(3)基于鏈表的數(shù)據(jù)結(jié)構(gòu)和算法優(yōu)化設(shè)計①減少查找插入位置過程中的比較次數(shù);②借鑒二分查找算法的思想。3.其他數(shù)據(jù)組織與處理方式大部分的內(nèi)存數(shù)據(jù)庫主要從以下幾個方面來提升數(shù)據(jù)的處理性能。減少對磁盤的訪

問;對數(shù)據(jù)進行分級存儲;采用改進后的數(shù)據(jù)結(jié)構(gòu)來組織、存儲數(shù)據(jù)。二、POI數(shù)據(jù)的組織與應(yīng)用1.POI數(shù)據(jù)的概念POI(興趣點)作為可以在電子地圖中查詢到的信息點要素,它描述了空間實體或者區(qū)域的空間位置、名稱地址等信息。衡量POI數(shù)據(jù)價值的指標有空間位置的準確性和

覆蓋率、空間位置的數(shù)量。2.POI數(shù)據(jù)的組織與表示POI數(shù)據(jù)一般以表記錄或點狀數(shù)據(jù)集的形式存在。POI數(shù)據(jù)的組織主要涉及空間索引

問題,空間索引是指依據(jù)空間對象的位置和形狀或者空間對象之間的某種空間關(guān)系,

按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)?？枷蛞粩?shù)組1.數(shù)組的創(chuàng)建(1)在Python中使用列表創(chuàng)建一維數(shù)組。例:學校元旦文藝匯演比賽時,現(xiàn)場有9位評委給各班節(jié)目打分,統(tǒng)計系統(tǒng)需要根據(jù)9位

評委的原始分計算平均分,作為各班表演節(jié)目的最終得分。創(chuàng)建保存評委原始分的一維數(shù)組s的程序如下:程序測試結(jié)果s=[0]*9print(s)[0,0,0,0,0,0,0,0,0](2)在Python中使用列表實現(xiàn)二維數(shù)組有兩種方式:一是直接定義,適合創(chuàng)建規(guī)模較小

的二維數(shù)組。例如:保存棋盤信息的程序(直接定義)測試結(jié)果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]二是間接定義,適合創(chuàng)建規(guī)模較大的二維數(shù)組,例如:保存棋盤信息的程序(間接定義)測試結(jié)果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列表中實現(xiàn)增加、刪除數(shù)組元素的函數(shù)函數(shù)和方法功能實例len(list)統(tǒng)計列表list中元素個數(shù)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協(xié)作體返校考,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程序執(zhí)行后,數(shù)組a中的數(shù)據(jù)可能是

(

)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]

解析

本題主要考查數(shù)組及隨機數(shù)的使用。由代碼可知,隨機生成的數(shù)據(jù),執(zhí)行后面代碼不會改變數(shù)據(jù)也不會移動位置。當i等于0、2、4時,生成的隨機數(shù)為5~10,不會大

于10,所以D中的12錯誤;當i等于1、3、5時,生成的隨機數(shù)要乘2,所以是10~20的偶數(shù),

所以C中15錯誤;從代碼ifa[j]==a[i]:i=i-1可知,數(shù)組a中不可能有相等的元素,所以B錯誤。

答案A1.(2022衢州期末,9)小萌編寫Python程序批量處理“從身份證號碼中提取出生年月

日”,將姓名和身份證號碼存儲在二維數(shù)組sfzh中,例如“周子夏”和“蔡佳杰”兩人

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

23"]]。程序代碼如下:#將姓名和身份證號存儲在二維數(shù)組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)運行程序后,數(shù)組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中創(chuàng)建鏈表item=[]#空鏈表head=-1#表示頭指針指向為空

2.鏈表節(jié)點的插入與刪除(1)單向鏈表中插入新節(jié)點的過程

(2)單向鏈表中刪除某一節(jié)點的過程

例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)#遍歷鏈表,顯示初始狀態(tài)為"A1->B2->C3->D-1->"qt=headpt=data[qt][1]bianli(head)#遍歷鏈表,顯示最終狀態(tài)為"A2->C1->B3->D-1->"執(zhí)行該程序段后,鏈表遍歷結(jié)果由初始狀態(tài)變?yōu)樽罱K狀態(tài),上述程序段中方框處可選

代碼為:①data[data[qt][1]][1]=pt②data[qt][1]=data[pt][1]③data[pt][1]=data[data[pt][1]][1]則方框處代碼的正確順序是

(

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

解析

本程序主要考查的是鏈表的重新鏈接,程序?qū)崿F(xiàn)的效果是A1->B2->C3->D-1->,變?yōu)锳2->C1->B3->D-1->,qt表示前一指針,pt表示后一指針,故'A'要指向'C','B'要指向'D',然后'C'要指向'B'。

答案D1.(2022百校聯(lián)考,9)采用列表模擬單向鏈表,data[p][0]為數(shù)據(jù)區(qū)域,data[p][1]為指針區(qū)

域。在單向鏈表指針為p的節(jié)點之后插入指針為s的節(jié)點,正確的操作是

(

)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屆百校起點調(diào)研考試,12)使用鏈表結(jié)構(gòu)模擬某景區(qū)游玩路線,鏈表a中每一個節(jié)

點包含三個數(shù)據(jù),第1個為景點名稱,第2個為預(yù)計游玩時間(單位:分鐘),第3個為下一個

景點指針。景區(qū)可以從多個景點的大門進入,但只能從"天梯"離開,輸出顯示各大門進

入路線及預(yù)計總時間的代碼如下。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("預(yù)計時間:",s,"分鐘")上述程序劃線處的可選代碼有:①p=head②p=head[i]③s=s+a[p][1]④p=a[p][2]則(1),(2),(3)處代碼依次為

(

)A.①③④B.①④③

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

考向三隊列順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)的比較1.順序存儲結(jié)構(gòu)(1)空間利用率高。(2)存取某個元素速度快。(3)插入元素和刪除元素存在元素移動,速度慢,耗時。(4)有空間限制,當需要存取的元素個數(shù)可能多于順序表的元素個數(shù)時,會出現(xiàn)“溢

出”問題,當元素個數(shù)遠少于預(yù)先分配的空間時,空間浪費巨大。2.鏈式存儲結(jié)構(gòu)(1)占用額外的空間以存儲指針(浪費空間)。(2)存取某個元素速度慢。(3)插入元素和刪除元素速度快。(4)沒有空間限制,存儲元素的個數(shù)無上限,基本只與內(nèi)存空間大小有關(guān)。3.順序存儲占用物理地址連續(xù)的一塊空間來存儲元素,元素之間的關(guān)系就是相鄰元素

間的關(guān)系;鏈式存儲占用的物理地址可連續(xù)可不連續(xù),所以要找到某個元素的后繼必

須用指針來指示。4.以查找為主采用順序表,以插入和刪除為主采用鏈表。5.在Python中實現(xiàn)隊列的操作(1)順序隊列m=100#隊列規(guī)模head=tail=0que=[""]*m#建隊data=input("Pleaseinputdata:")i=0whiledata!="#":#輸入#結(jié)束入隊操作iftail==m:print("隊列已滿!")else:que[tail]=datatail+=1data=input("pleaseinputdata:")whilehead<tail:#出隊操作print(que[head],end="")head+=1(2)循環(huán)隊列m=100#隊列規(guī)模head=tail=0que=[""]*m#建隊data=input("Pleaseinputdata:")i=0whiledata!="#":#輸入#結(jié)束入隊操作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.與隊列有關(guān)的Python模塊Python內(nèi)建有queue模塊,在這個模塊內(nèi)可以使用Queue()建立對象,然后可以使用下列

方法執(zhí)行queue的操作。fromqueueimportQueueq=queue()foriinrange(3):q.put(i):whilenotq.empty():print(q.get())queue類中定義的方法方法功能描述put()在隊尾插入數(shù)據(jù)get()在隊首取出數(shù)據(jù)qsize()返回隊列長度,即隊列中的元素個數(shù)empty()判斷隊列是不是空,隊列為空返回值為True,否則

為Falsefull()判斷隊列是不是滿,隊列為滿返回值為True,否則

為False例3

(2023浙江1月選考,9,2分)有1個隊列,隊首到隊尾的元素依次為8,3,2,9,5。約定:T

操作是指隊列中1個元素出隊后再入隊,Q操作是指隊列中1個元素出隊。則經(jīng)過TT-

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

(

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

解析

本題主要考查隊列的基本操作。TTT后隊列變?yōu)?,5,8,3,2。Q后變?yōu)?,8,3,2。TT后變?yōu)?,2,5,8。Q后變?yōu)?,5,8。

答案B1.(2023浙江6月選考,11,2分)列表q長度為20,q[0]至q[4]的值依次為'p','r','i','n','t',執(zhí)行如

下程序段后,輸出的最后一個字符為

(

)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協(xié)作體返?？?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)執(zhí)行該程序段后,輸出的結(jié)果是

(

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

考向四棧一、棧的結(jié)構(gòu)與存儲棧一般按順序結(jié)構(gòu)存儲,可以用數(shù)組實現(xiàn)。由于棧頂元素在數(shù)組中的位置會發(fā)生改

變,因此使用top變量來記錄棧頂元素在數(shù)組中的位置。如圖所示,?？諘r,top=-1;top=0

時,st[top]存儲棧底元素“A”;top=1時,st[top]存儲棧中第2個元素“B”;top=2時,st

[top]存儲棧頂元素“C”。

棧的結(jié)構(gòu)

棧的存儲二、棧的創(chuàng)建在Python中,當要存儲n個元素的棧時,可以用列表創(chuàng)建一個長度為n的棧。Python代碼實現(xiàn)如下:n=4top=-1

st=[""]*n三、入棧、出棧1.入棧操作入棧又叫壓棧操作,把數(shù)據(jù)元素壓入棧頂。棧空時,top=-1,每次入棧時,棧頂指針變量

top值依次加1,再給st[top]賦值。字母“A”“B”“C”“D”按序入棧的過程如圖所

示。

Python代碼實現(xiàn)如下: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):#棧中元素數(shù)returnlen(self.my_stack)defisEmpty(self):#?？张袛鄏eturnself.my_stack==[]stack=Stack()a=["data1","data2","data3"]foritemina:#入棧stack.push(item)print("棧中元素個數(shù)為:",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執(zhí)行該程序段后,a的值不可能是

(

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

解析

本題主要考查棧相關(guān)知識。觀察到A選項與原值相同,說明if與elif語句都不執(zhí)行,即a[i]!='#'時,op==0,反之op==1;B選項均為#,則只運行if不運行elif即可,則op一直為1。觀察C選項發(fā)現(xiàn)第1次與最后1次a值發(fā)生變化,則第1次op==1,最后1次op==0,其

他與A選項相同。D選項,a[0],a[1]的值均為#,表示A,B已經(jīng)入棧,則出棧順序為B,A,故D

不可能。

答案D1.(2023浙江6月選考,9,2分)棧s的最大長度為3,初始為空,經(jīng)過一系列入棧、出棧操作,

若元素入棧的順序是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協(xié)作體返?？?12)有如下Python程序段:tmps=[32,28,26,29]n=len(tmps);top=-1即練即清ans=[0]*nstk=