试题

试题 试卷

logo

题型:综合题 题类: 难易度:普通

浙江省七彩阳光联盟2023-2024学年高三上学期第一次联考信息技术试题

某公路由于长期没有维修,路上出现了很多个坑。为了尽快填补好这些坑,交通管理部门决定对m处地段采取交通管制。将该公路看成一条直线,坑就是直线上的坐标点,坑所在的路段需要封控管制。例如某管制路段2~4,需封控2、3、4路段。交管部门为了减少管制路段的长度,希望将这n个坑分成m段(一段可以只有一个坑),使得这m段公路的总长度最小。请你根据n个坑的位置(位置已按照从小到大进行排序),计算管制路段最小的总长度。代码运行效果如图所示。

请回答下列问题:

(1)、上图所示的例子中,若将路段数量修改为5,则管制路段总长度为
(2)、实现上述功能的Python 程序如下,请在划线处填入合适的代码。

m = int(input("路段数量:"))

s = input("坑的坐标依次为:").split(',')

n = len(s)

for i in range(n):

    s[i] = int(s[i])

flag = [False] * (n-1)

for i in range(1, m):

    k = -1

    for j in range(n-1):

        if:

            if k == -1 or s[j+1]-s[j] > s[k+1]-s[k]:

                k = j

    flag[k] = True

print("维修管制的路段依次为:")

dis, t = 0, 0

for i in range(n-1):

    if flag[i]:

        print(s[t],"~",s[i])

        dis += s[i]-s[t]+1

        

print(s[t],"~",s[n-1]) 

dis =  

print("管制 总长度为",dis)

举一反三
小明探索用链表思想实现插入排序。链表由节点连接而成,每个节点包含一个数据域和一个指针域。为了模拟这个过程,小明用a数组保存链表数据域,b数组保存链表指针域,排序的过程就是将每个数据的指针域不断链接到已有的有序链表合适位置,形成更长 的链表,直到所有的数据均链接到链表中。

例如将某节点插入到已有链表中,根据大小比较有三种情况:插入到最前面、插入到 最后、插入到中间,如图a所示,在链表中的节点 x 和节点 y之间插入节点n的过程示意:过程一(初始状态)如图1所示,链表中节点 x 的指针域指向节点y数据域,即图示①指向;过程二如图2所示,将节点n的指针域指向节点 y 数据域,即图示②指向;过程三如图 3 所示,将①指向断开,同时将节点 x 的指针域指向节点n数据域,即图示③指向;至此完成节点n的插入操作。

图a

具体程序设计方法如下:

1)将待排序的n个数保存在a(1)~a(n),b(1)~b(n)保存对应a数组各元素的位置,形成 n个没有链接的节点;

2)将a(1)结点看成只含有一个结点的链表head,且 head=1;

3)将a(2)节点插入到链表head的适当位置,使head仍有序,此时head成为含有两个结点的有序链表;以此方法依次将a数组中的其他节点插入到链表head中,最后链表 head上包含所有结点,且结点有序。依次输出head链表的数据域即完成排序。

程序运行界面如图b所示,采用此思想进行升序排序的 VB 代码如下,请回答下列问题。

图b

【加试题】某排序算法思想如下:若有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

返回首页

试题篮