浙江版高中信息技術(shù)復(fù)習(xí)教學(xué)專題八數(shù)據(jù)結(jié)構(gòu)與算法課件

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

專題八數(shù)據(jù)結(jié)構(gòu)與算法高考

技術(shù)浙江省專用考點(diǎn)一數(shù)據(jù)結(jié)構(gòu)與算法效率一、算法效率1.衡量標(biāo)準(zhǔn)算法效率的高低可由算法的復(fù)雜度來(lái)衡量。算法復(fù)雜度又分為算法的時(shí)間復(fù)雜度和

空間復(fù)雜度,其中時(shí)間復(fù)雜度反映了算法執(zhí)行所需要的時(shí)間,而空間復(fù)雜度反映了算

法執(zhí)行所需要占用的存儲(chǔ)空間。2.時(shí)間復(fù)雜度(1)一般將算法中語(yǔ)句的執(zhí)行次數(shù)作為時(shí)間復(fù)雜度的度量標(biāo)準(zhǔn)。語(yǔ)句總的執(zhí)行次數(shù)T

(n)是關(guān)于問題規(guī)模n的函數(shù)。所謂問題規(guī)模(也稱為輸入的大小)是指處理問題的大小,即用來(lái)衡量輸入數(shù)據(jù)量的整數(shù)。(2)時(shí)間復(fù)雜度常用符號(hào)O表述,不包括T(n)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù),如

n(n-1)的量級(jí)與n2相同,其時(shí)間復(fù)雜度可表示成O(n2)。(3)推導(dǎo)大O階的方法用O()來(lái)體現(xiàn)算法時(shí)間復(fù)雜度,稱之為大O階記法。其推導(dǎo)方法如下:①用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。②在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)。③如果最高階項(xiàng)存在且不是1,那么去除與這個(gè)項(xiàng)相乘的常數(shù)。得到的結(jié)果就是大O

階。例如,

n(n-1)

n2

n2(4)常見的時(shí)間復(fù)雜度耗費(fèi)時(shí)間的大小關(guān)系為O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)。二、數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響1.數(shù)據(jù)組織成不同的結(jié)構(gòu),是為了滿足不同問題的需求,便于算法對(duì)數(shù)據(jù)的操作,提高

算法處理數(shù)據(jù)的效率。2.數(shù)據(jù)結(jié)構(gòu)的不同選擇會(huì)影響算法的運(yùn)行效率。3.通過比較時(shí)間復(fù)雜度O()來(lái)比較不同算法的效率?？键c(diǎn)二迭代與遞歸一、迭代與迭代算法1.迭代是重復(fù)反饋過程的活動(dòng),其目的通常是使結(jié)果符合目標(biāo)需求。2.迭代算法是利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn),讓計(jì)算機(jī)重復(fù)執(zhí)行

一組指令(或一些步驟),這組指令(或這些步驟)每執(zhí)行一次時(shí),都會(huì)將變量從原值遞推

出一個(gè)新值。二、利用迭代算法處理問題利用迭代算法處理問題需要考慮三個(gè)方面:1.確定迭代變量在能夠用迭代算法處理的問題中,至少具有一個(gè)直接或間接地不斷由舊值遞推出新值

的變量,這個(gè)變量就是迭代變量。2.建立迭代關(guān)系式所謂迭代關(guān)系式,指如何從變量的前一個(gè)值推出其下一個(gè)值的公式(或關(guān)系)。3.控制迭代過程迭代過程在經(jīng)過若干次重復(fù)執(zhí)行以后要能結(jié)束,因此,要設(shè)定迭代結(jié)束的條件。三、遞歸的概念與特性1.概念大問題的解決中嵌套著與原問題相似的規(guī)模較小的問題,這種解決問題的方式在計(jì)算機(jī)科學(xué)中稱為遞歸,通過函數(shù)自己調(diào)用自己來(lái)實(shí)現(xiàn),即一個(gè)函數(shù)在其定義中直接或間

接調(diào)用自身的一種方法。2.遞歸的特性通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來(lái)求解,

遞歸往往能使函數(shù)的定義和算法的描述簡(jiǎn)潔且易于理解,極大地減少了程序代碼量。3.能采用遞歸描述的算法的特征為求解規(guī)模為N的問題,設(shè)法將它分解成規(guī)模較小的問題,然后從這些小問題的解中方

便地構(gòu)造出大問題的解,并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法。

當(dāng)遞歸到達(dá)某個(gè)邊界,如問題規(guī)?？s減為0或1時(shí),能直接得解。4.利用遞歸算法解決問題的關(guān)鍵步驟①抽象建立遞歸模型,確定遞歸公式。②確定臨界條件(即遞歸結(jié)束條件)?？键c(diǎn)三數(shù)據(jù)排序一、排序1.概念排序就是整理數(shù)據(jù)的序列,使其中元素按照某個(gè)值的遞增(或遞減)的次序重新排列的

操作。在排序的過程中,數(shù)據(jù)元素的值保持不變,但其在序列中的順序可能會(huì)改變。2.存儲(chǔ)方式待排序數(shù)據(jù)的存儲(chǔ)一般有數(shù)組和鏈表兩種方式,利用數(shù)組存儲(chǔ)數(shù)據(jù),在排序時(shí)需要對(duì)

數(shù)據(jù)本身進(jìn)行物理重排,可能需要移動(dòng)數(shù)據(jù)的位置,而利用鏈表存儲(chǔ)數(shù)據(jù),無(wú)須移動(dòng)數(shù)

據(jù),僅需修改指針即可。二、冒泡排序1.冒泡排序是在一系列數(shù)據(jù)中對(duì)相鄰兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整,讓較大的數(shù)“下沉

(上冒)”,較小的數(shù)“上冒(下沉)”的一種排序技術(shù)。2.算法效率:對(duì)于n個(gè)元素的數(shù)組,共需要n-1趟,第一趟的比較次數(shù)為n-1,第二趟的比較

次數(shù)為n-2,以此類推,最后一趟的比較只需1次。共需比較(n-1)+(n-2)+…+1=

次。其時(shí)間復(fù)雜度為O(n2)。三、選擇排序算法(1)在參加排序的數(shù)組的所有元素中找出最小(或最大)的數(shù)據(jù),使它與第一個(gè)元素(左

端)中的數(shù)據(jù)相互交換位置。然后在余下的元素中找出最小(或最大)的數(shù)據(jù),與第二個(gè)元素中的數(shù)據(jù)交換位置。以此類推,直到所有元素成為一個(gè)有序的序列。(2)對(duì)長(zhǎng)度為n的數(shù)組,每一趟排序過程都會(huì)掃描待排序區(qū)域的所有元素,將最小(或最

大)值交換到最左端,直至只剩下1個(gè)元素為止,總共排序n-1趟,比較的次數(shù)為

,時(shí)間復(fù)雜度為O(n2)?？键c(diǎn)四數(shù)據(jù)查找一、查找查找又稱檢索,計(jì)算機(jī)根據(jù)所給條件查找出滿足條件的對(duì)象,即在存儲(chǔ)的一批數(shù)據(jù)內(nèi)

尋找出一個(gè)特定的數(shù)據(jù),或者確認(rèn)在該批數(shù)據(jù)內(nèi)是否存在這樣的數(shù)據(jù)。若沒有找到滿

足條件的對(duì)象,則返回特定值,表明查找失敗;若查找到滿足條件的對(duì)象,則表明查找成

功。二、順序查找1.概念順序查找又稱線性查找,從順序表的一端開始,依次將每個(gè)元素的關(guān)鍵字與給定值key(查找鍵)進(jìn)行比較。若某個(gè)元素的關(guān)鍵字等于key,則表明查找成功;若所有元素都比

較完畢仍找不到,則表明查找失敗。2.優(yōu)缺點(diǎn)順序查找的優(yōu)點(diǎn)是算法簡(jiǎn)單,容易實(shí)現(xiàn),且對(duì)存放數(shù)據(jù)的表結(jié)構(gòu)無(wú)任何要求,不管數(shù)據(jù)

是否有序,均可使用,缺點(diǎn)是查找效率低,當(dāng)數(shù)據(jù)量較大時(shí)不宜采用。三、二分查找1.概念二分查找又稱折半查找,對(duì)分查找。二分查找首先將查找鍵與有序數(shù)組內(nèi)處于中間位

置的元素進(jìn)行比較,如果中間位置上的元素與查找鍵不同,根據(jù)數(shù)組元素的有序性,就可以確定在數(shù)組的前半部分還是后半部分繼續(xù)查找;在新確定的范圍內(nèi),繼續(xù)按上述

方法進(jìn)行查找,直到獲得最終結(jié)果。2.二分查找是一種效率很高的查找方法,要求被查找的數(shù)據(jù)序列必須是有序的,最多進(jìn)

行?log2n」+1次比較。考向一數(shù)據(jù)結(jié)構(gòu)與算法效率數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系,即數(shù)據(jù)的組織形式。(1)數(shù)據(jù)元素之間的邏輯關(guān)系,也稱為數(shù)據(jù)的邏輯關(guān)系。(2)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示,也稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。(3)數(shù)據(jù)的運(yùn)算,即對(duì)數(shù)據(jù)施加的操作。2.實(shí)際應(yīng)用中的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)主要考慮數(shù)據(jù)對(duì)象之間的邏輯關(guān)系,所以數(shù)據(jù)結(jié)構(gòu)一般

指向的就是邏輯結(jié)構(gòu)。例1

(2022Z20名校聯(lián)盟,3)下列有關(guān)數(shù)據(jù)結(jié)構(gòu)的說法正確的是

(

)A.數(shù)組是一種適用于組織、存儲(chǔ)涉及頻繁插入與刪除的數(shù)據(jù)結(jié)構(gòu)B.鏈表中數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的C.Excel軟件中的撤銷操作體現(xiàn)了隊(duì)列的思想D.樹結(jié)構(gòu)中,每個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)可以有多個(gè)

解析

本題主要考查數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)。鏈表是一種適用于組織、存儲(chǔ)涉及頻繁插入與刪除的數(shù)據(jù)結(jié)構(gòu),A選項(xiàng)錯(cuò)誤;Excel中的撤銷操作體現(xiàn)了棧的思想,C選項(xiàng)錯(cuò)

誤;樹結(jié)構(gòu)中,每個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)只可以有一個(gè),D選項(xiàng)錯(cuò)誤。

答案B1.(2024屆嘉興基測(cè),10)下面有關(guān)數(shù)據(jù)結(jié)構(gòu)的說法不正確的是

(

)A.在程序設(shè)計(jì)中,數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)時(shí)主要考慮對(duì)象之間邏輯關(guān)系的實(shí)現(xiàn)B.鏈表結(jié)構(gòu)適用于初始規(guī)模確定但在處理過程中頻繁進(jìn)行插入、刪除操作的數(shù)據(jù)C.數(shù)組結(jié)構(gòu)中采用下標(biāo)訪問數(shù)據(jù),訪問效率要高于鏈表結(jié)構(gòu)D.大多數(shù)軟件中都有“撤銷”功能,實(shí)現(xiàn)此功能應(yīng)采用隊(duì)列結(jié)構(gòu)答案

D

2.(2023浙江6月選考,12,2分)已排序的列表a有n個(gè)整型元素,現(xiàn)要查找出現(xiàn)次數(shù)最多的

值并輸出。若出現(xiàn)次數(shù)最多的值有多個(gè),則輸出最前面的一個(gè)。實(shí)現(xiàn)該功能的程序段即練即清如下,方框中應(yīng)填入的正確代碼為

(

)c,m,v=1,1,0foriinrange(1,n):print(a[v])A.ifa[i]==a[i-1]:c+=1ifc>m:m=cv=ielse:c=1B.ifa[i]==a[i-1]:c+=1ifc>m:m=cv=ielse:c=1C.ifa[i]==a[i-1]:c+=1else:ifc>m:m=cv=i-1c=1D.ifa[i]==a[i-1]:c+=1else:ifc>m:m=cv=i-1c=1答案

A

考向二迭代與遞歸迭代算法與遞歸算法的區(qū)別1.迭代是利用變量的舊值推算出變量的一個(gè)新值;而遞歸算法是指一個(gè)函數(shù)在其定義

中直接或間接調(diào)用自身的一種方法,它通常把一個(gè)復(fù)雜的問題轉(zhuǎn)化為一個(gè)與原問題相

似的規(guī)模較小的問題來(lái)解決,可以極大地減少代碼量,降低編程的難度。因此,迭代算

法效率較高,而遞歸算法比較占用空間,程序運(yùn)行效率較低。2.遞歸是通過函數(shù)自己調(diào)用自己,而迭代是不斷地調(diào)用賦值語(yǔ)句;遞歸中一定有迭代,

但是迭代中不一定有遞歸,遞歸和迭代在大部分情況下可以相互轉(zhuǎn)換。例2

(2022名校協(xié)作體聯(lián)考,11)有如下Python程序段:deff(x):ifx==1:return1else:returnx*f(x-1)s=0foriinrange(1,6):s+=f(i)print(s)執(zhí)行該程序段后,變量s的值是

(

)A.33B.34C.154D.153

解析

本題主要考查遞歸算法的程序的實(shí)現(xiàn)。從代碼x*f(x-1)可知,該函數(shù)是通過遞歸算法實(shí)現(xiàn)x的階乘。后面的循環(huán)是把1~5的階乘進(jìn)行累加,1!+2!+3!+4!+5!=1+2+6+24

+120=153,D選項(xiàng)正確。

答案D1.(2024屆浙南名校聯(lián)盟聯(lián)考,10)有如下Python程序段:deff(x):ifx==1:return2else:returnf(x-1)**2y=f(3)print(y)即練即清執(zhí)行該程序段后,輸出的結(jié)果是

(

)A.4B.8C.16D.32答案

C

2.(2024屆A9協(xié)作體返?？?9)有如下Python程序段:defpeach(n):ifn==10:return1else:return(peach(n+1)+1)*2print(peach(8))執(zhí)行該程序段后,輸出的結(jié)果是

(

)A.2B.6C.8D.10答案

D

考向三數(shù)據(jù)排序1.冒泡排序的代碼實(shí)現(xiàn)對(duì)數(shù)組a進(jìn)行升序排序,長(zhǎng)度為n的數(shù)組需要排序n-1趟。n=len(a)foriinrange(0,n-1):#排序趟數(shù)forjinrange(n-1,i,-1):#向左掃描,將最小值移到左端ifa[j]<a[j-1]:a[j],a[j-1]=a[j-1],a[j]2.選擇排序的代碼實(shí)現(xiàn)對(duì)數(shù)組a進(jìn)行升序排序,長(zhǎng)度為n的數(shù)組需要排序n-1趟。n=len(a)foriinrange(n-1):k=iforjinrange(i+1,n):#掃描待排序區(qū)間,尋找最小值下標(biāo)ifa[j]<a[k]:k=jifk!=i:#如果a[i]非最小值,則將最小值交換到下標(biāo)為i的位置a[i],a[k]=a[k],a[i]例3

(2022Z20名校聯(lián)盟聯(lián)考,12)某Python程序如下:importrandomn=random.randint(1,4)a=[7,2,7,3,9,4]foriinrange(1,n):forjinrange(0,6-i):ifa[j]<a[j+1]:a[j],a[j+1]=a[j+1],a[j]執(zhí)行該程序段后,數(shù)組a中的元素不可能為

(

)A.9,7,7,4,3,2B.7,7,3,9,4,2C.7,9,7,4,3,2D.7,2,7,3,9,4

解析

本題主要考查冒泡排序、隨機(jī)數(shù)的知識(shí)。n的范圍是1~4的整數(shù),當(dāng)n=1時(shí),range(1,1),循環(huán)次數(shù)為0。當(dāng)n=2、3、4時(shí)即循環(huán)1、2、3次的結(jié)果分別寫出,不能得到

A中結(jié)果。

答案A1.(2024屆Z20聯(lián)盟聯(lián)考,11)lst1和lst2都是升序排序的列表,執(zhí)行如下Python程序段:result=[]i=0#用于遍歷lst1j=0#用于遍歷lst2whilei<len(lst1)andj<len(lst2):

#①iflst1[i]<lst2[j]:result.append(lst1[i])i+=1即練即清e(cuò)lse:result.append(lst2[j])j+=1whilei<len(lst1):result.append(lst1[i])

#②i+=1whilej<len(lst2):result.append(lst2[j])

#③j+=1下列說法不正確的是

(

)A.程序段①執(zhí)行后,result可能與lst1相同B.程序段①執(zhí)行后,result可能與lst2相同C.在一次程序運(yùn)行中,②處代碼和③處代碼可能都被執(zhí)行D.程序執(zhí)行后,列表result中的元素升序排序答案

C

2.(2022紹興魯迅中學(xué)期中,11)有如下Python程序段:n=4a=[[j*n+i+1forjinrange(n)]foriinrange(n)]foriinrange(0,n,2):forjinrange(n//2):a[i][j],a[i][n-j-1]=a[i][n-j-1],a[i][j]則程序執(zhí)行后,a[0][1]和a[1][1]的值分別為(

)A.2和7B.3和6C.5和10D.9和6答案

D

考向四數(shù)據(jù)查找1.順序查找的代碼實(shí)現(xiàn)假設(shè)n個(gè)數(shù)據(jù)依次存儲(chǔ)在長(zhǎng)度為n的數(shù)組a中,查找鍵為key,自定義函數(shù)Seq_search(a,

key)返回?cái)?shù)組a中首個(gè)值為key的元素下標(biāo),若找不到key,則返回-1。defseq_search(a,key):foriinrange(len(a)):ifa[i]==key:returnielse:return-12.二分查找的代碼實(shí)現(xiàn)(1)假設(shè)n個(gè)遞增數(shù)據(jù)依次存儲(chǔ)在長(zhǎng)度為n的數(shù)組a中,查找鍵為key,自定義函數(shù)binary_

search(a,key)返回?cái)?shù)組a中某個(gè)值為key的元素下標(biāo),若找不到key,則返回-1。defbinary_search(a,key):L,R=0,len(a)-1whileL<=R:m=(L+R)//2#左偏m=(L+R+1)//2#右偏ifkey==a[m]:returnmelifkey<a[m]:R=m-1else:L=m+1return-1(2)二分查找算法使用遞歸函數(shù)bsearch(a,L,R,key)也能實(shí)現(xiàn),其中L和R分別表示查找區(qū)

間的左、右邊界。defbsearch(a,L,R,key):ifL>R:return-1m=(L+R)//2#左偏ifkey==a[m]:returnmelifkey<a[m]:returnbsearch(a,L,m-1,key)else:returnbsearch(a,m+1,R,key)例4

(2022七彩陽(yáng)光返?？?11)有如下Python程序段:importrandoma=[4,2,6,5,4,2,9,7]k=random.randint(1,10)i=0;j=len(a)-1;x=""whilei<=j:m=(i+j)//2ifk<=a[m]:j=m-1;x=x+"L"else:i=m+1;x=x+"R"print(x)執(zhí)行該程序段后,輸出的結(jié)果不可能出現(xiàn)的是

(

)A."LLL"B."LRL"C."RLR"D."RRRR"

解析

本題主要考查二分查找算法。k的值為1~10的整數(shù),m的第一個(gè)值為3,則對(duì)應(yīng)列表a中元素5,所以把[1,10]分成[1,5]和[6,10]兩段。最終分成四段[1,2]、[3,5]、[6,9]、[10,10]分別對(duì)應(yīng)四種不同的s的值"LLL","LRL","RRL","RRRR",所以不可能出現(xiàn)的是RLR。

答案C例5

(2022紹興諸暨期中,15)某二分查找算法的Python程序段如下:list1=["Carrot","Celery","Garlic","Lettuce","Mooli","Onion","Potato","Tomato"]key=list1[2]left,right=0,len(list1)-1c=0whileleft<=right:m=(left+right)//2c=c+1iflist1[m]>key:right=m-1else:left=m+1print(list1[left])程序執(zhí)行后,下列說法正確的是

(

)A.變量c的值為4B.程序輸出的結(jié)果為L(zhǎng)ettuceC.變量left的值為2D.變量right的值為3

解析

本題主要考查二分查找算法及Python程序?qū)崿F(xiàn)。已知left=0,right=7,key="Garlic",第一次查找m=(left+right)//2=3,c=c+1=1,a(3)="Lettuce",判斷l(xiāng)ist1[m]>key成立,執(zhí)行right=m-1=2;第二次查找m=(left+right)//2=1,c=