1. 小明所在的班级共有 20 名男生,要参加学校举办的拔河比赛,赛前根据体重分成 AB 两组进行训练,要求每组 10 人, 且每组男生的体重之和尽量接近。小明设计了如下算法:

①初步分组:将所有男生按体重从高到低排序,并以 ABAB…进行初步分组;

②计算体重差: 计算每组对应两个男生的体重差;

③交换学生:按体重差从高到低判断是否交换学生。

例如 20 名男生的体重(单位: kg)从高到低为:

95, 93, 93, 90, 90, 90, 84, 83, 83, 78, 77, 75, 74, 69, 64, 61, 61, 60, 56, 55。

步骤

体重

体重和

初步分组

A 组

95

93

90

84

83

77

74

64

61

56

777

B 组

93

90

90

83

78

75

69

61

60

55

754

体重差

2

3

0

1

5

2

5

3

1

1

23

交换学生

 

最终分组

A 组

95

93

90

83

78

77

69

64

61

56

766

B 组

93

90

90

84

83

75

74

61

60

55

765

小明按照以上算法编写Python程序如下,请在划线处填入合适的代码。

def group(student):    #初步分组

    a=[];b=[]

    i=0

    while i<len(student):

        a.append(student[i])

        b.append(student[i+1])

       

    return a,b

def cal_diff(a,b):     #计算体重差并降序排序

    d=[]

    for i in range(len(a)):

        d.append([i,a[i]-b[i]])

        for i in range(len(d)-1):

            for j in range(0,len(d)-i-1):

                if  :

                    d[j],d[j+1]=d[j+1],d[j]

        return d

def change(d,a,b):     #标记是否交换

    k=(sum(a)-sum(b))//2

    f=[0]*len(d)

    ssum=0

    for i in range(len(d)):

        ssum+=d[i][1]

        if ssum>k:

            ssum-=d[i][1]

        else:

           

            if ssum==k:

                break

    return f

student=[95, 93, 93, 90, 90, 90, 84, 83, 83, 78, 77, 75, 74, 69, 64, 61, 61, 60, 56, 55]

qA,qB=group(student)

print("初步分组后 A 组体重: ",qA,"和为:",sum(qA))

print("初步分组后 B 组体重: ",qB,"和为:",sum(qB))

diff=cal_diff(qA,qB)

flag=

for i in range(len(flag)):    #交换

    if flag[i]==1:

        qA[i],qB[i]=qB[i],qA[i]

print("交换后 A 组体重:",qA,"和为:",sum(qA))

print("交换后 B 组体重:",qB,"和为: ",sum(qB))

【考点】
过程与自定义函数; 排序算法及程序实现;
【答案】

您现在未登录,无法查看试题答案与解析。 登录
综合题 普通
能力提升
变式训练
拓展培优
换一批
1. 某项活动有n个单位(编号1到n)参加,需将员工分成若干个小组,每个小组的人数上限为m,小组编号按新建次序从1开始编号。分组时,首先按单位编号次序依次在各单位内部分分组,每m人分配到一个新建小组中,不足m人的剩余员工暂不分配;然后按剩余员工人数由大到小的顺序,依次为各单位剩余员工分配小组。

若某单位剩余员工人数为k,则分配方法为:在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组,如果找到的小组有多个,则选择空位数最少的小组,将此k人分配到该小组中;如果没有找到,则新建一个小组,将此k人分配到该小组中。

设n为5,m为20,各单位员工人数及单位内部的分组过程如图a所示,各单位剩余员工的分组过程如图b所示。

编写程序:给定各单位编号及员工人数,根据上述方法进行分组处理,按单位编号次序输出各单位所分配的分组编号。请回答下列问题:

(1) 由题意可知,若仅将图a中1号单位的员工人数修改为25,然后对图中5个单位重新分组,则1号单位所分配的分组编号为
(2) 定义如下bubble_sort(lst)函数,参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数,对lst进行降序排序。

def bubble_sort(lst):

    n=len(lst)

    for i in range(0, n-1):

       

    return

调用该函数,若 lst 为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],请回答①和②两个问题。

①虚线框中的程序段第 1 次执行后,关于 lst 中的剩余员工人数,下列说法正确的是(单选,填字母)。

A.lst[0][1]数值最小 B.lst[0][1]数值最大

C.lst[5][1]数值最小 D.lst[5][1]数值最大

②虚线框中的程序段执行的次数为

(3) 实现分组功能的部分 Python 程序如下,程序中用到的列表函数与方法如图 c 所示,请在程序中划线处填入合适的代码。

函数与方法

功能

w.append(x)

在列表 w 末尾添加元素 x

x.w.pop()

将列表 w 末尾元素赋值给 x,并将其从 w 中删除

def group(data, m):

    n=len(data)

    a=[]

    for i in range(n+1):

        a.append([])       # a[i]初始化为空列表,存放编号为 i 的单位所分配的分组编号

    gnum=0

    for i in range(n): #各单位内部分组

        while data[i][1]>=m:

            gnum+=1

            k=data[i][0]

            a[k].append(gnum)

           

    bubble_sort(data) #根据每个单位的剩余员工人数,对 data 进行降序排序

    b=[]

    for i in range(m):

        b.append([])

    i=0       #对剩余员工分组

    while i<n and data[i][1]!=0:

       

        while j<m and len(b[j])==0:

            j+=1

        if j<m:

            v=b[j].pop()

        else:

            gnum+=1

            v=gnum

        a[data[i][0]].append(v)

       

        i+=1

    #输出各单位的分组编号,代码略

'''

读取小组人数上限存入 m;读取 1 至 n 号单位的数据,依次存入列表 data 的 data[0]至 data[n-1]中。

Data[i]包含 2 个数据项,data[i][0],data[i][1]分别存放单位编号及员工人数,代码略

'''

group(lst, m)

综合题 困难
2. 小胡公司组织四人制篮球赛(2人对2人),现已报名n(n为偶数)人,根据这n人个人篮球赛成绩降序排序后存于单向链表a中,为使每队实力尽量均衡,将a中第1人和最后一人组队,第2人和倒数第2人组队,以此类推。例如有6名编号为T01、T02、T03、T04、T05、T06的队员报名参赛,按个人篮球赛成绩降序排序后的次序为:T05、T06、T02、T03、T04、T01,经过分组后分组情况如下图所示:

具体算法为:

⑴找到链表的中点

⑵将链表的右半段反转

⑶将链表左半段和反转后的右半段合并

⑷按顺序输出每组队员编号

小胡编写程序实现将这n人进行分组并输出每组队员编号,请在划线处填入合适的代码。

# 找到原链表的中点

def middleNode(head):

    slow = fast = head

    while a[fast][1] != -1 and a[a[fast][1]][1] != -1:

        slow =

        fast = a[a[fast][1]][1]

    return slow

# 将原链表的右半段反转

def reverseList(head):

    pre = -1

    cur = head

    while cur != -1:

        nextTemp = a[cur][1]

        a[cur][1] = pre

       

        cur = nextTemp

    return pre

# 将原链表的两段合并

def mergeList(h1, h2):

    while h1 != -1 and h2 != -1:

        h1_tmp = a[h1][1]

        h2_tmp = a[h2][1]

       

        h1 = h1_tmp

        a[h2][1] = h1

        h2 = h2_tmp

# 输出分组情况

def show():

    head = 0

    i = 0

    print('分组情况:')

    while head != -1:

        if i % 2 == 0:

            print('第', , '组:', a[head][0], '和 ', end='')

        else:

            print(a[head][0])

        i += 1

        head = a[head][1]

# 读入n人编号,并按个人篮球赛成绩降序排序后依次将编号存入a中并输出a(代码略)

mid = middleNode(0)

head1 = 0

head2 = a[mid][1]

head2 = reverseList(head2)

mergeList(head1, head2)

show()

综合题 困难
3. 有n册图书已按图书编号升序排列(编号互不重复,用7位长度的字符串表示)。经过多次借阅归还之后,部分图书顺序被打乱,现要找出这部分图书进行调整,以使整体升序。算法思想:先找到首尾两个图书编号升序区间,再处理得到待调整区间,最后对该区间中的图书编号排序。

编写VB程序,实现上述功能。运行程序,在列表框List1中显示全部图书编号。单击“整理”按钮Command1,在标签Label1中显示待调整区间图书的册数,在文本框Text1中显示待调整区间图书的起止编号,并在列表框List2中显示排序后的图书编号。程序运行界面如图所示,其中①和②两处分别指向待调整区间图书的起始和截止编号。

(1) 如图所示,若采用选择排序算法,仅将待调整区间图书进行升序排序,排序过程结束后,数组元素之间的比较次数为(填数字)。
(2) 实现上述功能的部分VB程序如下,请在划线处填入合适的代码。

'n是常量,代码略

Dim a(0 To n) As String

Private Sub Form_ Load()

    a(0)= "”

    '将n册图书的编号存入数组元素a(1)~a(n),在List1中显示,代码略

End Sub

Private Sub Command1_ Click()

    Dim i As Integer, k As Integer, left As Integer, right As Integer

    Dim min As String, max As String

    min= ": max= ": left= 1: right= 0

    For i= 1 To n- 1

        If a(i)> a(i + 1) Then

            max = a(i)

            left= i: Exit For

        End If

    Next i

    For i=n To 2 Step-1

        If  Then

           min= a(i)

right= i: Exit For

        End If

    Next i

    i= left

     Do While i <= right

        If a(i)> max Then

          max = a(i)

        ElseIf a(i) < min Then

            min= a(i)

        End If

       i=i+ 1

    Loop

    k=0

    If left < right Then

        left = getPos(1, left, min)

       

         k= right- left+ 1

Text1.Text= "待调整区间图书起始编号: " + a(left) + "-->截止编号: "+ a(right)

    End If

Label1.Caption = "待调整区间图书共有:" + Str(k) + "册"

    '对待调整区间的图书编号进行排序,在List2中输出整理结果,代码略

End Sub

Function getPos(head As Integer, tail As Integer, value As String) As Integer

    Dim i As Integer

    i= tai1

    Do While

        i=i- 1

    Loop

    getPos=i+ 1

End Function

综合题 困难