资源简介

第三章 字符串、队列和栈 章节测试
一、选择题
1．元素1，2，3，4，5，6依次入栈，若第1个出栈的元素是4，则不可能是第3个出栈的元素是（ ）
A．1 B．2 C．3 D．5
2．下列关于队列和栈的说法，不正确的是（ ）
A．队列是一种先进先出的线性表，可在队尾进行插入操作
B．栈的特性是″先进后出，后进先出″
C．某栈的入栈的顺序为″abc″，出栈顺序只有3种
D．队列和栈都是线性数据结构，都可以用数组来实现
3．有一空栈S，对待进栈的数据元素序列a，b，c，d，e，f依次进栈、进栈、出栈、进栈、进栈、出栈的操作，操作完成后，栈S的栈顶元素是（ ）
A．c B．d C．e D．f
4．在某餐厅点餐系统中， 利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail 指向队尾元素的下一个位置， 若 tail=head+3，则现在排队的顾客数量为（ ）
A．2 B．3 C．4 D．5
5．有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ）
A．2，9，5 B．2，5，8 C．5，8，2 D．8，3，2
6．设栈S和队列Q的初始状态为空，元素w1、w2、w3、w4、w5依次通过栈S，一个元素出栈后即进入队列Q，下列不可能是出队序列的是（ ）
A．w5、w4、w3、w2、w1 B．w3、w2、w1、w4、w5
C．w4、w2、w1、w3、w5 D．w1、w2、w3、w4、w5
7．有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为：（　　）
A．4，5 B．5，4 C．2，4 D．4，2
8．有如下 Python 程序段：
s = input('请输入一串小写字母')
head = 0; tail = 0; top = -1
s1 = [""]*((len(s)+1)//2)
s2 = [""]*(len(s)//2)
for i in range(len(s)):
if i % 2 == 0:
s1[tail] = s[i]
tail += 1
else:
top += 1
s2[top] = s[i]
x = ""
while head < tail and top > -1:
x = s1[head] + x
head += 1
x = x + s2[top]
top -= 1
print(x)
执行该程序段，输入字符串“abcdefg”，则输出的结果是（ ）
A．acegbdf B．acegfdb C．gecafdb D．ecafdb
9．有如下程序段：
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i if i < len(bt) and bt[i] is not None:
stack.append(i)
i=2*i+1
else:
i=stack.pop()
result.append(bt[i])
i=2*i+2
print("-".join(result))
则程序运行后输出的结果为（ ）
A．A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F
10．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下：
st=[-1]*100
top=-1
n=int(input("请输入一个十进制数： "))
while n>0:
while top!=-1:
print(st[top],end="")
top-=1
方框处的代码由以下四部分组成：
①n=n//2 ②top+=1 ③x=n%2 ④st[top]=x
下列选项中，代码顺序正确的是（ ）
A．③④②① B．③①②④ C．①②③④ D．①③④②
11．一个序列的入栈顺序为9,8,7,6,5,4。若7第一个出栈，则下列出栈序列中不可能的是（ ）
A．7,8,9,6,5,4 B．7,8,9,5,6,4
C．7,9,8,4,5,6 D．7,8,9,6,4,5
12．有如下Python程序段：
w=[12，5，8，9，3，16]
n=len(w)；stack=[0]*n
top=-1；k=0；t=25
while top!=-l or kwhile t>0 and kif t>=w[k]：
top+=l；stack[top]=k
t-=w[k]
k+=l
if t==0：
print（stack[:top+1]）
k=stack[top]；top-=l
t+=w[k]：k+=l
执行该程序段后，输出第一组列表是（ ）
A．[0，1，2] B．[1，2，3，4] C．[3，5] D．[12，5，8]
13．某Python程序如下：
from random import randint
a=[1,8,3,6,7,2,9,0,5,1,3]
s=[-1]*100;top=-1
i=0
x=randint（5,8）
while i while top!=-1 and a[i] < s[top]:
top-=1
top+=1;s[top]=a[i]
i+=1
while top!=-1:
print(s[top],end="")
top-=1
执行该程序段后，输出的结果不可能是（ ）
A．0 B．21 C．631 D．921
14．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　）
A．数 B．链表 C．队列 D．栈
15．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为( )
A．a、b、c、d B．d、c、b、a
C．b、a、c、d D．d、b、a、c
二、填空题
16．有一维数组1、2、3、4、5，依次按照某一线性存储，请回答以下问题：
（1）如果该线性结构是队列，写出出队序列。
（2）如果该线性结构是栈，输出序列可能是4、3、5、1、2吗？为什么？
（3）在一维数组A中有5个元素：8、12、20、25、33，采用二分查找25，请写出每次查找的过程？
三、操作题
17．暑假期间，小明担任了天文馆售票处的志愿者工作，工作内容是维持游客的买票秩序，在开始售票前后的一段时间内（7：50-8：00），他观察到排队买票的队列发生了以下变化。（买票中不算排队）
时间 状态
7：50 售票窗口前没有人排队
7：55 售票窗口前有5个人（用P1，P2，P3，P4，P5表示）依次在排队
8：00 开始售票，有3个人（P1，P2，P3）陆续买票离开，又来了4个人（P6，P7，P8，P9）依次排入队中
根据上述观察，思考并回答下面的问题。
（1）最先进入队列的是 ，P3买完票离开后，排在队首的人是 ，队列里有 个人在排队。
（2）为了便于游客参观，天文馆配置了伴游机器人，此机器人不仅可以当小导游陪伴游览，还可以利用其自带的搜索功能轻松查找馆内餐厅、洗手间及各个展馆位置，搜索功能主要依赖于 。
A．DNS B．GPS C．CSS D．iOS
（3）经过暑假志愿服务的经验，小明想为天文馆设计一款网上自助售票系统，请你帮助小明完成预约流程图。（填字母）
① ；② ；③ ；④ 。
A．是B．选择预约日期C．选择预约时间段D．否
18．为鼓励绿色出行，某市推出了优惠方案：乘一次地铁后可以获得一张优惠券，在有效期45分钟内(含)可免费搭乘一次公交车。有效期指乘公交车与乘地铁的开始时刻之差。搭乘公交车时，可以使用优惠券则一定会使用，如果有多张优惠券满足条件，则优先消费获得最早的优惠券。有人用Python编写程序计算出行的费用。他的某次出行过程如图a所示，程序运行结果如图b所示。
请回答下列问题：
（1）请在划线处填入合适的代码。
def Ctime(t):
# 自定义函数Ctime功能为将时间转为分钟计存入变量s，代码略。
return s
'''
读取出行记录，存储在列表a中，a[i][0]、a[i][1]、a[i][2]依次存储交通工具类型、票价、乘坐开始时刻。交通工具类型a[i][0]值为0表示地铁，1表示公交车。代码略。
'''
n = len(a)
for i in range(n):
a[i][2] = Ctime(a[i][2])
for i in range(n - 1):
for j in range(n - 1, i, -1):
a[j], a[j - 1]= a[j - 1], a[j]
# 输出出行记录，代码略。
total = 0
head = tail = 0
q = [-1] * n
for i in range(n):
if a[i][0] == 0:
total += a[i][1]
tail += 1
else:
while head < tail and q[head] < a[i][2] - 45:
head += 1
if :
total += a[i][1]
else:
print(a[i][2],"时刻使用了优惠券")
print("总共花费为:", total)
（2）程序中加框处代码有错，请改正。
（3）该程序主要应用的数据结构类型是 (选填：队列 / 栈 / 链表 / 二叉树)。
19．小明对入栈、出栈规则研究发现， 若有 n 个数字 1，2，3，……，n 按由小到大的顺 序入栈，则出栈序列必须遵循下述原则： 当数字 x 出栈后，则在x后出栈的小于x 的 所有数字必定以降序排列，比x大的数字可以夹杂在该降序序列中。现编写 Python 程 序，按上述原则验证一个随机产生的出栈序列是否可能， 程序运行界面如图所示。
(1) 根据题意，若有 7 个数字入栈， 则出栈序列“3→2→5→4→7→1→6”是 (单选，填字母： A．可能 / B．不可能)
(2) 实现上述功能的Python程序代码如下，程序中加框处代码有错，请改正 。
(3)请在划线①②处填入合适代码 、 。
import random
n=int(input('请输入入栈元素的个数：'))
data=[i+1 for i in range(n)]
random.shuffle(data) #将序列的所有元素随机排序
s=” ”
for i in range(n):
print('随机产生的出栈序列为： '+s[1:])
flag=True;i=0
while i①
for j in range(i+1,n):
if data[j]if data[j]x=data[j]
else:
②#去除最后多余的'→'
break
i+=1
if flag:
print('该出栈序列是可能的！')
else:
print('该出栈序列是不可能的！ ')
参考答案：
1．A
2．C
3．A
4．B
5．B
6．C
7．C
8．D
9．C
10．B
11．C
12．A
13．C
14．B
15．B
16．1、2、3、4、5
不可能，因为：4是第一出栈字符，说明1,2已别压入栈内；并且压入栈的次序为12345;由以上得出：12出栈的顺序只能是2、1，而不是1、2。所以，出栈序列4,3,5,1,2是不可能的 第一次查找，找到的元素为20，此时20小于目标数，所以在列表的后半部分查找，第二次查找到的元素为25，此时找到，所以共需要两次找到
17．P1 P4 5 B B C A D
18．q[tail]=a[i][2] head==tail 或 q[head]==-1 head+=1 a[j][2] < a[j - 1][2] 队列
19．B s+=’ →’+str(data[i]) x=data[i] flag=False

展开更多......

收起↑