数据结构大单元
——对分查找基础练习
班级 姓名
1. 用顺序查找在长度为10的某个数组中找某数,最少查找 次,最多查找 次;
用对分查找在长度为10的某个数组中找某数,最少查找 次,最多查找 次;
2. 用顺序查找在长度为n的某个数组中找某数,最少查找 次,最多查找 次;
用对分查找在长度为n的某个数组中找某数,最少查找 次,最多查找 次;
3.用顺序查找查找某数时,数组中的数据可以是无序的;
用对分查找查找某数时,每次查找后,为什么可以直接忽略另一半?被查找数据或数组中的数据是
(选填:有序/无序)。
天猫精灵X5版本的价格是299元,如果用经典对分查找思想猜价格,价格范围是200—400元(按整猜):
※ 在【200,400】中寻找299:
第一次猜价范围是 【200,400】 元,具体猜的价格是 300 元;
第二次猜价范围是 元,具体猜的价格是 249 元;
第三次猜价范围是 【250,299】 元,具体猜的价格是 元;
第四次猜价范围是 元,具体猜的价格是 元;
第五次猜价范围是 元,具体猜的价格是 元;
第六次猜价范围是 元,具体猜的价格是 元;
第七次猜价范围是 元,具体猜的价格是 元;
第八次猜价范围是 元,具体猜的价格是 元;
第九次猜价范围是 元,具体猜的价格是 元;
第十次猜价范围是 元,具体猜的价格是 元;
第十一次猜价范围是 元,具体猜的价格是 元;
※ 事实上【200,400】中共有201个整数,用经典对分思想只需要猜 次,299猜中之后需要继续猜么? (选填:是/否)
5.数组a的值为[18,21,34,45,56,68,72,89],数组中数据是否有序 (选填:有序/无序),是否符合对分查找的要求 (选填:是/否),用对分查找查找某数时,最少查找 次,最多查找 次,最多查找次数出现在45的 边(选填:左/右);
※ 在该数组中寻找18:
第一次查找数据的范围是 a[0]—a[7] ,具体比对的数组元素是 a[3] ,元素值是 45 ;
第二次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
第三次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
是否需要继续查找 (选填:是/否),总共查找了 次。
※ 在该数组中寻找5:
第一次查找数据的范围是 a[0]—a[7] ,具体比对的数组元素是 a[3] ,元素值是 45 ;
第二次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
第三次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
是否需要继续查找 (选填:是/否),总共查找了 次。
※ 在该数组中寻找72:
第一次查找数据的范围是 a[0]—a[7] ,具体比对的数组元素是 a[3] ,元素值是 45 ;
第二次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
第三次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
是否需要继续查找 (选填:是/否),总共查找了 次。
※ 在该数组中寻找83:
第一次查找数据的范围是 a[0]—a[7] ,具体比对的数组元素是 a[3] ,元素值是 45 ;
第二次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
第三次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
第四次查找数据的范围是 ,具体比对的数组元素是 ,元素值是 ;
是否需要继续查找 (选填:是/否),总共查找了 次。
6.有如下python程序段:
key=int(input("请输入待查数据: "))
b=[5,8,11,21,32,39,56,65,72]
i=0 ; j=len(b)-1
while i <= j:
m = (i+j)//2
if key == b[m]:
break
elif key < b[m]:
j = m-1
else:
i = m+1
※ 假如输入的值是5,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否), 是否需要继续查找 (选填:是/否),总共查找了 次,找到退出循环时,i与j关系的python表达式可以是 。
※ 假如输入的值是9,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),是否需要继续查找 (选填:是/否),总共查找了 次,找不到退出循环时,i与j关系的python表达式可以是 、 。
※ 假如输入的值是20,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第四次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),是否需要继续查找 (选填:是/否),总共查找了 次,找不到退出循环时,i与j关系的python表达式可以是 、 。
※ 假如输入的值是80,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第四次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),是否需要继续查找 (选填:是/否),总共查找了 次,找不到退出循环时,i与j关系的python表达式可以是 、 。
7.有如下python程序段:
key=int(input("请输入待查数据: "))
b=[5,8,11,21,21,21,56,65,72]
i=0 ; j=len(b)-1
while i <= j:
m = (i+j)//2
if key <= b[m]:
j = m-1
else:
i = m+1
※ 假如输入的值是5,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),找到了是否立即退出循环 (选填:是/否),总共查找了 次,执行以上代码退出循环时,i与j关系的python表达式可以是 、 。
※ 假如输入的值是9,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),是否需要继续查找 (选填:是/否),总共查找了 次,执行以上代码退出循环时,i与j关系的python表达式可以是 、 。
※ 假如输入的值是21,按照提示执行代码:
在进入while循环前i初值是 ,j初值是 ,key值是 ;
第一次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),是否需要继续查找 (选填:是/否),
第二次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第三次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
第四次循环执行后,m值是 ,b[m]值是 ,i值是 ,j值是 ;
是否找到 (选填:是/否),找到了是否立即退出循环 (选填:是/否),
总共查找了 次,执行以上代码退出循环时,i与j关系的python表达式可以是 、 。
变量i和j有什么特殊含义 。
8.有如下python程序段:
key=int(input("请输入待查数据: "))
b=[5,8,11,21,21,21,56,65,72]
i=0 ; j=len(b)-1 ; x=""
while i <= j:
m = (i+j)//2
if key < b[m]:
j = m-1 ; x=x+"L"
else:
i = m+1 ; x=x+"R"
※ 假如输入的值是5,执行以上代码后x的值为 ,i值是 ,j值是 ;
※ 假如输入的值是9,执行以上代码后x的值为 ,i值是 ,j值是 ;
※ 假如输入的值是11,执行以上代码后x的值为 ,i值是 ,j值是 ;
※ 假如输入的值是21,执行以上代码后x的值为 ,
变量i和j有什么特殊含义 。
※ 假如输入的值是35,执行以上代码后x的值为 ,i值是 ,j值是 ;
※ 假如输入的值是56,执行以上代码后x的值为 ,i值是 ,j值是 ;
※ 假如输入的值是68,执行以上代码后x的值为 ,i值是 ,j值是 ;
※ 假如输入的值是72,执行以上代码后x的值为 ,i值是 ,j值是 ;