《排序算法的程序实现(教师版）.docx》由会员分享，可在线阅读，更多相关《排序算法的程序实现(教师版）.docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、排序算法的程序实现（教师版）1.有如下程序段:For i = 1 To 2For j = 5 To i + 1 Step -1If a(j) a(i) Thent = a(j): a(j) = a(i): a(i) = tEnd IfNext jNext i数组元素a(1)到a(5)的值依次为“33,24,45,16,77”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为()A.77,45,33,16,24B.77,33,45,16,24C.77,24,45,16,33D.77,45,33,24,16答案 A解析 这是一个选择排序,其排序思想是:在i遍排序中,从最后一个元素开始到
2、第i+1个元素依次和第i号元素比较,如果有比i号元素大的立刻交换,并且记录元素下标,一遍全部比较结束后再交换进行下一轮。2.小赵对选择排序算法进行了如下改进:在数组的所有元素中找出最小和最大数据的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。小赵编写的VB程序段如下:p = 1: q = 10Do While p qiMin = p: iMax = pFor i = p + 1 To qIf a(i) a(iMax) Then iMax = iNext it = a
3、(iMin): a(iMin) = a(p): a(p) = tt = a(iMax): a(iMax) = a(q): a(q) = tp = p + 1q = q - 1Loop要使程序实现上述算法思想,则方框中的语句是()A.If iMax = p Then iMax = iMinB.If iMin = p Then iMin = iMaxC.If iMax = p Then iMin = iMaxD.If iMin = p Then iMax = iMin答案 A解析 如果找到的最小值的元素序号iMin=q,最大值的元素序号iMax=p,那么在执行完语句t = a(iMin): a(i
4、Min) = a(p): a(p) = t后,实际上最大值同时也被交换到了a(q)中。这种情况下,如果直接执行后续的语句t = a(iMax): a(iMax) = a(q): a(q) = t,则又将最大值交换到a(p)中,并把最小值也换回到原来的a(q)中。为避免交换好的数据换回来,可以把iMax的值赋为q或iMin,如此t = a(iMax): a(iMax) = a(q): a(q) = t语句就变成了自己和自己交换,不会把交换好的数据换回来。3.有如下VB程序段:Dim s(1 To 6) As Strings(1)=4:s(2)=343:s(3)=312:s(4)=12:s(5)=
5、246:s(6)=121c= For i=1 To 5For j=i+1 To 6If s(i)+s(j)345,4366451。根据代码s(i)+s(j)s(j)+s(i)可知排序方式是降序,排序后的数组元素依次为4、343、312、246、12、4.有如下VB程序段:For i = 5 To 4 Step -1k = iFor j = 6 - i To 1 Step-1 If a(j) a(k) Then k = jNext jIf i k Thent = a(i): a(i) = a(k): a(k) = tEnd IfNext i数组元素a(1)到a(5)的值依次为“41,66,70,
6、83,31”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为 ()A.31,41,66,83,70B.83,70,66,41,31C.83,66,70,41,31D.31,41,66,70,83答案C第一遍循环,i=5,k=5,内循环为j=1 to 1只执行1次,比较a(1)a(5)不成立,不交换。第2遍循环,i=4,k=4, 内循环为j=2 to 1执行2次,从1号与4号元素中对比找出1号元素最小,将之与4号元素交换。5.有如下程序段:bottom=6:i=1:r=Val(Text1.Text)Do While ia(j-1) Thent=a(j):a(j)=a(j-1):a(
7、j-1)=tEnd IfNext ji=i+1For j=i To bottom -1If a(j)a(j+1) Thent=a(j):a(j)=a(j+1):a(j+1)=tEnd IfNext jbottom=bottom-1Loop数组元素a(1)到a(6)的值依次为“73、56、28、61、44、92”,若在文本框Text1中输入“2”,则经过该程序段“加工”后,数组元素a(1)到a(6)的值依次为()A.73,61,56,92,44,28B.92,73,56,61,44,28C.92,73,61,56,28,44D.92,73,61,56,44,28答案B本题是双向冒泡排序算法,内循
8、环前半部分从后往前,将大的元素往上冒;后半部分从前往后,将小的元素往下沉。因为r值为2,所以仅排序一次,排序后数组a各元素值为92、73、56、61、44、28。6.n个数据的冒泡升序排序需要经过n-1遍的加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面,在第i遍加工过程中需要进行n-i对数据的比较。在某些情况下,第i遍加工过程中,在上面部分较小数据已经有序情况下,不需要再进行n-i对数据的比较。如对“17,18,19,24,23,20”这6个数据排序中,第1遍排序结束后数据为“17,18,19,20,24,23”,第2遍排序时不再需要对20及其前面共4个数据进行比较。以下程序实现
9、了冒泡升序排序的优化,在划线处填入合适的代码。Dim n As IntegerDim a(1 To 100) As Integern=10,排序前生成的数据存储在数组a中,并在列表框List1中显示,代码略Private Sub Command1_Click()Dim i As Integer,j As Integer,start As Integer,t As Integeri=2Do While i=nstart=nFor j=n To i Step-1If Thent=a(j):a(j)=a(j-1):a(j-1)=tEnd IfNext ji=start+1LoopFor i=1 To
10、 nList2.AddItem=Next iEnd Sub答案 a(j)a(j-1)start=jStr(a(i)解析 程序要实现升序排序,所以只有当后面的数据小于前面的数据时才需要数据交换,而从后面交换的语句中可以看出是a(j)与a(j-1)交换,所以第空填a(j)=A And c=a And c=z Thena(j)=a(j)+1End IfNext iFor i=1 To 25For j=1 To If a(j)a(j+1) Thent1=a(j):a(j)=a(j+1):a(j+1)=t1t2=b(j):b(j)=b(j+1):b(j+1)=t2End IfNext jNext iFo
11、r i=1 To 26List1.AddItem b(i) &: & a(i)Next iEnd Sub答案 Chr(Asc(a)+i-1)j=Asc(c)-Asc(a)+126-i解析 该语句所在循环功能对数组a、b进行初始化,把数组a中的每个元素赋值为0,把数组b中的每个元素依次赋值为“a”、“b”、“c”、“z”,所以处填Chr(Asc(a)+i-1)。该处的功能是:如果取出字符c为字母,则该字母个数加1,字母个数存入数组a对应的元素中,即a(1)存放字母“a”的个数,a(2)存放字母“b”的个数,处要找出字母对应的元素下标j,所以j=Asc(c)-Asc(a)+1。该处二重循环的功能是对保存在数组a中各字母出现的次数进行降序排列,数组b也作相应调整,排列使用冒泡法,每次是从数组第1个元素开始进行两两比较,通过一轮循环把最小值移到最后(移到第27-i号元素中),所以处语句为26-i。