數(shù)據(jù)查找（教學(xué)設(shè)計）高中信息技術(shù)選修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)（浙教版2019）

5.4數(shù)據(jù)查找（教學(xué)設(shè)計）年級高二年級授課時間2課時課題5.4數(shù)據(jù)查找教學(xué)目標(biāo)1.了解數(shù)據(jù)查找的基本概念和常見算法。2.掌握順序查找、二分查找等數(shù)據(jù)查找算法的原理和實現(xiàn)方法。3.能夠分析和比較不同數(shù)據(jù)查找算法的優(yōu)缺點。還能夠應(yīng)用所學(xué)知識解決實際問題。教學(xué)重難點重點：1.數(shù)據(jù)查找的基本概念和算法原理；2.順序查找和二分查找算法的實現(xiàn)方法；3.不同數(shù)據(jù)查找算法的比較和應(yīng)用。難點：1.理解二分查找算法的遞歸實現(xiàn)；2.分析不同數(shù)據(jù)查找算法的時間復(fù)雜度。教學(xué)準(zhǔn)備多媒體課件、多媒體教室教學(xué)過程教師活動學(xué)生活動新課導(dǎo)入一、課堂導(dǎo)入1.通過幾張圖片展示：上下面兩幅圖片中有幾處不同的地方，同學(xué)們能不能快速的找出來？下列5個圖標(biāo)找出哪一個是微信圖標(biāo)？能一眼看出來嗎？生活中還有哪些查找的具體例子，你是通過什么樣的方法快速進(jìn)行查找的。在日常生活中，人們經(jīng)常會進(jìn)行各種查找操作，如在上查找公交車的線路、在電子詞典中查找某個單詞的讀音和含義、在音樂網(wǎng)站上查找自己喜歡的音樂以及利用搜索引擎在浩瀚的信息海洋中查找需要的信息等。新知講授一、查找1.概念查找（Search）又稱檢索，計算機(jī)根據(jù)所給條件查找出滿足條件的對象，即在存儲的一批數(shù)據(jù)內(nèi)尋找出一個特定的數(shù)據(jù)，或者確定在該批數(shù)據(jù)內(nèi)是否存在這樣的數(shù)據(jù)。2.查找①沒有找到滿足條件的對象返回特定值，表明查找失??；②查找到滿足條件的對象表明查找成功，一般要求返回該對象的存儲位置或?qū)ο笾当旧?。通常，程序?qū)凑詹檎业慕Y(jié)果（找到或未找到）來決定接著應(yīng)執(zhí)行后面哪一個計算步驟。如超市購物付款時，當(dāng)收銀員掃描一件貨物的條形碼時，計算機(jī)需要在幾萬條不同的記錄中尋找這件商品，然后顯示相應(yīng)的商品名稱和價格。二、常見的排序算法1.順序查找（1）算法思想從第一個數(shù)據(jù)開始，按數(shù)據(jù)的順序逐個將數(shù)據(jù)與給定的值進(jìn)行比較。若某個數(shù)據(jù)與給定值相等，則查找成功，記錄所查數(shù)據(jù)的位置；反之，則查找不成功。（2）算法特點①算法簡單，對數(shù)據(jù)是否有序沒有要求。②查找效率較低，當(dāng)數(shù)據(jù)量大時不宜使用。（3）案例講解以“在成績查詢系統(tǒng)中查找某學(xué)號”為例，假定某學(xué)習(xí)小組8名學(xué)生的學(xué)號數(shù)據(jù)存儲在數(shù)組d中，要查詢的學(xué)生學(xué)號（查找鍵）已經(jīng)存儲在變量key中。①算法演算從數(shù)組d的第1個元素d[0]開始，依次判斷各元素的值是否與查找鍵key的值相等。若某個數(shù)組元素d[i]的值等于key，則結(jié)束處理（找到了指定的數(shù)據(jù)）；若找遍了所有8個元素，無任何元素的值等于key，則結(jié)束處理（未找到指定的數(shù)據(jù)）。在規(guī)模為8的數(shù)組d中，分別按順序查找算法尋找數(shù)據(jù)18和15的情況，處理過程中找到的第4個數(shù)組元素d[3]中的數(shù)據(jù)與18相等，表示8個數(shù)據(jù)中存在值為18的元素；而若key為15時，查找完所有數(shù)據(jù)仍未找到，表示8個數(shù)據(jù)中不存在值為15的元素。順序查找過程實例②順序查找將待查找的數(shù)值與序列中的數(shù)逐個進(jìn)行比較，直到找出與給定數(shù)值相同的數(shù)為止，其算法簡單，時間復(fù)雜度為O(n)。順序查找算法流程圖③實現(xiàn)此算法的Python程序如下：d=[25,22,13,18,14,11,17,19]key=18flag=Falselength=len(d)foriinrange(length):ifd[i]==key:flag=Truebreakifflag==True:print("查找成功！")else:print("未找到")④順序查找算法也可以寫成函數(shù)的形式，如右表所示：defseq_search(s,a):length=len(s)flag=Falseforiinrange(length):ifs[i]==a:flag=Truebreakifflag==True:returnielse:returnFalsed=[25,22,13,18,14,11,17,19]key=15result=seq_search(d,key)print(result)（4）探討與討論①順序查找算法的部分代碼如下：Flag=Falsei=0whilei<5andFlag==False:i=i+1ifa[i]==key:Flag=TrueifFlag==False:i=0數(shù)組元素a=[8,7,3,5,4]，若key值為3，則運行該程序后，變量i的值是（）A.0 B.2 C.3 D.5②某查找算法的VB代碼如下：k=0i=0whilei<=6:ifa[i]==key:k=ii=i+1數(shù)組元素a=[5,3,5,1,8,5,9]，當(dāng)變量key值為5時，運用該算法處理后，變量k的值是()A.1 B.2 C.5 D.02.二分查找（1）算法思想二分查找（BinarySearch）又稱折半查找、對分查找。首先將查找的數(shù)與有序數(shù)組內(nèi)處于中間位置的數(shù)據(jù)比較，如果中間位置上的數(shù)與查找的數(shù)不同，則根據(jù)有序性，確定應(yīng)該在數(shù)組的前半部分還是后半部分繼續(xù)查找。在新確定的范圍內(nèi)，繼續(xù)按上述方法，直到獲得最終結(jié)果。（2）算法特點①要求被查找數(shù)據(jù)必須有序。②查找效率非常高，適用于大數(shù)據(jù)查找。在數(shù)組中的數(shù)據(jù)是有序的，若是升序的，是指下標(biāo)越小的數(shù)組元素中存儲的數(shù)據(jù)也越小，降序則相反。（3）基本方法為簡單起見，設(shè)數(shù)組d中存儲了n個互不相同的數(shù)據(jù)，并且數(shù)組d中的數(shù)據(jù)是升序的，則應(yīng)有：d[0]＜d[1]＜…＜d[n–2]＜d[n–1]。使用兩個變量i和j分別記錄查找范圍內(nèi)的第一個數(shù)組元素和最后一個數(shù)組元素的下標(biāo)。開始時，整個數(shù)組中的所有n個元素都在查找范圍內(nèi)，即變量i的初值為0，j的初值為n–1，用(i,j)表示查找范圍從d[i]起到d[j]為止。二分查找的基本方法是：在查找范圍(i,j)內(nèi)，可以利用數(shù)據(jù)的有序性，而不必逐個地進(jìn)行查找。①首先確定該區(qū)間的中點位置：m=(i+j)/2」（m表示小于等于的最大整數(shù)）。②然后將查找鍵key與d[m]比較，結(jié)果必然是如下三種情況之一：(a)key＜d[m]，查找鍵小于中點d[m]處的數(shù)據(jù)。因為數(shù)組d中的數(shù)據(jù)遞增，可以確定在(m,j)內(nèi)不可能存在值為key的數(shù)據(jù)，所以只需在新的范圍(i,m–1)中繼續(xù)查找。(b)key=d[m]，找到了需要的數(shù)據(jù)。(c)key＞d[m]，由與（a）相同的理由，只需在新的范圍(m+1,j)中繼續(xù)查找。在通過一次比較后，新的查找范圍不會超過上一次查找范圍的一半。（4）案例講解以規(guī)模為11的數(shù)組d為例，觀察二分查找的過程。在數(shù)組d的11個元素中，已按增序存儲了11個數(shù)據(jù)，要尋找的數(shù)據(jù)為12（已存儲在變量key中）。①算法演算初，數(shù)組d中的11個元素（從d[0]到d[10]）都在查找范圍內(nèi)，中點處的數(shù)組元素是d[5]。通過第1次比較（d[5]與key的比較）后發(fā)現(xiàn)，key的值比中點處的數(shù)據(jù)小，在數(shù)組d的右半部分（從d[6]到d[10]的范圍）內(nèi)不存在要找的數(shù)據(jù)，只需在數(shù)組d的左半部分（從d[0]到d[4]的范圍）進(jìn)行下一次查找。第2次比較時，中點處的數(shù)組元素是d[2]。比較后發(fā)現(xiàn)，第3次查找的范圍為d[0]到d[1]，中點處的數(shù)組元素是d[0]。此時，key的值比中點處的數(shù)據(jù)大，第4次的查找范圍只有一個元素，即d[1]，而d[1]的值與key的值相等，找到指定的數(shù)據(jù)。②查找過程中，查找范圍的變化情況二分查找過程實例③在規(guī)模為n的數(shù)組d中進(jìn)行二分查找的流程圖二分查找算法流程圖④實現(xiàn)此算法的Python程序如下：key=12d=[6,12,15,18,22,25,28,35,46,58,60]f=False#i和j定義子數(shù)組的邊界，一開始搜索的是整個數(shù)組i=0j=len(d)–1whilei<=j:m=(i+j)//2ifd[m]==key:f=Trueb=mbreakifkey<d[m]:#到左邊去找j=m–1else:#到右邊去找i=m+1iff==True:print("查找成功！第"+str(b)+"個")else:print("沒有找到！")（5）拓展鏈接：二分查找算法的遞歸實現(xiàn)二分查找過程中的每一次判斷都是將需要查找的值和數(shù)組的中間值進(jìn)行不斷的比較，直到找到或找遍整個序列。①二分查找算法可利用遞歸來實現(xiàn)，程序如右表：defbsearch(s,array):iflen(array)==0:print("未找到！")returnFalsemid=(len(array)–1)//2ifarray[mid]==s:print("找到了！")returnTrueelifs<array[mid]:returnbsearch(s,array[:mid])else:returnbsearch(s,array[mid+1:])key=12d=[6,12,15,18,22,25,28,35,46,58,60]print(bsearch(key,d))②二分查找與二叉樹?二分查找過程可用一棵二叉樹來描述，樹中的每個根節(jié)點對應(yīng)當(dāng)前查找區(qū)間的中點元素，它的左子樹和右子樹分別對應(yīng)該區(qū)間的左子表和右子表。通常把此樹稱為二分查找的判定樹。?在有序表上二分查找一個關(guān)鍵字等于key的元素時，對應(yīng)著判定樹中從根節(jié)點到待查節(jié)點的一條路徑，與關(guān)鍵字進(jìn)行比較的次數(shù)就等于該路徑上的節(jié)點數(shù)，或者說等于待查節(jié)點的層數(shù)。?查找key為12的元素時，從根節(jié)點到待查節(jié)點的一條路徑為25→15→6→12，比較次數(shù)為4次。通過觀察可知，在n個元素排序的順序表里，某一次查找過程中，所做比較次數(shù)不超過判定樹的高度加1，即log2n」+1。?由于二分查找在有序表上進(jìn)行，所以其對應(yīng)的判定樹就是一棵二叉排序樹。二分查找的判定樹實例（6）拓展鏈接：二叉排序樹二叉排序樹也稱為二叉查找樹，這種結(jié)構(gòu)的二叉樹既能實現(xiàn)排序功能，也能實現(xiàn)查找功能。①排序二叉排序樹的排序功能主要通過二叉樹的建立和遍歷過程來實現(xiàn)，其在建立過程中要始終滿足如下性質(zhì)：（a）若它的左子樹不為空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值。（b）若它的右子樹不為空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值。（c）它的左右子樹也分別為二叉排序樹。一組數(shù)據(jù)“23，20，13，18，14，11”建立的二叉排序樹如右圖所示，對此二叉樹進(jìn)行中序遍歷時，結(jié)果為從小到大的有序序列：11，13，14，18，20，23。二叉排序樹②查找二叉查找樹的查找過程為：首先將給定值和根節(jié)點的關(guān)鍵字比較，若相等，則查找成功；若不相等，則根據(jù)給定值和根節(jié)點關(guān)鍵字之間的大小關(guān)系，在左子樹或右子樹中繼續(xù)進(jìn)行查找。若查到為空樹時，說明該樹中沒有待查記錄，故查找不成功。在上圖中所示的二叉查找樹中查找關(guān)鍵字key為14的節(jié)點，則查找過程為：（a）先將數(shù)據(jù)14與根節(jié)點中的數(shù)據(jù)23比較，由于14小于23，則在左子樹中繼續(xù)查找。（b）將數(shù)據(jù)14與節(jié)點數(shù)據(jù)20比較，由于14小于20，則在左子樹中繼續(xù)查找。（c）將數(shù)據(jù)14與節(jié)點數(shù)據(jù)13比較，由于14大于13，則在右子樹中繼續(xù)查找。（d）同樣的方法繼續(xù)查找，當(dāng)找到節(jié)點數(shù)據(jù)14時，與要查找的數(shù)據(jù)相等，則查找成功。（7）探討與討論①用對分查找從數(shù)列3、6、7、10、12、16、25、30、75中查找數(shù)據(jù)10，則依次訪問的數(shù)據(jù)為()A.12、6、7、10 B.12、7、10C.12、6、10 D.12、7、6、10②某二分查找算法的程序如下：i＝0j＝7n＝10whilei<＝j(luò)：n＝n＋1m＝(i＋j)//2ifkey＝＝d[m]：breakelifkey>d[m]：j＝m－1else：i＝m＋1數(shù)組元素d[0]到d[7]的值依次為″83，75，62，41，33，27，16，2″，若運行該程序段后，n的值為2，則key的值可能是()A.62或16B.62或27C.75或27D.75或16三、排序算法的應(yīng)用查找算法在實際生活中的應(yīng)用航空公司VIP會員積分查詢：不少航空公司都會提供優(yōu)惠的會員服務(wù)，當(dāng)某會員飛行里程累積達(dá)到一定數(shù)量后，可以使用里程積分兌換獎勵機(jī)票或獎勵升艙等服務(wù)?，F(xiàn)給定某航空公司部分VIP會員的飛行里程、積分等信息，要求實現(xiàn)根據(jù)VIP號碼快速查詢會員積分的功能。某航空公司的部分會員信息表1.抽象與建模從表中的數(shù)據(jù)可以看出，每個會員的信息是一條記錄，包括VIP號、姓名、飛行里程、積分等數(shù)據(jù)項。要顯示某個會員的積分信息，先得從多條記錄中查找到該會員的記錄，如下所示：若用a[i]表示該條記錄，則該會員的積分可采用以下形式表示：a[i][3]（表示該條記錄的第4個數(shù)據(jù)項的值）2.設(shè)計算法與數(shù)據(jù)結(jié)構(gòu)對表格數(shù)據(jù)可采用4個一維數(shù)組按列或1個一維數(shù)組按行來存儲。要顯示某個會員的積分，先要從多條會員信息的數(shù)據(jù)中找到該會員。查找可采用順序查找算法或二分查找算法。從算法的時間復(fù)雜度方面考慮，二分查找算法的效率高于順序查找算法，但若采用二分查找算法，被查找的數(shù)據(jù)序列必須是有序的，即要按VIP號為關(guān)鍵字進(jìn)行排序。3.編寫程序(1)假如數(shù)據(jù)以1個一維數(shù)組按行來存儲，利用二分查找算法查找，程序如下：importcsv#數(shù)據(jù)讀入csvFile=open("vip.csv","r")reader=csv.reader(csvFile)a=[]foriteminreader:a.append(item)csvFile.close()#排序defbubble_sort(d):foriinrange(1,len(d)):forjinrange(1,len(d)–i):ifint(d[j][0])>int(d[j+1][0]):temp=d[j]d[j]=d[j+1]d[j+1]=temp#二分查找defbsearch(s,array):i=1#查找范圍不包含第一行數(shù)據(jù)j=len(array)–1whilei<=j:m=(i+j)//2ifint(array[m][0])==s:returnmifs<int(array[m][0]):j=m–1else:i=m+1return–1#未找到返回–1bubble_sort(a)key=int(input('請輸入要查詢的VIP號：'))m=bsearch(key,a)ifm!=–1:print(a[m][1],"先生/女士，您的積分為：",a[m][3])else:print('找不到VIP號對應(yīng)的用戶信息！')運行程序，當(dāng)輸入VIP編號“600815”時，程序輸出“李亞東先生/女士，您的積分為：436”的信息。4.探討與討論四、課堂小練五、小結(jié)1.查找(1)概念(2)條件2.常見的查找算法(1)順序查找①算法思想②算法特點③算法演算(2)二分查找①算法思想②算法特點③算法演算(3)拓展鏈接①二分查找算法的遞歸實現(xiàn)②二叉排序樹3.查找算法的應(yīng)用(1)案例講解①抽象與建模②設(shè)計算法與數(shù)據(jù)結(jié)構(gòu)③編寫程序“在成績查詢系統(tǒng)中查找某學(xué)號”為例，通過算法演算，深入淺出的解析這一過程。實現(xiàn)此算法的Python程序。順序查找算法，那么同學(xué)們可以將其寫成函數(shù)的形式，后續(xù)直接調(diào)用即可。深入淺出的解析這一過程。實現(xiàn)此算法的Python程序。拓展鏈接，二分查找算法的遞歸實現(xiàn)，在此基礎(chǔ)上，加深對二分查找的理解，融入遞歸的知識，與之前章節(jié)的知識先后呼應(yīng)。將二分查找與二叉樹進(jìn)行結(jié)合，讓學(xué)生更好的理解二分查找。拓展鏈接，二叉排序樹，在此基礎(chǔ)上，加深對二分查找的理解，融入二叉樹的知識，與之前章節(jié)的知識先后呼應(yīng)。將排序算法的應(yīng)用進(jìn)行抽象化的展示，通過生活中的例子：航空公司VIP會員積分查詢，這一案例的講解，從三個方面循序漸進(jìn)的深入解析，抽象與建模讓學(xué)生理解Python中的查找函數(shù)如何解決實際中的問題，然后設(shè)計算法與數(shù)據(jù)結(jié)構(gòu)讓學(xué)生體驗用Python中的查找函數(shù)解決問題的基本流程，最后編寫程序，逐步形成運用Python中的查找函數(shù)解決問題的思維方式和學(xué)科方法。按照由粗到細(xì)、逐步求精的策略,推動學(xué)生加深對順序查找、二分查找的深刻認(rèn)識。課堂練習(xí)（有題有答案有解析）1.查找又稱，計算機(jī)根據(jù)所給條件查找出滿足條件的對象，即尋找出，或者確定在該批數(shù)據(jù)內(nèi)是否存在這樣的數(shù)據(jù)。2.若沒有找到滿足條件的對象，則返回特定值，表明查找；若查找到滿足條件的對象，則表明查找，一般要求返回。3.順序查找又稱，從的一端開始，依次將每個元素的關(guān)鍵字與給定值key（查找鍵）進(jìn)行比較。若某個元素的關(guān)鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。4.順序查找將待查找的數(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é)點對應(yīng)當(dāng)前查找區(qū)間的中點元素，它的左子樹和右子樹分別對應(yīng)該區(qū)間的左子表和右子表，通常把此樹稱為。8.二叉排序樹的排序功能主要通過二叉樹的和過程來實現(xiàn)。9.二叉查找樹的查找過程為：首先將給定值和根節(jié)點的比較，若相等，則查找成功；若不相等，則根據(jù)給定值和根節(jié)點關(guān)鍵字之間的大小關(guān)系，在或中繼續(xù)進(jìn)行查找。若查到為時，說明該樹中沒有待查記錄，故查找不成功。10.給定任意的查找鍵，在序列3,5,8,12,15,23中進(jìn)行數(shù)據(jù)查找，下列說法不正確的是（）A.若用順序查找實現(xiàn)，則最少查找1次B.若用二分查找實現(xiàn)，則最少查找1次C.若用順序查找實現(xiàn)，則最多查找6次D.若用二分查找實現(xiàn)，則最多查找4次11.若線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則適用的查找方法為()。A.隨機(jī)查找B.散列查找C.二分查找D.順序查找參考答案：1.檢索、在存儲的一批數(shù)據(jù)內(nèi)、一個特定的數(shù)據(jù)2.失敗、成功、該對象的存儲位置或?qū)ο笾当旧?.線性查找、順序表4.順序查找將待查找的數(shù)值與序列中的數(shù)逐個進(jìn)行比較，直到找出與給定數(shù)值相同的數(shù)為止，其算法簡單，時間復(fù)雜度為O(n)。5.折半查找、對分查找、有序的、有序數(shù)組、中間位置、不同、前半部分、后半部分6.整個序列7.一棵二叉樹、二分查找的判定樹。8.建立、遍歷9.關(guān)鍵字、左子樹、右子樹、空樹10.答案：D[解析]順序查找時從頭到尾逐個查找，數(shù)組中共有6個元素，所以最少可能一次找到，最多數(shù)組每個元素查找一遍共六次;二分查找查找的最多次數(shù)為logzn+1次，由于數(shù)組共有6個元素，所以最多查找次數(shù)為3次，最少為1次。綜合以上信息，D項說法錯誤故選:D。11.答案：A[解析]隨機(jī)查找表中元素時，訪問表中任一元素所需時間與元素的位置和排列次序無關(guān)。以散列方式存儲和查找數(shù)據(jù)時，元素的存儲位置與其關(guān)鍵字相關(guān)。二分法查找只能在有序順序表中進(jìn)行。由于鏈表中的元素只能通過取得元素所在的節(jié)點的指針進(jìn)行，因此只能順序查找表中的元素。課堂小結(jié)課堂小結(jié)一、查找1.概念2.條件二、常見的查找算法1.順序查找（1）算法思想（2）算法特點（3）算法演算2.二分查找（1）算法思想（2）算法特點（3）算法演算3.拓展鏈接（1）二分查找算法的遞歸實現(xiàn)（2）二叉排序樹三、查找算法的應(yīng)用1.案例講解（1）抽象與建模（2）設(shè)計算法與數(shù)據(jù)結(jié)構(gòu)（3）編寫程序作業(yè)設(shè)計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，下列選項中不正確的是()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ù)據(jù)必須有序B.對分查找時，被查找的數(shù)據(jù)不一定有序C.順序查找總能找到要查找的關(guān)鍵字D.一般情況下，對分查找的效率較高7.下列有關(guān)查找的說法中,不正確的是（）A.采用順序查找時,被查找的數(shù)據(jù)集中的元素?zé)o須有序B.采用二分查找時,被查找的數(shù)據(jù)集中的元素必須有序C.二分查找總能找到要查的鍵值D.二分查找的效率通常比順序查找高8.下列有關(guān)查找的說法，正確的是（）A.進(jìn)行對分查找時，被查找的數(shù)據(jù)必須已按升序排列B.進(jìn)行對分查找時，若查找的數(shù)據(jù)不存在，則無須輸出結(jié)果C.在《新華字典》中查找某個漢字，最適合使用順序查找D.對規(guī)模為n的數(shù)據(jù)進(jìn)行順序查找，平均查找次數(shù)是9.運用二分查找算法可以提高查找的效率，前提是待查找序列必須是()排序的。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ù)時，第1次查找的數(shù)據(jù)是d[3]C.使用二分查找任何查找鍵時，查找的次數(shù)最少3次D.使用二分查找數(shù)據(jù)時，第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.答案：C[解析]利用對分查找的原理可以，第一次訪問5位置的55，55<93，所以第二次訪問81，82<93，第三次訪問93，故選:C.2.答案：B[解析]順序查找是比數(shù)據(jù)的第一個元素開始依次比較，AC兩項分別查找53和70的次數(shù)為5次和8次，說法正確;B項對分查找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個元素,因此使用順序查找時,共查找3次。使用二分查找時,依次被訪問的數(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é)合選項，可知依次需要進(jìn)行比較的數(shù)據(jù)可能是4。故選A。6.答案：D[解析]順序查找對被查找的數(shù)據(jù)是否有序沒有要求而對分查找時被查找的數(shù)據(jù)必須有序。故A、B選項錯誤。順序查找和對分查找都不能保證一定能找到要查找的關(guān)鍵字，C選項錯誤。順序查找是對全部范圍內(nèi)的每個元素依次進(jìn)行比較，而對分查找每次對一半范圍內(nèi)的數(shù)據(jù)進(jìn)行比較，一般來說，對分查找的效率比順序查找要高，D選項正確。故選