《创新高三一轮复习系列选考总复习（浙江专）信息技术讲义： 必修3 第二章算法的程序实现 Word含答案.DOC》由会员分享，可在线阅读，更多相关《创新高三一轮复习系列选考总复习（浙江专）信息技术讲义： 必修3 第二章算法的程序实现 Word含答案.DOC（64页珍藏版）》请在金锄头文库上搜索。
1、第二章算法的程序实现考试标准考试内容考试要求考试属性1.枚举算法及程序实现c加试2.解析算法及程序实现c3.排序算法及程序实现(1)冒泡排序(2)选择排序c4.查找算法及程序实现(1)顺序查找(2)对分查找c5.递归算法a6.VB访问Access数据库(1)通过ADO对象连接数据库(2)通过Recordset对象获取数据表中的数据a一、排序算法及程序实现1.排序的含义及方式(1)所谓排序就是将无序的数列变成有序的数列。(2)排列方式分为升序(也称递增，即从小到大排列)和降序(也称递减，即从大到小排列)。2.冒泡排序(1)冒泡排序基本思想将n个数据看作竖向排列的一组数据，每趟排序自下而上对每对相
2、邻数据进行比较，若次序不符合要求就进行交换，每趟排序结束时都能使排序范围内关键字最小的记录像一个气泡一样升到上端的对应位置，整个排序过程共进行n1趟，依次将关键字最小、次小的各个数据冒到表的第一个、第二个位置上。用冒泡排序对n个数据进行排序时，共需进行n1趟排序，比较的总次数为。(2)冒泡排序程序实现说明：要排序的n个数据已存放d数组中，以升序为例的程序如下：For i1 To n1n个数排序共需进行n1趟For jn To i1 Step 1每一趟从后往前，相邻两数两两比较If d(j)d(j1) Then若满足条件则进行互换tempd(j)d(j)d(j1)d(j1)tempEnd IfN
3、ext jNext i温馨提示：若要按降序排列，只需将程序中的语句“If d(j)d(j1) Then”改为“If d(j)d(j1) Then”即可。3.选择排序(1)选择排序的基本思想每趟排序是在所有的数据中找出最小(或最大)的数据，使它与第一个数据相互交换位置，然后再在剩下的数据中找出最小(或最大)的数据，与第二个数据相互交换位置，以此类推，直到所有元素成为一个有序序列。(2)选择排序的程序实现说明：要排序的n个数据已存放d数组中。以升序为例的程序如下：For i1 To n1n个排序共进行n1趟排序ki第i趟排序时，首先用k记录iFor ji1 To nk位置上的数依次与j位置上的数进
4、行比较If d(k)d(j)Then kj若找到比k位置上更小的数，则更新k的值Next jIf ki Then若i位置上的数不是最小数，则和k位置上的数进行互换tempd(i)d(i)d(k)d(k)temp End IfNext i温馨提示：若要按降序排列，只要将语句If d(k)d(j) Then kj改成If d(k)d(j1) Then kj即可。二、查找算法及程序实现1.查找算法所谓查找就是在指定的数据中寻找某一特定的数据。查找结果有两种，即找到(查找成功)和未找到(查找失败)。2.顺序查找(1)顺序查找的基本思想从第一个数据开始，从左往右(或从上到下)将数据按顺序逐个与给定的值进
5、行比较，若某个数据和给定值相等，则查找成功，找到并输出所查数据的位置；反之，查找失败。若有n个数，则可能的最多查找次数为n。(2)顺序查找算法基本框架设要查找的数为key，待查找的数存放在数组d中。For语句框架：For i1 to n若d(i)key，则表示找到，做相应处理Next i若in表示未找到Do While语句框架：i1Do while in若d(i)key，则表示找到，做相应处理ii1Loop若in表示未找到(3)顺序查找的程序实现在n个数组元素中依次查找，找到第1个满足条件的值，查找即结束，输出找到元素所在的位置；若找不到，输出“未找到”。程序实现：设要查找的数据是key(在文
6、本框Text1中输入)，查找的数据存放在数组d中。pos为找到数的位置，pos0表示未找到。P表示查找的次数。keyVal(Text1.Text)Val要根据实际情况决定是否要添加p0pos0findFalsefind表示查找结果i1Do While in And Not find表示还没找完并且还未找到，则继续查找，Not find也可表示为findfalsepp1If keyd(i) ThenposifindTrueEnd Ifii1LoopIf find Then也可表示为If findtrue thenText2.Text”在d(”Str(pos)”)中”ElseText2.Text“
7、未找到”End If3.对分查找(1)对分查找的基本思想在有序的数据序列中(一般存放在数组中)，首先把要查找的数据与数组中间位置的元素进行比较，如果相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。温馨提示：对分查找的前提是被查找的数据序列必须是有序。“未找到”是指当指定范围内的起点大于终点仍未找到该数据。(2)对分查找算法基本框架说明：要查找的数为key，待查找的数存放在数组d中。i为查找范围的起点，j为查找范围的终点，m为范围i，j的中间位置。i1jnDo While ij计
8、算中点位置m比较key与d(m)，并做相应处理 Loop 若ij，则表示未找到(3)对分查找程序实现在n个数组元素中依次查找，找到第1个满足条件的值，查找就结束，输出找到元素所在的位置；若找不到，输出“未找到”。程序实现：设要查找的数据是key(在文本框Text1中输入)，查找的数据存放在数组d中。在文本框Text2中输出查找结果，若找到输出“找到！位置为：X”，否则输出“未找到！”在文本框Text3中输出共查找的次数。p表示查找的次数。核心代码为(以升序为例)：keyVal(Text1.Text)表示要查找的数p0表示查找的次数findFalse查找的结果，若findtrue表示找到，fin
9、dfalse表示未找到i1查找的起始范围jn查找的终点范围Do While ij And Not find如果还未找完并且未找到pp1查找次数计数m(ij)2计算中点位置mIf keyd(m) Then表示找到的情况findTrueText2.Text”找到！位置为：”Str(m)End IfIf Keyd(m)Then表示查找的数比中间位置上的数大时im1Else表示查找的数比中间位置上的数小时jm1End IfLoopIf Not find Then Text2.Text”未找到！”Text3.Text”共查找的次数为：”Str(p)温馨提示：计算中点位置的语句还可以写成：mInt(ij)
10、/2)或mFix(ij)/2)。三、递归算法1.递归的概念函数或过程调用其本身，称为递归。2.递归算法的基本思想递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题，直到可以直接得出它的解，从而得到原来问题的解。3.采用递归算法须具备的条件(1)每一步骤解决问题的方法要一致。(2)要有结束的边界条件。四、Connection对象用Connection建立和数据库的连接时，首先创建一组ADO对象用于设置打开连接和产生结果集，需要设置连接字符串ConnectionString的参数。下列语句定义一个Connection对象的实例co
11、nn，conn是实例的名称，命名规则与VB变量定义相同，并设置conn的连接字符串：Dim conn As New ADODB.ConnectionDim abc As New ADODB.Recordsetconn.ConnectionString”ProviderMicrosoft.ACE.OLEDB.12.0；Data Source”& App.Path & ”souse1.accdb”其中，“Provider”用于指定连接的提供者，“Data Source”用于指定数据库的文件名(含绝对路径)。App.Path返回当前应用程序所在的绝对路径。Connection对象具有Open、Exe
12、cute、Close等方法，其中Open方法用于建立到数据源的连接，Execute用于执行指定的查询、SQL语句或特定提供者的文本等内容，而Close方法则用于关闭连接。五、Recordset对象用Recordset对象从数据库中查询记录时，要设置ActiveConnection属性的值。语句Set abc.ActiveConnectionconn，使Recordset对象的实例abc与Connection对象的实例conn建立关联。在abc与conn建立关联后，可用Recordset对象的Open方法打开、查询数据表的记录。Open方法的参数为SQL命令。如：abc.Open“SELECT*
13、FROM info”运行后，记录集abc中的数据为SQL语句“SELECT*FROM info”查询到的记录。同样，Recordset对象的Close方法用于关闭对象。Abc.close表示关闭记录集。Recordset对象的Fields集合用于返回当前记录中的数据，如：abc.Fields(”book”)返回当前记录中”book”字段的值；abc.Fields(0)返回当前记录中第一个字段的值，如果第一个字段名为“book”，则abc.Fields(0)与abc.Fields(“book”)返回值相同。例如Recordset对象实例abc打开了下表的记录集：Recordset对象打开的记录集
14、：bookauthorpricePublishing平凡的世界路遥78.2海南人民出版社红楼梦曹雪芹53.6上海教育出版社假设当前记录为第2条记录，则Fields集合返回当前记录某个字段的数据有以下两种方法：(1)abc.Fields(字段序号)，其中字段序号从0开始编号。(2)abc.Fields(“字段名称”)故abc.Fields(0)和abc.Fields(“book”)都返回“红楼梦”，abc.Fields(1)和abc.Fields(“author”)都返回“曹雪芹”，abc.Fields(2)和abc.Fields(“price”)都返回“53.6”，abc.Fields(3)和abc.Fields(“Publishing”)都返回“上海教育出版社”。通过Recordset对象从数据库中返回的这些数据可以通过数组的形式存储，以方便我们后序进行统计、排序、查找等处理。Recordset对象的AddNew方法为可更新的Recordset对象创建一个新记录，它添加一条新的空记录，并且定位在该记录上；Delete方法可将当前记录从记录集中删除；Edit方法可以
