专题八 数据结构与算法（全文逐字提取・最详细版） 专题八 数据结构与算法 考点清单 考点一 数据结构与算法效率 一、算法效率 衡量标准 算法效率的高低可由算法的复杂度来衡量。算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要占用的存储空间。 时间复杂度 一般将算法中语句的执行次数作为时间复杂度的度量标准。语句总的执行次数 T (n) 是关于问题规模 n 的函数。所谓问题规模 (也称为输入的大小) 是指处理问题的大小，即用来衡量输入数据量的整数。 时间复杂度常用符号 O 表述，不包括 T (n) 函数的低阶项和首项系数，如 1/2 n (n-1) 的量级与 n² 相同，其时间复杂度可表示成 O (n²)。 推导大 O 阶的方法 用 O () 来体现算法时间复杂度，称之为大 O 阶记法。其推导方法如下： ① 用常数 1 取代运行时间中的所有加法常数。 ② 在修改后的运行次数函数中，只保留最高阶项。 ③ 如果最高阶项存在且不是 1，那么去除与这个项相乘的常数。得到的结果就是大 O 阶。 例如：1/2 n (n-1) → 保留最高阶 → 1/2 n² → 去除常数 → n² 常见的时间复杂度耗费时间的大小关系为 O (1) < O (log₂n) < O (n) < O (n²) < O (n³) < O (2ⁿ) < O (n!) 二、数据结构对算法效率的影响 数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的操作，提高算法处理数据的效率。 数据结构的不同选择会影响算法的运行效率。 通过比较时间复杂度 O () 来比较不同算法的效率。 考点二 迭代与递归 一、迭代与迭代算法 迭代是重复反馈过程的活动，其目的通常是使结果符合目标需求。 迭代算法是利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令 (或一些步骤)，这组指令 (或这些步骤) 每执行一次时，都会将变量从原值递推出一个新值。 二、利用迭代算法处理问题 利用迭代算法处理问题需要考虑三个方面： 确定迭代变量：在能够用迭代算法处理的问题中，至少具有一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 建立迭代关系式：所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式 (或关系)。 控制迭代过程：迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。 三、递归的概念与特性 概念：大问题的解决中嵌套着与原问题相似的规模较小的问题，这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 递归的特性：通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归往往能使函数的定义和算法的描述简洁且易于理解，极大地减少了程序代码量。 能采用递归描述的算法的特征 为求解规模为 N 的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界，如问题规模缩减为 0 或 1 时，能直接得解。 利用递归算法解决问题的关键步骤 ① 抽象建立递归模型，确定递归公式。 ② 确定临界条件 (即递归结束条件)。 考点三 数据排序 一、排序 概念 排序就是整理数据的序列，使其中元素按照某个值的递增 (或递减) 的次序重新排列的操作。在排序的过程中，数据元素的值保持不变，但其在序列中的顺序可能会改变。 存储方式 待排序数据的存储一般有数组和链表两种方式，利用数组存储数据，在排序时需要对数据本身进行物理重排，可能需要移动数据的位置，而利用链表存储数据，无须移动数据，仅需修改指针即可。 二、冒泡排序 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数 “下沉 (上冒)”，较小的数 “上冒 (下沉)” 的一种排序技术。 算法效率：对于 n 个元素的数组，共需要 n-1 趟，第一趟的比较次数为 n-1，第二趟的比较次数为 n-2，以此类推，最后一趟的比较只需 1 次。共需比较 (n-1)+(n-2)+⋯+1= n (n-1)/2 次。其时间复杂度为 O (n²) 三、选择排序算法 在参加排序的数组的所有元素中找出最小 (或最大) 的数据，使它与第一个元素 (左端) 中的数据相互交换位置。然后在余下的元素中找出最小 (或最大) 的数据，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。 对长度为 n 的数组，每一趟排序过程都会扫描待排序区域的所有元素，将最小 (或最大) 值交换到最左端，直至只剩下 1 个元素为止，总共排序 n-1 趟，比较的次数为 n (n-1)/2，时间复杂度为 O (n²) 考点四 数据查找 一、查找 查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确认在该批数据内是否存在这样的数据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功。 二、顺序查找 概念 顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值 key (查找键) 进行比较。若某个元素的关键字等于 key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 优缺点 顺序查找的优点是算法简单，容易实现，且对存放数据的表结构无任何要求，不管数据是否有序，均可使用，缺点是查找效率低，当数据量较大时不宜采用。 三、二分查找 概念 二分查找又称折半查找，对分查找。二分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素与查找键不同，根据数组元素的有序性，就可以确定在数组的前半部分还是后半部分继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 二分查找是一种效率很高的查找方法，要求被查找的数据序列必须是有序的，最多进行⌊log₂n⌋+1 次比较。 考向突破（含全部例题、题目、答案、解析） 考向一 数据结构与算法效率 数据结构 数据结构指的是数据之间的相互关系，即数据的组织形式。 数据元素之间的逻辑关系，也称为数据的逻辑关系。 数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。 数据的运算，即对数据施加的操作。 实际应用中的数据结构设计主要考虑数据对象之间的逻辑关系，所以数据结构一般指向的就是逻辑结构。 例 1（2022 Z20 名校联盟，3） 下列有关数据结构的说法正确的是（） A. 数组是一种适用于组织、存储涉及频繁插入与删除的数据结构 B. 链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的 C. Excel 软件中的撤销操作体现了队列的思想 D. 树结构中，每个子节点的父节点可以有多个 解析：链表适合频繁插入删除；撤销是栈思想；树子节点只能有一个父节点。 答案：B 针对训练 1-1 下列关于算法效率分析的说法，正确的是（） A. 算法复杂度是指算法控制结构的复杂程度 B. 算法的时间复杂度是指算法执行的速度 C. 算法的空间复杂度是指算法执行所需的时间 D. 算法的时间复杂度是指算法在执行过程中基本运算的次数 答案：D 1-2 下列有关数据结构对算法效率的影响的描述，不正确的是（） A. 同一个算法不一定能适用多种不同的数据结构 B. 针对同一个数据结构设计不同的算法，算法的运行效率可能相同 C. 使用链表存储和处理数据比使用数组效率更优 D. 设计算法时，应根据实际问题选择合适的数据结构 答案：C 考向二 迭代与递归 迭代算法与递归算法的区别 迭代是利用变量的旧值推算出变量的一个新值；而递归算法是指一个函数在其定义中直接或间接调用自身的一种方法，它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大地减少代码量，降低编程的难度。因此，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低。 递归是通过函数自己调用自己，而迭代是不断地调用赋值语句；递归中一定有迭代，但是迭代中不一定有递归，递归和迭代在大部分情况下可以相互转换。 例 2（2022 名校协作体，11） 有如下 Python 程序段： python 运行 def f(x): if x==1: return 1 else: return x*f(x-1) s=0 for i in range(1,6): s+=f(i) print(s) 执行该程序段后，变量 s 的值是（） A.33 B.34 C.154 D.153 解析：f (x) 是递归求阶乘。1!+2!+3!+4!+5!=1+2+6+24+120=153 答案：D 针对训练 2-1（2022 丽水质量监控，11） 有如下 Python 程序段： python 运行 def s(x): if x<=2: y=x else: y=s(x-1)+s(x-2) return y a=int(input("请输入正整数:")) result =s(a) print(result) 运行程序，输入值为 6，则输出结果为（） A.8 B.9 C.13 D.14 答案：C 2-2 猴子吃桃问题：一群猴子摘了一堆桃子，不知道总数。猴子们第一天吃了总数的一半多一个，第二天吃了剩余桃子的一半多一个，……，直到第十天，发现只剩 1 个桃子了。 (1) 第九天时总共有____个桃子，猴子们当天吃了____个桃子。 (2) 设计一个递归算法，编程计算猴子总共摘了几个桃子，请在划线处填入合适的代码。 python 运行 def fun(n): if ① return 1 else: return ② 答案：(1) 4；3 (2) ① n==10 ② 2*(fun(n+1)+1) 考向三 数据排序 1. 冒泡排序的代码实现 对数组 a 进行升序排序，长度为 n 的数组需要排序 n-1 趟。 python 运行 n=len(a) for i in range(0,n-1): for j in range(n-1,i,-1): if a<a: a,a=a,a 2. 选择排序的代码实现 对数组 a 进行升序排序，长度为 n 的数组需要排序 n-1 趟。 python 运行 n=len(a) for i in range(n-1): k=i for j in range(i+1,n): if a<a: k=j if k!=i: a,a=a,a 例 3（2022 Z20 名校联盟，12） 某 Python 程序如下： python 运行 import random n = random.randint(1,4) a= for i in range(1,n): for j in range(0,6-i): if a<a: a,a=a,a 执行该程序段后，数组 a 中的元素不可能为（） A.9,7,7,4,3,2 B.7,7,3,9,4,2 C.7,9,7,4,3,2 D.7,2,7,3,9,4 解析：n 取 1~4，最多排 3 趟，无法完全有序成 A。 答案：A 针对训练 3-1（2022 丽水质量监控，10） 采用选择排序算法对数据序列 “12,23,24,15,11,10” 完成升序排序，则需要交换的次数为（） A.3 B.4 C.5 D.6 答案：A 3-2（2022 绍兴鲁迅中学期中，11） 有如下 Python 程序段： python 运行 n=4 a= for i in range(n)] for i in range(0,n,2): for j in range(n//2): a,a=a,a 则程序执行后，a 和 a 的值分别为（） A.2 和 7 B.3 和 6 C.5 和 10 D.9 和 6 答案：D 考向四 数据查找 1. 顺序查找的代码实现 python 运行 def seq_search(a, key): for i in range(len(a)): if a==key: return i return -1 2. 二分查找的代码实现 python 运行 def binary_search(a,key): L,R=0,len(a)-1 while L<=R: m=(L+R)//2 if key==a: return m elif key<a: R=m-1 else: L=m+1 return -1 递归版： python 运行 def bsearch(a,L,R,key): if L>R: return -1 m=(L+R)//2 if key==a: return m elif key<a: return bsearch(a,L,m-1,key) else: return bsearch(a,m+1,R,key) 例 4（2022 七彩阳光返校考，11） 有如下 Python 程序段： python 运行 import random a= k = random.randint(1,10) i=0;j=len(a)-1;x="" while i<=j: m=(i+j)//2 if k<=a: j=m-1;x=x+"L" else: i=m+1;x=x+"R" print(x) 执行该程序段后，输出的结果不可能出现的是（） A.“LLL” B.“LRL” C.“RLR” D.“RRRR” 解析：第一次 m=3 (a =5)，只能分成左、右两大区，不可能出现 RLR。 答案：C 针对训练 4-1（2022 A9 协作体返校考，11） 有如下 Python 程序段： python 运行 a= key =int(input("请输入一个整数:")) i,j,k,c,flag = 0,9,0,"N",False while i <=j and flag == False: m=(i+j+1)//2 k=k+1 if key ==a: c="Y" flag=True if key>a: j=m-1 else: i=m+1 print(c,k) 执行该程序段后，下列说法正确的是（） A. 该程既能用于升序序列的查找，也能用于降序序列的查找 B. 若输出 k 的值为 2，则 c 的值一定为 Y C. 若输入 key 的值为 74，程序执行后变量 i 和 j 的值分别为 0 和 4 D. 若输入两位任意正整数，k 的值介于 1 和 3 之间 答案：B 4-2（2022 绍兴柯桥期末，12） 某二分查找算法的 Python 程序段如下： python 运行 a= L,R=0,9 s=[] key =int(input("请输入要查找的数据:")) while L <= R: m=(L+R+1)//2 if a== key: break elif a > key: R=m-1 else: L=m+1 s.append(a) print(s) 执行该程序，当输入的值为 30 时，程序输出的结果是（） A. B. C. D. 答案：B 4-3 有如下 Python 程序段： python 运行 d= n=len(d) key =int(input("please input key:")) i=0 c=0 flag=True s="" while i<=n-1: if key ==d: flag= False s=s+str(i)+"," i=i+1 if flag: print("未找到") else: print("找到，索引位置为：",s) 程序运行时，输入 key 的值为 9，程序运行后，变量 i 的值为（） A. 未找到 B. 找到，索引位置为：1 C. 找到，索引位置为：1,3 D. 找到，索引位置为：1,3,6 答案：D