數(shù)據(jù)查找（分層作業(yè)）高中信息技術(shù)選修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)（浙教版2019）

5.4數(shù)據(jù)查找2課時(shí)（分層作業(yè)）【基礎(chǔ)達(dá)標(biāo)】1.查找又稱，計(jì)算機(jī)根據(jù)所給條件查找出滿足條件的對象，即尋找出，或者確定在該批數(shù)據(jù)內(nèi)是否存在這樣的數(shù)據(jù)。2.若沒有找到滿足條件的對象，則返回特定值，表明查找；若查找到滿足條件的對象，則表明查找，一般要求返回。3.順序查找又稱，從的一端開始，依次將每個元素的關(guān)鍵字與給定值key（查找鍵）進(jìn)行比較。若某個元素的關(guān)鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。4.順序查找將待查找的數(shù)值與序列中的數(shù)，直到找出與給定數(shù)值相同的數(shù)為止，其算法簡單，時(shí)間復(fù)雜度為。5.二分查找又稱、。它是一種效率很高的查找方法，但被查找的數(shù)據(jù)序列必須是。二分查找首先將查找鍵與內(nèi)處于位置的元素進(jìn)行比較，如果中間位置上的元素的數(shù)值與查找鍵，根據(jù)數(shù)組元素的有序性，就可確定在數(shù)組的還是繼續(xù)查找；在新確定的范圍內(nèi)，繼續(xù)按上述方法進(jìn)行查找，直到獲得最終結(jié)果。6.二分查找過程中的每一次判斷都是將需要查找的值和數(shù)組的中間值進(jìn)行不斷的比較，直到找到或找遍。7.二分查找過程可用來描述，樹中的每個根節(jié)點(diǎn)對應(yīng)當(dāng)前查找區(qū)間的中點(diǎn)元素，它的左子樹和右子樹分別對應(yīng)該區(qū)間的左子表和右子表，通常把此樹稱為。8.二叉排序樹的排序功能主要通過二叉樹的和過程來實(shí)現(xiàn)。9.二叉查找樹的查找過程為：首先將給定值和根節(jié)點(diǎn)的比較，若相等，則查找成功；若不相等，則根據(jù)給定值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，在或中繼續(xù)進(jìn)行查找。若查到為時(shí)，說明該樹中沒有待查記錄，故查找不成功。10.給定任意的查找鍵，在序列3,5,8,12,15,23中進(jìn)行數(shù)據(jù)查找，下列說法不正確的是（）A.若用順序查找實(shí)現(xiàn)，則最少查找1次B.若用二分查找實(shí)現(xiàn)，則最少查找1次C.若用順序查找實(shí)現(xiàn)，則最多查找6次D.若用二分查找實(shí)現(xiàn)，則最多查找4次11.若線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則適用的查找方法為()。A.隨機(jī)查找B.散列查找C.二分查找D.順序查找【鞏固提升】1.某數(shù)組有10個元素，依次為10、23、32、40、55、64、77、81、93、100，若采用對分查找法在該數(shù)組中查找數(shù)據(jù)93，依次被訪問的數(shù)據(jù)為()A.64、81、92B.55、77、81、93C.55、81、93D.64、81、100、932.數(shù)組里有12個元素，依次為:34、40、41、43、53、55、65、70、72、74、80、95，下列選項(xiàng)中不正確的是()A.如使用順序查找法，53需要查找5次B.如使用對分法查找，53需要查找3次C.如使用順序查找法，70需要查找8次D.如使用對分法查找，70需要查找4次3.分別使用順序查找算法和二分查找算法在數(shù)據(jù)序列“5,6,10,13,15,20,21.26,30”中查找數(shù)據(jù)10,下列關(guān)于查找的次數(shù)的說法中正確的是()A.順序查找2次,二分查找3次B.順序查找3次,二分查找2次C.順序查找3次,二分查找3次D.順序查找3次,二分查找4次4.在10個有序的數(shù)“21,45,56,65,68,72,79,83,88,96"中查找75,則依次需要進(jìn)行比較的數(shù)據(jù)是（）A.68，83，72B.21，45，56，65，68，72，79C.68，83，72，79D.68，45，56，655.在7個有序的數(shù)列“1，2，3，4，5，6，7”中，采用二分查找法查找數(shù)值key，依次需要進(jìn)行比較的數(shù)據(jù)可能是()A.4B.4，6，2C.4，2，5D.4，6，5，76.下列有關(guān)查找的說法中，正確的是()A.順序查找時(shí)，被查找的數(shù)據(jù)必須有序B.對分查找時(shí)，被查找的數(shù)據(jù)不一定有序C.順序查找總能找到要查找的關(guān)鍵字D.一般情況下，對分查找的效率較高7.下列有關(guān)查找的說法中,不正確的是（）A.采用順序查找時(shí),被查找的數(shù)據(jù)集中的元素?zé)o須有序B.采用二分查找時(shí),被查找的數(shù)據(jù)集中的元素必須有序C.二分查找總能找到要查的鍵值D.二分查找的效率通常比順序查找高8.下列有關(guān)查找的說法，正確的是（）A.進(jìn)行對分查找時(shí)，被查找的數(shù)據(jù)必須已按升序排列B.進(jìn)行對分查找時(shí)，若查找的數(shù)據(jù)不存在，則無須輸出結(jié)果C.在《新華字典》中查找某個漢字，最適合使用順序查找D.對規(guī)模為n的數(shù)據(jù)進(jìn)行順序查找，平均查找次數(shù)是9.運(yùn)用二分查找算法可以提高查找的效率，前提是待查找序列必須是()排序的。A.遞增B.遞減C.有序D.無序10.已知單調(diào)函數(shù)f()在[0,1]區(qū)間上存在一個x0，使f(x0)=0?，F(xiàn)用對分查找法搜索x0的值，開始搜索區(qū)間為[0,1]，若經(jīng)過10次對分查找后還需繼續(xù)搜索，則第11次搜索區(qū)間的長度為（）A.B.C.1/102D.1/21011.8位同學(xué)的語文數(shù)學(xué)成績總分從高到低為“178，176，173，172，170，168，163，160。用二分查找法178的過程中，依次被訪問到的成績數(shù)據(jù)是()A.178B.172，176，178C.172，173，178D.172，173，176，17812.7位學(xué)生的身高(單位cm)從高到低依次為:178，177，175，172，170，165，162.用對分查找法找到178的過程中，依次被訪問到的數(shù)據(jù)是（）A.178B.172，175，178C.172，177，178D.172，175，177，17813.某數(shù)組d中的數(shù)據(jù)依次是[8,12,15,28,28,32,36,39]，要查找某個元素是否在數(shù)組中，下列說法正確的是()A.數(shù)組中有相同數(shù)據(jù)28，所以只能使用順序查找B.使用二分查找數(shù)據(jù)時(shí)，第1次查找的數(shù)據(jù)是d[3]C.使用二分查找任何查找鍵時(shí)，查找的次數(shù)最少3次D.使用二分查找數(shù)據(jù)時(shí)，第2次查找的數(shù)據(jù)可能是d[1]或d[6]14.數(shù)組P中存放著學(xué)生的相關(guān)信息，如圖所示，若要查找數(shù)組中是否存在“小李”的信息，以下說法正確的是()P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)P(10)小張小李小楊小陳小鄭小王小鄧小周小郭小范A.在數(shù)組P中既能使用順序查找也能使用二分查找B.在數(shù)組P中使用順序查找需要查找2次C.在數(shù)組P中使用二分查找需要查找4次D.在數(shù)組P中二分查找的效率高于順序查找15.分別使用順序查找算法和二分查找算法在數(shù)據(jù)序列“5,6,10,13,15,20,21,26,30”中查找數(shù)據(jù)10,下列關(guān)于查找的次數(shù)的說法中正確的是（）A.順序查找2次,二分查找3次B.順序查找3次,二分查找2次C.順序查找3次,二分查找3次D.順序查找3次,二分查找4次【鏈接高考】1.用順序查找在長度為10的某個數(shù)組中找某數(shù)，最少查找次，最多查找次。用對分查找在長度為10的某個數(shù)組中找某數(shù)，最少查找次，最多查找次。2.一段樓梯共有10級臺階，規(guī)定每步只能跨1級或2級，要登上第10級臺階有種不同的走法。3.有一段樓梯，共6級臺階，規(guī)定每一步只能跨1級、2級或3級，那么登上6級臺階有種不同走法。4.某查找算法的代碼如下:key=inl(inpul("請輸人待査元素key:"))a=[62,5,11,17,5.6,99,5,73,45]loc=1foriinrange(len(a)):ifa[i]==key:loc=ibreakifloc!=1:print(loc)else:print("查無此數(shù)")(1)當(dāng)輸入key的值為5時(shí),執(zhí)行該代碼處理后輸出的結(jié)果是。(2)若希望輸出key最后一次出現(xiàn)的位置,只需要對代碼進(jìn)行修改操作。(3)該查找算法的時(shí)間復(fù)雜度為。5.數(shù)組a存放著一組正整數(shù),其中奇數(shù)在前,偶數(shù)在后。奇數(shù)與偶數(shù)已分別升序排序,形如[1,7,13,15,21,2,4,8,22,26,30,36,40]。依據(jù)二分查找思想,小萌設(shè)計(jì)了一個從數(shù)組a中查找數(shù)據(jù)key的算法,其程序如下：i=0;j=9key=int(input("請輸人待查數(shù)據(jù):"))whilei<=j:m=(i+j)//2ifa[m]==key:breakifkey%2==0anda[m]%2==1:①elifkey%2==1anda[m]%2==0：②else:if③：j=m1else:i=m+1ifi>j:print("未找到")else:print("數(shù)組元素a["+str(m)+"]即為所求!")請?jiān)诔绦騽澗€處填人合適的代碼。①。②。③。6.一個整數(shù)序列,如果兩個相鄰元素的差恰好正負(fù)(負(fù)正)交替出現(xiàn),則稱為該序列為搖擺序列。小王同學(xué)想求出某個數(shù)列的最長搖擺子序列以序列[3,14,7,6,9,12,10,8,13,5]為例,整體不是搖擺序列,但子序列[3,14,7,9、[3,14,6,12]等都屬于搖擺子序列,其中最長的搖擺子序列是[3,14,6,12,8,13,5]。根據(jù)圖a分析得知，當(dāng)序列有一段連續(xù)的遞增(或遞減)時(shí),可形成搖擺子序列,我們只需要找到每一次轉(zhuǎn)折中的拐點(diǎn)元素。小王編寫了一個Python程序?qū)崿F(xiàn)該功能:程序運(yùn)行時(shí),輸入一串用逗號分隔和結(jié)束的數(shù)字,可以得到最長搖擺序列的長度,以及具體的序列。程序運(yùn)行界面如圖b所示:請輸入以逗號分隔和結(jié)束的數(shù)據(jù)(不超過20個數(shù)):3,14,7,6,9,12,10,8,13,最長搖擺子序列長度為6最長搖擺子序列為:3,14,6,12,8,13圖b(1)若輸人數(shù)據(jù)“2,4,5,3,2,1”,則最長搖擺子序列為。(2)實(shí)現(xiàn)上述功能的Python代碼如下,請?jiān)趧澗€處填入合適的代碼。s=input("請輸人以逗號分隔和結(jié)束的數(shù)據(jù)(不超過20個數(shù)):")a=[0]*20;b=[False]*20flag，n，i，t，ans=0，0，0，’，’deff(n):f=1globalans#global表示此處的ans就是全局變量ansans=str(a[n1])foriinrange(n2,1,1) Ifb[i]:f=f+1①returnfforchins:ifch==”,”:a[i]=int(t);n+=1;i+=1;t=""else:t=t+chforiinrange(l,n):gd=Tirueifflag==0:ifa[i]>a[i1]:flag=1elifa[i]<a[i1]:flag=2else:gd=Falseelifflag==1anda[i]<a[i1]:flag=2elif②flag=1else:gd=False③iff(n)<3:print("不構(gòu)成搖擺子序列")else:print("最長搖擺子序列長度為",str(í(n)))print("最長搖擺子序列為:",ans)7.設(shè)有n個顧客同時(shí)等待一項(xiàng)服務(wù),顧客主需要的服務(wù)時(shí)間為ti(1≤i≤n),應(yīng)如何安排n個顧客的服務(wù)次序才能使顧客總的等待時(shí)間達(dá)到最小。這個時(shí)間是多少？參考答案【基礎(chǔ)達(dá)標(biāo)】1.檢索、在存儲的一批數(shù)據(jù)內(nèi)、一個特定的數(shù)據(jù)2.失敗、成功、該對象的存儲位置或?qū)ο笾当旧?.線性查找、順序表4.順序查找將待查找的數(shù)值與序列中的數(shù)逐個進(jìn)行比較，直到找出與給定數(shù)值相同的數(shù)為止，其算法簡單，時(shí)間復(fù)雜度為O(n)。5.折半查找、對分查找、有序的、有序數(shù)組、中間位置、不同、前半部分、后半部分6.整個序列7.一棵二叉樹、二分查找的判定樹。8.建立、遍歷9.關(guān)鍵字、左子樹、右子樹、空樹10.答案：D[解析]順序查找時(shí)從頭到尾逐個查找，數(shù)組中共有6個元素，所以最少可能一次找到，最多數(shù)組每個元素查找一遍共六次;二分查找查找的最多次數(shù)為logzn+1次，由于數(shù)組共有6個元素，所以最多查找次數(shù)為3次，最少為1次。綜合以上信息，D項(xiàng)說法錯誤故選:D。11.答案：A[解析]隨機(jī)查找表中元素時(shí)，訪問表中任一元素所需時(shí)間與元素的位置和排列次序無關(guān)。以散列方式存儲和查找數(shù)據(jù)時(shí)，元素的存儲位置與其關(guān)鍵字相關(guān)。二分法查找只能在有序順序表中進(jìn)行。由于鏈表中的元素只能通過取得元素所在的節(jié)點(diǎn)的指針進(jìn)行，因此只能順序查找表中的元素?！眷柟烫嵘?.答案：C[解析]利用對分查找的原理可以，第一次訪問5位置的55，55<93，所以第二次訪問81，82<93，第三次訪問93，故選:C.2.答案：B[解析]順序查找是比數(shù)據(jù)的第一個元素開始依次比較，AC兩項(xiàng)分別查找53和70的次數(shù)為5次和8次，說法正確;B項(xiàng)對分查找53，i=1，j=12，m=(i+j)2=6，第6個元素為55，比53大，因此i=1，j=m1=5，m=(i+j)\2=3，第3個元素為41,41比53小，i=m+1=4，j=5，m=(i+j)\2=4,第4個元素為43，43比53小，因此，i=m+1=5，j=5，m=(i+j)\2=5，第5個元素為53，找到元素，共查找了4次，而非3次;故選:B.3.答案：C[解析]本題考查順序查找和二分查找的算法思想。數(shù)據(jù)10是數(shù)據(jù)序列中第3個元素,因此使用順序查找時(shí),共查找3次。使用二分查找時(shí),依次被訪問的數(shù)據(jù)為15，6,10,即二分查找的次數(shù)也為3。4.答案：C[解析]從10個數(shù)“21,45,56,65,68,72,79,83,88,96"中查找75的二叉判定樹如圖所示,故答案選C。5.答案：[解析]該二分查找用二叉樹表示如下，結(jié)合選項(xiàng)，可知依次需要進(jìn)行比較的數(shù)據(jù)可能是4。故選A。6.答案：D[解析]順序查找對被查找的數(shù)據(jù)是否有序沒有要求而對分查找時(shí)被查找的數(shù)據(jù)必須有序。故A、B選項(xiàng)錯誤。順序查找和對分查找都不能保證一定能找到要查找的關(guān)鍵字，C選項(xiàng)錯誤。順序查找是對全部范圍內(nèi)的每個元素依次進(jìn)行比較，而對分查找每次對一半范圍內(nèi)的數(shù)據(jù)進(jìn)行比較，一般來說，對分查找的效率比順序查找要高，D選項(xiàng)正確。故選:D。7.答案：C[解析]順序查找對被查找的數(shù)據(jù)是否有序沒有要求,而二分查找要求被查找的數(shù)據(jù)必須有序。順序查找和二分查找都不能保證一定能我到要查找的關(guān)鍵字,故C選項(xiàng)不正確。順序查找是對全部范圍內(nèi)的每個元案依次進(jìn)行比較,而二分查我每次對一半范圍內(nèi)的數(shù)據(jù)進(jìn)行比較,一般來說,二分查找的效率比順序查找要高。8.答案：D[解析]進(jìn)行對分查找時(shí)，被查找數(shù)據(jù)必須是有序的，降序或升序，查找數(shù)據(jù)不存在，依然需要輸出結(jié)果，《新華字典》中的漢字是有序的，適合采用對分查找，對規(guī)模為n的數(shù)據(jù)進(jìn)行順序查找，最多查找n次，最少查找1次，所以平均查找次數(shù)是(n+1)/2，故選:D.9.答案：C[解析]運(yùn)用二分查找法進(jìn)行查找時(shí)，必須為一個有序序列，無論是升序還是降序，所以C符合題意。故選:C。10.答案：D[解析]由題知知f(x)是單調(diào)函數(shù)，意味著f(x)已按大小有序排列，根據(jù)對分查找的概念，開始搜索區(qū)間為[0,1]，經(jīng)過1次對分查找后，第2次的搜索長度變?yōu)?/2,經(jīng)過2次對分查找后，第3次的搜索長度變?yōu)?/22...經(jīng)過10次對分查找后，第11次的搜索長度變?yōu)?/210，故選D。11.答案：B[解析]根據(jù)二分查找的定義可知，第一次查找為172，第二次查找為176，第三次查找為178。故選:B。12.答案：C[解析]據(jù)題意，所有數(shù)字降序排序，對分查找時(shí):第1次查找:將數(shù)組中的7個數(shù)字分成兩半，中間位置是(1+7)/2=4，第4位是數(shù)字172,172小于查找的數(shù)字178，就在數(shù)組第4位的左邊繼續(xù)查找;第2次查找:在數(shù)組第1位到第3位中找，中間位置時(shí)(1+3)/2=2，第2位是數(shù)字177，177小于178，就在數(shù)組第2位的左邊繼續(xù)查找;第3次查找:在第1位找，第1位的數(shù)字正好等于178，查找到數(shù)字，查找結(jié)束，整個查找過程訪問過的數(shù)字172，177，178;故選:C。13.答案：B[解析]數(shù)組d中的數(shù)據(jù)是有序的，可以用二分查找法進(jìn)行查找，故選項(xiàng)A是錯誤的;第一次查找時(shí)，m=3，即定位到的數(shù)據(jù)是d3，故B選項(xiàng)是正確的。如果第一次查找時(shí)的數(shù)據(jù)恰好是要查找的數(shù)據(jù)，那么查找次數(shù)最少是1次，故選項(xiàng)C是錯誤的;第二次查找時(shí)，d3]左邊是3個元素，定位到d[1，右邊是4個元素，定位到d5]，故選項(xiàng)D是錯的。故選B。14.答案：B[解析]對分查找雖然效率高，但是對于有序數(shù)組而言的，分析題目，P數(shù)字是沒有順序的，既不是降序也不是升序，所以不適合采用二分查找，利用順序查找查找兩次就能找見小李，故選:B.15.答案：C[解析]本題考查順序查找和二分查找的算法思想。數(shù)據(jù)10是數(shù)據(jù)序列中第3個元素,因此使用順序查找時(shí),共查找3次。使用二分查找時(shí),依次被訪問的數(shù)據(jù)為15，6，10，即二分查找的次數(shù)也為3?！炬溄痈呖肌?.答案：1、10、1、4[解析]本題考查的是順序查找與對分查找的相關(guān)知識。順序查找從數(shù)組的一端開始，順序掃描數(shù)組，依次將掃描到的元素和給定值Key相比較。若當(dāng)前掃描到的元素與Key相等，則查找成功;若掃描結(jié)束若仍未找到，則查找失敗;對分查找:是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功;否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。用順序查找在長度為10的某個數(shù)組中找某數(shù)，最少查找1次，最多查找10次;用對分查找在長度為10的某個數(shù)組中找某數(shù)，最少查找1次，最多查找4次，因?yàn)閷Ψ植檎业臅r(shí)間復(fù)雜度為log210，即為4。2.答案：89[解析]由于登臺階每次只能跨1級或2級，因此登上第n級臺階的情形僅與登上第n1級和第n一2級臺階有關(guān)，可以考慮建立遞推關(guān)系。列表如下:級數(shù)123456……10走法1234813……89登上第1級臺階只有1種走法，即a1=1;登上第2級臺階有2種走法，即az2;登上第3級臺階有3種走法，即a:3;登上第4級臺階有5種走法，即a5。以此類推，登上各級臺階的走法依次為1，2，3，5，8，13，21，34，55，89。其中a1=89，即登上第10級臺階有89種不同走法。3.答案：24[解析]假設(shè)共1級臺階，則只有1種走法，2級，有2種走法，3級，有4種走法，4級，1+2+4=7種走法，5級，2+4+7=13種走法，6級，4+7+13=24種走法，故答案為:24。4.答案：(1)1(2)將break語句刪除(3)0()[解析]該代碼實(shí)現(xiàn)的是輸出順序查找數(shù)組中key第一次出現(xiàn)的位置,key=5,所以輸出的結(jié)果為1;想修改為查找出key最后一次出現(xiàn)的位置并輸出,只需要讓for循環(huán)繼續(xù)查找到最后一次出現(xiàn)的位置并輸出,所以只需要刪除break語句;該代碼采用一重循環(huán)枚舉a數(shù)組中的所有數(shù)再與key進(jìn)行對比,所以時(shí)間復(fù)雜度為O(n)。5.答案：①i=m+1②j=m1③key<a[m][解析]根據(jù)題目的描述“奇數(shù)在前,偶數(shù)在后”可知:若滿足key是偶數(shù)且中間項(xiàng)a[m]為奇數(shù),則向后找;若滿足key是奇數(shù)且中間項(xiàng)a[m]為偶數(shù),則向前找;如果中間項(xiàng)a[m]與key同奇同偶,那么根據(jù)二分查找的思想繼續(xù)查找。6.答案：(1)2,5,1(2)①ans=str(a[i])+’,’+ans②flag=2anda[i]>a[i1]③b[i1]=gd[解析]本題考查數(shù)組的應(yīng)用。其中列表a用于存儲輸入的數(shù)據(jù)元素,列表b用于記錄是否為拐點(diǎn)，為輸入的數(shù)據(jù)元素