专题18　基于数据结构的算法实现 学案（含解析）2025届高中信息技术.DOCX

专题18基于数据结构的算法实现

学习目标1.掌握队列中元素入队和出队的条件；

2.掌握链表的构建方法.

队列是线性结构的一种，因此也可以用链式结构的方式来实现。并且链式结构的队列，由于节点空间都是在入队的时候动态申请的，因此在计算机内存空间足够的情况下，一般不需要考虑队满的情况，也就不存在溢出的情况，所以不需要使用循环链式队列来处理假溢出的情况。链式队列在链表的链尾插入元素，然后让队尾指针指向链尾元素。链式队列的出队，就是将链表的首元节点从链表中删去，让其后继节点成为首元节点，然后让队头指针指向该节点。

(2024年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进行降序排序。

defbubble_sort(lst):

n＝len(lst)

foriinrange(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中删除

图c

defgroup(data,m):

n＝len(data)

a＝[]

foriinrange(n＋1)：

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

gnum＝0

foriinrange(n)：#各单位内部分组

whiledata[i][1]＝m：

gnum＋＝1

k＝data[i][0]

a[k].append(gnum)

①________

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

b＝[]

foriinrange(m):

b.append([])

i＝0

whileinanddata[i][1]！＝0:#对剩余员工分组

②________

whilejmandlen(b[j])＝＝0:

j＋＝1

ifjm：

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]，