第10讲 数据排序与查找（专项训练）（浙江专用）2027年高考信息技术一轮复习讲练测

第10讲 数据排序与查找 目录 01 课标达标练 考向01 考查冒泡排序与选择排序 考向02 考查插入排序 考向03 考查二分查找及其边界变式 02 核心突破练 03 真题溯源练 01 考查冒泡排序与选择排序【★选考高频★难点】 考纲对标：掌握冒泡排序（相邻比较、逆序交换）与选择排序（记录极值下标、一趟一换）的基本思想与代码实现，能由趟数推断序列状态，正确统计比较次数与交换次数；能根据排序过程追踪变量与数据变化。浙江选考选择题高频考查。 1.【结合校园体测成绩考查冒泡排序】某校体测身高（cm）数据存于列表a=[168,155,172,160,165]，现用冒泡排序算法对该列表进行升序排序。下列说法正确的是（ ） A. 第一趟结束后，最大值172一定位于列表末尾 B. 每一趟排序的比较次数都相同 C. 冒泡排序每一趟至多交换一次 D. 冒泡排序第一趟结束后所有元素均已有序 2.【结合图书借阅量考查选择排序】某图书馆对5本图书的月借阅量进行升序排序，借阅量列表a=[7,3,9,5,1]，采用选择排序。下列说法正确的是（ ） A. 第一趟找到最小值1并与a[0]交换 B. 每一趟都必然发生交换 C. 选择排序一趟内可能交换多次 D. 选择排序不需要记录极值下标 02 考查插入排序【★选考高频】 考纲对标：理解插入排序将待排序元素插入到已有序序列的合适位置的思想，掌握其代码实现与数据移动次数规律；能根据序列状态推导每趟插入后的结果。浙江选考选择题高频考查。 1.【结合学生成绩考查插入排序】列表a=[5,2,8,3,6]，采用插入排序（升序）进行排序。下列说法正确的是（ ） A. 第一趟从第一个元素5开始向前插入 B. 第一趟结束后序列为[2,5,8,3,6] C. 插入排序在数据完全逆序时移动次数最少 D. 插入排序无需已有有序部分即可插入 2.【结合一卡通消费记录考查插入排序】某同学一周的消费金额（元）存于列表a=[12,8,15,9,11]，用插入排序（升序）排序。下列关于数据移动次数的说法，正确的是（ ） A. 第一趟需要移动3个元素 B. 每次插入最少需要移动0个元素 C. 插入排序的数据移动次数固定不变 D. 数据基本逆序时移动次数最少 03 考查二分查找及其边界变式【★选考高频★难点】 考纲对标：掌握二分查找的前提（数据有序）与标准代码（while low<=high、mid=(low+high)//2、low=mid+1、high=mid-1），能追踪low、high、mid的变化并计算比较次数；理解查找第一个不小于某值及查找不成功等边界变式。浙江选考选择题高频考查。 1.【结合成绩单考查二分查找过程】某有序列表a=[2,5,8,12,16,23,38,56,72,91]，采用二分查找查找元素23，low、high的初值分别为0和9。下列说法正确的是（ ） A. mid的初值为5，第一次比较即可找到23 B. 二分查找会改变原列表的存储顺序 C. 查找过程中可能出现low大于high的情况 D. 二分查找对无序列表同样适用 2.【结合查找失败情形考查二分边界】有序列表a=[1,4,7,10,13,16]，用二分查找查找元素9（列表中不存在）。下列说法正确的是（ ） A. 第一次比较后查找立即结束 B. 查找过程中mid的值保持不变 C. 查找结束时low会大于high D. 查找结束后high一定等于low 【新情境：图书借阅榜・多重条件排序与二分查找】某校图书馆每月统计图书借阅量，数据以列表book存储，每个元素为[书名,借阅量]，如book=[[“算法导论”,35],[“漫画入门”,18],[“程序设计”,35],[“数学之美”,22],[“数据结构”,18]]。现编写程序实现：先按借阅量降序排序（借阅量相同按书名升序），再输出借阅量最高的前3本书，最后用二分查找查找某借阅量是否出现。请回答下列问题： （1）实现“借阅量降序、书名升序”排序时，用于判断相邻元素是否应交换、最能体现多重条件的表达式是（单选） A. book[j][1] > book[j+1][1] B. book[j][1] < book[j+1][1] or (book[j][1]==book[j+1][1] and book[j][0]>book[j+1][0]) C. book[j][0] > book[j+1][0] D. book[j][1] == book[j+1][1] （2）实现“借阅量相同按书名升序”时，比较的对象与顺序应为（单选） A. 只比较书名 B. 只比较借阅量 C. 先比较借阅量，再比较书名 D. 先比较书名，再比较借阅量 （3）排序完成后，用二分查找在book中查找借阅量18是否出现。下列说法正确的是（单选） A. 二分查找要求数据有序，降序序列同样可以进行二分查找 B. 二分查找只能用于升序序列 C. 使用二分查找前必须先执行一次冒泡排序 D. 二分查找的比较次数一定少于顺序查找 （4）用冒泡排序实现上述排序，程序片段如下： for i in range(len(book)-1): for j in range(len(book)-1-i): if ①: book[j], book[j+1] = book[j+1], book[j] ①处应填入的代码为：______ 【新情境：校园一卡通消费查询・排序与顺序/二分查找】某校园一卡通系统记录学生月消费金额，存入列表fee=[58,72,35,90,66,45,80,62]。现编写程序实现：先对fee升序排序，再用顺序查找查询金额35在列表中的位置，并统计高于平均消费金额的人数。请回答下列问题： （1）对长度为n的升序列表采用顺序查找查找一个存在的元素，最多需要比较的次数是（单选） A. 1次 B. n-1次 C. n次 D. n/2次 （2）若改用二分查找在有序列表fee中查找金额，下列说法正确的是（单选） A. 二分查找不受“数据有序”这一前提的限制 B. 二分查找每次比较后都要访问列表的全部元素 C. 二分查找每次比较后能排除约一半的待查元素 D. 二分查找的最坏比较次数一定小于顺序查找 （3）统计“高于平均消费金额”的人数，程序片段如下： avg = sum(fee) / len(fee) cnt = 0 for x in fee: if ①: cnt += 1 ①处应填入的代码为：______ 1.（选考真题・2023年1月浙江信息技术选考 第10题）列表s包含8个互不相等的元素，即s[0]、s[1]、s[2]、……、s[7]，有如下Python程序段： n = 8 for i in range(1, n - 1): for j in range(1, n - i - 1): if s[j] > s[j - 1]: s[j], s[j - 1] = s[j - 1], s[j] 该程序段实现的是（ ） A. s[0]到s[5]的降序排列 B. s[1]到s[6]的降序排列 C. s[1]到s[7]的升序排列 D. s[2]到s[6]的升序排列 2.（选考真题・2025年6月浙江信息技术选考 第12题）定义如下函数，返回key在列表data中的下标，若key不存在则返回-1。 def bsearch(data, key): i, j = 0, len(data) - 1 while i <= j: m = (i + j) // 2 for k in range(m - 1, m + 2): if i <= k <= j and data[k] == key: return k if data[m] < key: i = m + 2 else: j = m - 2 return -1 如果调用函数返回结果不正确，则data可能是（ ） A. [16,19,18,22,20,29,25] B. [16,19,20,18,22,25,29] C. [18,16,19,20,22,29,25] D. [18,16,20,19,25,22,29] 3.（选考真题・2021年1月浙江信息技术选考 第11题）采用冒泡排序算法对某数据序列进行排序，经过第一轮排序后的结果是“2，8，3，9，5，6，7”，那么原数据序列不可能的是（ ） A. 8，3，9，5，2，7，6 B. 8，3，9，2，6，5，7 C. 8，2，9，3，5，7，6 D. 8，3，2，9，6，5，7 4.（选考真题・2021年1月浙江信息技术选考 第12题）某对分查找算法的VB程序段如下： 随机产生包含20个整型元素的升序序列，依次存入数组a，代码略 i = 1：j = 20：s = "" key = Val(Text1.Text) Do While i <= j m = (i + j) \ 2 s = s + Str(a(m)) If a(m) = key Then Exit Do If a(m) > key Then j = m - 1 Else i = m + 1 Loop Text2.Text = s 在文本框Text1中输入待查找数，执行该程序段后，下列选项中，文本框Text2中显示的内容不可能的是（ ） A. 78 50 46 33 B. 51 37 41 48 C. 74 50 46 51 D. 73 83 87 89 学科网（北京）股份有限公司1 / 17 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $ 第10讲 数据排序与查找 目录 01 课标达标练 考向01 考查冒泡排序与选择排序 考向02 考查插入排序 考向03 考查二分查找及其边界变式 02 核心突破练 03 真题溯源练 01 考查冒泡排序与选择排序【★选考高频★难点】 考纲对标：掌握冒泡排序（相邻比较、逆序交换）与选择排序（记录极值下标、一趟一换）的基本思想与代码实现，能由趟数推断序列状态，正确统计比较次数与交换次数；能根据排序过程追踪变量与数据变化。浙江选考选择题高频考查。 1.【结合校园体测成绩考查冒泡排序】某校体测身高（cm）数据存于列表a=[168,155,172,160,165]，现用冒泡排序算法对该列表进行升序排序。下列说法正确的是（ ） A. 第一趟结束后，最大值172一定位于列表末尾 B. 每一趟排序的比较次数都相同 C. 冒泡排序每一趟至多交换一次 D. 冒泡排序第一趟结束后所有元素均已有序 【答案】A 【解析】本题考查冒泡排序的过程。 A正确：冒泡排序升序时，每趟将未排序部分的最大值“冒泡”到末尾，第一趟后172必定到达最后； B错误：第一趟比较4次，之后每趟比较次数依次递减； C错误：一趟内相邻逆序元素可能发生多次交换； D错误：第一趟只确定最后一个元素的位置，其余元素仍需继续排序。 2.【结合图书借阅量考查选择排序】某图书馆对5本图书的月借阅量进行升序排序，借阅量列表a=[7,3,9,5,1]，采用选择排序。下列说法正确的是（ ） A. 第一趟找到最小值1并与a[0]交换 B. 每一趟都必然发生交换 C. 选择排序一趟内可能交换多次 D. 选择排序不需要记录极值下标 【答案】A 【解析】本题考查选择排序。 A正确：选择排序每趟找出未排序部分最小值的下标，再将其与最前位置交换； B错误：若最前位置本已是最小值，则本趟不交换； C错误：选择排序每趟至多交换一次； D错误：选择排序必须记录极值下标，一趟结束后才进行交换。 02 考查插入排序【★选考高频】 考纲对标：理解插入排序将待排序元素插入到已有序序列的合适位置的思想，掌握其代码实现与数据移动次数规律；能根据序列状态推导每趟插入后的结果。浙江选考选择题高频考查。 1.【结合学生成绩考查插入排序】列表a=[5,2,8,3,6]，采用插入排序（升序）进行排序。下列说法正确的是（ ） A. 第一趟从第一个元素5开始向前插入 B. 第一趟结束后序列为[2,5,8,3,6] C. 插入排序在数据完全逆序时移动次数最少 D. 插入排序无需已有有序部分即可插入 【答案】B 【解析】本题考查插入排序。 A错误：插入排序默认第一个元素已有序，从第二个元素开始向前插入； B正确：第一趟将2插入到5之前，得到[2,5,8,3,6]； C错误：数据完全逆序时移动次数最多，基本有序时最少； D错误：插入排序须将新元素插入到已有序部分。 2.【结合一卡通消费记录考查插入排序】某同学一周的消费金额（元）存于列表a=[12,8,15,9,11]，用插入排序（升序）排序。下列关于数据移动次数的说法，正确的是（ ） A. 第一趟需要移动3个元素 B. 每次插入最少需要移动0个元素 C. 插入排序的数据移动次数固定不变 D. 数据基本逆序时移动次数最少 【答案】B 【解析】本题考查插入排序的数据移动。 A错误：第一趟仅将a[1]向前比较，最坏移动1个元素，不可能移动3个； B正确：若待插入元素已处于正确位置（不小于前一个元素），则无需移动，移动次数可为0； C错误：移动次数取决于数据的初始顺序； D错误：基本有序时移动次数最少，逆序时最多。 03 考查二分查找及其边界变式【★选考高频★难点】 考纲对标：掌握二分查找的前提（数据有序）与标准代码（while low<=high、mid=(low+high)//2、low=mid+1、high=mid-1），能追踪low、high、mid的变化并计算比较次数；理解查找第一个不小于某值及查找不成功等边界变式。浙江选考选择题高频考查。 1.【结合成绩单考查二分查找过程】某有序列表a=[2,5,8,12,16,23,38,56,72,91]，采用二分查找查找元素23，low、high的初值分别为0和9。下列说法正确的是（ ） A. mid的初值为5，第一次比较即可找到23 B. 二分查找会改变原列表的存储顺序 C. 查找过程中可能出现low大于high的情况 D. 二分查找对无序列表同样适用 【答案】C 【解析】本题考查二分查找的过程。 A错误：mid=(0+9)//2=4，a[4]=16，第一次比较后令low=5；再mid=(5+9)//2=7，a[7]=56，令high=6；再mid=(5+6)//2=5，a[5]=23找到，共比较3次； B错误：二分查找不改变列表的存储顺序； C正确：查找不成功时最终会出现low>high，从而结束循环； D错误：二分查找的前提是列表有序。 2.【结合查找失败情形考查二分边界】有序列表a=[1,4,7,10,13,16]，用二分查找查找元素9（列表中不存在）。下列说法正确的是（ ） A. 第一次比较后查找立即结束 B. 查找过程中mid的值保持不变 C. 查找结束时low会大于high D. 查找结束后high一定等于low 【答案】C 【解析】本题考查二分查找不成功的边界。 A错误：需要多轮比较收缩区间才能确定9不存在； B错误：每轮low或high收缩，mid随之改变； C正确：未找到时low与high交错，出现low>high，循环条件不成立而结束； D错误：结束时low>high，而非相等。 【新情境：图书借阅榜・多重条件排序与二分查找】某校图书馆每月统计图书借阅量，数据以列表book存储，每个元素为[书名,借阅量]，如book=[[“算法导论”,35],[“漫画入门”,18],[“程序设计”,35],[“数学之美”,22],[“数据结构”,18]]。现编写程序实现：先按借阅量降序排序（借阅量相同按书名升序），再输出借阅量最高的前3本书，最后用二分查找查找某借阅量是否出现。请回答下列问题： （1）实现“借阅量降序、书名升序”排序时，用于判断相邻元素是否应交换、最能体现多重条件的表达式是（单选） A. book[j][1] > book[j+1][1] B. book[j][1] < book[j+1][1] or (book[j][1]==book[j+1][1] and book[j][0]>book[j+1][0]) C. book[j][0] > book[j+1][0] D. book[j][1] == book[j+1][1] （2）实现“借阅量相同按书名升序”时，比较的对象与顺序应为（单选） A. 只比较书名 B. 只比较借阅量 C. 先比较借阅量，再比较书名 D. 先比较书名，再比较借阅量 （3）排序完成后，用二分查找在book中查找借阅量18是否出现。下列说法正确的是（单选） A. 二分查找要求数据有序，降序序列同样可以进行二分查找 B. 二分查找只能用于升序序列 C. 使用二分查找前必须先执行一次冒泡排序 D. 二分查找的比较次数一定少于顺序查找 （4）用冒泡排序实现上述排序，程序片段如下： for i in range(len(book)-1): for j in range(len(book)-1-i): if ①: book[j], book[j+1] = book[j+1], book[j] ①处应填入的代码为：______ 【答案】(1)B；(2)C；(3)A；(4)①book[j][1] < book[j+1][1] or (book[j][1]==book[j+1][1] and book[j][0]>book[j+1][0]) 【解析】本题考查多重条件排序与二分查找的综合应用。 （1）先比借阅量book[j][1]，借阅量相同时再比书名book[j][0]，故选B； （2）“借阅量降序、书名升序”需先比主关键字（借阅量），相同时再比次关键字（书名），故选C； （3）二分查找只要求数据有序（升序或降序均可），A正确，B错误；若数据本已有序则无需再排序，C错误；D的比较次数并不总小于顺序查找，D错误； （4）降序要求前一个借阅量大于后一个才不交换，即借阅量升序（book[j][1] < book[j+1][1]）时交换；借阅量相同时，按书名升序，书名大的在后应交换（book[j][0] > book[j+1][0]），故①处填入上述条件。 【新情境：校园一卡通消费查询・排序与顺序/二分查找】某校园一卡通系统记录学生月消费金额，存入列表fee=[58,72,35,90,66,45,80,62]。现编写程序实现：先对fee升序排序，再用顺序查找查询金额35在列表中的位置，并统计高于平均消费金额的人数。请回答下列问题： （1）对长度为n的升序列表采用顺序查找查找一个存在的元素，最多需要比较的次数是（单选） A. 1次 B. n-1次 C. n次 D. n/2次 （2）若改用二分查找在有序列表fee中查找金额，下列说法正确的是（单选） A. 二分查找不受“数据有序”这一前提的限制 B. 二分查找每次比较后都要访问列表的全部元素 C. 二分查找每次比较后能排除约一半的待查元素 D. 二分查找的最坏比较次数一定小于顺序查找 （3）统计“高于平均消费金额”的人数，程序片段如下： avg = sum(fee) / len(fee) cnt = 0 for x in fee: if ①: cnt += 1 ①处应填入的代码为：______ 【答案】(1)C；(2)C；(3)①x > avg 【解析】本题考查顺序查找与二分查找的综合应用。 （1）顺序查找从头到尾逐一比较，最坏情况是待查元素位于末尾，需比较n次，故选C； （2）二分查找每次取中点，比较后排除中点一侧约一半元素，C正确；A错误：二分查找必须以有序为前提；B错误：二分查找每次只访问一个中点元素；D错误：二分查找最坏比较次数未必小于顺序查找； （3）统计高于平均消费金额的人数，即对每个x判断x>avg，故①处填入x > avg。 1.（选考真题・2023年1月浙江信息技术选考 第10题）列表s包含8个互不相等的元素，即s[0]、s[1]、s[2]、……、s[7]，有如下Python程序段： n = 8 for i in range(1, n - 1): for j in range(1, n - i - 1): if s[j] > s[j - 1]: s[j], s[j - 1] = s[j - 1], s[j] 该程序段实现的是（ ） A. s[0]到s[5]的降序排列 B. s[1]到s[6]的降序排列 C. s[1]到s[7]的升序排列 D. s[2]到s[6]的升序排列 【答案】A 【解析】i=1时，j的取值范围为[1,5]：j=1时比较s[0]与s[1]，j=5时比较s[4]与s[5]，故排序区间最大为[0,5]。当s[j]>s[j-1]（前小后大）时交换，较大者前移，实现s[0]到s[5]的降序排列。故选A。 2.（选考真题・2025年6月浙江信息技术选考 第12题）定义如下函数，返回key在列表data中的下标，若key不存在则返回-1。 def bsearch(data, key): i, j = 0, len(data) - 1 while i <= j: m = (i + j) // 2 for k in range(m - 1, m + 2): if i <= k <= j and data[k] == key: return k if data[m] < key: i = m + 2 else: j = m - 2 return -1 如果调用函数返回结果不正确，则data可能是（ ） A. [16,19,18,22,20,29,25] B. [16,19,20,18,22,25,29] C. [18,16,19,20,22,29,25] D. [18,16,20,19,25,22,29] 【答案】B 【解析】函数每次在mid附近检查data[m-1]、data[m]、data[m+1]三个位置，若未命中则按data[m]与key的大小令i=m+2或j=m-2收缩。选项B中元素19位于20之后、18之前，存在局部逆序；当key取19时，第一次m=3，窗口检查data[2]=20、data[3]=18、data[4]=22均不等于19，且data[3]=18<19令i=5，区间收缩为[5,6]，而19实际位于下标1，已被排除在搜索区间之外，此后无法找到，返回-1，结果不正确。故选B。 3.（选考真题・2021年1月浙江信息技术选考 第11题）采用冒泡排序算法对某数据序列进行排序，经过第一轮排序后的结果是“2，8，3，9，5，6，7”，那么原数据序列不可能的是（ ） A. 8，3，9，5，2，7，6 B. 8，3，9，2，6，5，7 C. 8，2，9，3，5，7，6 D. 8，3，2，9，6，5，7 【答案】D 【解析】冒泡排序（升序）第一轮会将序列中的最大值移动到末尾。题干第一轮后的结果为2，8，3，9，5，6，7，其末位为7；而选项D（8，3，2，9，6，5，7）中最大数9位于第4位，经第一轮相邻比较与交换后，9必然向后交换直至到达末尾，故D第一轮后的末位应为9，不可能得到末位为7的题干结果。因此原数据序列不可能是D，故选D。 4.（选考真题・2021年1月浙江信息技术选考 第12题）某对分查找算法的VB程序段如下： 随机产生包含20个整型元素的升序序列，依次存入数组a，代码略 i = 1：j = 20：s = "" key = Val(Text1.Text) Do While i <= j m = (i + j) \ 2 s = s + Str(a(m)) If a(m) = key Then Exit Do If a(m) > key Then j = m - 1 Else i = m + 1 Loop Text2.Text = s 在文本框Text1中输入待查找数，执行该程序段后，下列选项中，文本框Text2中显示的内容不可能的是（ ） A. 78 50 46 33 B. 51 37 41 48 C. 74 50 46 51 D. 73 83 87 89 【答案】C 【解析】对分查找每次访问下标m=(i+j)\2并将其加入s。若选项C显示“74 50 46 51”，则m依次为10、5、2、1，对应访问a(10)=74、a(5)=50、a(2)=46、a(1)=51。序列为升序，故a(1)应不大于a(2)=46，但显示中a(1)=51>46，与升序前提矛盾，故该显示序列不可能出现。故选C。 学科网（北京）股份有限公司1 / 17 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $