0 返回首页
1. 小胡公司组织四人制篮球赛（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()

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

您现在未登录，无法查看试题答案与解析。 登录
综合题 困难
能力提升
变式训练
拓展培优
换一批
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. 小明所在的班级共有 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))
综合题 普通
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
综合题 困难