试题

试题 试卷

logo

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

浙江省高中信息技术 其他排序算法练习

某公司面试程序题如下:公司有10000名员工,请设计一个算法对该公司员工的年龄做递增排序输出。小刘设计了一个算法:利用数组b记录每个数据出现的次数,数组b下标范围为年龄范围,然后根据每个年龄值的个数进行排序。

例如,有如下年龄存在数组a中:

a(1)

a(2)

a(3)

a(4)

a(5)

a(6)

a(7)

a(8)

a(9)

a(10)

20

19

18

19

15

12

15

20

17

19

利用一个数组b(b(10 To 20))记录每个数出现的次数:

b(10)

b(11)

b(12)

b(13)

b(14)

b(15)

b(16)

b(17)

b(18)

b(19)

b(20)

0

0

1

0

0

2

0

1

1

3

2

根据数组b对数组a进行排序:

a(1)

a(2)

a(3)

a(4)

a(5)

a(6)

a(7)

a(8)

a(9)

a(10)

12

15

15

17

18

19

19

19

20

20

Dim a(10000) As Integer      ‘存放读入的年龄数据

Dim b(100) As Integer      ‘存放各个年龄出现的个数

Private Sub Command1_Click()

‘从数据库读入年龄数据放入数组a中

End Sub

Private Sub Command2_Click()

 For i = 1 To 100

 b(i) = 0

 Next i

 For i = 1 To 10000      ‘统计每个年龄数据的个数

    ①    

 Next i

 End Sub

Private Sub Command3_Click()

 j = 0

 For i = 1 To 100

  If b(i) <> 0 Then

   Do While b(i) <> 0

      ②       

    a(j) = i

     ‘③

  Loop

 End If

Next i

 For i = 1 To 10000

 List2.AddItem Str(a(i))

Next i

End Sub

(1)、为实现程序功能,请在划线①②处填入合适的代码。

①处填入的代码为

②处填入的代码为

(2)、加框处③代码有错,请修正。

③处的代码修改为

举一反三
【加试题】某公司需要设计一个生日查询系统:输入某个日期,就能查出在这天生日的所有员工姓名,并统计出生人人数,以便于公司提前为员工准备生日礼物。员工信息存储在数据库文件“员工信息.mdb”的数据表“members”中,数据表“members”的结构如下:

VB应用程序界面如上图所示,在文本框text1中输入查询的日期(以月日形式,如0623),单击“查询”按钮,在列表框中显示所有这个日子出生的员工姓名(按姓名排序),并在Label3处显示员工数量,如果人数为0,则在列表框中显示“本天没有员工生日”。

解决此问题的VB程序如下,阅读程序并完成后面的问题。

‘定义存放员工姓名的数组na

Private Sub CmsqClick()

  Dim n As Integer , i As Integer , j As Integer

  Dim t1 As String

  ‘连接数据库获取数据

  Dim cn As new connection

  Dim rs As new recordest

  Dim str1 As String , str2 As String

     str1 =”driver=Microsoft access driver(*.mdb)”;dbq=”&app.path”&”员工信息.mdb”

     cn.open str1

     str2 = “select * form members where 生日 =’“ + text1.text + ”’”

     rs.open str2 , cn.adOpenDynamic ,adLockOptimistic

     n = 0

     Do While Not Rs.EOF

       n = n + 1

       na(i) = rs.Fields(“姓名”).value

       rs.MoveNext

     Loop 

     rs.close

     cn.close

‘按姓名排序

If n = 0 Then

  List1.AddItem “本天没有员工生日”

Else

  For i = 1 to n-1

    For j = 1 to n+1 Step -1

      If na(j) < na(j-1) Then

        t1 = na(j) :     ①      : na(j-1) = t1

      End If

    Next j

   Next i

   For i = 1 to n

     List1.AddItem     ②   

   Next i

   Label3.Caption = “这天共” + Str(n) + “位员工生日”

  End If

End Sub

“中国好声音”节目组要小杰用VB编写一个程序:现场将有900个观众,要在900个观众中产生10个中奖号码的程序,每位观众用三位数字进行编号,要求产生的10个号码不能重复,并且升序排列输出。

①检查产生号码是否重复:把产生的中奖号码放在数组a中,新产生的号码与已经产生的号码进行一一对比,如果找到相等的数,则重新产生新号码。

②找到新产生号码存放的数组下标:从下标为1的数组元素开始,新号码(第i个号码)分别与他们进行一一比较,找到第一个比新号码大的数,该数所在的下标就是新号码应存放的下标。如果在已经产生的数中没有找到比新号码大的数,则新号码应存放在下标为i的数组元素中。下表以产生第5个号码为例,如果产生的号码是130,第一个比他大的数是a(2),下标为2的数组元素应存放新号码;如果产生的号码是300,则新号码应存放在下标为5的数组元素中。

数组元素

a(1)

a(2)

a(3)

a(4)

数组元素的值

110

168

215

267

③移动数组元素到新的位置:如果在已经产生的号码中找到比新号码大的数,从上一个产生的号码开始,到新号码应存放的数组元素,依次把他们向后面移动。以②中产生130为例,从a(4)开始,让a(5)的值等于a(4),a(4)的值等于a(3),依次类推,直到新号码应存放的数组元素a(2)为止。

④将新产生的号码放在相应的数组元素中。

程序运行的界面如下图所示,实现上述功能的VB程序代码如下:

Dim a(10) As Single

Private Sub Command1_Click()

Dim i As Integer, j As Integer

Dim temp As Single, k As Integer   'temp产生随机数,k随机数存放数组元素的下标

Randomize

a(1) = Int(Rnd() * 900 + 100)

For i = 2 To 10

  temp = Int(Rnd() * 900 + 100)

  If seach(temp, i - 1) = True Then

    i = i - 1

  Else

k = i

    For j = 1 To i - 1

        If  temp < a(i)  Then k = j: Exit For   ‘①

    Next j

    For j = i - 1 To k Step -1

      a(j + 1) = a(j)

    Next j

         ②    

  End If

Next i

List1.Clear

For i = 1 To 10

  List1.AddItem Str(a(i))

Next i

End Sub

‘函数实现在数组a中,从下标为1的数组元素到下标为t数组元素,查找有无s的数值

Function seach(s  As Single, t As Integer) As Boolean

Dim i As Integer

seach = False

For i = 1 To t

  If     ③    Then seach = True: Exit For

Next i

End Function

二叉树是每个结点最多有两个子树的树结构,如值为9的结点有两个子树6和8,值为6的结点有两个子树5和3。若设二叉树的深度为h,则除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。现要构造大根堆,堆是一棵顺序存储的完全二叉树,大根堆又是一种特殊的堆,它的特征是每个双亲结点的值都不小于其孩子结点的值。如下图所示,值为9的结点是6和8的双亲结点,而6和8分别是9的左孩子和右孩子;同理,6是5和3的双亲结点,而5和3分别是6的左孩子和右孩子……

假如我们用数组表示上述大根堆:

a(1)

a(2)

a(3)

a(4)

a(5)

a(6)

a(7)

a(8)

a(9)

9

6

8

5

3

4

7

2

1

现有一算法把一个无序数组改造成大根堆。例如:我们在上图的大根堆中再增加一个值为8的新元素,如下图所示。

数组存储为:

a(2)

a(3)

a(4)

a(5)

a(6)

a(7)

a(8)

a(9)

a(10)

6

8

5

3

4

7

2

1

8

具体操作方法如下:

第一步:因为a(10)大于它的双亲结点a(5),故需交换a(10)和a(5)的值;

数组存储为:

第二步:因为a(5)大于它的双亲结点a(2),故需交换a(5)和a(2)(t)值;

数组存储为:

a(1)

a(2)

a(3)

a(4)

a(5)

a(6)

a(7)

a(8)

a(9)

a(10)

9

8

8

5

6

4

7

2

1

3

第3步:因为a(2)不大于它的双亲结点a(1),故无需做交换操作。此时新元素已经放到了正确的位置,新的大根堆构造完成,上移行动结束。

返回首页

试题篮