數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)02.-高考信息技術(shù)一輪二輪復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)（浙教版2019）

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)（二）【知識(shí)要點(diǎn)】1.鏈表的概念與特性鏈表的概念：鏈表指的是將需要處理的數(shù)據(jù)對(duì)象以節(jié)點(diǎn)的形式，通過(guò)指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)。2.表頭:每個(gè)鏈表?yè)碛幸粋€(gè)表頭——head(也稱頭指針),有兩個(gè)作用:(1)鏈表的入口,只有通過(guò)頭指針才能進(jìn)入鏈表。(2)為循環(huán)鏈表設(shè)立邊界,便于數(shù)據(jù)處理時(shí)的邊界判斷和處理。3.節(jié)點(diǎn)：鏈表中的每個(gè)節(jié)點(diǎn)一般由“數(shù)據(jù)區(qū)域”和“指針區(qū)域”兩部分構(gòu)成。數(shù)據(jù)區(qū)域用于保存實(shí)際需要處理的數(shù)據(jù)元素，指針區(qū)域用來(lái)保存該節(jié)點(diǎn)相鄰節(jié)點(diǎn)的存儲(chǔ)地址。某個(gè)節(jié)點(diǎn)前面的相鄰節(jié)點(diǎn)稱為該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，后面的相鄰節(jié)點(diǎn)稱為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。4.鏈表的分類。(1)單向鏈表:只有一個(gè)指針區(qū)域,指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。雙向鏈表:有兩個(gè)指針區(qū)域,一個(gè)指向該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),一個(gè)指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。循環(huán)鏈表:根據(jù)需要把鏈表第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)使用指針鏈接,就形成了循環(huán)鏈表。5.鏈表的特性①同一個(gè)鏈表中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)均相同。(1)每個(gè)節(jié)點(diǎn)的數(shù)據(jù)區(qū)域中的數(shù)據(jù)類型是相同的。(2)每個(gè)節(jié)點(diǎn)指針區(qū)域中的指針數(shù)量和功能相同的。②每個(gè)鏈表必定有一個(gè)頭指針,以實(shí)現(xiàn)對(duì)鏈表的引用和邊界處理。(1)引用鏈表時(shí)使用頭指針head進(jìn)入鏈表。(2)訪問(wèn)鏈表中某一個(gè)節(jié)點(diǎn)只能從頭指針開(kāi)始,通過(guò)指針鏈接依次訪問(wèn),不能通過(guò)下標(biāo)直接引用。(3)對(duì)于循環(huán)鏈表,一輪訪問(wèn)的開(kāi)始和結(jié)束都可以借助頭指針指向位置進(jìn)行判斷,即邊界處理。③鏈表占用的空間不固定。(1)鏈表的相鄰節(jié)點(diǎn)存儲(chǔ)時(shí)不需要連續(xù)空間,充分利用了內(nèi)存的零散空間,提高了存儲(chǔ)空間利用率。(2)鏈表的存儲(chǔ)空間由節(jié)點(diǎn)數(shù)決定,節(jié)點(diǎn)的增加或減少會(huì)導(dǎo)致鏈表占用的空間不固定。6.鏈表的基本操作（python中沒(méi)有專門的鏈表結(jié)構(gòu),但是列表(list)相當(dāng)靈活,可以用二維列表來(lái)模擬鏈表。為了方便模擬,先做幾個(gè)約定:空鏈表:頭指針head=1,為空鏈表；節(jié)點(diǎn):每個(gè)節(jié)點(diǎn)又是一個(gè)列表,含有二個(gè)元素:[數(shù)據(jù),指針]；尾節(jié)點(diǎn):某個(gè)節(jié)點(diǎn)元素,指針=1,說(shuō)明不存在后繼節(jié)點(diǎn)；索引:每個(gè)節(jié)點(diǎn)在列表的索引位置,模擬節(jié)點(diǎn)在內(nèi)存中的位置。）①鏈表的創(chuàng)建：例：item=[];head=1(1)根據(jù)問(wèn)題特點(diǎn)規(guī)劃節(jié)點(diǎn)的數(shù)據(jù)域和指針域。(2)根據(jù)規(guī)劃創(chuàng)建一個(gè)空鏈表(3)根據(jù)輸入的實(shí)際數(shù)據(jù)形成節(jié)點(diǎn)并逐步插入到已有的鏈表中。②鏈表節(jié)點(diǎn)的訪問(wèn)。例：p=head#頭節(jié)點(diǎn)入口whilep!=1:#節(jié)點(diǎn)不為空 print(item[p][0])#輸出數(shù)據(jù)域 p=item[p][1]#下一個(gè)節(jié)點(diǎn)鏈表只能通過(guò)頭指針(head)進(jìn)行訪問(wèn)。其他節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)間的指針依次訪問(wèn)。若要訪問(wèn)鏈表中第n個(gè)節(jié)點(diǎn),則步驟是:通過(guò)頭指針進(jìn)入鏈表→通過(guò)第一個(gè)節(jié)點(diǎn)的指針訪問(wèn)第二個(gè)節(jié)點(diǎn)→通過(guò)第二個(gè)節(jié)點(diǎn)的指針訪問(wèn)第三個(gè)節(jié)點(diǎn)→……→通過(guò)第n1個(gè)節(jié)點(diǎn)的指針訪問(wèn)第n個(gè)節(jié)點(diǎn)。③鏈表節(jié)點(diǎn)的插入與刪除。(1)鏈表節(jié)點(diǎn)的插入。①鏈表節(jié)點(diǎn)的插入指的是根據(jù)新輸入的實(shí)際數(shù)據(jù)形成節(jié)點(diǎn),然后修改新節(jié)點(diǎn)與其前驅(qū)節(jié)點(diǎn)的指針,將新節(jié)點(diǎn)插入到鏈表的正確位置。②插入舉例（一定要注意語(yǔ)句的先后順序,防止鏈表斷鏈。下面的代碼在p指向節(jié)點(diǎn)后插人一個(gè)新的節(jié)點(diǎn)t）item[t][1]=item[p][1]item[p][1]=t情況操作步驟在空/非空單向鏈表中插入第一個(gè)節(jié)點(diǎn)根據(jù)新輸入的實(shí)際數(shù)據(jù)形成新節(jié)點(diǎn)﹔修改新節(jié)點(diǎn)的指針指向與頭指針一致;修改頭指針指向新節(jié)點(diǎn)在非空單向鏈表兩個(gè)節(jié)點(diǎn)中間插入新節(jié)點(diǎn)(或者在末尾插入新節(jié)點(diǎn))根據(jù)新輸入的實(shí)際數(shù)據(jù)形成新節(jié)點(diǎn)﹔修改新節(jié)點(diǎn)的指針指向與前一節(jié)點(diǎn)的指針指向一致;將前一節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)③插入過(guò)程。插入新的節(jié)點(diǎn)，一定要注意語(yǔ)句的先后順序,防止鏈表斷鏈。下面的代碼在p指向節(jié)點(diǎn)后插入一個(gè)新節(jié)點(diǎn)t:item[t][1]=item[p][1]；item[p][1]=t(2)鏈表節(jié)點(diǎn)的刪除①鏈表節(jié)點(diǎn)的刪除，是通過(guò)將需要?jiǎng)h除的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和其后繼節(jié)點(diǎn)直接相連的方式實(shí)現(xiàn)。②刪除舉例。情況操作步驟刪除鏈表第一個(gè)節(jié)點(diǎn)修改頭指針head指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)刪除非空鏈表中間的一個(gè)節(jié)點(diǎn)修改該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)刪除鏈表最后一個(gè)節(jié)點(diǎn)修改該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針指向?yàn)榭闸蹌h除過(guò)程刪除某個(gè)節(jié)點(diǎn),一定要保留它的前驅(qū)節(jié)點(diǎn)的信息。假定變量p指向待刪除節(jié)點(diǎn),變量t指向p的前驅(qū)節(jié)點(diǎn):item[t][1]=item[p][1]根據(jù)鏈表的特點(diǎn)，還可以寫成：item[t][1]=item[item[t][1]][1]。7.Python語(yǔ)言中的類（1）類和實(shí)例①在Python中，對(duì)象用類創(chuàng)建。類是現(xiàn)實(shí)世界或思維世界中的實(shí)體在計(jì)算機(jī)中的反映，用來(lái)描述具有相同的屬性和方法的對(duì)象的集合，它定義了每個(gè)對(duì)象所共有的屬性和方法。②在Python中，類被稱為類對(duì)象，類的實(shí)例被稱為類的對(duì)象。創(chuàng)建一個(gè)新類意味著創(chuàng)建一個(gè)新類型的對(duì)象，從而允許創(chuàng)建一個(gè)該類型的對(duì)象實(shí)例。每個(gè)類的實(shí)例可以擁有保存自己狀態(tài)的屬性和改變自己狀態(tài)的、定義在類中的方法。（2）類的定義class類名：Python使用class關(guān)鍵字來(lái)定義類，其語(yǔ)法格式如下：類體類是抽象的，要使用類定義的功能，就必須進(jìn)行類的實(shí)例化，即創(chuàng)建類的對(duì)象，其語(yǔ)法格式為：對(duì)象名=類名(參數(shù)列表)。（3）類中的屬性①類的數(shù)據(jù)成員是在類中定義的成員變量，用來(lái)存儲(chǔ)描述類的狀態(tài)特征的值，也稱為屬性。屬性可以被該類中定義的方法訪問(wèn)，也可以通過(guò)類的對(duì)象進(jìn)行訪問(wèn)。②通過(guò)“self.變量名”定義的屬性，稱為類的對(duì)象屬性，屬于類實(shí)例化的特定對(duì)象。對(duì)象屬性在類的內(nèi)部通過(guò)“self.變量名”訪問(wèn)，在外部通過(guò)“對(duì)象名.變量名”來(lái)訪問(wèn)。③類屬性屬于整個(gè)類，是在類中所有方法之外定義的變量，所有實(shí)例之間共享一個(gè)副本。類屬性在類的內(nèi)部通過(guò)“類名.類屬性名”或“self.類屬性名”訪問(wèn)，在外部可以通過(guò)類對(duì)象和實(shí)例對(duì)象訪問(wèn)公有的類屬性，但不能訪問(wèn)私有的類屬性。（4）類的對(duì)象方法①類的對(duì)象方法對(duì)類的某個(gè)實(shí)例化對(duì)象進(jìn)行操作，一般以self作為其第一個(gè)形式參數(shù)（也可以使用其他名字）。聲明對(duì)象方法的語(yǔ)法格式如下：def方法名（self，[形參列表]）方法體方法的調(diào)用格式為：對(duì)象名.方法名([實(shí)參列表])。②注意：雖然對(duì)象方法的第一個(gè)參數(shù)是self，但是在調(diào)用時(shí)，用戶不需要也不能給該參數(shù)傳遞值，Python會(huì)自動(dòng)地把對(duì)象傳遞給self參數(shù)。實(shí)現(xiàn)一個(gè)求長(zhǎng)方體體積函數(shù)的類classBox():def__init__(self,length1,width1,height1):self.length=length1self.width=width1self.height=height1defvolume(self):returnself.length*self.width*self.height#以上是定義類my_box=Box(10,10,10)print("長(zhǎng)方體體積是%d"%my_box.volume())鏈表的類實(shí)現(xiàn)：Python中用自定義類方式來(lái)構(gòu)建鏈表,真正體現(xiàn)了鏈表的特性,各種操作更加方便自然。1.構(gòu)建節(jié)點(diǎn)類:classLinkNode():def__init__(self,data,next=None):self.data=dataself.next=next2.構(gòu)建鏈表:a=["Tom","Jerry","Spike","Tyke","Butch,Topsy","Tuffy"]#準(zhǔn)備好節(jié)點(diǎn)數(shù)據(jù)head=LindNode(a[0])p=head#鏈表一般不能改變頭指針變量foriinrange(1,len(a)):p.next=LindNode(a[i])p=p.next【例題剖析】例1下列有個(gè)鏈表的說(shuō)法,不正確的是:()A.鏈表是將處理的對(duì)象以節(jié)點(diǎn)的形式,通過(guò)指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)B.鏈表中的每個(gè)節(jié)點(diǎn)結(jié)構(gòu)均相同,都包含“數(shù)據(jù)區(qū)域”和“指針區(qū)域”C.要訪問(wèn)有n個(gè)節(jié)點(diǎn)的鏈表的最后一個(gè)節(jié)點(diǎn),和第一個(gè)節(jié)點(diǎn)一樣快速D.鏈表的主要形式有單向鏈表,雙向鏈表和循環(huán)鏈表【答案】C【解析】本題目涉及鏈表的基本特性,由于鏈表和數(shù)組不同,的每個(gè)節(jié)點(diǎn)只能通過(guò)節(jié)點(diǎn)間的指針依次訪問(wèn)。頭節(jié)點(diǎn)一次就可以,尾節(jié)點(diǎn)要遍歷完所有節(jié)點(diǎn)。例2.已知學(xué)生類的定義如下:classStudent:def_init_(self,name,age_=18,sex_="女"):=nameself.age=age_self.sex=sex_def__str__(self):returnf"姓名:{},年齡:{self.age},性別:{self.sex}"下列代碼段定義了一個(gè)學(xué)生類的實(shí)例a,并輸出其值:a=Student("張梅","16")print(a)則執(zhí)行該段程序后,程序輸出的值為()A.姓名:張梅,年齡:16,性別:B.姓名:張梅,年齡:18,性別:女C.姓名:張梅,年齡:16,性別:女D.姓名:張梅,年齡:18,性別:女【答案】C【解析】當(dāng)使用print()函數(shù)輸出類的實(shí)例的值時(shí),會(huì)自動(dòng)調(diào)用魔術(shù)方法__str__();Student類的_init_()方法有兩個(gè)默認(rèn)參數(shù)age_=18,sex_="女",定義類的實(shí)例a=Student("張梅","16")時(shí)，sex_取默認(rèn)值。【習(xí)題鞏固】1.下列有關(guān)鏈表的特性的描述,正確的是()A.同一鏈表中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)可以不同B.一旦創(chuàng)建好鏈表后,鏈表的占用空間將固定不變C.鏈表中相鄰節(jié)點(diǎn)存儲(chǔ)時(shí)需要連續(xù)的存儲(chǔ)空間D.每個(gè)鏈表必定有有一個(gè)頭指針,只有通過(guò)頭指針才能進(jìn)入鏈表2.單向鏈表與數(shù)組都屬于線性表，它們都用于存儲(chǔ)具有相同屬性的數(shù)據(jù)，下列說(shuō)法不正確的是()A.對(duì)于需要頻繁插入和刪除元素的情況，使用單向鏈表比使用數(shù)組合適B.查找特定元素，使用單向鏈表比使用數(shù)組方便C.數(shù)組適用于最大元素個(gè)數(shù)容易確定的情況D.存儲(chǔ)相同的元素，使用單向鏈表比使用數(shù)組方便3.已知指針p和q分別指向單鏈表x中的第一個(gè)結(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)，假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)節(jié)點(diǎn)，已知節(jié)點(diǎn)的指針區(qū)域?yàn)閚ext?，F(xiàn)要實(shí)現(xiàn)在s所指結(jié)點(diǎn)之后插入鏈表x，則正確的操作為()A.s.next＝p；q.next＝s.next B.p.next＝s.next；s.next＝qC.s.next＝q；p.next＝s.next D.q.next＝s.next；s.next＝p4.在Python中可以使用二維列表來(lái)模擬單向鏈表,用包含兩個(gè)元素列表來(lái)表示每一個(gè)節(jié)點(diǎn),其中第一個(gè)元素存儲(chǔ)數(shù)據(jù),第二個(gè)元素存儲(chǔ)指針(即后繼節(jié)點(diǎn)在二維列表中的索引)。下列代碼創(chuàng)建了一個(gè)擁有3個(gè)節(jié)點(diǎn)的鏈表a:a=[[7,2],[8,1],[9,1]]head=0則其頭節(jié)點(diǎn)和尾節(jié)點(diǎn)數(shù)據(jù)域的值分別為()A.7和8B.7和9C.8和9D.2和15.下列關(guān)于數(shù)組和鏈表的特征,說(shuō)法正確的是()A.數(shù)組元素的數(shù)據(jù)類型可以相同,也可以不相同B.數(shù)組元素的占用的存儲(chǔ)空間可以連續(xù),也可以不連續(xù)C.鏈表節(jié)點(diǎn)的數(shù)據(jù)類型可以相同,也可以不相同D.鏈表節(jié)點(diǎn)占用的存儲(chǔ)空間可以連續(xù),也可以不連續(xù)6.使用Python的二維列表來(lái)模擬單向鏈表,如下代碼創(chuàng)建了一個(gè)擁有4個(gè)節(jié)點(diǎn)的鏈表a:a=[[7,1],[8,2],[9,1],[6,0]]head=3依次輸出各節(jié)點(diǎn)數(shù)據(jù)域的值,則輸出內(nèi)容為()A.7,8,9,6B.6,7,8,9C.9,8,7,6D.9,6,7,87.在Python中用列表模擬鏈表結(jié)構(gòu)，某程序段如下：a=[["H",1],["a",2],["n",3],["g",4],["2",5],["0",6],["2",7],["2",0]]p,head=3,3;q,c=1,0;m,n=3,0whilen<4:c=c+1ifc==m:n=n+1;c=0ifp==head:head=a[p][1]a[q][1]=headp=a[p][1]else:a[q][1]=a[p][1]p=a[p][1]else:q=pp=a[p][1]#從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表a邏輯順序的所有節(jié)點(diǎn)，并依次輸出節(jié)點(diǎn)的數(shù)據(jù)，代碼略該程序段執(zhí)行后的輸出結(jié)果為()ng02B.g02nC.2an2D.22an8.已知一個(gè)有7個(gè)節(jié)點(diǎn)的單向鏈表，設(shè)有頭指針head和尾指針tail，如右圖所示，下列操作需要遍歷多個(gè)節(jié)點(diǎn)的是（）A.刪除該鏈表中的最后一個(gè)節(jié)點(diǎn)B.刪除該鏈表中的第一個(gè)節(jié)點(diǎn)C.在該鏈表第一個(gè)節(jié)點(diǎn)前插入一個(gè)新節(jié)點(diǎn)D.在該鏈表最后一個(gè)節(jié)點(diǎn)后插入一個(gè)新節(jié)點(diǎn)9.下面程序運(yùn)行后，結(jié)果顯示如下，請(qǐng)問(wèn)，程序中①②處的代碼分別是（）classstudent(object):def__init__(self,x1,x2):①=x1②=x2defscreen(self):print("數(shù)學(xué):",self.mh,"英語(yǔ):",self.eng)subj=student(95,93)subj.screen()A.self.mh、self.engB.mh、engC.self.__mh、self.__engD..__mh、.__eng10.使用Python二維列表來(lái)模擬雙向鏈表,用包含三個(gè)元素的列表來(lái)表示每一個(gè)節(jié)點(diǎn),其中第一個(gè)元素存儲(chǔ)數(shù)據(jù),第二、三個(gè)元素分別存儲(chǔ)前驅(qū)指針prev和后繼指針next。下列代碼創(chuàng)建了一個(gè)擁有4個(gè)節(jié)點(diǎn)的雙鏈表a:a=[[2,2,3],[8,3,1],[0,1,0],[4,0,1]];head=2則其頭節(jié)點(diǎn)和尾節(jié)點(diǎn)數(shù)據(jù)域的值分別為()A.2和4B.0和8C.8和0D.3和111.使用Python二維列表來(lái)模擬雙向鏈表,用包含三個(gè)元素的列表來(lái)表示一個(gè)節(jié)點(diǎn)，其中第一個(gè)元素存儲(chǔ)數(shù)據(jù)，第二、三個(gè)元素分別存儲(chǔ)前驅(qū)節(jié)點(diǎn)的地址和后繼節(jié)點(diǎn)的地址(1表示無(wú)前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn))。下列代碼創(chuàng)建了一個(gè)有4個(gè)節(jié)點(diǎn)的升序（從小到大）雙向鏈表a。a=[[12,2,3],[18,3,1],[10,1,0],[14,0,1]],;head=2現(xiàn)要用append方法插入新數(shù)據(jù)17，并使a依舊保持升序，則插入后的列表a為()A.[[12,2,3],[18,3,1],[10,1,0],[14,0,1],[17,3,1]]B.[[12,2,3],[18,3,1],[10,1,0],[14,0,4],[17,3,1]]C.[[12,2,3],[18,4,1],[10,1,0],[14,0,4],[17,3,1]]D.[[12,2,3],[18,4,1],[10,1,0],[14,0,1],[17,3,1]]12.有如下Python程序段:a=[[3,4,2],[4,2,3],[8,4,1],[6,1,4],[5,3,2]]p=head=2whilea[p][1]!=head:print(a[p][0],end="一>")p=a[p][1]print(a[p][0])則執(zhí)行上述語(yǔ)句后,程序輸出結(jié)果為()A.3>8>5>6>4B.8>5>6>4C.4>8>5>6D.8>4>6>513.下面程序?yàn)閷?shí)現(xiàn)在鏈表中插入一個(gè)大于3的數(shù)后使鏈表data的數(shù)據(jù)依然有序。data=[[14,1],[25,4],[3,0],[48,1],[27,3]]q=2foriinrange(len(data)):ifx>data[q][0]:① q=data[q][1]② )data[k][1]=len(data)1print(data)）C.①q ①q 14.使用列表模擬單鏈表，其存儲(chǔ)結(jié)構(gòu)如第10題圖所示，遍歷該鏈表，將訪問(wèn)到的節(jié)點(diǎn)的數(shù)據(jù)域的字符依次連接，得到字符串‘LOVE’,則指針域中的索引值依次為()A.0123 B.3102 C.2011 D.201115.有如下Python程序段a=[[2,2,3],[8,3,1],[0,—1,0],[4,0,1]]head=2ifa[head][2]!=1:#有后繼節(jié)點(diǎn)a[a[head][2]][1]=—1head=a[head][2]上述代碼段中的二維列表a看作是一個(gè)雙向鏈表,則執(zhí)行上述語(yǔ)句后,雙向鏈表的結(jié)構(gòu)可以表示為（）A.0>2>4>8B.0>2>4C.0>2>8D.2>4>816.某醫(yī)院每天提前發(fā)放100個(gè)預(yù)約號(hào)，考慮到老年人身體原因，預(yù)約病人按照以下規(guī)則進(jìn)行就診:①老年人(年齡>=60歲)比非老年人優(yōu)先就診。②老年人按年齡從大到小的順序就診，年齡相同的按預(yù)約順序就診。③非老年人按預(yù)約順序就診。小王根據(jù)以上規(guī)則編寫了一個(gè)Python程序，程序運(yùn)行時(shí)，實(shí)時(shí)讀取病人預(yù)約數(shù)據(jù)，并根據(jù)以上規(guī)則，實(shí)時(shí)調(diào)整并顯示當(dāng)前診順序，程序運(yùn)行界面如圖所示。（1）如圖所示，若當(dāng)前就診順序?yàn)椤?567401530”，下一位預(yù)約病人年齡為60，則就診順序變?yōu)開(kāi)_____________________。（2）實(shí)現(xiàn)上述功能的代碼如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。#遍歷鏈表data,頭指針為headdefvisit(data,head):cur=headwhilecur!=1:print(data[cur][0],end="")cur=data[cur][1]print("\n")data=[]head=tail=1#head、tail分別表示鏈表頭節(jié)點(diǎn)和尾節(jié)點(diǎn)所在位置foriinrange(100):#為了簡(jiǎn)潔，本程序只輸入、存儲(chǔ)病人的年齡信息age=int(input("請(qǐng)輸入病人的信息："))cur=headifage>=60:whilecur!=1anddata[cur][0]>=age:#查找第一個(gè)數(shù)據(jù)域小于age的節(jié)點(diǎn)pre=cur_____①______ifcur==head:#在頭節(jié)點(diǎn)插入新節(jié)點(diǎn)data.append([age,cur])head=len(data)1else:#在鏈表中間插入新節(jié)點(diǎn)data.append([age,cur])______②_____ifcur==1:#更新尾指針位置tail=len(data)1else:#直接插在鏈表尾節(jié)點(diǎn)后data.append([age,1])ifhead==1:#添加第一個(gè)節(jié)點(diǎn)head=tail=0else:______③_____tail=len(data)1print("當(dāng)前就診順序?yàn)椋?)visit(data,head)17.山頂上有10個(gè)圓形排列的洞，一只狐貍和一只兔子各住一個(gè)洞。狐貍總想吃掉兔子。一天兔子對(duì)狐貍說(shuō)：“你想吃我有一個(gè)條件，先把洞從1～10編上號(hào)，你先到1號(hào)洞找我；第二次隔1個(gè)洞（即3號(hào)洞）找我，第三次隔2個(gè)洞（即6號(hào)洞）找我，以后依此類推，次數(shù)不限。但狐貍從早到晚進(jìn)進(jìn)出出了1000次，仍沒(méi)有找到兔子。請(qǐng)問(wèn)免子可能躲在哪個(gè)洞里？實(shí)現(xiàn)上述功能的Python程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼：hone=[];n=10;m=1000#構(gòu)造一個(gè)循環(huán)鏈表，并給n個(gè)洞編號(hào)，設(shè)置洞的初始標(biāo)志為0#鏈表的節(jié)點(diǎn)樣式為：[洞的標(biāo)志,洞的編號(hào)]foriinrange(n1):hone.append([0,i+1])（1）1#狐貍開(kāi)始找兔子，將進(jìn)入過(guò)的洞標(biāo)志改為1，尋找m次結(jié)束head=0k=headhone[0][0]=1foriinrange(1,m):forjinrange(1,i+2):（2）2hone[k][0]=1#輸出標(biāo)志仍為0的洞，即兔子可能藏身地點(diǎn)foriinrange(len(hone)):ifhone[i][0]==0:print("兔子可能躲在第"+（3）+"號(hào)洞")18．猴子選大王問(wèn)題：有n只猴子，挑選大王。挑選規(guī)則如下：(1)將這n只猴子，圍成一圈。從某一只猴子開(kāi)始，按順時(shí)針?lè)较蛞来尉幪?hào)為1—n。(2)給定一個(gè)初始值k，從1號(hào)猴子開(kāi)始，沿順時(shí)針?lè)较驈?開(kāi)始報(bào)數(shù)，報(bào)到k的猴子退出。(3)將k值增1，從剛才退出猴子逆時(shí)針?lè)较虻?只猴子開(kāi)始，從1開(kāi)始沿逆時(shí)針?lè)较驁?bào)數(shù)，報(bào)到k的猴子退出。(4)將k值增1，從剛才退出猴子順時(shí)針?lè)较虻?只猴子開(kāi)始，從1開(kāi)始沿順時(shí)針?lè)较驁?bào)數(shù)，報(bào)到k的猴子退出。(5)按上述(3)(4)兩步，反復(fù)報(bào)數(shù)，直到圈中只剩下1只猴子。這只猴子就是大王。現(xiàn)要求，輸入猴子的總只數(shù)n，和初始k值，要求輸出大王的編號(hào)。同學(xué)們?cè)诔汤蠋煹闹笇?dǎo)下，利用如下數(shù)據(jù)結(jié)構(gòu)來(lái)表示猴子和圓圈：1只猴子用包含3個(gè)元素的列表表示，其中第1個(gè)元素表示猴子的編號(hào)，第2個(gè)元素表示當(dāng)前猴子的前1只沒(méi)有退出圓圈的猴子的索引號(hào)，第3個(gè)元素表示當(dāng)前猴子的后1只沒(méi)有退出圓圈的猴子的索引號(hào)。圈中猴子用列表元素表示。比如，[[1,2,1],[2,0,2],[3,1,0]]表示包含3只猴子的圓圈，這也是3只猴子在挑選大王之前的初始狀態(tài)。根據(jù)上面的數(shù)據(jù)結(jié)構(gòu)，小李同學(xué)設(shè)計(jì)的算法并實(shí)現(xiàn)的python代碼如下，請(qǐng)回答下列問(wèn)題。n=int(input("請(qǐng)輸入猴子的數(shù)量："))k=int(input("請(qǐng)輸入k值："))monkey=[]foriinrange(n):tmp=[i+1,i1,i+1]#tmp表示索引號(hào)為i的猴子節(jié)點(diǎn)ifi==n1:tmp[2]=0elifi==0:①monkey.append(tmp)p=0;cnt=1;flag=0whilemonkey[p][2]!=p:p=monkey[p][2flag%2]cnt+=1ifcnt==k:②monkey[monkey[p][2]][1]=monkey[p][1]cnt=0k+=1③print('大王是：',monkey[p][0],'號(hào)')（1）根據(jù)上述算法，如輸入猴子數(shù)量n為3，k值為2，則大王編號(hào)為▲號(hào)。（2）為使程序正確運(yùn)行，請(qǐng)?jiān)趧澗€處填入合適代碼。19.下列Python程序的功能是創(chuàng)建一個(gè)鏈表,并在鏈表中間插入一個(gè)新節(jié)點(diǎn),請(qǐng)回答下列問(wèn)題。classNode():def_init_(self,data=None):self.data=dataself.next=NoneclassLink_list():def_init_(self):self.head=Nonedefprint_list(self):ptr=self.headwhileptr:print(ptr.data)ptr=ptr.nextdefinsertnode(self,pre_node,newdata):ifpre_node==None:print("插入位置不對(duì)")returnnew_node=Node(newdata)①

②

link=Link_list()link.head=Node(1)n2=Node(5)n3=Node(9)link.head.next=n2n2.next=n3link.print_list()print("新的鏈表")link.insertnode(n2,7)③#打印鏈表

(1)操作后的新鏈表中的節(jié)點(diǎn)為;

(2)請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。20.在Python語(yǔ)言中，可以使用列表來(lái)模擬鏈表節(jié)點(diǎn)的插入操作。以下Python程序段用二維列表來(lái)定義單向鏈表。如要在該鏈表