2018年浙江高中信息技术排序和查找算法复习资料总结

1、2018年浙江省高中信息技术选考排序和查找算法复习资料1、 排序算法1. 选择排序（1） 概念：找出数组元素中最小（大）的数据，使它与第一个元素中的数据交换位置;在余下的元素中继续找最小（大）的元素，与第二个元素中的数据交换位置;（2） 比较的次数：n*(n-1)/2 交换的次数：小于n-1 趟数：n-1 （3）算法：将数组内的数据从小到大排序for i=1 to n-1min=ifor j=i+1 to nif d(j)d(min) then min=jnext jif mini then k=d(min)d(min)=d(i)d(i)=kend ifnext i（4）例题：例题1：使用选择

2、排序的方法对数据8、6、1、9、4从大到小排序，需要进行数据比较、数据互换的次数分别是（ D ）A、4,5 B、10,2 C、3,3 D、10,4例题2：小陈设计了一个带密码的趣味“4+1”小游戏，小陈告诉大家，该密码可以通过以下方法破解：将一组顺序是“3、2、8、5、9”的数码，在用选择排序法将这组数码从大到小的排序过程中，进行两次数据交换，即得。则该密码可能是（ D ）A、98523 B、92853 C、98523 D、98253例题3：以下表格中的数据为2009年快乐女生十进七淘汰赛的选手信息。某同学设计了一个Visual Basic程序用于选出晋及前七名的选手信息。程序界面如下图所示，

3、单击“十进七晋级名单”，在list2里显示晋及前七名的选手信息。阅读、完善以下程序，并上机验证。完成下面问题： Dim xs(1 To 10) As StringDim df(1 To 10) As IntegePrivate Sub Form_Load()Dim i As Integerxs(1) = 黄 英“ : df(1) = 88xs(2) = 江映蓉“ : df(2) = 87xs(3) = 李霄云“ : df(3) = 72xs(4) = 刘惜君“ : df(4) = 77xs(5) = 谈莉娜“ : d(5) = 61xs(6) = 郁可唯“ : df(6) = 81xs(7)

4、= 潘虹越“ : df(7) = 48xs(8) = 潘 辰“ : df(8) = 38xs(9) = 李媛希“ : df(9) = 36xs(10) = 曾轶可“: df(10) = 51For i = 1 To 10List1.AddItem xs(i) + + Str(df(i)List1.AddItem Next iEnd SubPrivate Sub Command1_Click()Dim j As Integer, k As Integer, m As IntegerDim temp1 As StringDim temp2 As IntegerFor j = 1 To 9 m =

5、j For k = j + 1 To 10 If Then m= k Next k If j m Then temp1 = xs(j): : xs(m) = temp1 temp2 = df(j): df(j) = df(m): df(m) = temp2 End IfNext jFor j = List2.AddItem xs(j) + + Str(df(j)List2.AddItem Next jEnd Sub1）command1上单击事件处理过程中采用的算法是： 选择排序 （填：冒泡排序或选择排）2）command1上单击事件处理过程中采用的排序方式是： 升序 （填升序或降序）3）程序中

6、划线处应填入 df(k) df(m) 4）程序中划线处应填入 xs(j) = xs(m) 5）程序中划线处应填入 1 to 7 2. 冒泡排序(1) 概念：把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数据换到上面的一个元素中，重复这一过程，直到处理完最后两个元素中的数据，称为第一遍加工。然后对余下的n-1个元素重复上述处理过程，直至最后进行余下的两个数据的比较和交换。（2）算法：将数组内的数据从小到大排序for i=1 to n-1for j=n to i+1 step -1if d(j)d(j-1) Then temp=

7、d(j):d(j)=d(j-1):d(j-1)=tempEnd If Next jNext i For i = 1 To 10List2.AddItem Str(d(i) 在列表2中显示排序后的数据Next iEnd Sub3. 选择排序和冒泡排序对比：若数组d里有n个待排序的数据，分别用冒泡法和选择法对此进行排序，试填充下表中的数据。2、 查找算法1. 顺序查找（1）概念：从数组的第一个数据开始，逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，输出所查数据的位置；反之，查找不成功，输出“数据不存在于此数组中”（2）算法：2. 对分查找（1） 概念：前提：数组中被查找的数据必须是有序的基本思想： 首先将查找的数据与有