浙江省高中信息技术选考排序和查找算法复习资料.docx
《浙江省高中信息技术选考排序和查找算法复习资料.docx》由会员分享,可在线阅读,更多相关《浙江省高中信息技术选考排序和查找算法复习资料.docx(8页珍藏版)》请在冰点文库上搜索。
浙江省高中信息技术选考排序和查找算法复习资料
浙江省高中信息技术选考排序和查找算法复习资料
2019年浙江省高中信息技术选考排序和查找算法复习资料
一、排序算法
(1)概念:
找出数组元素中最小(大)的数据,使它与第一个元素中的数据交换位置;在余下的元素中继续找最小(大)的元素,与第二个元素中的数据交换位置;
(2)比较的次数:
n*(n-1)/2交换的次数:
小于n-1趟数:
n-1
(3)算法:
将数组内的数据从小到大排序
(4)例题:
例题1:
使用选择排序的方法对数据8、6、1、9、4从大到小排序,需要进行数据比较、数据互换的次数分别是(D)
A、4,5B、10,2C、3,3D、10,4
例题2:
小陈设计了一个带密码的趣味“4+1”小游戏,小陈告诉大家,该密码可以通过以下方法破解:
将一组顺序是“3、2、8、5、9”的数码,在用选择排序法将这组数码从大到小的排序过程中,进行两次数据交换,即得。
则该密码可能是(D)
A、98523B、92853C、98523D、98253
例题3:
以下表格中的数据为2009年快乐女生十进七淘汰赛的选手信息。
某同学设计了一个VisualBasic程序用于选出晋及前七名的选手信息。
程序界面如下图所示,单击“十进七晋级名单”,在list2里显示晋及前七名的选手信息。
阅读、完善以下程序,并上机验证。
完成下面问题:
Dimxs(1To10)AsString
Dimdf(1To10)AsIntege
PrivateSubForm_Load()
DimiAsInteger
xs
(1)="黄英“:
df
(1)=88
xs
(2)="江映蓉“:
df
(2)=87
xs(3)="李霄云“:
df(3)=72
xs(4)="刘惜君“:
df(4)=77
xs(5)="谈莉娜“:
d(5)=61
xs(6)="郁可唯“:
df(6)=81
xs(7)="潘虹越“:
df(7)=48
xs(8)="潘辰“:
df(8)=38
xs(9)="李媛希“:
df(9)=36
xs(10)="曾轶可“:
df(10)=51
Fori=1To10
List1.AddItemxs(i)+""+Str(df(i))List1.AddItem""
Nexti
EndSub
PrivateSubCommand1_Click()
DimjAsInteger,kAsInteger
DimmAsInteger
Dimtemp1AsString
Dimtemp2AsInteger
Forj=1To9m=j
Fork=j+1To10
If①Thenm=k
Nextk
Ifj<>mThen
temp1=xs(j):
②
xs(m)=temp1
temp2=df(j)
df(j)=df(m):
df(m)=temp2
EndIf
Nextj
Forj=③
List2.AddItemxs(j)+""+Str(df(j))List2.AddItem""
Nextj
EndSub
1)command1上单击事件处理过程中采用的算法是:
选择排序(填:
冒泡排序或选择排)
2)command1上单击事件处理过程中采用的排序方式是:
升序(填升序或降序)
3)程序中划线①处应填入df(k)>df(m)
4)程序中划线②处应填入xs(j)=xs(m)
5)程序中划线③处应填入1to7
(1)概念:
把待排序的n个元素的数组看成是垂直堆放的一列数据,从最下面的一个元素起,自下而上地比较相邻两个元素中的数据,将较小的数据换到上面的一个元素中,重复这一过程,直到处理完最后两个元素中的数据,称为第一遍加工。
然后对余下的n-1个元素重复上述处理过程,直至最后进行余下的两个数据的比较和交换。
(2)算法:
将数组内的数据从小到大排序
(3)例题:
例题1:
5位学生100米短跑的成绩(单位:
秒)如下表。
若采用冒泡排序算法对其进行排序,则第3趟的排序结果是(A)
B
D
例题2:
下表记录了6个数据排序的过程。
分析表中数据可知,该排序采用的算法与排序方式分别为(C)
A、冒泡排序、降序B、选择排序、降序
C、冒泡排序、升序D、选择排序、升序
例题3:
随机产生10个两位正整数,并对它们进行排序。
用VB编写的程序运行界面如下图所示,请阅读并完善程序段,并上机验证。
Dimd(1to10)asinteger'定义一个一维数组d,用于存放10个正整数
DimiAsIntegerAsInteger
DimjAsInteger,tempAsInteger
PrivateSubCommand1_Click()
'随机产生10个两位正整数
Randomize'随机数初始化
List1.Clear'原始数据清空
Fori=1To10
d(i)=int(Rnd*90)+10
List1.AddItemStr(d(i))
'将数据显示到原始数据列表中
Next
EndSub
PrivateSubCommand2_Click()‘对10个两位正整数进行排序
'将排序后的列表数据清空
Fori=1To9
Forj=10toi+1step-1
Ifd(j)>d(j-1)Then
temp=d(j):
d(j)=d(j-1):
d(j-1)=temp
EndIf
Nextj
Nexti
Fori=1To10
List2.AddItemStr(d(i))'在列表2中显示排序后的数据
Nexti
EndSub
:
若数组d里有n个待排序的数据,分别用冒泡法和选择法对此进行排序,试填充下表中的数据。
二、查找算法
1.顺序查找
(1)概念:
从数组的第一个数据开始,逐个将数据与给定的值进行比较。
若某个数据和给定的值相等,则查找成功,输出所查数据的位置;反之,查找不成功,输出“数据不存在于此数组中”
(2)算法:
2.对分查找
(1)概念:
前提:
数组中被查找的数据必须是有序的
基本思想:
首先将查找的数据与有序数组内处于中间位置的数据进行比较,如果两者相等则查找成功;否则根据数组元素的有序性,就可确定该数据应该在数组的前半部分还是后半部分继续进行查找。
在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。
对分查找程序的实现