高三信息技术浙江选考一轮复习 算法与程序设计 算法的程序实现.docx

高三信息技术浙江选考一轮复习 算法与程序设计 算法的程序实现.docx

《高三信息技术浙江选考一轮复习 算法与程序设计 算法的程序实现.docx》由会员分享，可在线阅读，更多相关《高三信息技术浙江选考一轮复习 算法与程序设计 算法的程序实现.docx（13页珍藏版）》请在冰点文库上搜索。

高三信息技术浙江选考一轮复习算法与程序设计算法的程序实现

算法与程序设计

算法的程序实现

[浙江考试标准]

考试内容

考核要求

考试属性

1.枚举算法及程序实现

c

加试

2.解析算法及程序实现

c

3.排序算法及程序实现

（1）冒泡排序

（2）选择排序

c

4.查找算法及程序实现

（1）顺序查找

（2）对分查找

c

5.递归算法

a

6.VB访问Access数据库

（1）通过ADO对象连接数据库

（2）通过Recordset对象获取数据表中的数据

a

一、枚举算法

1．枚举算法的基本思想

根据问题的本身性质，①________出该问题②________可能的情况，并根据题目的条件逐一分析、判断是否满足条件，若满足，则它是问题的一个解，从而挑选出符合条件的③________。

2．枚举算法解题的基本思路

（1）确定枚举对象、枚举范围和判断条件。

（2）一一列举可能的解，验证是否是问题的解。

3．枚举算法程序实现的三要素。

（1）枚举解时，既不能遗漏任何一个真正解，又不能有重复，用循环语句实现。

（2）条件判断时，利用问题提供的约束条件筛选、判断解的正确性，用分支语句实现。

（3）求解形式一般以输出解的内容或进行与解有关的其他计算。

二、解析算法

1．解析算法的基本思想

用解析的方法找出表示问题的前提条件与所求结果之间关系的④________，并通过表达式的计算来实现问题的求解。

2．解析算法解题的基本思路

（1）建立正确的数学模型，即得出正确的数学表达式。

（2）保证计算过程描述的正确性。

用正确合理的VB变量、表达式来表示已经得出的数学表达式。

3．解析算法程序实现的步骤

（1）运用解析算法分析问题，寻找问题中各要素之间的关系，用⑤________表示它们的关系。

（2）写出解决问题的解析步骤，编写程序实现，通过运行程序求得问题的正确解。

三、冒泡排序

1．冒泡排序

基本思想是在待排序的数据中，先找到最小（大）的数据将它放到最前面，再从第二个数据开始，找到第二小（大）的数据将它放到第二个位置，以此类推，直到只剩下最后一个数据为止。

2．冒泡排序的实现要素

（1）将数据存放在数组中，确定数组的名称、元素个数。

（2）比较与交换⑥________进行，在冒泡排序中，第i遍排序比较n－i次，最多交换n－i次。

（3）强调⑦__________元素的比较和交换。

3．冒泡排序的程序实现

（1）从后向前实现冒泡排序

从后向前实现冒泡排序的程序结构：

（2）从前向后实现冒泡排序

从前向后实现冒泡排序的程序结构：

【自我校对】　①一一列举　②所有　③所有解　④数学表达式　⑤数学表达式　⑥同时　⑦相邻

四、选择排序

1．选择排序

基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依次类推，直至所有数据排序完成。

2．选择排序的实现要素

（1）将数据存放在数组中，确定数组的名称、元素个数。

（2）强调⑧________。

在第i遍排序中，比较n－i次，最多交换1次。

（3）变量k仅用于记录需要寻找的最值（最大值或最小值）位置，比较的是d（j）与d（k），交换的是⑨________。

3．选择排序的程序实现

（1）从前向后实现选择排序

从前向后实现选择排序的程序结构（升序排序）：

（2）从后向前实现选择排序

从后向前实现选择排序的程序结构（升序排序）：

【答案】　⑧先比较，再交换　⑨d（k）和d（i）

五．查找算法

⑩________的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置；反之，查找不成功。

⑪________的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，使查找成功，或直到子表不存在，查找不成功。

【答案】　⑩顺序查找　⑪对分查找

六、递归算法

函数或过程调用它本身，称为⑫________。

⑬________的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的解。

即采用“大事化小，小事化了”的基本思想。

递归算法必须具备的条件：

①每一步骤解决问题的方法要一致。

②有边界条件。

【答案】　⑫递归　⑬递归算法

七、VB访问数据库

1．通过ADO连接数据库

ADO是微软公司提供的一种应用程序访问数据库的编程接口。

该接口包含了多个对象，其中Connection对象用于与数据库建立连接，在建立连接后，可通过Recordset对象获取数据表中的数据。

在用Connection建立与数据库的连接时，需要设置ConnectionString属性的值（即连接字符串），以指定连接数据库所用的驱动程序、数据源名称、用户名和密码等。

Connection对象具有Open、Close等方法，其中⑭________方法用于打开到数据源的连接，⑮________方法用于关闭连接。

2．通过Recordset对象获取数据库中的数据，步骤如下：

（右边是对应的代码）：

说明：

①myrecord是定义的Recordset对象的名字。

②mytable是数据库中某张表的名称。

③EOF属性：

若当前记录的位置在最后的记录之后，则返回True，否则返回False。

④MoveNext方法：

指针移到下一条记录。

⑤这段代码应该在连接数据库后，关闭数据库前。

【答案】　⑭Open　⑮Close

1．（2012年6月浙江会考）计算三角形面积的算法如下：

①输入三角形三边长a，b，c　②计算半周长p＝（a＋b＋c）/2　③计算三角形面积s＝Sqr（p*（p－a）*（p－b）*（p－c））　④输出面积s

上述算法属于（　　）

A．排序算法B．解析算法

C．枚举算法D．查找算法

B　[本题主要考查各种算法的基本思想。

本题中算法的基本思想是通过数学表达式的计算来解决问题，符合解析算法的基本思想。

]

2．（2014年3月浙江学考）运行下列VB程序，在文本框Text1中输入28，界面如图所示。

PrivateSubCommand1_Click（）

　DimsAsSingle

　DimvAsSingle

　DimtAsSingle

　s＝0

　v＝l0

　t＝Val（Text1.Text）

　s＝s＋v*t

　Label1.Caption＝Str（s）

　EndSub

单击“计算”按钮Command1后，标签Label1中显示的内容是

（1）________。

该程序采用了

（2）________（填：

解析/排序/查找）算法。

【解析】　本题主要考查各种算法的基本思想特点及程序阅读能力。

s的值通过s＝s＋v*t计算得到，s的初值是0，将v＝10，t＝28（从文本框中输入）代入，得到s＝280，符合解析算法的基本思想。

【答案】　

（1）280　

（2）解析

一、冒泡排序与选择排序对比

冒泡排序与选择排序

冒泡排序

选择排序

思想方法

边比较边交换

先选出最大值或最小值，再交换

核心代码

Fori＝1Ton－1

Fori＝1Ton－1

Forj＝nToi＋1Step－1

Ifa（j）

temp＝a（j－1）

a（j－1）＝a（j）

a（j）＝temp

EndIf

Nextj

Nexti

k＝i

Forj＝i＋1Ton

Ifa（j）

k＝j

Nextj

Ifk<>iThen

temp＝a（i）

a（i）＝a（k）

a（k）＝temp

EndIf

Nexti

相同点

①n个数都需要n－1遍排序，其中变量i控制排序的遍数

②比较的次数一样多，都是（n－1）＋（n－2）＋…＋3＋2＋1次

③最好的情况下，交换的次数一样，都是0次

不同点

边比较边交换，最坏的情况下交换的次数是（n－1）＋（n－2）＋…＋3＋2＋1次

先选择再交换，最坏的情况下交换的次数是n－1次

如何区分

因为是相邻两数比较，因此代码中有类似“a（j）和a（j－1）”比较的条件表达式

因为是先选出最大值或最小值，再交换，因此代码中有寻找最大值或最小值的代码，并且用变量（如k）来记录该值所在的位置。

如果k＜＞i则交换

二、枚举算法与顺序查找

枚举算法

顺序查找

思想方法

一一列举所有可能解并验证

数据源从头到尾逐个比较

核心代码

For（列举所有可能的解）

If可能解是正确解

then输出该解

next

For（从数组的第一个元素到最后一个元素）

If当前元素＝关键词

then输出该位置

next

区分方法

①For语句用于列举所有可能的解，即解的范围

①For语句用于访问整个查找源的数据，一般是从开始位置到结束位置

②If语句是验证当前列举的可能解是否是正确解

②If语句用于判断当前访问的元素是不是等于关键词

③正确解可能有多个，因此找到一个正确解后，循环继续，直到所有可能的解都被检验过

③一旦某个位置的数据等于关键词，则记录该位置，并且查找任务结束，通常用语句exitfor退出循环

不管是枚举算法还是顺序查找，都可以写成For循环语句，区分的方法是要分析问题的本质：

for语句是为了一一列举所有可能的解还是从头到尾逐个访问数据源中的数据；if语句是检验可能解还是比较关键词。

三、对分查找

对分查找的基本思想：

查找的数据源a

（1）到a（n）是有序的（如从小到大排序），查找的关键词是key，则第一次查找的范围是[1，n]，如果中间位置为m，则m＝fix（（1＋n）/2）。

如果key＝a（m），则查找成功；如果key

在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，则查找成功；或直到子表不存在，则查找不成功。

说明：

①对分查找的前提是被查找的数据必须是有序的。

②对分查找每次访问的是当前查找范围里中间位置上的数据，并根据该数据与关键词的大小关系，将下一次的查找范围缩小一半。

③规模为n个数的数据源，使用对分查找时，最多经过Int（log2n）＋1次查找。

1．7位学生的身高（单位：

cm）从高到低依次为：

178,177,175,172,170,165,162。

用对分查找法找到178的过程中，依次被访问到的数据是（　　）

A．178B．172,175,178

C．172,177,178D．172,175,177,178

C　[本题主要考查对对分查找算法基本思想的理解。

将7个数据从1到7进行编号。

第一次访问到的数据是第4个，即172（中间位置m＝Fix（（1＋7）/2）＝4），178＞172，因此下一次查找的范围是前半部分，即第1个到第3个。

因此第二次访问的数据应该是第2个，即177（中间位置m＝Fix（（1＋3）/2）＝2），178＞177，因此下一次查找的范围是前半部分，即第1个，因此第三次访问的数据是第1个，即178。

]

2．某校通过政府招投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为19万、15万、21万、13万、12万元人民币。

若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是（　　）

A．1B．2

C．3D．4

B　[原始数据19、15、21、13、12，第一遍排序19与21互换，得到21,15,19,13,12；第二遍排序15与19互换，得到21,19,15,13,12；第三遍排序与第四遍排序都不需要数据互换。

因此总共是2次数据互换。

]

3．实现某排序算法的部分VB程序如下：

　Fori＝1To6

k＝i

Forj＝i＋1To7

　Ifa（j）

Nextj

Ifi<>kThen

　t＝a（i）：

a（i）＝a（k）∶a（k）＝t

　EndIf

Nexti

在排序过程中，经过某一遍排序“加工”后，数组元素a

（1）到a（7）的数据依次为“10,41,75,12,63,11,85”。

则下一遍排序“加工”后数组元素a

（1）到a（7）的数据依次是（　　）

A．10,11,41,75,12,63,85

B．10,11,75,12,63,41,85

C．10,11,12,75,63,41,85

D．10,11,12,41,63,75,85

B　[本题主要考查选择排序算法的代码特点。

选择排序的基本操作是先找出最小数或最大数所在的位置，记录在一个变量中，再根据需要进行数据交换，因此代码中会出现“k＝j”以及“Ifi＜＞k”的代码，根据代码特点，可确定本题的排序算法是选择排序。

一旦确定是选择排序，接着就可以用选择排序的思想方法来对数据进行排序。

根据第一遍排序结果可得知排序的结果是数据从小到大排，选择排序的基本思想是从所有的记录中选出最小（从小到大排）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小的数据与第二个数据交换。

以此类推，直至所有数据排序完成。

因此“10,41,75,12,63,11,85”的下一遍选择排序的结果应该是：

“10,11,75,12,63,41,85”。

]

4．有如下对a

（1）到a（6）进行升序排序的程序片段：

Fori＝1To5

k＝i

Forj＝i＋1To6

　____①____

Nextj

Ifk<>iThent＝a（i）：

a（i）＝a（k）：

a（k）＝t

　Nexti

划线部分①应填（　　）

A．Ifa（j）

B．Ifa（j）

C．Ifa（j）>a（k）Thenk＝j

D．Ifa（j）>a（k）Thenk＝i

【解析】　本程序段为选择排序（按升序排序），每趟比较找出最小值，存入a（k）中，k记录最小值编号j。

【答案】　A

5．通过编程寻找3位的水仙花数。

什么是水仙花数：

水仙花数是指一个n位数（n≥3），它的每个位上的数字的n次幂之和等于它本身。

例如153是水仙花数，因为13＋53＋33＝153。

解决此问题的VisualBasic程序如下，程序界面如图所示，在列表框List1中输出结果。

在①和②划线处，填入合适的语句或表达式，把程序补充完整。

PrivateSubCommand1_Click（）

DimiAsInteger

Dima，b，cAsInteger

For____①____

　a＝i\100

　b＝i\10Mod10

　c＝iMod10

　If____②____ThenList1.AddItemStr（i）

Next

EndSub

（1）程序中划线处①应填入________。

（2）程序中划线处②应填入________。

【解析】　

（1）枚举算法在列举的过程中，不能遗漏任何一个可能的解，寻找3位的水仙花数，100到999都是可能解。

因此列举所有可能解的语句应该是：

Fori＝100to999。

（2）if语句用于检验当前列举的可能解i是否是正确解。

水仙花数的验证条件是：

它的每个位上的数字的n次幂之和等于它本身，本程序要求找出3位的水仙花数，因此n＝3，变量a、b、c是可能解i的百位、十位和个位上的数字，因此验证条件是a^3＋b^3＋c^3＝i。

【答案】　①i＝100To999　②a^3＋b^3＋c^3＝i