高中信息技术浙江高考复习资料算法和程序设计 9页

选修1：算法与程序设计第一单元算法一、知识内容（一）使用计算机解决问题的一般过程考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。1．一般过程（1）分析问题确定要使用计算机来“做什么”，即确定解题的任务。（2）寻求解决问题的途径和方法。（3）用计算机进行处理。2．确定解决问题的方法及步骤化确定了解决问题的方法后，必须把解决问题的方法步骤化，即用某种方式告诉计算机每个需做什么。计算机开始计算之前，需把解决问题的程序存储在内存中。通常一个程序包括指令和数据两部分。（1）指令部分：指令是对计算机操作类型和操作数地址做出规定的一组符号。（2）数据部分：计算所需的原始数据、计算的中间结果或最终结果。3．设计程序时需要考虑的问题（1）数据的存储：计算所需要的原始数据、计算产生的中间结果需要存储在不同的变量中。（2）计算的过程：把解决问题的方法步骤化，并用计算机能执行的指令来有序地实现对应的步骤。（3）典型的指令类型有输入指令、输出指令、算术运算指令、逻辑运算指令和控制转移指令。（二）算法及算法的表示方法考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．算法的特征（1）有穷性。一个算法必须保证它的执行步骤是有限的，即它是能终止的。（2）确定性。算法中的每个步骤必须有确切的含义，不应当有模棱两可的。（3）能行性。算法中的每一个步骤都要足够简单，能实际能作的，而且在能在有限的时间内完成。（4）有0个或多个输入。（5）有一个或多个输出。（三）用自然语言和流程图表示算法考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．自然语言就像写文章时所列的提纲一样，可以有序地用简洁的自然语言加数学符号来描述算法。2．流程图用国家颁布的标准（GB1526-89，ISO5807-1985）中规定的图示及方法来画流程图，常用的构件有如图所示。9\n3．伪代码使用某些程序设计语言中控制结构，来描述算法中各步骤地执行次序和模式；使用自然语言、数学符号或其他符号，来表示计算步骤要完成的处理或需要涉及的数据。（四）顺序、选择和循环三种基本模式考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．顺序模式就是按指令的先后顺序依次执行2．分支模式就是根据分支条件，判断条件成立情况，选择某一条路径中的指令执行3．循环模式就是首先判断条件是否成立，如果不成立则直接执行循环体外的第一条指令，如果条件成立则执行循环体内的指令，然后再次判断条件是否成立，如果条件成立再次执行循环体内的指令，直至条件不成立跳出循环体为止。三种基本模式流程示意图如下图所示。9\n第二单元VB程序设计一、知识内容（一）面向对象程序设计的基本思想与方法考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。1．面向对象程序设计（objectorientedprogramming，缩写OOP）方法：在进行程序设计是从分析问题领域中各种客观事物本体的属性和行为，以及它们之间的相互关系着手，在计算机中建立起这些客体的映象——对象，用对象对应于问题领域中的客体，用对象间的消息传递来表示客体的相互作用、相互关系。（二）属性、类、事件和事件处理的概念考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。1．对象是客观存在的事物或概念。它有两个特点：状态和行为。2．一个对象的状态是通过若干个属性（property）来描述的；行为是指对属性进行操作和处理的方法（method）。在面向对象的程序设计中，一个对象是由一组对象状态的数据和一组描述处理对象属性的方法的代码构成的。对象的属性定义其外观，方法定义其行为，事件定义其与用户的交互。3．类（class）是对相同性质的对象的一种抽象，而一个对象则是类的一个“实例”。4．事件（event）就是发生在对象上的事情，通常是由用户在对象上激发的一种动作。一个事件的发生，可以引起某个对象上某个方法（事件处理过程）的执行，即由某个事件驱动了相应的事件处理过程的执行。这就是面向对象程序设计中的事件驱动概念。（二）VB应用程序的界面设计与调式考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．VB应用程序的界面设计（1）VB程序设计语言：基于Basic语言的可视化程序设计环境，采用面向对象的程序设计方法（OOP）。（2）VB应用程序设计环境的的窗口主要由对象窗口、控件工具箱、属性窗口、工程窗口组成。（3）控件工具箱集中了常用的基本控件：标签label、文本框TextBox、命令按钮CommandButton、列表框ListBox等。(4)窗体（Form）是VB应用程序的基本结构。窗体可以看作是一个“容器”，其中放置着各种各样在应用程序中必须用到的对象。2．VB应用程序的运行和保存运行：单击工具栏中“运行”选项中的启动按钮，运行应用程序。保存：在“文件”菜单中选“工程另存为”，该应用程序的窗体和工程分别存储到文件中，其相应的文件扩展名分别是“ .frm”和“ .vbp”。也可以选“文件”菜单中的“生成工程xxx.exe”，这样，就可在Windows环境中直接运行这个应用程序了。（四）事件处理代码的编制方法考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。对于对象而言，事件就是发生在该对象上的事情，通常是由用户在对象上激发的一种动作。一个事件的发生，可以引起某个对象上某个方法的执行，即由某个事件驱动了相应的事件处理过程的行为。在事件处理过程中，可以按预定设计好的方式，改变某个对象的相关属性值，因此是这个对象的状态得到相应的改变。（五）VB基本数据类型、常量、变量和数组9\n考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．数据：数据是信息的一种记录形式。在VB中，常用的基本数据类型有以下几种：Integer(整数型)、Long(长整数型)、Single(单精度实数型)、Double(双精度实数型)、String(字符串型)、Boolean(逻辑型)、Date(日期型)。*逻辑（Boolean）数据类型只有两个值True，或False。将逻辑数据转换成整型时：True为-1，False为0；其它数据转换成逻辑数据时：非0为True,0为False。2．常量：常量是在程序执行过程中其值不变的存储单元或数据。在VB中，常量有整数常量、实数常量、字符串常量和逻辑常量这几种类型。3．变量：变量的命名规则1.以字母或汉字开头，后可跟字母、数字或下划线组成.2.变量名最长为255个字符；3.VB中不区分变量名的大小写，不能使用VB中的关键字；4.字符之间必须并排书写，不能出现上下标变量说明语句的常用形式为：Dim　变量名　As　变量的类型。4．数组：数组是由一批同类型的变量构成的一个序列，组成数组的每一个变量被称为数组的元素，也称为下标变量，下标是一个整数，用来指出某个元素在数组中的位置。一维：Dim数组名([<下界>to]<上界>)[As<数据类型>]二维：Dim数组名([<下界>]to<上界>，[<下界>to]<上界>)[As<数据类型>]一维数组的常用形式为：Dim数组变量名(A1ToA2)As元素的类型。二维数组的常用形式为：Dim数组变量名(A1ToA2，B1ToB2)As元素的类型。（六）VB各类表达式与标准函数考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．VB中的常用标准函数（1）常用数学函数：Abs(X)、Int(X)、Sqr(X)、Rnd（）、Exp(X)、Log(X)、Sin(X)、Cos(X)、Tan(X)。（2）常用类型转换函数和字符串函数：Asc(X)、Chr(X)、Val(X)、Str(X)、Len(X)、9\nMid(X,n,k)、Fix(X)。Int(9.59)=9Int(9.28)=9Int(-9.59)=-10Int(-9.21)=-10Asc("Abcd")值为：65（只取首字母的Ascii值）Val("abc123")值为：0,Val("1.2sa10")值为1.2chr(x),将Ascii转化为字符str(x)将数值转化字符fix(x)截掉小数部分fix(9.59)=9fix(9.28)=9fix(-9.59)=-9fix(-9.21)=-9Mid(x,m,n)：返回字符串x从第m个字符起的n个字符所组成的字符串。Mid("ABCDEFG",2,3)"BCD“Len(x)：返回字符串x的长度，如果x不是字符串，则返回x所占存储空间的字节数。len("Thisisabook!")15随机函数RndRnd函数可以不要参数，其括号也省略。返回[0~1)（即包括0，但不包括1）之间的双精度随机数。若要产生1~100的随机整数，则可通过下面的表达式来实现：Int(Rnd*100)+1'包括1和100Int(Rnd*99)+1'包括1，但不包括100产生[N，M]区间的随机数的VisualBasic表达式：Int(Rnd*(M-N+1))+N2．基本运算与表达式（1）VB的基本运算：VB的基本运算包括算术运算、关系运算和逻辑运算三大类。算术类基本运算有：＾、-、*、/、\、Mod、+、-关系类基本运算有：=、<>、<、>、<=、>=逻辑类基本运算有：Not、And、Or（2）表达式：表达式主要用来规定值的计算过程，以及对于某些情况或条件的判断。一个表达式中可能包括算术运算、关系运算和逻辑运算等多种基本运算，以及这些基本运算所涉及的数据（变量和常量）。（3）基本运算的优先级从高到低为：＾（1级），-（指负号，2级），﹡、/（3级），\（4级），Mod（5级），+、-（6级），=、<>、<、>、<=、>=（7级），Not（8级），And（9级），Or（10级）。1、整数除法25.3\6.3=25\6=425.6\6.6=26\7=32、取余25.3mod6.3=25mod6=125.6mod6.6=26mod7=5（七）常用的VB语句考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。（八）使用VB实现顺序、选择、循环三种控制结构考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．赋值语句：变量名=表达式　　　　　　或　对象名.属性名=表达式9\n2．选择语句：　　判断语句形式：（1）If<表达式>Then语句块EndIf或If<表达式>Then<语句>（2）If<表达式>Then<语句块1>Else<语句块2>EndIf或If<表达式>Then<语句1>Else<语句2>（3）If<表达式1>Then<语句块1>ElseIf<表达式2>Then<语句块2>…[Else语句块n+1]EndIf循环：（1）、For初值to终值[Step步长]语句块Next循环变量（2）、DoWhile<条件>语句块Loop4．注释：注释是以单引号（'）开头的一串文字，可以出现在程序中需要说明的位置上，通过这一串文字，对附近的程序段进行简要的说明，增加程序的可读性。注释对程序的执行效果没有任何影响，程序运行时自动跳过注释。（九）过程、事件处理过程、自定义函数考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。命令按钮：COMMANDBUTTON属性：name,Caption,Top,Left,Height,Width,Font,Enabled,backcolor事件：click,load,dblclick,keypress标签LABEL属性：name,Caption,Top,Left,Height,Width,Font,Enabled,backcolor事件：click,load,dblclick,keypress文本框TEXTBOX属性：name,text,Top,Left,Height,Width,Font,Enabled,backcolor事件：click,load,dblclick,keypress,Change列表框控件ListBox属性：List、ListCount和ListIndex,MultiSelect,Selected,Sorted事件：click,load,dblclick,Change方法：AddItem()，RemoveItem()，Clear()9\n4．函数：函数是类似于过程的另一个程序模块，不同之处是函数执行完成后，函数的计算结果被送到函数的调用点上，供程序的后继部分继续进行处理。自定义函数：Function函数名（参数表）As类型名　　　　　　　　　　　　语句块　　　　　　　　EndFunction了解自定义函数，读懂程序。递归：自己调用自己9\n第三单元算法的程序实现一、知识内容（一）枚举算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。枚举算法的基本思想是根据问题的本身性质，一一列举出该问题所有可能的情况，并根据题目的条件逐个作出判断，从中挑选出符合条件的解答。枚举算法属于搜索策略，适用于那些解变量确定的连续值域的问题。设置枚举算法要列举出所有可能的情况，不能遗漏，也不能重复。（二）解析算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。解析算法的基本思想是用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过数学表达式的计算来实现问题的求解。（三）排序算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．冒泡排序冒泡排序的基本思想是在待排序的数据中，先找到最小（大）的数据将它放到最前面，再从第二个数据开始，找到第二小（大）的数据将它放到第二个位置，以此类推，直到只剩下最后一个数据为止。2．选择排序选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。（四）查找算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。1．顺序查找顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置；反之，查找不成功。2．对分查找对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，使查找成功，或直到子表不存在，查找不成功。对分查找的条件是被查找的数据必须是有序的。mid=(i+j)\2,若后半部分i=mid+1,若前半部分i=mid-1二、例题分析1．有5位运动员100米成绩依次为13.8，12.5，13.0，13.2，13.4，原始数据13.812.513.013.213.4第一趟12.513.813.013.213.4第二趟第三趟12.513.013.213.813.4第四趟12.513.013.213.413.8若采用选择排序算法对其进行从小到大排序，则第二趟的排序结果是(A)12.513.813.213.413.0(B)12.513.413.213.813.0(C)12.513.013.813.213.4(D)12.513.213.813.413.09\n参考答案：C所考知识点：选择排序选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。此题中要从小到大排序，并且已经实现第一趟排序，故在后面4个数据当中找出最小的数据“13.0”与第2个数据“13.8”交换，所以结果选C2．数列1，4，7，10，13，……的递推公式为()。(A)f(1)=1;f(n)=n+3(B)f(1)=1;f(n)=n*2-1(C)f(1)=1;f(n)=n*2+1(D)f(1)=1;f(n)=f(n-1)+3参考答案：D所考知识点：递归算法由数列可推出规律，从第二项开始，每一项跟前一项的差为3，故得出递推公式3．用选择排序法对数据7，6，3，9，2从大到小排序，共需经过多少次数据对调。(A)3(B)4(C)5(D)10参考答案：A所考知识点：选择排序此题只能根据选择排序的思路，共需进行四趟比较，具体过程如下：原始数据76392第一趟96372第二趟97362第三趟97632第四趟97632其中，第四趟不需要进行数据对调，前三趟都进行了对调4．要从n个数据元素中顺序查找一个元素，最多查找次数是(A)1(B)n(C)n/2(D)lgn参考答案：B所考知识点：顺序查找此题稍简单，只要稍理解顺序查找的概念，就能选择答案5．对分查找算法的前提是(A)被查找数据元素个数是奇数    (B)被查找数据元素个数是偶数(C)被查找数据元素是有序的   (D)被查找数据元素是无序的参考答案：C所考知识点：对分查找的概念此题稍简单，只要稍理解对分查找的概念，就能选择答案6．用对分查找法从数列3，6，7，10，12，16，25，30，75中找到数据10的最少查找次数是(A)2   (B)3    (C)4    (D)7参考答案：B所考知识点：对分查找用对分查找的方法需分别对上列数据进行编号，共9个数，依次序号为1~9。按照对分查找的思路，依次查找的数据为12、6、10，所以查找次数为3次。9