试题

试题 试卷

logo

题型:单选题 题类:模拟题 难易度:普通

浙江省绍兴市上虞区2020届高三下学期信息技术第二次教学质量调测卷

采用冒泡排序算法对原数据序列“5,6,4, 7, 2, 1”的奇数位进行升序排序,若排序遍后为“2, 6, 5,7,4,1”,则下一遍排序后为(   )
A、1, 2, 6,5,7, 4 B、2,6,1,7,4,5 C、6,5,7,4,2, 1 D、2,6,4,7,5,1
举一反三
二叉树是每个结点最多有两个子树的树结构,如值为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),故无需做交换操作。此时新元素已经放到了正确的位置,新的大根堆构造完成,上移行动结束。

编写一个查找最接近的数的VB程序:程序运行时,在文本框Text1中输人产生随机数的个数(1到100之间),单击命令按钮“产生随机数并升序排列”后,在列表框List1中显示已经按升序排列后的随机整数,然后在文本框Text2中输入要查找的整数,单击命令按钮"查找"后,在标签Label3中显示随机整数序列中与待查找数最接近的整数(当最接近的数有2个时,输出较大的一个)。程序运行效果如图所示:

实现上述功能的VB代码如下,请在横线处填入合适代码。

Dim n As Integer          '存储随机数的个数

Dim f(1To100)As Boolean

'f(i)为True时表示随机整数i已经产生过

Dim a(1 To 100)As Integer

'依次存放升序排序后的n个随机数

Private Sub Command1_Click()

'命令按钮“产生随机数并升序排列”的单击事件

    Dim i As Integer

    Randomize

    For i=1 To 100

        f(i)=False

    Next i

    n=Val(Text1. Text)

    For i=1 To n

        t=Int(Rnd * 100+1)

        Do While f(t)=True

            t=Int(Rnd * 100+1)

        Loop

        {#blank#}1{#/blank#}

    Next i

    j=0

    For i=1 To 100        '实现排序并输出

        If f(i)=True Then

            {#blank#}2{#/blank#}

            a(j)=i

            List1.AddItem Str(i)

        End If

    Next i

End Sub

Private Sub Command2_Click()

'命令按钮“查找”的单击事件

    Dim key As Integer

    key=Val(Text2. Text)

    If key <=a(1) Then Label3. Caption=Str(a(1)): Exit Sub

    If key >=a(n) Then Label3. Caption=Str(a( n)): Exit Sub

    L=1: R=n

    Do While L<=R                '找到与 key 较为接近的两个数a(R)和a(L)

        m=(L+R)\2

        If key<=a(m)Then

            R=m-1

        Else

            L=m+1

        End If

    Loop

    If {#blank#}3{#/blank#}Then

    '在a(R)和 a(L)中选出更接近key的数

        Label3. Caption=Str(a(R))

    Else

        Label3. Caption=Str(a L))

    End If

End Sub

返回首页

试题篮