高中信息技術(shù) （高考復(fù)習(xí)）專題八數(shù)據(jù)結(jié)構(gòu)與算法

考點(diǎn)一數(shù)據(jù)結(jié)構(gòu)與算法效率一、算法效率1.衡量標(biāo)準(zhǔn)算法效率的高低可由算法的復(fù)雜度來衡量。算法復(fù)雜度又分為算法的

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

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

執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)。所謂問題規(guī)模(也稱為輸入的大

小)是指處理問題的大小,即用來衡量輸入數(shù)據(jù)量的整數(shù)?？键c(diǎn)清單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()來體現(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

n24)常見的時(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()來比較不同算法的效率?？键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)用自己來實(shí)現(xiàn),

即一個(gè)函數(shù)在其定義中直接或間接調(diào)用自身的一種方法。2.遞歸的特性:通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相

似的規(guī)模較小的問題來求解,遞歸往往能使函數(shù)的定義和算法的描述簡

潔且易于理解,極大地減少了程序代碼量。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ù),無須移動(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ì)長度為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)是算法簡單,容易實(shí)現(xiàn),且對(duì)存放數(shù)據(jù)的表結(jié)構(gòu)無任何要

求,不管數(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-1下列關(guān)于算法效率分析的說法,正確的是

(

)A.算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度B.算法的時(shí)間復(fù)雜度是指算法執(zhí)行的速度C.算法的空間復(fù)雜度是指算法執(zhí)行所需的時(shí)間D.算法的時(shí)間復(fù)雜度是指算法在執(zhí)行過程中基本運(yùn)算的次數(shù)答案

D1-2下列有關(guān)數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響的描述,不正確的是

(

)A.同一個(gè)算法不一定能適用多種不同的數(shù)據(jù)結(jié)構(gòu)B.針對(duì)同一個(gè)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)不同的算法,算法的運(yùn)行效率可能相同C.使用鏈表存儲(chǔ)和處理數(shù)據(jù)比使用數(shù)組效率更優(yōu)D.設(shè)計(jì)算法時(shí),應(yīng)根據(jù)實(shí)際問題選擇合適的數(shù)據(jù)結(jié)構(gòu)答案

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

函數(shù)在其定義中直接或間接調(diào)用自身的一種方法,它通常把一個(gè)復(fù)雜的

問題轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來解決,可以極大地減

少代碼量,降低編程的難度。因此,迭代算法效率較高,而遞歸算法比較占

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

一定有迭代,但是迭代中不一定有遞歸,遞歸和迭代在大部分情況下可以

相互轉(zhuǎn)換。例2

(2022名校協(xié)作體,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)正確。答案D2-1

(2022麗水質(zhì)量監(jiān)控,11)有如下Python程序段:defs(x):ifx<=2:y=xelse:y=s(x-1)+s(x-2)returnya=int(input("請(qǐng)輸入正整數(shù):"))result=s(a)print(result)運(yùn)行程序,輸入值為6,則輸出結(jié)果為

(

)A.8B.9C.13D.14答案

C2-2猴子吃桃問題:一群猴子摘了一堆桃子,不知道總數(shù)。猴子們第一天

吃了總數(shù)的一半多一個(gè),第二天吃了剩余桃子的一半多一個(gè),……,直到第

十天,發(fā)現(xiàn)只剩1個(gè)桃子了。(1)第九天時(shí)總共有

個(gè)桃子,猴子們當(dāng)天吃了

個(gè)桃子。(2)設(shè)計(jì)一個(gè)遞歸算法,編程計(jì)算猴子總共摘了幾個(gè)桃子,請(qǐng)?jiān)趧澗€處填入

合適的代碼。deffun(n):

if①

:return1else:return②

答案

(1)4;3

(2)①n==10②2*(fun(n+1)+1)考向三數(shù)據(jù)排序1.冒泡排序的代碼實(shí)現(xiàn)對(duì)數(shù)組a進(jìn)行升序排序,長度為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)行升序排序,長度為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)盟,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,2

B.7,7,3,9,4,2

C.7,9,7,4,3,2

D.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é)果。答案A3-1

(2022麗水質(zhì)量監(jiān)控,10)采用選擇排序算法對(duì)數(shù)據(jù)序列“12,23,24,1

5,11,10”完成升序排序,則需要交換的次數(shù)為

(

)A.3B.4C.5D.6答案

A3-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ǔ)在長度為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ǔ)在長度為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-12)二分查找算法使用遞歸函數(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七彩陽光返校考,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.答案C4-1

(2022A9協(xié)作體返?？?11)有如下Python程序段:a=[99,85,74,68,53,42,34,27,20,13]key=int(input("請(qǐng)輸入一個(gè)整數(shù):"))i,j,k,c,flag=0,9,0,"N",Falsewhilei<=jandflag==False:m=(i+j+1)//2k=k+1ifkey==a[m]:c="Y"flag=Trueifkey>a[m]:j=m-1else:i=m+1print(c,k)執(zhí)行該程序段后,下列說法正確的是

(

)A.該程既能用于升序序列的查找,也能用于降序序列的查