- 二一组卷

题型：综合题题类：常考题难易度：普通

浙江省高中信息技术排序算法及程序实现同步练习

小王在研究n个数的冒泡排序算法，发现可以从两个方面进行优化:

⑴在每遍冒泡过程中，若最后一次交换的是last与last-1位置，则last位置之前的相邻数据均已有序。进行下一遍冒泡时，无序区域设置[last， n]，这样可使无序区域缩小。

⑵若在某一遍排序中没有数据交换，说明待排序数据都已经有序，冒泡排序过程可在此遍排序后结束。因此可以引入一个变量flag，记录在每遍排序过程中是否发生了交换。

小王设计了如下VB程序，功能如下:按Cominandl“生成数据”后，生成一组随机的两位整数存入数组a，并输出在列表框List1中。单击Command2“排序”后，a中的数据进行降序排序，排序后的数据显示在列表框List2中，排序过程中实际的冒泡遍数显示在Label2上。程序运行界面如下所示。

实现上述功能的VB程序如下，回答下列问题:

（1）、若按小王优化后的冒泡排序算法，数据28，15，10，8，12进行降序排序，冒泡的遍数(填数字)。

（2）、在画线处填入合适的代码。

Dim a(1 To 20) As Integer

Private Sub Commandl_Click()

Dim i As Integer, j As Integer

List1. Clear: List2. Clear

Randomize

For i=1 To 20

For j=1 To i-1

If a(i)=a(j) Then i=i-1: Exit For

Next j

Next i

For i=1 To 20

Listl. Addltem Str(a(i))

Next i

End Sub

Private Sub Commandl2_Click()

Dim flag As Boolean, i As Integer, j As Integer

Dim temp As Integer, nuui As Integer, last As Integer

nuin=0: last=1

flag=True

Do While flag=True

For j=20 To last+1 Step-1

If a(j) > a(j-1) Then

temp=a(j): a(j)=a(j-1): a(j-1)=temp

flag=True ‘有交换发生

End If

Next j

num=num+1

Loop

For i=1 To 20

List2. Addltem Str(a(i))

Next i

Label3. Caption=“本次排序的冒泡遍数为:” & Str (num)

End Sub

举一反三

下列VB程序的功能是：程序运行时，单击命令按钮Commandl后，产生10个[1，999]范围内互不相同的随机整数，依次显示在列表框List1中，然后将它们按从小到大的顺序排序，排序结果显示在列表框List2中。

数组a用于存储产生的10个随机整数，函数f(x)用于判断随机整数x与已生成的整数是否有重复，若有重复则返回True，否则返回False。

【加试题】有如下VB程序段：

s = "adobe": ans = ""

For i = 1 To Len(s)

A(i) = Mid(s, i, 1)

Next i

For i = 1 To Len(s)

k = i

For j = i To Len(s) Step 2

If a(j) < a(k) Then k = j

Next j

If k <> i Then t = a(k): a(k) = a(i): a(i) = t

Ans = ans + a(i)

Next i

label1.Caption = ans

该程序段运行后，标签Label1中显示的内容是（）

【加试题】某排序算法思想如下：若有11个桶，编号从0～10，随机产生多个整数，每产生一个整数时，就在以该整数位编号的桶中放一面小旗子，最后只要按顺序数每个桶中有几面小旗子，就能得到这几个整数的有序排列。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次，按桶的编号顺序读出旗子数量，没有旗子的桶略过,得到有序整数为“2,3,5,5,8”。

为此，小李编写了一个VB程序，功能如下：运行程序，窗体加载时随机产生6个[0,9]的随机整数，并在列表框List1中依次显示排序前数据，单击“排序”按钮Command1，在列表框List2 中显示经过上述排序算法后的数据。运行结果如图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。

Dim a(10) As Integer '数组a表示桶的编号，如a(0)表示第0号桶

Private Sub Command1_Click()

Dim i As Integer, j As Integer

For i = 0 To 10

For j = 1 To ①{#blank#}1{#/blank#}

List2.AddItem CStr(i)

Next j

Next i

End Sub

Private Sub Form_Load()

Dim i As Integer

Randomize

For i = 0 To 10 '将数组初始化为0

a(i) = 0

Next i

For i = 1 To 6 '产生6个[0,9]的随机数

t = Int(Rnd * 10)

a(t) = '第t桶中小旗子数量加1 ② {#blank#}2{#/blank#}

List1.AddItem CStr(t)

Next i

End Sub

【加试题】有如下VB程序段，当n为8时，上述程序段的运行结果a(1)至a(8)的值分别为1,8,3,6,5,4,7,2，则划线出应填入的代码分别为（）

n = Val(Text1.Text)

For i = 1 to n

a(i) = i

Next i

For i = 1 to n/2-1

For j = n to 2*(i+1) step -2

If ① Then t = a(j):a(j)=a(j-2):a(j-2)=t

Next j

For j = 1 to n- i*2 step 2

If ② Then t = a(j):a(j)=a(j+2):a(j+2)=t

Next j

Next i

给定一个数组(有n个元素)，小李通过边分段、边合并的方式将n个数据处理成一个非降序数据段(a(1)≤a(2)≤a(3)≤……≤a(n))，每一轮数据处理方法如下：

⑴查找相邻两个非降序数据段在未处理的数据区域中，从前往后找出第一个最长非降序数据段。若该数据段后而没有元素，则本轮处理完毕；否则在第1个数据段的后面，从前往后找出数组中第二个最长非降序数据段。

⑵合并两个数据段

借助数组tmp，将查找到的两个相邻数据段合并成一个非降序数据段，然后将合并后的数据依次存回到原数组中。

⑶若数组中还有未处理的数据，则重复⑴⑵步骤。

每一轮数据处理完毕后，重新从数组第1个数据开始进行下一轮处理。若检测到某一轮没有合并处理，则说明n个数据己构成非降序数据段，数据处理结束。

有如下程序段：

For i=1 To 3

For j=i+1 To 7

If a(j)< a(i) Then

k= a(j): a(j)= a(i): a(i)=k

c=c+1

End If

Next j

s= Str(a(i))+s

Next i

Text1.Text=Str(c) & ":" & s

数组元素a(1)至a(7)中值分别为3，9，1，5，8，6，2，该程序段运行后，文本框Text1中显示的内容是（）

相关试卷

公司介绍

服务介绍

帮助中心