高考信息技术专题13 队列.pptx

第六单元数据结构;知识点;;;1.队列是一种__________、后进后出的线性表，允许插入的一端称为______，允许删除的一端称为______。

2.队列中的数据元素称为队列元素，在队列中插入一个元素称为______，从队列中删除一个元素称为______。

3.______元素只有一个后继，______元素只有一个前驱，其他元素既有一个前驱，又有一个后继。

4.队列一般按顺序结构存储，可以用数组来实现。设置________________和___________记录队首元素位置和队尾元素的下一个位置。

5.队列元素个数计算方法：tail－head。;队列是一种在数组两端分别进行存取的数据结构，最大特点是数据在存取时，无需查询，时间复杂度为O(1)，先存取的数据先被取出。队列是一种先进先出、后进后出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。队列一般按顺序结构存储，可以用数组来实现。;; ; ;;;1.用列表(数组)创建一个n个空间值为0的队列语句：que＝[0]*n；head＝tail＝0。

2.元素x入队时，先将元素存储到_______指针指向位置，然后______指针加1，即向队尾方向移动。语句：que[tail]＝x；tail＋＝1。

3.元素出队时，当队列非空时条件_______________，先读取队首head指针指向的元素，然后head指针加1，即向队尾方向移动，直到________________为止。语句：x＝que[head]；head＋＝1。;头指针head记录队首元素位置，队尾指针tail记录队尾元素的下一个位置，队列q的队尾元素值为q[tail－1]。入队时，考虑队列空间是否充足，当条件tail＝＝len(que)成立时，表示空间已满，不能入队。若队列不满，需将x赋值给q[tail]，让其成为新的队尾元素，再移动tail指针。出队时，先要判断队列是否为空，再将q[head]赋值给x，再移动head指针。;【例1】列表q长度为20，q[0]至q[4]的值依次为p，r，i，n，t，执行如下程序段后，输出的最后一个字符为()

head，tail＝0，5

whileheadtail：

ifhead%3＝＝0：

print(q[head])

else：

q[tail]＝q[head]

tail＋＝1

head＋＝1

A.t B.n C.i D.r; ;【变式1】有如下Python程序段：

s＝″abcdddbha″

que＝[″″]*10

head＝tail＝0

foriinrange(len(s))：

ifs[i]notinque[head：tail]：

que[tail]＝s[i]

tail＋＝1

else：

head＋＝1

print(que[head：tail])

程序运行后，输出的结果是()

A.[a，b，c，d，h] B.[a，b，c，d，d]

C.[c，d，b，h，a] D.[a，d，d，d，a]; ;【例2】有如下Python程序段：

importrandom

a＝[″x1″，″x2″，″x3″，″x4″，″x5″，″x6″]

k＝3

sq＝[－1]*len(a)

head＝tail＝i＝0

whileilen(a)ortail－head0：

op＝random.randint(0，1)

ifop＝＝0andtail－head0：

iftail－headk：

print(a[sq[tail－1]]，end＝″″)

tail－＝1;else：

print(a[sq[head]]，end＝″″)

head＋＝1

elifop＝＝1andilen(a)：

sq[tail]＝i

tail＋＝1

i＋＝1

则程序运行后，输出结果可能的是()

A.x1x4x6x2x3x5 B.x4x1x6x2x3x5

C.x1x2x3x6x4x5 D.x6x5x4x3x1x2; ;【变式2】有Python程序段如下：

importrandom

q＝[″″]*100；head＝tail＝0；ans＝″″

s＝input()

foriinrange(len(s))：

q[tail]＝s[i]；tail＋＝1

whileheadtail：

x＝random.randint(0，1)#随机生成整数0或1

ans＋＝q[head]；head＋＝1

ifheadtailandx%2＝＝0：

q[tail]＝q[head]

tail＋＝1；head＋＝1

print(ans); ;;;;;;;;7.有如下