信息科技2016学年第一学期期末算法复习

信息科技复习稿（程序篇） 1.算法的定义：为解决某一问题而设计的确定的有限的步骤。 2.算法的特点：有穷性、确定性、可行性、有 0 个或多个输入、有一个或多个输出。 例. 以下流程图，符合算法特征的是（ ）。 A B C D 例. 下列关于算法的特征描述不正确的是_ A、有穷性：算法必须在有限步之内结束 B、确定性：算法的每一步必须有确切的定义 C、输入：算法必须至少有一个输入 D、输出：算法必须至少有一个输出 3.描述算法的方法：用自然语言描述、用流程图描述、用程序描述。 例. 算法描述可以有很多种表达方式，下面不属于算法描述方式的是_ A.自然语言 B.流程图 C.伪代码 D.机器语言 4.用计算机解决问题的一般过程：分析问题 设计算法 编写程序 上机调试。 5.变量的命名规则：只能由字母、数字和下划线三类字符组成，但第一个字符必须是字母， 字母大小写都可以。变量名长度适当，要有意义。 例. 下列变量命名中，合法的变量名是_。 A、x+5 B、do C、n7 D、miss_1 6.变量赋值：将赋值号右边常量的值或变量的值，或表达式的结果存放在左边变量名对应 的存储单元中，成为左边变量的值。 格式：变量=常量 例如：a=3 变量=变量 例如：b=a 变量=表达式 例如：c=2*a+b 注意：= 是赋值号 7.变量的特点：变量的值“取之不尽，一冲就丢”。 8.三类运算: 算术运算符：+ 加 - 减 * 乘 / 除 整除 乘方 Mod 求余数 关系运算符：=、=大于等于、不等于 逻辑运算符：Not And Or 运算规则 算术运算最优先，关系运算次之，最后为逻辑运算，括号可以改变次序。 逻辑运算次序 先 not 后 and 再 or。 Int(x) 取整运算,求不大于 x 的最大整数 Sqr(x) 求 x 的算术平方根 Abs(x) 求 x 的绝对值 例. 若变量 a、b 的值分别为 3、4，则表达式 a+b/(a-b)的值是_。 例. 若变量 x 的值为 5，则表达式 33 mod x6 的值是_。 例. 若变量 x、y 的值分别为 6、7，则表达式(x5) and (y-1）的值是_ 例. 若 x，y 都是正整数，表示“x 是 y 的倍数”的逻辑表达式是_。 A、xy=0 B、int(x/y)=0 C、int(x/y)=x/y D、x mod y=1 例. 若 a，b 都是正整数，且关系表达式(a*b) mod 2=0 为真（True），则下列说法正确的 是_。 A、a，b 一定同时为奇数 B、a，b 中必有一个为偶数 C、a，b 中必有一个为奇数 D、a，b 一定同时为偶数 例. 设 x=4126 能得到其百位上数字“1”的正确表达式是_。 A、x mod 100 B、x100 mod 10 C、x100 mod 100 D、x10 mod 10 例. 逻辑表达式（”A”1）的值是_ _。 A不确定 BF CT D表达式有错误 9. 数组：一种特殊的变量，用 a1这样的形式来表现，a 是数组的名称，1 是下标，表示 这个元素在数组中所处的位置。下标可以是常量、变量、甚至是表达式。如：ai , a3+4 例. 给数组 a 赋值如下表，运行 i=1：i=i+3 之后，读取 a(i)的值为 A : 2.4 B : 4.3 C : 3.8 D : 1.7 11. 排序法：对批量的数据按照一定的顺序进行排列的一种操作方法。 冒泡排序：逐遍加工，每一遍排好一个数据，最后一遍加工后完成排序。从右往左，一次 比较相邻的 2 个元素，把小的往前交换。 选择排序：每一遍加工过程中通过遍历记录下最值的位置，最后再将最值的位置和待排元 素的位置进行交换，每一遍加工过程中只要调整一次位置。 例. 数组 a 中存放了某校田径运动会中八名 100 米短跑运动员的成绩，数据存放情况如下 表： a1 a2 a3 a4 a5 a6 a7 a8 12.8 13.3 12.3 12.6 13.5 12.1 13.0 13.8 若按升序排列，并采用冒泡排序算法自右向左进行比较和交换，那么在第二轮数据比较交 换中，共交换 次。 例. 数组 a 中存放了某校田径运动会中八名 100 米短跑运动员的成绩，数据存放情况如下 表: a1 a2 a3 a4 a5 a6 a7 a8 12.8 13.3 12.3 12.6 13.5 12.1 13.0 13.8 若按升序排列，并采用冒泡排序算法自右向左进行比较和交换，那么在第二轮数据比较交 换后，数组元素 a7的值是 。 例. 将 6 名选手的歌唱比赛成绩存放在数组 a 中，如下表所示： 若按升序排列，采用冒泡排序算法自右向左进行比较和交换，那么完成前二轮的数据处理， 比较的总次数为（ ） A : 9 B : 5 C : 10 D : 4 12. 查找法：在批量的数据中找到所需的对象。关键过程就是取一个元素，读出其的值同 时和要查找的数据进行比较，若相等则表示找到，若不等则继续下一个。 顺序查找：从第 1 个数开始，比较和需要查找的数据是否相等，直到相等输出元素的下标。 对分查找：在一个有序的数组中，从中间元素开始查找，若不等则缩小一半的查找范围， 在剩下的元素中继续取中间位置的元素进行查找，直到找出为止。 例. 数组 a 中存放了某校田径运动会中七名 100 米短跑运动员的成绩，数据存放情况如下 表： a1 a2 a3 a4 a5 a6 A7 12.1 12.3 12.6 12.8 13.0 13.3 13.5 若用对分查找算法查找数值 13.5，则需要查找的次数是 。 例.数组 a 中存放了某校田径运动会中七名 100 米短跑运动员的成绩，数据存放情况如下表: a1 a2 a3 a4 a5 a6 a7 12.1 12.3 12.6 12.8 13.0 13.3 13.5 若用对分查找算法查找数值 12.6，则需要查找的次数是 。 例. VB 数组 A 中存放了某校学生的身高数据（单位：厘米），数据存放情况如下表： 若要查找数组中是否存在数据 182，以下表述正确的是（ ）。 A . 本组数据既能采用对分查找算法，也能采用顺序查找算法 B . 本组数据采用对分查找需比较 4 次，而顺序查找只需 2 次，所以对分查找效率高的说 法不对 C . 本组数据须先对数据进行升序排序后才能进行对分查找 D . 本组数据由于存在相同数据 176，所以不能采用对分查找算法 13. 机器人：我也是醉了，分不清楚方向的少年们，随便看看吧。 例. 机器人走迷宫：图 a 为迷宫（黑色表示障碍区，不能通行），图 b 为机器人的智能程 序。机器人用箭头表示，箭头方向为机器人的前进方向，机器人会按智能程序要求行走， 并会从底边的某个位置走出迷宫。该位置的编号是 例.机器人灭火：下图为着火点搜索范围和机器人的智能程序。黑色区域表示障碍区，不能 通行；红色星状图为着火点。机器人用箭头表示，箭头方向为机器人的前进方向，机器人 会按智能程序要求进行搜索，直至完成灭火任务。完成灭火任务后，输出的 i 值为 。 14. 简单循环编程：最关键的是看着题目和给出的代码中，分析需要用到哪些量，并且分 别要用哪些变量来表示这些量。然后就是这些变量的初值，终值，变化过程，完整的连起 来就是一个完整的代码了。下面不来虚的，直接通过例题以及同类的练习题，自己摸索套 路。 例. 计算 S=10/1001+10/1002+10/100310/N 的值（N 由输入决定，若 N 为 1200，则运 行结果为？）精确到 0.001 分析：用到 3 个变量，S 表示和，N 表示输入的最后一个分母，I 表示每一个分母。则代码 如下： i = 1001 s = 0 n = InputBox(“n“) Do While i b Then s=s+x End If x = x + 1 Loop Print s 例. 六位正整数，能被 157 和 233 同时整除，且第一位数与最后一位数相等，求满足条件 的六位正整数。 分析：需要用到三个变量，x 表示六位正整数，a 表示第一位，b 表示最后一位。第一个六 位数是 100000，最后一个是 999999。a、b 需要在循环中求，因为会变。判断条件是 a=b， 条件成立直接输出 x，不成立舍弃。代码如下： x = 100000 Do While _删去下划线并填空 _删去下划线并填空