- 二一组卷

题型：综合题题类：常考题难易度：困难

浙江省杭州市2017-2018学年高三上学期信息技术教学质量检测

【加试题】某数据存储算法如下：使用长度为n的一维数组h来存储m个不同整数型数据(m<n)，数据的存储位置t根据存储数据的值除n取余计算得到。例如使用长度为11的数组来存储67，45，1 275，119，145，269，64共7个数据，先存储第1个数据67，67 Mod 11=1，在第1位置上没有数据，则存放在第1位置。第2个数据45，45 Mod 11=1，而在第1位置上已存有数据，那么查找下一位置有没有数据，现第2位置上没有数据，则存放在第2位置。在查找空位时如果到了数组最后一个位置还没有空位，则从头继续查找，以此类推……，举例数据存储结果如表所示。

位置	0	1	2	3	4	5	6	7	8	9	10
数据	64	67	45	145		269				119	1275

（1）、若按上述规则，再存储一个数据79，则存储在第位置。

（2）、当n=97时，实现上述数据存储及相应数据查找的VB程序如下，运行结果如图所示，请在画线处填入合适的代码。

Const n=97

Dim d(0 To 96)As Integer，h(0 To 96)As Integer

Dim m As Integer ‘变量m为数据个数

Private Sub Command1_Click() ‘数据存储

Dim i As Integer，t As Integer

‘从数据库读取数据先存储在数组d中，代码略

List1.Clear

For i=0 To n-1

h(i)=-1 ‘数组元素初始化

Next i

For i=0 To m

①

Do While h(t)<>-1

t=(t+1)Mod l2

Loop

h(t)=d(i)

Next i

For i=0 To n-1

List1．AddItem Str(i)＆“：”&Str(h(i))

Next i

End Sub

Private Sub Command2_Click() ‘数据查找

Dim x As Integer，Y As Integer，z As Integer

x=Val(Text1．Text)

y=x Mod n

z=1

Do While ②

z=z+1

y=(y+1)Mod n

Loop

If h(y)=x Then

Label2．Caption=“共查找了”&Str(z)&“次，在第”&，Str(y)&“位置找到”

Else

Label2．Caption=“共查找了”&Str(z)＆“次，没有找到”

End If

End Sub

① ②

（3）、数组h中的元素值初始化为-1表示含义是。

举一反三

日期判断:从文本框Text1输入一个8位数字表示的日期，其中第1到4位表示年（第1位确定不为零），第5到6位表示月，第7到8位表示日。单击“判断”按钮，判断该日期是否合法，将结果依次输出到列表框List1。程序界面如下图所示：

提示：年份值符合下列两种情况之一的是闰年。

⒈年份是4的倍数，但不是100的倍数；

⒉年份是400的倍数。

【加试题】数组元素a(0)到a(9)的值依次为“13,20,22,25,30,33,40,52,65,100”，文本框Text1中输入的值是33，执行该程序段，下列描述正确的是（）

key = Val(Text1.Text)

i = 0: j = 9: s = 0

Do While i <= j

m = Fix((i + j) \ 2 + 0.5)

s = s + 1

If key = a(m) Then

Label1.Caption = Label1.Caption + "→" + Str(m)

Exit Do 'Exit Do表示退出循环

End If

If key <a(m) Then j = m - 1 Else i = m + 1

Label1.Caption = Label1.Caption + "→" + Str(m)

Loop

Label2.Caption = "历经" + CStr(s) + "步"

【加试题】对于数组（形如a数组：4、5、6、1、2、3或b数组：1、2、3、4、5、6），我们称元素1为此二数组的拐点。为寻找此类递增或循环递增数组的拐点，可以用顺序查找和对分查找的方法，通常相比之下对分查找算法较优，以下为使用对分法查找拐点的算法。

做法是比较中点与当前查找范围第1个数大小关系，用对分法使查找范围逼近拐点；当余下数组只有二个元素时，可根据此二元素大小关系得到拐点的位置。

依据上述描述设计了VB程序，界面如图所示。请回答下列问题：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

数组元素a(1)至a(5)依次为5，22，28，42，55，在a(3)处分成两段，交换位置后为：

a(1)	a(2)	a(3)	a(4)	a(5)
28	42	55	5	22

旋转数组a的最小元素是5。

数组d(1)至d(5)依次为0，1，1，1，1，在d(5)处分成两段，交换位置后为：

d(1)	d(2)	d(3)	d(4)	d(5)
1	0	1	1	1

旋转数组d的最小元素是0。

小明依据查找算法思想，设计一个查找旋转数组d最小元素的程序，功能如下：运行程序时，利用“添加”按钮Command1和文本框Text1依次输入旋转数组d的值，在列表List1中显示旋转数组，单击“求解”按钮Command2，在标签Label2中显示旋转数组d最小元素值。运行效果如图1所示，实现该功能的VB程序如下：

图1

Dim n As Integer

Dim d(1 To 100) As Integer '数组 d 存储待排序数据

Private Sub Command1_Click()

'按旋转数组规则将数据存入数组d中，代码略

End Sub

Private Sub Command2_Click()

Dim mid As Integer, L As Integer, R As Integer

L = 1: R = n

mid = L

Do While d(L) >= d(R)

If Then '改错

mid = R

Exit Do

End If

mid = (L + R) \ 2

If d(L)=d(R) And d(mid)=d(R) Then

mid =______________ '填空

Exit Do

End If

If d(L) < d(mid) Then

L = mid

ElseIf d(mid) < d(R) Then

R = mid

End If

Loop

Label2.Caption = "最小值为" + Str(d(mid))

End Sub

End If

Next i

End Function

用对分查找从数列“1,5,9,13,16,20,33,40,61,77,89”中查找“5”,一共需要比较的次数为（）

用对分查找的方法求不等式2x+3x-5≤n(n≥0)的最大正整数解，编写的VB程序段如下：

Private Sub Command1_Click( )

Dim L As Integer, R As Integer,n As Integer

x As Integer

n=Val(Text1.Text)

L=1

R=n+1

Do While

x=(L+R)\2

if 2^X+3*x-5<=n Then L=x+1

Else R=x-1

Loop

Label1.Cption=“方程2^X+3*x-5<=n的最大正整数解为：”+

End Sub

要使程序实现上述算法思想，则方框上的语句是（）

相关试卷

公司介绍

服务介绍

帮助中心