必修1 数据与计算 第4单元　计算与问题解决 复习学案（含答案）-2024年江苏省普通高中学业水平合格性考试 信息技术

第 4 单 元　计算与问题解决
计算是获得信息的一种过程，所以计算是动态的，信息的获得是计算的延伸。可以说，问题解决的过程，实质上是描述和变换信息的过程。
4.1算法及其特征
1.算法的重要特征
（1）有穷性。算法必须能在执行有限个步骤之后终止。
（2）确切性。算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
（3）输入项。一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件。
（4）输出项。算法一定要有输出。
（5）可行性。算法中执行的任何计算都可以在有限时间内完成（也称为有效性）。算法中的运算都必须是可以实现的。
对算法的评价主要从时间复杂度和空间复杂度来考虑。
2.枚举
“枚举”或称作“穷举”，是一种最为直接、简单的算法思想。它将所有可能的答案一一列举，合适就保留，不合适就丢弃。
枚举法解决问题的一般结构：循环＋判断。
优势：正确性容易证明。
1.一个正确的算法应该具有5个特性，除输入项、输出项特性外，另外3个特性是（　　）。
A.确切性、可行性、有穷性　　B.易读性、确切性、有效性
C.有穷性、稳定性、确切性　　D.可行性、易读性、有穷性
2.以下关于算法中输入、输出的描述中正确的是（　　）。
A.算法可以没有输入，表示该算法不涉及任何数据信息
B.算法可以没有输出，表示该算法运行结果为“无解”
C.算法必须要有输入，否则算法无法进行
D.算法至少要有一个输出
3.采用盲目搜索的方法，在搜索的过程中对所得的结果逐一筛选，排除不符合要求的结果，保留那些符合要求的结果，这种方法叫作（　　）。
A.解析法　　B.递推法　　C.枚举法　　D.选择法
4.关于枚举法，下列说法错误的是（　　）。
A.枚举法的基本思想就是，根据问题的部分已知条件预估解的范围，并在此范围内对所有可能的情况进行逐一验证，直到找到满足已知条件的解为止
B.枚举范围的大小直接影响着枚举法的执行效率
C.枚举法，也称蛮力法或暴力搜索法，理论上利用这种方法可破解任何一种密码
D.枚举范围中的判定条件直接影响着枚举法的执行效率
5.使用枚举算法解决问题的优势为（　　）。
A.算法简单、直接　　B.运算时间短
C.可以求解任何问题　　D.算法灵活多样
4.2数值计算
在Python中，绘制函数图像一般要用到numpy和matplotlib两个模块，这两个模块需要另外安装。
1.numpy模块
numpy是一个科学计算包，其中包含很多数学函数，如三角函数、矩阵计算方法等，还支持处理大型矩阵、矢量运算、线性代数等功能。
·range（）和arange（）的区别
range（start，end，step），返回一个list对象，起始值为start，终止值为end，但不含终止值，步长为step。只能创建int型list。
arange（start，end，step），与range（）类似，但是返回一个array对象。需要引入import numpy as np，并且arange可以使用float型数据。
2.matplotlib模块
matplotlib是Python中最出色的绘图库，功能很完善。调用时，坐标系可以根据数值范围自动生成。
3.迭代法
迭代法也称为辗转法，是用计算机解决问题的一种基本方法。
迭代通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
利用迭代算法解决问题，有以下三个关键步骤：
（1）确定迭代变量；
（2）建立迭代关系式；
（3）对迭代过程进行控制。
1.在Python中，绘制函数图像需要使用的模块是（　　）。
A.win32com、numpy　　B. numpy、matplotlib
C.math、matplotlib　　D.random、math
2.下列有关利用计算机绘制函数图像的描述中错误的是（　　）。
A.精确度高，便于数据分析
B.可以根据实际需要绘制不同形式的图像
C.可以通过读图直接求出函数的值
D.提高了人们的工作效率
3.numpy是一个科学计算包，其中包含很多数学函数，如三角函数、矩阵计算方法等。arange函数是该模块中的函数。下列说法中错误的是（　　）。
A.可以用arange函数创建一个等差数列
B.arange函数如在0～2π之间每隔0.01取个值，则可以用arange（0，2* numpy.pi，0.01）来表示，其中numpy.pi表示π
C.import numpy as np后，x＝np，arange（0，2* numpy.pi，0.01），可以将x应用到y＝np.sin（x）图像绘制
D.可以用arange函数创建一个等比数列
4.关于迭代法，下列描述中正确的是（　　）。
A.每一次的迭代进行，肯定离最终的正确结果越来越近
B.每一次的迭代结果，其实质就是下一次运算的初始值
C.如果没有正确结果，迭代次数可以无止境地进行下去
D.迭代的计算结果肯定比数学公式计算精确
5.斐波那契数列的迭代表达式是（　　）。
A.f1＝f2，f2＝f1＋f2　　B.f1＝f1＋f2，f2＝f1
C.f1，f2＝f1＋f2，f1　　D.f1，f2＝ f2，f1＋f2
4.3非数值计算
1.分治策略
分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。
2.二分查找
二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。它是一种高效的查找方法，可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要lo次。二分法查找的前提条件是被查找的数据必须是有序的。
查找的基本算法有：顺序查找、二分查找、分块查找和哈希查找等。
3.递归
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1，1，2，3，5，8，13，…”，可以递归定义为：
F（n）＝
递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次的计算后得出结果，而不会产生无限循环的情况。
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归两者缺一不可。结合分治策略，递归也可用“分”“治”“合”三个字概括。
（1）分：将原问题分解成k个子问题。
（2）治：对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。
（3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
·迭代与递归的关系
迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有着密切的联系。
迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是重复调用函数自身。
递归中，遇到满足终止条件的情况时逐层返回；迭代则通常使用计数器结束循环。
迭代程序可以转换成等价的递归程序。
1.“大事化小、小事化了”体现出的问题求解的思想是（　　）。
A.递推法　　B.穷举法　　C.分治法　　D.归纳法
2.二分查找算法利用的算法思想是（　　）。
A.分治策略　　B.穷举法　　C.贪心法　　D.回溯法
3.对线性表进行二分查找时，要求线性表必须（　　）。
A.以顺序方式存储　　B.以顺序方式存储，且数据元素有序
C.以链接方式存储.　　D.以链接方式存储，且数据元素有序
4.对于数列3，8，11，15，17，19，25，30，44，采用“二分查找”法查找“8”时，需要查找多少次？ （　　）。
A.3　　B.4　　C.5　　D.6
5.下面关于递归说法中正确的是（　　）。
A.函数间接调用自己不是递归
B.递归出口和递归关系是递归函数编写的关键
C.递归函数的嵌套调用次数没有限制
D.递归函数的执行效率优于非递归函数
第4单元
4.1　1.A　2.D　3.C　4.D　5.A
4.2　1.B　2.C　3.D　4.B　5.D
4.3　1.C　2.A　3.B　4.A　5.B