5.4 数据查找（分层作业）信息技术浙教版2019选择性必修1

5.4数据查找 2课时（分层作业） 【基础达标】 1.查找又称 ，计算机根据所给条件查找出满足条件的对象，即 寻找出 ，或者确定在该批数据内是否存在这样的数据。 2.若没有找到满足条件的对象，则返回特定值，表明查找 ；若查找到满足条件的对象，则表明查找 ，一般要求返回 。 3.顺序查找又称 ，从 的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 4.顺序查找将待查找的数值与序列中的数 ，直到找出与给定数值相同的数为止，其算法简单，时间复杂度为 。 5.二分查找又称 、 。它是一种效率很高的查找方法，但被查找的数据序列必须是 。二分查找首先将查找键与 内处于 位置的元素进行比较，如果中间位置上的元素的数值与查找键 ，根据数组元素的有序性，就可确定在数组的 还是 继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 6.二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍 。 7.二分查找过程可用 来描述，树中的每个根节点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，通常把此树称为 。 8.二叉排序树的排序功能主要通过二叉树的 和 过程来实现。 9.二叉查找树的查找过程为：首先将给定值和根节点的 比较，若相等，则查找成功；若不相等，则根据给定值和根节点关键字之间的大小关系，在 或 中继续进行查找。若查到为 时，说明该树中没有待查记录，故查找不成功。 10.给定任意的查找键，在序列3,5,8,12,15,23中进行数据查找，下列说法不正确的是（） A.若用顺序查找实现，则最少查找1次 B.若用二分查找实现，则最少查找1次 C.若用顺序查找实现，则最多查找6次 D.若用二分查找实现，则最多查找4次 11.若线性表采用链式存储结构，则适用的查找方法为()。 A.随机查找 B.散列查找 C.二分查找 D.顺序查找 【巩固提升】 1.某数组有10个元素，依次为10、23、32、40、55、64、77、81、93、100，若采用对分查找法在该数组中查找数据93，依次被访问的数据为() A.64、81、92 B.55、77、81、93 C.55、81、93 D.64、81、100、93 2.数组里有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.分别使用顺序查找算法和二分查找算法在数据序列“5,6,10,13,15,20,21.26,30”中查找 数据10,下列关于查找的次数的说法中正确的是() A.顺序查找2次,二分查找3次 B.顺序查找3次,二分查找2次 C.顺序查找3次,二分查找3次 D.顺序查找3次,二分查找4次 4.在10个有序的数“21,45,56,65,68,72,79,83,88,96"中查找75,则依次需要进行比较的数据是（） A.68，83，72 B.21，45，56，65，68，72，79 C.68，83，72，79 D.68，45，56，65 5.在7个有序的数列“1，2，3，4，5，6，7”中，采用二分查找法查找数值key，依次需要 进行比较的数据可能是() A.4 B.4，6，2 C.4，2，5 D.4，6，5，7 6.下列有关查找的说法中，正确的是() A.顺序查找时，被查找的数据必须有序 B.对分查找时，被查找的数据不一定有序 C.顺序查找总能找到要查找的关键字 D.一般情况下，对分查找的效率较高 7.下列有关查找的说法中,不正确的是（） A.采用顺序查找时,被查找的数据集中的元素无须有序 B.采用二分查找时,被查找的数据集中的元素必须有序 C.二分查找总能找到要查的键值 D.二分查找的效率通常比顺序查找高 8.下列有关查找的说法，正确的是（） A.进行对分查找时，被查找的数据必须已按升序排列 B.进行对分查找时，若查找的数据不存在，则无须输出结果 C.在《新华字典》中查找某个汉字，最适合使用顺序查找 D.对规模为n的数据进行顺序查找，平均查找次数是 9.运用二分查找算法可以提高查找的效率，前提是待查找序列必须是()排序的。 A.递增 B.递减 C.有序 D.无序 10.已知单调函数f()在[0,1]区间上存在一个x0，使f(x0)=0。现用对分查找法搜索x0的值，开始搜索区间为[0,1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为（） A. B. C.1/102 D.1/210 11.8位同学的语文数学成绩总分从高到低为“178，176，173，172，170，168，163，160。用二分查找法178的过程中，依次被访问到的成绩数据是() A.178 B.172，176，178 C.172，173，178 D.172，173，176，178 12.7位学生的身高(单位cm)从高到低依次为:178，177，175，172，170，165，162.用对分查找法找到178的过程中，依次被访问到的数据是（） A.178 B.172，175，178 C.172，177，178 D.172，175，177，178 13.某数组d中的数据依次是[8,12,15,28,28,32,36,39]，要查找某个元素是否在数组中，下列说法正确的是() A.数组中有相同数据28，所以只能使用顺序查找 B.使用二分查找数据时，第1次查找的数据是d [3] C.使用二分查找任何查找键时，查找的次数最少3次 D.使用二分查找数据时，第2次查找的数据可能是d [1]或d [6] 14.数组P中存放着学生的相关信息，如图所示，若要查找数组中是否存在“小李”的信息，以下说法正确的是() P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) 小张 小李 小杨 小陈 小郑 小王 小邓 小周 小郭 小范 A.在数组P中既能使用顺序查找也能使用二分查找 B.在数组P中使用顺序查找需要查找2次 C.在数组P中使用二分查找需要查找4次 D.在数组P中二分查找的效率高于顺序查找 15.分别使用顺序查找算法和二分查找算法在数据序列“5,6,10,13,15,20,21,26,30”中查找数据10,下列关于查找的次数的说法中正确的是（） A.顺序查找2次,二分查找3次 B.顺序查找3次,二分查找2次 C.顺序查找3次,二分查找3次 D.顺序查找3次,二分查找4次 【链接高考】 1.用顺序查找在长度为10的某个数组中找某数，最少查找 次，最多查找 次。 用对分查找在长度为10的某个数组中找某数，最少查找 次，最多查找 次。 2.一段楼梯共有10级台阶，规定每步只能跨1级或2级，要登上第10级台阶有 种不同的走法。 3.有一段楼梯，共6级台阶，规定每一步只能跨1级、2级或3级，那么登上6级台阶有 种不同走法。 4.某查找算法的代码如下: key=inl(inpul("请输人待査元素key:")) a=[62,5,11,17,5.6,99,5,73,45] loc=-1 for i in range(len(a)): if a[i]==key: loc=i break if loc!=-1: print(loc) else: print("查无此数") (1)当输入key的值为5时,执行该代码处理后输出的结果是 。 (2)若希望输出key最后一次出现的位置,只需要对代码进行 修改操作。 (3)该查找算法的时间复杂度为 。 5.数组a存放着一组正整数,其中奇数在前,偶数在后。奇数与偶数已分别升序排序,形如[1,7,13,15,21,2,4,8,22,26,30,36,40]。 依据二分查找思想,小萌设计了一个从数组a中查找数据 key 的算法,其程序如下： i=0;j=9 key=int(input("请输人待查数据:")) while i<=j: m=(i+j)//2 if a[m]= =key:break if key%2==0 and a[m]%2==1: ① elif key%2==1 and a[m]%2==0： ② else : if ③ ： j=m-1 else : i=m+1 if i>j: print("未找到") else : print("数组元素a["+str(m)+"]即为所求!") 请在程序划线处填人合适的代码。 ① 。 ② 。 ③ 。 6.一个整数序列,如果两个相邻元素的差恰好正负(负正)交替出现,则称为该序列为摇摆序列。小王同学想求出某个数列的最长摇摆子序列以序列[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]。根据图a分析得知，当序列有一段连续的递增(或递减)时,可形成摇摆子序列,我们只需要找到每一次转折中的拐点元素。 小王编写了一个Python程序实现该功能:程序运行时,输入一串用逗号分隔和结束的数字,可 以得到最长摇摆序列的长度,以及具体的序列。 程序运行界面如图b所示: 请输入以逗号分隔和结束的数据(不超过20个数):3,14,7,6,9,12,10,8,13, 最长摇摆子序列长度为 6 最长摇摆子序列为:3,14,6,12,8,13 图b (1)若输人数据“2,4,5,3,2,1”,则最长摇摆子序列为 。 (2)实现上述功能的Python代码如下,请在划线处填入合适的代码。 s=input("请输人以逗号分隔和结束的数据(不超过 20个数):") a=[0]*20;b=[False]* 20 flag，n，i，t，ans=0，0，0，’，’ def f(n): f=1 global ans #global表示此处的ans就是全局变量ans ans=str(a[n-1]) for i in range(n-2,-1,-1) If b[i]: f=f+1 ① return f for ch in s: if ch ==”,”: a[i]= int(t);n +=1;i+= 1;t="" else : t=t+ch for i in range(l,n): gd = Tirue if flag == 0: if a[i]> a[i - 1]: flag=1 elif a[i]< a[i - 1]: flag=2 else : gd= False elif flag ==1 and a[i]<a[i-1]: flag =2 elif ② flag=1 else: gd = False ③ if f(n)< 3: print("不构成摇摆子序列") else: print("最长摇摆子序列长度为",str(í(n))) print("最长摇摆子序列为:",ans) 7.设有n个顾客同时等待一项服务,顾客主需要的服务时间为ti(1≤i≤n),应如何安排n个顾客的服务次序才能使顾客总的等待时间达到最小。这个时间是多少？ 参考答案 【基础达标】 1.检索、在存储的一批数据内、一个特定的数据 2.失败、成功、该对象的存储位置或对象值本身 3.线性查找、顺序表 4.顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其算法简单，时间复杂度为O(n)。 5.折半查找、对分查找、有序的、有序数组、中间位置、不同、前半部分、后半部分 6.整个序列 7.一棵二叉树、二分查找的判定树。 8.建立、遍历 9.关键字、左子树、右子树、空树 10.答案：D [解析]顺序查找时从头到尾逐个查找，数组中共有6个元素，所以最少可能一次找到，最多数组每个元素查找一遍共六次;二分查找查找的最多次数为logzn+1次，由于数组共有6个元素，所以最多查找次数为3次，最少为1次。综合以上信息，D项说法错误故选:D。 11.答案：A [解析]随机查找表中元素时，访问表中任一元素所需时间与元素的位置和排列次序无关。以散列方式存储和查找数据时，元素的存储位置与其关键字相关。二分法查找只能在有序顺序表中进行。由于链表中的元素只能通过取得元素所在的节点的指针进行，因此只能顺序查找表中的元素。 【巩固提升】 1.答案：C [解析]利用对分查找的原理可以，第一次访问5位置的55，55<93，所以第二次访问81，82<93，第三次访问93，故选:C. 2.答案：B [解析]顺序查找是比数据的第一个元素开始依次比较，AC两项分别查找53和70的次数为5次和8次，说法正确;B项对分查找53，i=1，j=12，m=(i+j)2=6，第6个元素为55，比53大，因此i=1，j=m-1=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 [解析]本题考查顺序查找和二分查找的算法思想。数据10是数据序列中第3个元素,因此使用顺序查找时,共查找3次。使用二分查找时,依次被访问的数据为15，6,10,即二分查找的次数也为3。 4.答案：C [解析]从10个数“21,45,56,65,68,72,79,83,88,96"中查找75的二叉判定树如图所示,故答案选C。 5.答案： [解析]该二分查找用二叉树表示如下，结合选项，可知依次需要进行比较的数据可能是4。 故选A。 6.答案：D [解析]顺序查找对被查找的数据是否有序没有要求而对分查找时被查找的数据必须有序。故A、B选项错误。顺序查找和对分查找都不能保证一定能找到要查找的关键字，C选项错误。顺序查找是对全部范围内的每个元素依次进行比较，而对分查找每次对一半范围内的数据进行比较，一般来说，对分查找的效率比顺序查找要高，D选项正确。 故选:D。 7.答案：C [解析]顺序查找对被查找的数据是否有序没有要求,而二分查找要求被查找的数据必须有序。顺序查找和二分查找都不能保证一定能我到要查找的关键字,故C选项不正确。顺序查找是对全部范围内的每个元案依次进行比较,而二分查我每次对一半范围内的数据进行比较,一般来说,二分查找的效率比顺序查找要高。 8.答案：D [解析]进行对分查找时，被查找数据必须是有序的，降序或升序，查找数据不存在，依然需要输出结果，《新华字典》中的汉字是有序的，适合采用对分查找，对规模为n的数据进行顺序查找，最多查找n次，最少查找1次，所以平均查找次数是(n+1)/2，故选:D. 9.答案：C [解析]运用二分查找法进行查找时，必须为一个有序序列，无论是升序还是降序，所以C符合题意。故选:C。 10.答案：D [解析]由题知知f(x)是单调函数，意味着f(x)已按大小有序排列，根据对分查找的概念，开始搜索区间为[0,1]，经过1次对分查找后，第2次的搜索长度变为1/2,经过2次对分查找后，第3次的搜索长度变为1/22...经过10次对分查找后，第11次的搜索长度变为1/210，故选D。 11.答案：B [解析]根据二分查找的定义可知，第一次查找为172，第二次查找为176，第三次查找为178。故选:B。 12.答案：C [解析]据题意，所有数字降序排序，对分查找时:第1次查找:将数组中的7个数字分成两半，中间位置是(1+7)/2=4，第4位是数字172,172小于查找的数字178，就在数组第4位的左边继续查找;第2次查找:在数组第1位到第3位中找，中间位置时(1+3)/2=2，第2位是数字177，177小于178，就在数组第2位的左边继续查找;第3次查找:在第1位找，第1位的数字正好等于178，查找到数字，查找结束，整个查找过程访问过的数字172，177，178;故选:C。 13.答案：B [解析]数组d中的数据是有序的，可以用二分查找法进行查找，故选项A是错误的;第一次查找时，m=3，即定位到的数据是d3，故B选项是正确的。如果第一次查找时的数据恰好是要查找的数据，那么查找次数最少是1次，故选项C是错误的;第二次查找时，d3]左边是3个元素，定位到d[1，右边是4个元素，定位到d5]，故选项D是错的。故选B。 14.答案：B [解析]对分查找虽然效率高，但是对于有序数组而言的，分析题目，P数字是没有顺序的，既不是降序也不是升序，所以不适合采用二分查找，利用顺序查找查找两次就能找见小李，故选:B. 15.答案：C [解析]本题考查顺序查找和二分查找的算法思想。数据10是数据序列中第3个元素,因此使用顺序查找时,共查找3次。使用二分查找时,依次被访问的数据为15，6，10，即二分查找的次数也为3。 【链接高考】 1.答案：1、10、1、4 [解析]本题考查的是顺序查找与对分查找的相关知识。顺序查找从数组的一端开始，顺序扫描数组，依次将扫描到的元素和给定值Key相比较。若当前扫描到的元素与Key相等，则查找成功;若扫描结束若仍未找到，则查找失败;对分查找:是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。用顺序查找在长度为10的某个数组中找某数，最少查找1次，最多查找10次;用对分查找在长度为10的某个数组中找某数，最少查找1次，最多查找4次，因为对分查找的时间复杂度为log210，即为4。 2.答案：89 [解析]由于登台阶每次只能跨1级或2级，因此登上第n级台阶的情形仅与登上第n-1级和第n一2级台阶有关，可以考虑建立递推关系。列表如下: 级数 1 2 3 4 5 6 …… 10 走法 1 2 3 4 8 13 …… 89 登上第1级台阶只有1种走法，即a1=1;登上第2级台阶有2种走法，即az-2;登上第3级台阶有3种走法，即a:-3;登上第4级台阶有5种走法，即a-5。以此类推，登上各级台阶的走法依次为1，2，3，5，8，13，21，34，55，89。其中a1=89，即登上第10级台阶有89种不同走法。 3.答案：24 [解析]假设共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() [解析]该代码实现的是输出顺序查找数组中key第一次出现的位置,key=5,所以输出的结果为1;想修改为查找出key最后一次出现的位置并输出,只需要让for循环继续查找到最后一次出现的位置并输出,所以只需要删除break语句;该代码采用一重循环枚举a数组中的所有数再与key进行对比,所以时间复杂度为O(n)。 5.答案：①i=m+1 ②j=m-1③key<a[ m ] [解析]根据题目的描述“奇数在前,偶数在后”可知:若满足 key 是偶数且中间项a[m]为奇数,则向后找;若满足 key是奇数且中间项a[m]为偶数,则向前找;如果中间项a[m]与 key同奇同偶,那么根据二分查找的思想继续查找。 6.答案：(1)2,5,1 (2)①ans=str(a[i])+’,’+ans ②flag=2 and a[i]>a[i-1] ③b[i-1]=gd [解析]本题考查数组的应用。其中列表a用于存储输入的数据元素,列表b用于记录是否为拐点，为输入的数据元素个数，ans记录最长摇摆子序列的具体元素，函数f(n)用于统计摇摆子序列的长度,若小于3,则不是摇摆子序列,若大于等于3,则构成摇摆子序列。函数f(n)中从后往前遍历b数组,若为True,则i为拐点,将元素 a[i]记录到 ans中，由于是从后往前遍历数组，因此①空书写ans=str(ai)+','+ans。flag数组用于记录摇摆序列的前一次状态,若为初始状态则为0,若为递增状态则为1,若为递减状态则为2。联系前一个elif,则这次elif情况为:前一 次状态为递减,且当前 a[i]>a[i-1]时,变换状态为递增。因此②空书写 flag==2 and a[i]>a[i-1] 循环中i从1开始进行枚举a数组元素，gd记录是否为拐点，是拐点则为True,否则是False。flag 状态未改变则不是拐点，gd值为False。由于flag是摇摆序列的前一次状态，因此状态变换时实际上拐点为 i-1,因此③空用该书写 b[i-1]=gd。 7.答案：30 [解析]1.首先要明确问题，即找到一个顺序来安排顾客的服务次序，以最小化总等待时间。 2.确定使用最短作业优先调度策略，将顾客按照服务时间排序，然后按照排序后的顺序为 顾客提供服务。 3.计算总等待时间，它是每个顾客等待时间的累加。 4.SJF 策略的关键是选择服务时间最短的顾客优先，这可以通过排序来实现。 这个问题属于经典的作业调度问题，即如何安排多个任务的执行顺序以最小化总等待时间。这个问题的目标是找到一种顺序，使得总等待时间最小。 解决这个问题的一种有效方法是使用最短作业优先调度(Shortest Job First,SJF)策略。按照服务时间(ti)的大小对顾客进行排序，然后按照排序后的顺序依次为顾客提供服务。 以下是详细的步骤和示例: 1.首先，将顾客按照服务时间从小到大排序。 2.然后，按照排序后的顺序依次为顾客提供服务。 示例: 假设有四个顾客，他们的服务时间分别是t1=5、t2=2、t3=10、t4=1.按照服务时间排序后的顺序是 t4、t2、t1、t3.然后按照 t4、t2、t1、t3 的顺序为顾客提供服务。 计算总等待时间: 总等待时间=(0+1)+(1+2)+(3+5)+(8+10)=30，所以，按照 SJF 策略，总等待时间最小为30。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$