浙江省高中信息技术选考排序和查找算法复习资料.docx

1、浙江省高中信息技术选考排序和查找算法复习资料浙江省高中信息技术选考排序和查找算法复习资料2019 年浙江省高中信息技术选考排序和查找算法复习资料一、排序算法（1）概念：找出数组元素中最小（大）的数据，使它与第一个元素中的数据交换位置 ;在余下的元素中继续找最小（大）的元素，与第二个元素中的数据交换位置 ;（2）比较的次数： n*(n-1)/2 交换的次数：小于 n-1 趟数： n-1（3）算法：将数组内的数据从小到大排序（4）例题：例题 1：使用选择排序的方法对数据8、6、1、9、4 从大到小排序，需要进行数据比较、数据互换的次数分别是（ D ）A、4,5 B、10,2 C、3,3 D、10,

2、4例题2 ：小陈设计了一个带密码的趣味“4+1”小游戏，小陈告诉大家，该密 码可以通过以下方法破解：将一组顺序是“3、2、8、5、 9”的数码，在用选择排序法将这组数码从大到小的排序过程中，进行两次数据交换，即得。则该密码可能是（ D ）A、98523 B、 92853 C、98523 D、 98253例题 3：以下表格中的数据为 2009 年快乐女生十进七淘汰赛的选手信息。某同学设计了一个Visual Basic 程序用于选出晋及前七名的选手信息。程序界面如下图所示，单击“十进七晋级名单”，在list2 里显示晋及前七名的选手信息。阅读、完善以下程序，并上机验证。完成下面问题：Dim xs(

3、1 To 10) As String Dim df(1 To 10) As Intege Private 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) = 潘虹越“ : df(7) = 48xs(8) = 潘 辰“ : df(8) = 38xs(9) = 李媛希“ : df

4、(9) = 36xs(10) = 曾轶可“ : df(10) = 51 For i = 1 To 10List1.AddItem xs(i) + + Str(df(i) List1.AddItem Next i End SubPrivate Sub Command1_Click()Dim j As Integer, k As IntegerDim m As Integer Dim temp1 As StringDim temp2 As IntegerFor j = 1 To 9 m = jFor k = j + 1 To 10If Then m= k Next kIf j m Thentemp

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

6、 7(1) 概念：把待排序的 n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数据换到上面的一个元素中，重复这一过程，直到处理完最后两个元素中的数据，称为第一遍加工。然后对余下的 n-1个元素重复上述处理过程，直至最后进行余下的两个数据的比较和交换。（2）算法：将数组内的数据从小到大排序（3）例题：例题 1：5 位学生 100 米短跑的成绩（单位：秒）如下表。若采用冒泡排序算法对其进行排序，则第3 趟的排序结果是（ A ） B D 例题 2：下表记录了 6 个数据排序的过程。分析表中数据可知，该排序采用的算法与排序方式分别为（ C ）

7、A、冒泡排序、降序 B、选择排序、降序C、冒泡排序、升序 D、选择排序、升序例题 3：随机产生10 个两位正整数， 并对它们进行排序。用 VB 编写的程序运行界面如下图所示，请阅读并完善程序段，并上机验证。Dim d(1 to 10) as integer 定义一个一维数组 d，用于存放 10 个正整数Dim i As Integer As IntegerDim j As Integer, temp As IntegerPrivate Sub Command1_Click() 随机产生 10 个两位正整数Randomize 随机数初始化List1.Clear 原始数据清空For i = 1 T

8、o 10d(i) = int(Rnd*90)+10List1.AddItem Str(d(i) 将数据显示到原始数据列表中Next End SubPrivate Sub Command2_Click() 对 10 个两位正整数进行排序 将排序后的列表数据清空For i = 1 To 9For j = 10 to i+1 step -1If d(j)d(j-1) Then temp=d(j):d(j)=d(j-1):d(j-1)=tempEnd IfNext jNext iFor i = 1 To 10List2.AddItem Str(d(i) 在列表 2 中显示排序后的数据Next i En

9、d Sub ：若数组 d 里有 n 个待排序的数据， 分别用冒泡法和选择法对此进行排序， 试填充下表中的数据。二、查找算法1. 顺序查找（1）概念：从数组的第一个数据开始，逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，输出所查数据的位置；反之，查找不成功，输出“数据不存在于此数组中”（2）算法：2.对分查找（1）概念：前提：数组中被查找的数据必须是有序的基本思想：首先将查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找。在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。对分查找程序的实现