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

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