必修3第二单元

知识梳理知识梳理要点突破要点突破第二第二单元算法的程序元算法的程序实现知识梳理知识梳理要点突破要点突破考试标准考试标准考考试内容内容考考试要求要求考考试属性属性1.枚枚举算法及程序算法及程序实现c加加试2.解析算法及程序解析算法及程序实现c3.排序算法及程序排序算法及程序实现c(1)冒泡排序冒泡排序(2)选择排序排序4.查找算法及程序找算法及程序实现c(1)顺序序查找找(2)对分分查找找5.递归算法算法a6.VB访问Access数据数据库a(1)通通过ADO对象象连接数据接数据库(2)通通过Recordset对象象获取数据表中的数据取数据表中的数据知识梳理知识梳理要点突破要点突破一、排序算法及程序实现一、排序算法及程序实现1.排序的含排序的含义及方式及方式(1)所所谓排序就是将无序的数列排序就是将无序的数列变成有序的数列。成有序的数列。(2)排排列列方方式式分分为升升序序(也也称称递增增，即即从从小小到到大大排排列列)和和降降序序(也也称称递减，即从大到小排列减，即从大到小排列)。知识梳理知识梳理要点突破要点突破2.冒泡排序冒泡排序(1)冒泡排序基本思想冒泡排序基本思想将将n个个数数据据看看作作竖向向排排列列的的一一组数数据据，每每趟趟排排序序自自下下而而上上对每每对相相邻数数据据进行行比比较，若若次次序序不不符符合合要要求求就就进行行交交换。每每趟趟排排序序结束束时都都能能使使排排序序范范围内内关关键字字最最小小的的记录像像一一个个气气泡泡一一样升升到到上上端端的的对应位位置置，整整个个排排序序过程程共共进行行n1趟趟，依依次次将将关关键字字最最小小、次小次小的各个数据冒到表的第一个、第二个的各个数据冒到表的第一个、第二个位置上。位置上。知识梳理知识梳理要点突破要点突破(2)冒泡排序算法框架冒泡排序算法框架For i1 To n1 n个数据个数据进行排序，共需行排序，共需进行行n1趟趟第第i趟趟排排序序：从从第第n个个数数到到第第i个个数数，比比较相相邻两两个个数数，符符合合条条件件则进行互行互换。(3)冒泡排序程序冒泡排序程序实现说明：要排序的明：要排序的n个数据已存放个数据已存放d数数组中，以升序中，以升序为例的程序如下：例的程序如下：For i1 To n1n个数排序共需个数排序共需进行行n1趟趟For jn To i1 Step1每每一一趟趟从从后后往往前前，相相邻两两数数两两两两比比较知识梳理知识梳理要点突破要点突破 If d(j)d(j1)Then若若满足条件足条件则进行互行互换 tempd(j)d(j)d(j1)d(j1)temp End IfNext jNext i温温馨馨提提示示：若若要要按按降降序序排排列列，只只需需将将程程序序中中的的语句句“If d(j)d(j1)then”改改为“If d(j)d(j1)Then”即可。即可。知识梳理知识梳理要点突破要点突破3.选择排序排序(1)选择排序的基本思想排序的基本思想每每趟趟排排序序是是在在所所有有的的数数据据中中找找出出最最小小(或或最最大大)的的数数据据，使使它它与与第第一一个个数数据据相相互互交交换位位置置，然然后后再再在在剩剩下下的的数数据据中中找找出出最最小小(或或最最大大)的的数数据据，与与第第二二个个数数据据相相互互交交换位位置置，以以此此类推推，直直到到所所有有元素成元素成为一个有序序列。一个有序序列。知识梳理知识梳理要点突破要点突破(2)选择排序算法框架排序算法框架For i1 To n1n个数排序共需个数排序共需进行行n1趟趟第第i趟排序趟排序在第在第i至第至第n个位置中找到最小数的位置个位置中找到最小数的位置k将找到的最小数将找到的最小数(k位置上的数位置上的数)与与i位置上的数互位置上的数互换Next i注意：当注意：当ki时，将，将k位置上的数与位置上的数与i位置上的数互位置上的数互换。知识梳理知识梳理要点突破要点突破(3)选择排序的程序排序的程序实现说明：要排序的明：要排序的n个数据已存放个数据已存放d数数组中。中。以升序以升序为例的程序如下：例的程序如下：For i1 To n1n个排序共个排序共进行行n1趟排序趟排序ki第第i趟排序趟排序时，首先用，首先用k记录iFor ji1 To nk位置上的数依次与位置上的数依次与j位置上的数位置上的数进行比行比较 If d(k)d(j)Then kj若若找找到到比比k位位置置上上更更小小的的数数，则更新更新k的的值Next j知识梳理知识梳理要点突破要点突破If 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)顺序序查找的基本思想找的基本思想从从第第一一个个数数据据开开始始，从从左左往往右右(或或从从上上到到下下)将将数数据据按按顺序序逐逐个个与与给定定的的值进行行比比较，若若某某个个数数据据和和给定定值相相等等，则查找找成成功功，找到并找到并输出所出所查数据的位置；反之，数据的位置；反之，查找失找失败。若有若有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(在在文文本本框框Text1中中输入入)，查找找的的数数据据存存放放在数在数组d中。中。pos为找到数的位置，找到数的位置，pos0表示未找到。表示未找到。P表示表示查找的次数。找的次数。keyVal(Text1.Text)Val要根据要根据实际情况决定是否要添加情况决定是否要添加p0pos0知识梳理知识梳理要点突破要点突破findFalsefind表示表示查找找结果果i1Do While in And Not find表表示示还没没找找完完并并且且还未未找找到到，则继续查找，找，Not find也可表示也可表示为findfalse pp1 If keyd(i)Then posi findTrue End Ifii1Loop知识梳理知识梳理要点突破要点突破If find Then也可表示也可表示为If findtrue thenText2.Text“在在d(“Str(pos)”)中中”ElseText2.Text“未找到未找到”End If知识梳理知识梳理要点突破要点突破3.对分分查找找(1)对分分查找的基本思想找的基本思想在在有有序序的的数数据据序序列列中中(一一般般存存放放在在数数组中中)，首首先先把把要要查找找的的数数据据与与数数组中中间位位置置的的元元素素进行行比比较，如如果果相相等等，则查找找成成功功并并退退出出查找找；否否则，根根据据数数组元元素素的的有有序序性性，确确定定数数据据应在在数数组的的前前半半部部分分还是是在在后后半半部部分分查找找；在在确确定定了了新新的的查找找范范围后后，重重复复进行行以上比以上比较，直到找到或未找到，直到找到或未找到为止。止。温馨提示：温馨提示：对分分查找的前提是被找的前提是被查找的数据序列必找的数据序列必须是有序。是有序。“未找到未找到”是指当指定范是指当指定范围内的起点大于内的起点大于终点仍未找到点仍未找到该数据。数据。知识梳理知识梳理要点突破要点突破(2)对分分查找算法基本框架找算法基本框架说明：要明：要查找的数找的数为key，待，待查找的数存放在数找的数存放在数组d中。中。i为查找找范范围的的起起点点，j为查找找范范围的的终点点，m为范范围i，j的的中中间位置。位置。i1jnDo While ij 计算中点位置算中点位置m 比比较key与与d(m)，并做相，并做相应处理理 Loop 若若ij，则表示未找到表示未找到知识梳理知识梳理要点突破要点突破(3)对分分查找程序找程序实现在在n个个数数组元元素素中中依依次次查找找，找找到到第第1个个满足足条条件件的的值，查找找就就结束，束，输出找到元素所在的位置；若找不到，出找到元素所在的位置；若找不到，输出出“未找到未找到”。程序程序实现：设要要查找找的的数数据据是是key(在在文文本本框框Text1中中输入入)，查找找的的数数据据存存放放在数在数组d中。中。在在文文本本框框Text2中中输出出查找找结果果，若若找找到到输出出“找找到到！位位置置为：X”，否，否则输出出“未找到！未找到！”在文本框在文本框Text3中中输出共出共查找的次数。找的次数。P表示表示查找的次数。找的次数。知识梳理知识梳理要点突破要点突破核心代核心代码为(以升序以升序为例例)：keyVal(Text1.Text)表示要表示要查找的数找的数p0表示表示查找的次数找的次数findFalse查找找的的结果果，若若findtrue表表示示找找到到，find false表示未找到表示未找到i1查找的起始范找的起始范围jn查找的找的终点范点范围Do While ij And Not find如果如果还未找完并且未找到未找完并且未找到pp1查找次数找次数计数数m(ij)2计算中点位置算中点位置mIf keyd(m)Then表示找到的情况表示找到的情况 findTrue知识梳理知识梳理要点突破要点突破 Text2.Text“找到！位置找到！位置为：”Str(m)End IfIf Keyd(m)Then表示表示查找的数比中找的数比中间位置上的数大位置上的数大时 im1Else表示表示查找的数比中找的数比中间位置上的数小位置上的数小时 jm1End IfLoopIf Not find Then Text2.Text“未找到！未找到！”Text3.Text“共共查找的次数找的次数为：”Str(p)温温馨馨提提示示：计算算中中点点位位置置的的语句句还可可以以写写成成：mInt(ij)/2)或或mFix(ij)/2)。知识梳理知识梳理要点突破要点突破三、递归算法三、递归算法1.递归的概念的概念2.递归算法的基本思想算法的基本思想3.采用采用递归算法算法须具具备的条件的条件函数或函数或过程程调用其本身，称用其本身，称为递归。递归算算法法的的基基本本思思想想是是把把规模模较大大的的、较难解解决决的的问题变成成规模模较小小的的、容容易易解解决决的的同同一一问题，规模模较小小的的问题又又变成成规模模更更小小的的问题，直到可以直接得出它的解，从而得到原来，直到可以直接得出它的解，从而得到原来问题的解。的解。(1)每一步每一步骤解决解决问题的方法要一致。的方法要一致。(2)要有要有结束的束的边界条件。界条件。知识梳理知识梳理要点突破要点突破四、四、Connection对象对象用用Connection建建立立和和数数据据库的的连接接时，首首先先创建建一一组ADO对象象用用于于 设 置置 打打 开开 连 接接 和和 产 生生 结 果果 集集，需需 要要 设 置置 连 接接 字字 符符 串串ConnectionString的的参参数数。下下列列语句句定定义一一个个Connection对象象的的实例例conn，conn是是实例例的的名名称称，命命名名规则与与VB变量量定定义相相同同，并并设置置conn的的连接字符串：接字符串：Dim conn As New ADODB.ConnectionDimabc As New ADODB.Recordsetconn.ConnectionString“ProviderMicrosoft.ACE.OLEDB.12.0；Data Source”&App.Path&“souse1.accdb”知识梳理知识梳理要点突破要点突破其其中中，“Provider”用用于于指指定定连接接的的提提供供者者，“Data Source”用用于于指指定定数数据据库的的文文件件名名(含含绝对路路径径)。App.Path返返回回当当前前应用用程程序序所所在的在的绝对路径。路径。Connection对象象具具有有Open、Execute、Close等等方方法法，其其中中Open方方法法用用于于建建立立到到数数据据源源的的连接接，Execute用用于于执行行指指定定的的查询、SQL语句句或或特特定定提提供供者者的的文文本本等等内内容容，而而Close方方法法则用用于于关关闭连接。接。知识梳理知识梳理要点突破要点突破五、五、Recordset对象对象用用 Recordset对 象象 从从 数数 据据 库 中中 查 询 记 录 时，要要 设 置置ActiveConnection属属性性的的值。语句句Set abc.ActiveConnectionconn，使使Recordset对象象的的实例例abc与与Connection对象象的的实例例conn建立关建立关联。在在abc与与conn建建立立关关联后后，可可用用Recordset对象象的的Open方方法法打打开开、查询数据表的数据表的记录。Open方方法法的的参参数数为SQL命命令令。如如：abc.Open“SELECT*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对象打开的象打开的记录集：集：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方方法法可可以以编辑修修改改数数据据库的的记录，注注意意首首先先要要将将需需要要编辑的的记录成成为当当前前记录，然然后后使使用用Edit方方法法修修改改记录内内容容，使使用用Edit方方法法后后，再再移移动记录或或者者使使用用Update方方法法把把数数据据存存入入到到数数据据库中中；Move方方法法可可以以使使不同的不同的记录成成为当前当前记录，主要有，主要有5种使用方法：种使用方法：知识梳理知识梳理要点突破要点突破MoveFirst：移：移动到到记录集的第一条集的第一条记录。MoveLast：移：移动到到记录集的最后一条集的最后一条记录。MoveNext：移：移动到到记录集的下一条集的下一条记录。MovePrevious：移：移动到到记录集的上一条集的上一条记录。Move：可以使用：可以使用Move方法向前或向后移方法向前或向后移动若干条若干条记录。但但应注注意意：若若到到数数据据表表结尾尾处还继续向向下下移移动，程程序序会会出出错，因因此此在在使使用用MoveNext时要要判判断断Recordset的的BOF和和EOF属属性性，判判断断记录指指针是是不不是是到到达达首首记录之之前前或或尾尾记录之之后后。EOF取取值为“True”时表示已表示已经到达到达记录集的集的结尾，否尾，否则EOF的的值为“False”。若若BOF和和EOF的取的取值均均为“True”则表示此表示此记录集集为空。空。知识梳理知识梳理要点突破要点突破三、三、SQL：Select语句语句SELECT语句句是是结构构化化查询语言言SQL中中常常见的的语句句，主主要要用用于于从从数数据据表表中中查询数数据据，如如语句句“SELECT*FROM info”表表示示查询数数据表据表“info”的全部数据。的全部数据。语句句总结如下：如下：(1)定定义Connection对象的象的实例例conn和和Recordset对象的象的实例例abc。Dim conn As New ADODB.ConnectionDimabc As New ADODB.Recordset知识梳理知识梳理要点突破要点突破(2)为实例例conn设置置ConnectionString属性属性值。conn.ConnectionString“ProviderMicrosoft.ACE.OLEDB.12.0；DATA Source”&App.Path&“souse1.accdb”(3)打开与数据打开与数据库的的连接。接。conn.Open(4)建立建立实例例abc与与conn之之间的关的关联。Set abc.ActiveConnectionconn(5)执行行SELECT命令，将命令，将查询结果返回果返回给abc。abc.Open“SELECT*FROM info”知识梳理知识梳理要点突破要点突破(6)在在应用程序中引用用程序中引用abc中当前中当前记录的字段的字段值。Label1.Captionabc.Fields(“book”)Label2.Captionabc.Fields(“price”)(7)关关闭记录集。集。Abc.close(8)关关闭与数据与数据库的的连接。接。conn.Close知识梳理知识梳理要点突破要点突破一、冒泡排序和选择排序一、冒泡排序和选择排序冒冒泡泡排排序序和和选择排排序序的的程程序序实现很很相相似似，都都用用到到双双重重循循环，以以及及数数组元元素素之之间的的比比较，因因此此需需要要准准确确区区分分两两者者之之间的的代代码异异同，能将程序同，能将程序补充完整。充完整。知识梳理知识梳理要点突破要点突破二、明确两种排序算法的比较次数和交换次数二、明确两种排序算法的比较次数和交换次数冒冒泡泡排排序序算算法法比比较次次数数为总的的比比较次次数数：n(n1)/2。在在每每一一遍遍加加工工的的过程程中中需需要要对逆逆序序的的数数据据两两两两进行行交交换，选择排排序序的的比比较次次数数为n(n1)/2。两两种种排排序序的的比比较次次数数与与待待排排序序元元素素的的初初始始状状态无无关关，而而交交换次次数数与与待待排排序序元元素素的的初初始始状状态有有关关，即即当当待待排排序序元元素素已已经有有序序，交交换0次次，最最坏坏情情况况下下选择排排序序交交换n1次次，冒泡排序最坏情况下交冒泡排序最坏情况下交换(n1)(n2)/2次。次。知识梳理知识梳理要点突破要点突破三三、理理解解两两种种排排序序算算法法的的原原理理基基础础上上能能准准确确模模拟拟数数据据交交换换后后数数列列的变化的变化一一般般情情况况下下，冒冒泡泡排排序序的的交交换发生生在在相相邻两两数数为逆逆序序对时，相相邻两两数数两两两两交交换，其其范范围是是待待排排序序区区域域；选择排排序序的的交交换发生生在在待待排排序序区区域域的的最最小小(最最大大)数数和和待待排排序序区区域域的的第第一一个个数数进行行交交换，若若最最小小数数(最最大大数数)是是待待排排序序区区域域的的第第一一个个数数，则无无需需交交换。这要要求求学学生生对知知识进行行内内化化理理解解，死死记硬硬背背的的方方式式则会会遇遇到到困困难，建建议在在复复习之之初初可可以以用用跟跟踪踪模模拟的的方方式式，观察察数数据据的的变化化来加深理解。来加深理解。知识梳理知识梳理要点突破要点突破四、对分查找算法的应用的前提条件四、对分查找算法的应用的前提条件五、对分查找的工作原理的理解五、对分查找的工作原理的理解六、两种查找的程序实现六、两种查找的程序实现待待查数列有序，而数列有序，而顺序序查找没有找没有这样的要求，可以无序。的要求，可以无序。比比较次数是学生容易忽略的地方。次数是学生容易忽略的地方。包括中包括中间点位置的确定、新的点位置的确定、新的查找区找区间的的变化以及模化以及模拟跟踪。跟踪。知识梳理知识梳理要点突破要点突破【典例【典例1】对10个数据个数据进行冒泡排序，需要比行冒泡排序，需要比较的次数是的次数是()A.90 B.110 C.45 D.55解析解析本题要求对规模为本题要求对规模为10个的数据进行冒泡排序的比较次数。个的数据进行冒泡排序的比较次数。根根据据冒冒泡泡排排序序算算法法比比较较次次数数的的计计算算方方法法可可知知，当当n10时时，比比较次数较次数10(101)/245，所以选择答案，所以选择答案C。答案答案C知识梳理知识梳理要点突破要点突破【变变式式1】对数数组元元素素a(1)到到a(6)进行行降降序序排排序序，采采用用选择排排序序算法的某算法的某VB程序段如下：程序段如下：For m1 To 5pmFor nm1 To 8 If a(n)a(p)Then pnNext nIf pm Then _Next m当当第第一一遍遍排排序序之之后后得得到到的的数数据据序序列列为12，2，6，8，9，11。方方框中的框中的语句是句是()知识梳理知识梳理要点突破要点突破A.tp：pm：mtB.a(p)a(m)：a(p)a(m)C.pm：mpD.ta(p)：a(p)a(m)：a(m)t解解析析选选择择排排序序算算法法中中，内内层层循循环环的的部部分分用用于于找找出出m到到5的的数数列列中中，最最大大的的数数，当当发发现现之之后后，存存储储的的是是该该数数据据的的下下标标。当当内内存存循循环环结结束束之之后后，发发现现在在第第m个个位位置置上上存存放放的的不不是是最最大大数数时时，需需要要将将两两个个数数进进行行交交换换，而而不不是是将将下下标标进进行行互互换换。且且交交换换的的程程序序编编写写需需要有第三个暂存变量来辅助存储。要有第三个暂存变量来辅助存储。答案答案D知识梳理知识梳理要点突破要点突破【典典例例2】篮球球联赛中中，有有5个个班班级的的比比赛积分分依依次次为14，11，13，8，9。若若采采用用冒冒泡泡排排序序算算法法对其其进行行从从小小到到大大排排序序，则完完成第二遍成第二遍时的的结果是果是()A.8，11，13，14，9 B.8，9，13，14，11C.8，9，14，11，13 D.14，13，11，9，8知识梳理知识梳理要点突破要点突破解解析析从从小小到到大大冒冒泡泡排排序序的的基基本本思思想想是是从从最最后后的的一一个个元元素素起起，自自后后向向前前比比较较相相邻邻的的两两个个数数据据，将将较较小小的的数数据据换换到到前前面面，较较大大的的换换到到后后面面。重重复复这这一一过过程程，直直到到处处理理完完最最后后两两个个数数据据，称称为为一一遍遍加加工工。因因此此第第一一遍遍加加工工时时：9和和8，9不不动动；8和和13，13换换到到后后面面，8换换到到前前面面；8和和11，11换换到到后后面面，8换换到到前前面面；8和和14，14换换到到后后面面，8换换到到前前面面。这这是是第第一一遍遍加加工工，结结果果是是：8，14，11，13，9。第第二二遍遍加加工工时时：9和和13，13换换到到后后面面，9换换到到前前面面；9和和11，1l换换到到后后面面，9换换到到前前面面；9和和14，14换换到到后后面面，9换换到到前前面面。这这是是第第二二遍加工，结果是：遍加工，结果是：8，9，14，11，13。答案答案C知识梳理知识梳理要点突破要点突破【变变式式2】(20159月月浙浙江江选选考考模模拟拟)采采用用如如下下选择排排序序算算法法对数数组a中中5个个数数据据“23，86，98，65，2”按按从从小小到到大大的的顺序序进行行排排序。序。For i1 To 4 ki For ji1 To 5 If a(j)a(k)Then kj Next j If ki Then ta(i)：a(i)a(k)：a(k)t End IfNext i知识梳理知识梳理要点突破要点突破整整个个排排序序过程程中中，数数组中中的的数数据据比比较次次数数和和交交换次次数数分分别是是()A.10次和次和3次次 B.10次和次和4次次C.15次和次和3次次 D.15次和次和10次次解解析析本本题题考考查查对对VB冒冒泡泡排排序序算算法法的的实实现现过过程程。第第一一遍遍排排序序时时，比比较较4次次，交交换换1次次，数数据据变变为为“2，86，98，65，23”；第第二二遍遍排排序序时时，比比较较3次次，交交换换1次次，数数据据变变为为“2，23，98，65，86”；第第三三遍遍排排序序时时，比比较较2次次，交交换换1次次，数数据据变变为为“2，23，65，98，86”；第第四四遍遍排排序序时时，比比较较1次次，交交换换1次次，数数据据变变为为“2，23，65，86，98”；合计数据比较；合计数据比较10次，交换次，交换4次，选项次，选项B正确。正确。答案答案B知识梳理知识梳理要点突破要点突破【典例【典例3】(20126月浙江会考月浙江会考)有如下有如下Visual Basic程序段：程序段：ma(1)i2Do While i10If ma(i)Then ma(i)ii1Loop该程序段程序段执行后，行后，变量量m中存中存储的是的是()A.a(1)至至a(10)中的最大中的最大值B.a(1)至至a(10)中的最小中的最小值C.a(2)至至a(10)中的最大中的最大值D.a(2)至至a(10)中的最小中的最小值知识梳理知识梳理要点突破要点突破解析解析本题主要考查选择排序的核心代码：寻找最小值或最大值。本题主要考查选择排序的核心代码：寻找最小值或最大值。先先假假设设数数组组的的第第一一项项是是最最大大的的，并并赋赋值值给给变变量量m，然然后后把把从从第第二二项项开开始始的的所所有有数数组组元元素素跟跟变变量量m进进行行比比较较，如如果果比比m大大，则则把把该该元元素素赋赋值值给给m。这这样样循循环环结结束束后后，变变量量m中中存存储储的的就就是是该该数数据据中中的最大值。的最大值。答案答案A知识梳理知识梳理要点突破要点突破【变变式式3】(2013浙浙江江学学业业水水平平考考试试)实现某某排排序序算算法法的的部部分分VB程序如下：程序如下：For i1 To 6kiFor ji1 To 7 If a(j)a(k)Then kjNext jIf ik Thenta(i)：a(i)a(k)：a(k)tEnd IfNext i知识梳理知识梳理要点突破要点突破在在排排序序过程程中中，经过某某一一遍遍排排序序“加加工工”后后，数数组元元素素a(1)到到a(7)的的数数据据依依次次为“10，41，75，12，63，11，85”。下下一一遍遍排排序序“加工加工”后数后数组元素元素a(1)到到a(7)的数据依次是的数据依次是()A.10，11，41，75，12，63，85B.10，11，75，12，63，41，85C.10，11，12，75，63，41，85D.10，11，12，41，63，75，85知识梳理知识梳理要点突破要点突破解解析析(1)根根据据算算法法的的代代码码特特征征确确定定是是选选择择排排序序。(2)由由a(j)a(k)确确定定排排序序的的目目标标是是升升序序。(3)观观察察某某遍遍排排序序“加加工工”后后的的数数列列发发现现只只有有第第一一个个元元素素已已经经处处于于有有序序状状态态，因因此此下下一一遍遍排排序序后后的的目目标标是是将将第第二二个个小小的的数数11选选出出来来和和第第二二个个位位置置的的数数41进进行行交交换换，从从而而获获得得所求答案。所求答案。答案答案B知识梳理知识梳理要点突破要点突破【典典例例4】下下列列VB程程序序段段是是选择排排序序程程序序的的主主要要部部分分。其其中中虚虚线框内代框内代码用于用于寻找数据元素找数据元素d(i)到到d(n)的最小的最小值。For i1 To n1If ik Then ktd(i)：d(i)d(k)：d(k)ktNext i知识梳理知识梳理要点突破要点突破框内代框内代码运行运行结束束时，保存最小，保存最小值的数的数组元素一定是元素一定是()A.d(n)B.d(j)C.d(i)D.d(k)解解析析变变量量k记记录录当当前前找找到到的的最最小小值值的的位位置置，即即数数组组元元素素的的下下标标，则则d(k)就就是是当当前前找找到到的的最最小小的的数数组组元元素素。它它的的思思想想方方法法是是先先假假设设数数组组的的第第i项项是是最最小小的的(第第i遍遍排排序序)，因因此此k记记为为i，然然后后把把从从第第i1项项开开始始的的所所有有数数组组元元素素跟跟d(k)进进行行比比较较，如如果果比比d(k)小小，则则用用k记记录录该该元元素素的的下下标标。这这样样循循环环结结束束后后，变变量量k中中存存储储的的就就是是数数组组中中从从第第i项项至至第第n项项的的最最小小元元素素的的下下标标，d(k)就就是是第第i项项至至第第n项项中中的的最小元素。最小元素。答案答案D知识梳理知识梳理要点突破要点突破【变变式式4】对数数组元元素素a(1)到到a(8)进行行升升序序排排序序，其其排排序序算算法法的的VB部分程序段如下：部分程序段如下：For m1 To 7pmFor nm1 To 8Next nIf pm Then ta(p)：a(p)a(m)：a(m)tNext m知识梳理知识梳理要点突破要点突破方框中的方框中的语句是句是()A.If a(n)a(p)Then pmB.If a(n)a(p)Then pnC.If a(n)a(p)Then pnD.If a(n)a(p)Then pm解解析析(1)这这样样的的题题首首先先要要观观察察已已有有的的程程序序代代码码确确定定算算法法类类型型，比比如如“pmFor nm1 To 8”可可以以确确定定该该排排序序算算法法为为选选择择排排序序。(2)再再确确认认排排序序的的升升降降特特性性，确确定定判判断断的的条条件件，最最后后看看清清楚楚变变量量的的名名称称。由由于于是是升升序序排排序序，则则判判断断的的条条件件是是a(n)a(p)的的时时候候更更新新p指针，指向当前第指针，指向当前第m小的数，也就是小的数，也就是n所在的位置。所在的位置。答案答案B知识梳理知识梳理要点突破要点突破【典典例例5】使使用用对分分查找找在在已已排排序序的的数数组d(数数组元元素素d(1)d(2)d(n)中中查找找key的的算算法法流流程程图如如图所所示示。其其中中框中的内容分框中的内容分别是是()知识梳理知识梳理要点突破要点突破A.jm1im1B.jm1im1C.jm1im1D.jm1im1解解析析因因为为数数据据是是升升序序排排列列的的，因因此此，当当keyd(m)时时，要要查查找找的的数数据据应应在在m的的左左边边，即即查查找找的的范范围围的的终终点点j修修改改为为jm1，当当keyd(m)时时，要要查查找找的的数数据据应应在在m的的右右边边，即即查查找找的的范范围围的的起起点点j修改为修改为im1。答案答案C知识梳理知识梳理要点突破要点突破【典例【典例6】有两有两组数据：数据：54，31，43，12，8，73，56，34，89，60，23，6787，83，75，70，63，59，55，37，33，21，17，7下列有关下列有关查找方法的描述，不正确的是找方法的描述，不正确的是()A.可以直接使用可以直接使用顺序序查找找B.可以直接使用可以直接使用对分分查找找C.可以直接使用可以直接使用对分分查找找D.可以直接使用可以直接使用顺序序查找找解解析析观观察察数数列列为为无无序序，显显然然不不符符合合对对分分查查找找的的有有序序前前提提。为为降降序序，可可以以用用对对分分查查找找，同同时时也也适适用用于于顺顺序序查查找找。注注意意此此题问的是不正确的选项。题问的是不正确的选项。C知识梳理知识梳理要点突破要点突破【典典例例7】某某学学校校图书管管理理系系统中中有有10万万条条图书资料料记录(已已经索索引引排排序序)，假假设从从中中取取出出一一条条记录并并与与待待查找找项进行行比比较所所花花时间为10毫毫秒秒，则用用对分分法法在在该系系统中中查找找任任意意一一本本指指定定图书最多花最多花费的的时间约为()A.100万毫秒万毫秒 B.50万毫秒万毫秒C.10毫秒毫秒 D.170毫秒毫秒知识梳理知识梳理要点突破要点突破答案答案D知识梳理知识梳理要点突破要点突破【典典例例8】小小王王设计了了一一个个算算法法来来求求xn(x的的n次次方方)的的值，他他的的算算法法思思想想是是：把把xn转换为x*xn1，而而xn1又又可可以以转换为x*xn2，如如此此继续，直直到到x*x0，而而x01，从从而而求求出出了了xn的的值。小小王王采采用用的算法是的算法是()A.解析算法解析算法 B.枚枚举算法算法C.递归算法算法 D.查找算法找算法解解析析本本题题中中求求“xn”的的值值，采采用用“大大事事化化小小，小小事事化化了了”的的方法，符合递归算法的基本思想。方法，符合递归算法的基本思想。答案答案C知识梳理知识梳理要点突破要点突破【典例【典例9】下列下列VB程序中，程序中，f是一个是一个递归函数。函数。Private Sub Command1_Click()Dim y as Long Text1.Text“”“”yf(3)Label1.Captionstr(y)End SubFunction f(n As Integer)as Long Text1.TextText1.TextStr(n)If n1 Then f1知识梳理知识梳理要点突破要点突破 Else ff(n1)2 End IfEnd Function程程序序运运行行时，单击命命令令按按钮Command1后后，文文本本框框Text1中中显示示的内容是的内容是()A.3 B.321 C.123 D.2知识梳理知识梳理要点突破要点突破解解析析 这这段段程程序序由由两两部部分分组组成成：事事件件处处理理过过程程(Private Sub Command1_Click()和和自自定定义义函函数数(Function f(n As Integer)As Long)。在在自自定定义义函函数数f中中又又出出现现了了调调用用函函数数f本本身身的的语语句句ff(n1)2，因此，因此f函数采用的是递归算法。函数采用的是递归算法。在在事事件件处处理理过过程程Private Sub Command1_Click()中中，语语句句yf(3)表表示示调调用用函函数数f，将将参参数数3传传递递给给f函函数数中中的的变变量量n，最最终终将将函函数数的的返回值赋给变量返回值赋给变量y。函数函数f执行时，执行时，n的值和的值和Text1中的内容如下表所示：中的内容如下表所示：F(n)nText1.textF(3)33F(2)232F(1)1321知识梳理知识梳理要点突破要点突破因此，在文本框因此，在文本框Text1上显示的内容为上显示的内容为321。如如问问标标签签Label1中中显显示示的的内内容容为为多多少少？那那又又该该如如何何解解题题呢呢？这这就就要要求求大大家家掌掌握握递递归归算算法法的的实实现现过过程程了了。递递归归函函数数f(n)的的执执行行过过程程如图所示：如图所示：即即yf(3)5，因此在标签，因此在标签Label1上显示的内容为上显示的内容为5。答案答案B知识梳理知识梳理要点突破要点突破七、七、VB和数据库的连接和数据库的连接八、八、Fields集合集合对学学生生来来说，这部部分分知知识比比较陌陌生生，牵涉涉一一系系列列的的基基本本概概念念和和操操作作，刚开开始始容容易易出出现各各种种错误，需需要要学学会会根根据据产生生的的错误提提示，分析示，分析产生生该错误的可能原因。的可能原因。要要求求了了解解Fields集集合合通通过指指定定字字段段序序号号或或字字段段名名返返回回数数据据的的方方法法，要要清清楚楚字字段段名名和和字字段段序序号号之之间的的对应关关系系以以及及当当前前记录是是哪哪一一条。条。Fields集合返回的是当前集合返回的是当前记录的数据。的数据。知识梳理知识梳理要点突破要点突破九、九、VB应用程序应用程序通通过ADO访问Access数数据据库，将将数数据据库作作为VB程程序序设计时的的数数据据源源，可可用用数数组的的形形式式存存储获取取的的数数据据，进而而可可以以通通过枚枚举、解析等算法解析等算法对从数据从数据库中中获取的数据取的数据进行行简单的的处理。理。知识梳理知识梳理要点突破要点突破【典典例例11】通通过ADO的的Recordset对象象从从数数据据库中中获取取数数据据，代代码如下：如下：Dim aa As New ADODB.Recordsetaa.Open“SELECT*FROM info”在在调试时出出现了如了如图所示的所示的错误提示：提示：知识梳理知识梳理要点突破要点突破产生生该错误提示的原因可能是提示的原因可能是()A.没有定没有定义ADO的的Connection对象象实例例B.Recordset对象象实例没有打开例没有打开记录集集 C.没有没有设置置Recordset对象象实例的例的ActiveConnection连接属性接属性D.指定的数据指定的数据库文件不存在文件不存在解解析析代代码码中中第第一一行行定定义义了了Recordset对对象象实实例例aa，第第二二行行代代码码的的功功能能是是打打开开记记录录集集，查查询询数数据据库库的的SQL语语句句“SELECT*FROM info”表表示示获获取取数数据据库库中中表表“info”的的所所有有记记录录，没没有有错错误误。但但代代码码中中没没有有设设置置Recordset对对象象实实例例aa的的ActiveConnection属属性性值值，使使之与之与Connection对象实例产生关联，所以提示该错误。对象实例产生关联，所以提示该错误。答案答案C知识梳理知识梳理要点突破要点突破【典典例例12】通通过ADO的的Recordset对象象实例例aa打打开开了了如如下下表表所所示的示的记录集：集：序号序号货名名售价售价数量数量1B5笔笔记本本6.51224B橡皮橡皮1.2503签字笔字笔1.1454圆规5.325知识梳理知识梳理要点突破要点突破当当前前记录是是第第3条条，要要用用Fields集集合合返返回回第第3个个字字段段的的信信息息，正正确确的表示是的表示是()A.aa.Fields(0)B.aa.Fields(1)C.aa.Fields(“序号序号”)D.aa.Fields(“售价售价”)解解析析需需要要了了解解Fields集集合合的的两两种种书书写写格格式式，指指定定字字段段名名或或者者字字段段序序号号。题题目目要要求求返返回回第第3个个字字段段的的信信息息，即即“售售价价”字字段段的的信信息息。而而字字段段序序号号是是从从0开开始始编编号号，所所以以第第3个个字字段段应应该该是是编编号号2，故故A、B选项均错误。选项均错误。答案答案D知识梳理知识梳理要点突破要点突破【典典例例13】小小叶叶编写写了了一一个个Visual Basic程程序序，用用于于查找找数数据据库sq.mdt，文文件件中中所所有有相相同同身身高高的的同同学学编号号。程程序序运运行行界界面面如如图所所示示，在在列列表表框框List1中中显示示所所有有同同学学的的编号号和和身身高高(按按身身高高从从低低到到高高排排列列)，在在文文本本框框Text1中中输入入需需要要查找找的的身身高高，单击“查找找”按按钮Command1，在在列列表表框框List2中中显示示所所有有此此身身高高的的同同学学编号号。数数组a和和数数组b分分别存存储同同学学的的编号号和和对应的的身身高高(身高已从低到高排列身高已从低到高排列)。知识梳理知识梳理要点突破要点突破解决此解决此问题的程序代的程序代码如下：如下：Dim conn As New ADODB.ConnectionDim rs As New ADODB.RecordsetDim n As IntegerDim a(500)As StringDim b(500)as IntegerPrivate Sub Form_Load()conn.ConnectionString“ProviderMicrosoft.ACE.OLEDB.12.0；DATA Source”&App.Path&“/sq.accdb”conn.Open知识梳理知识梳理要点突破要点突破到到记录集最后一条集最后一条记录后退出循后退出循环Set rs.ActiveConnectionconnrs.Open“SELECT*FROM shengao”n0Do While Not rs.EOFnn1a(n)rs.Fields(“bh”)b(n)rs.fields(“sg”)rs.MoveNext移移动到下一条到下一条记录Looprs.close知识梳理知识梳理要点突破要点突破 conn.Close Set rsNothing Set connNothingEnd SubPrivate Sub Command1_Click()此此过程程用用于于在在列列表表框框List2中中显示示给定定身身高高的的所所有有学学生生的的编号，代号，代码略。略。End Sub以下函数用于以下函数用于查找找给定身高的学生的相关信息定身高的学生的相关信息Private Function FindEx(k As Integer)As Integer Dim f As Boolean，i As Integer，j As Integer，m As Integer知识梳理知识梳理要点突破要点突破 Dim f As Boolean，i As Integer，j As Integer，m As Integer i1：jn fFalse Do While(ij)And Not(f)mFix(ih)/2)If kb(m)Thenf_ElseIf kb(m)Thenjm1知识梳理知识梳理要点突破要点突破Else_End IfEnd IfLoopIf f Then FindExm Else FindEx0找到返回找到返回m,否否则返回返回0End Function(1)FindEx函函数数主主要要采采用用的的算算法法是是_。(填填：顺序序查找找/对分分查找找)(2)在在程程序序和和划划线处，填填入入适适当当的的语句句或或表表达达式式，把把程程序序补充充完整：完整：程序中程序中划划线处应填入填入_。程序中程序中划划线处应填入填入_。知识梳理知识梳理要点突破要点突破解解析析先先设设置置查查找找范范围围i和和j(i1，jn)，查查找找过过程程中中，mFix(ij)/2)程程序序在在区区别别i和和j中中取取中中间间数数据据，然然后后将将需需要要查查找找的的数数据据与与b(m)比比较较，相相等等则则返返回回m；若若不不相相等等，再再比比较较k和和b(m)，如如果果是是小小于于，就就将将查查找找的的终终点点j设设置置为为m1，否否则则将将查查找找的的起起点点i设设置置为为m1。答案答案(1)对分分查找找(2)Trueim1或或i1m