资源简介

三、 栈及其基本操作
1. 栈s的初始状态为空,经过一系列入栈、出栈操作后,元素的入栈顺序为a,b,c,d,e,f,g, 出栈顺序为b,e,d,c,f,a,g,则栈s的容量至少是(　C　)
A. 2 B. 3
C. 4 D. 5
【解析】 本题考查栈的知识。b出时,a在;e在栈顶时,栈内有acde,栈s的容量至少是4,C正确。
2. 某括号序列中,若左括号出现的顺序及个数与右括号保持一致,则称该序列中的括号是匹配的。例如,序列“())(”中的括号是不匹配的,可将其中第3个、第4个括号修改为“()”使其重新匹配。现给出一个长度为偶数的不匹配序列,为使其重新匹配,统计最少需要修改的括号数。实现上述功能的Python程序段如下:
s = input()　　# 输入括号序列,序列中仅包含“(”和“)”两种字符
top = －1; ans = 0
for i in range(len(s)):
　　if s[i] == "(":
　　　　top ＋= 1
　　else:
　　　　if 　(1)　:
　　　　　　top ＋= 1
　　　　　　ans ＋= 1
　　　　else:
　　　　　　　(2)　
ans ＋= 　(3)　
上述程序段的方框处可选代码如下:
①top != －1 　②top == －1 　③top ＋= 1 　④top －= 1 　⑤top // 2 　⑥(top ＋ 1)// 2
则方框处的代码依次是(　D　)
A. ①③⑥ B. ①④⑤
C. ②④⑤ D. ②④⑥
【解析】 本题考查栈及Python综合知识。观察程序段可知,程序遇到左括号的时候top＋1,为了匹配top会－1,而ans是最少修改的次数。该程序算法思想为:若遇到左括号top会累加,否则是遇到右括号执行else部分,else部分中若top=－1,则说明是第一次遍历遇到了右括号,为了匹配得先改成左括号,所以ans会加1,故(1)处答案为②top ==－1;否则说明有多个左括号,现在遇到了右括号为了匹配则会使top－1,故(2)处答案为④top －=1;(3)处用极值法思考会更快,由于是偶数长度,而为了使左括号出现的顺序及个数与右括号保持一致,若top=－1说明刚好匹配,故⑥(top ＋ 1)//2=0。D正确。
3. 元素1、2、3、4、5依次入栈,假设出栈序列为X、3、Y、Z、4。下列关于X、Y、Z的叙述,正确的是(　D　)
A. X不可能为1 B. Y不可能为2
C. Z不可能为5 D. X或Y的值比Z小
【解析】 本题考查栈的操作相关知识。根据入栈和出栈顺序,当1入栈,1出栈的时候符合X是第一个出栈的,A错误。当1入栈,X=1出栈,2入栈－3入栈－3出栈,Y=2出栈,4入栈－5入栈,Z=5出栈,4出栈符合题目要求,故Y的值可能为2,B错误。1入栈－2入栈－X=2出栈－3出栈;接着Y=1出栈－4入栈－5入栈,才能Z=5出栈,最后4出栈也符合题目出入栈要求,C错误。
4. 有一个入栈序列为e1,e2,e3,e4,下列选项中,可能的出栈序列是(　A　)
A. e2,e4,e3,e1 B. e3,e1,e4,e2
C. e3,e4,e1,e2 D. e4,e3,e1,e2
【解析】 本题考查栈知识。B中e3先出栈,下面还有e2,e1不能紧跟着出栈,错误。C、D同理,错误。e1、e2依次入栈,e2首先出栈,e3、e4再依次入栈,然后e4、e3、e1依次出栈,所以出栈序列为:e2,e4,e3,e1,A正确。
5. 用一个带盖的玻璃筒来放取乒乓球,放、取只能在带盖的一端进行(另一端为封闭状态),且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4,则取出球的编号序列不可能是(　C　)
A. 1、2、3、4 B. 2、3、4、1
C. 4、2、3、1 D. 3、2、1、4
【解析】 本题考查栈知识。题目描述的乒乓球进出过程,符合栈的特点。根据栈的后进先出的特点可知,不可能的出球编号序列是:4、2、3、1,C正确。
6. 下列关于数据结构的说法,正确的是(　A　)
A. 队列和栈都是操作受限的线性表
B. 链表必定有1个头指针和1个尾指针
C. 字符串中不能存储空格字符
D. 数组元素的数据类型可以不一致
【解析】 本题考查数据结构相关知识。链表一定有头指针,尾指针不是必需的,B错误。空格字符和其他字符没什么区别,字符串中可以存储,C错误。根据数组的定义,数组中的元素类型必须一致,D错误。
7. 某栈的入栈顺序为“abc”,出栈顺序为“bca”,则经过的操作为(　B　)
A. 入栈、出栈、入栈、出栈、入栈、出栈
B. 入栈、入栈、出栈、入栈、出栈、出栈
C. 入栈、入栈、入栈、出栈、出栈、出栈
D. 入栈、出栈、入栈、入栈、出栈、出栈
【解析】 根据栈“先进后出、后进先出”的特点可以模拟:a入栈、b入栈、b出栈、c入栈、c出栈、a出栈,B正确。
8. 对栈进行操作时,若进栈的元素顺序是“A、B、C、D”,则出栈的顺序不可能是(　C　)
A. “A、B、C、D” B. “D、C、B、A”
C. “D、C、A、B” D. “C、D、B、A”
【解析】 出栈的规则是“先进后出”或“后进先出”。根据此特点可知,“D、C、A、B”的出栈顺序是不可能的,C符合题意。
9. 用Python列表自带的函数和方法来模拟栈,代码如下:
import random
a=[1,2,3,4,5]
stack=[a[0]]
i=1
res=[]
while i　　if random.randint(0,1)==0 or len(stack)==0:
　　　　stack.append(a[i])
　　else:
　　　　res.append(stack.pop())
　　　　i－=1
　　i＋=1
while len(stack)>0:
　　res.append(stack.pop())
print(res)
执行该程序段后,结果不可能为(　D　)
A. [1, 2, 3, 4, 5] B. [2, 1, 4, 3, 5]
C. [1, 5, 4, 3, 2] D. [1, 4, 2, 3, 5]
【解析】 栈遵循“先进后出”的规则,1先入栈,然后出栈,接着2,3,4入栈,4出栈,此时栈顶元素为3,不可能2先出栈,D符合题意。
10. 地面上有标号为 A、B、C的3根细柱,在A柱上放有 10个直径相同且中间有孔的圆盘,从上到下依次编号为 1,2,3,…,将 A柱上的部分圆盘经过B柱移入 C柱,也可以在 B柱上暂存。如果 B柱上的操作记录如下:“进,进,出,进,进,出,出,进,进,出,进,出,出”,那么在 C柱上,从下到上的盘子的编号为(　A　)
A. 2 4 3 6 7 5 B. 2 4 1 2 5 7
C. 2 4 3 1 7 6 D. 2 4 3 6 5 7
【解析】 本题考查栈的知识。“进进”表示将A柱上的1、2先后移入B柱上,2在1的上面,接着“出”表示将B柱上的2移入C柱上;同理下一组“进进”,此时B柱从上到下依次是4、3、1,“出出”表示将B柱上的4、3移入C柱上,此时C柱从上到下依次是3、4、2;下一组“进进出”后,C柱从上到下依次是6、3、4、2;最后一组“进出出”后,C柱从上到下依次是5、7、6、3、4、2,即2 4 3 6 7 5,A正确。
11. 利用栈的“先进后出”的特点可以实现数的进制转换。有如下Python程序段,实现的是十进制数转换为十六进制数的功能,运行界面如图所示。
请输入十进制整数:466
其十六进制数为:1 D 2
请回答下列问题:
(1)十进制数55,其十六进制数为　37　。
(2)请在画线处填入合适的代码。
s=[""]*100
top=－1
n=int(input("请输入十进制整数: "))
while n>0:
　　top＋=1
　　r=n%16
　　if r>9:
　　　　①　s[top]=chr(r＋55)　
　　else:　　
　　　　s[top]=r
　　②　n=n//16　
print("其十六进制数为:",end=" ")
while ③　top >－1　:
　　print(s[top],end=" ")
　　top－=1
【解析】 本题考查栈的应用。利用除16取余倒排法解题。(1)十进制数55,其十六进制数为37。(2)①top是栈顶,该处功能是实现将取得的余数进栈操作。若余数大于9,则应该将其转换为相应的A~F的大写英文字符,利用数字和ASCII码的规律可知,10加上55,对应字符恰好为英文字符“A”。因此答案是chr(r＋55)。②每次取余后,n都要被16整除,因此更新n的值为新值,直到n=0为止。③将所有得到的余数出栈,top指针每次减1,直到top=－1结束,此时所有数据出栈完毕。
12. 在数学算式“(9÷(5－2)＋3)* 6”中,位置1和位置4有左括号“(”,位置8和位置11有右括号“)”。 位置1的左括号与位置11的右括号相匹配,位置4的左括号与位置8的右括号相匹配。而对于数学算式“a(b－c))”,位置8的右括号没有可匹配的左括号。设计一个程序,判断输入的数学算式中的括号(只有小括号)是否匹配。实现上述功能的Python代码如下,运行界面如图所示。请在画线处填入合适的代码。
请输入数学算式:(9÷(5－2)＋3)*6
括号匹配
st=[""]*100
top=①　－1　
flag=True
s=input("请输入数学算式: ")
for i in range(len(s)):
　　if s[i]=="(":
　　　　top=top＋1
　　　　②　st[top]=s[i]　
　　elif s[i]== ")":
　　　　if top==－1:
　　　　　　flag=False
　　　　　　break
　　　　else:
　　　　　　③　top=top－1　
if top>=0:
　　flag=False
if flag:
　　print("括号匹配")
else:
　　print("括号不匹配")
【解析】 本题考查栈的应用知识。①栈顶的初值一般初始化为－1。②本题的意图是利用栈来实现对括号的配对检查,当出现一个左括号时将其压栈处理,若检测到右括号时进行出栈处理。③若检查到最后来到top=－1,则表明左右括号匹配,否则不匹配。
13. 例如,“CBAABC”称为回文字符串,而“ABC”则不是回文字符串。可以利用栈来检查是否为回文字符串,小王利用Python编写如下程序实现上述功能,运行界面如图所示。请在画线处填入合适的代码。
请输入字符串:12321
字符串:12321 是回文字符串
st=[""]*100
top=－1
①　flag=True　
s=input("请输入字符串:")
k=len(s)//2
for i in range(k):
　　top＋=1
　　st[top]=s[i]
if ②　len(s)%2==1　:
　　k=k＋1
for i in range(k,len(s)):
　　ch=st[top]
　　top－=1
　　if ③　ch!=s[i]　:
　　　　　flag=False;break;
if flag:
　　　print("字符串:",s,"是回文字符串")
else:
　　　print("字符串:",s,"不是回文字符串")
【解析】 本题考查利用Python的栈实现检查回文字符串的目的。①从代码看,此处需要实现变量flag的初始化,且其值为True。②k值是字符串长度的一半,若字符串长度为奇数,则k值加1,从而避免将奇数字符的最中间的字符进行比较。③利用栈的功能将前一半的字符按顺序入栈,然后将后一半的字符串和出栈后的字符进行逐个比较,只要有一个字符不同就说明不是回文串。最后检查完毕后,若flag依然是True,则表明是回文串。
14. 自从学习了不同进制之后,小明设计了一个计算不同进制数的加法器,并用Python编程实现。输入一个加法算式,加数可以是十进制数、二进制数或者十六进制数,程序的功能是输出它们的和。例如,输入形如“1010B＋1DH＋109D=”的加法算式后,执行程序输出“和是148”的结果。实现上述功能的Python程序如下:
s=input( 输入一个混合进制的加法算式: )
dic={ B :2, D :10, H :16}
st=[ ]*100
top, i, x, m=－1, 0, 0, 0
while i　　if s[i]== ＋ or s[i]== = :
　　　　m=①　dic[st[top]]　
　　　　top=top－1
　　　　t=0
　　　　while top!=－1:
　　　　　　if st[top]>= A and st[top]<= F :
　　　　　　　　st[top]=ord(st[top])－ord( A )＋10
　　　　　　else:
　　　　　　　　st[top]=int(st[top])
　　　　　　②　x=x＋st[top]*m**t　
　　　　　　t=t＋1
　　　　　　top=top－1
　　else:
　　　　③　top=top＋1　
　　　　st[top]=s[i]
　　i=i＋1
print( 和是 ,x)
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)若输入“1011B＋2DH＋178D”,输出的结果是　和是68　。
【解析】 本题考查栈的应用。根据代码可知，st列表中保存着当前加数的每一位。如对于式子“1010B＋1DH＋109D=”,当读到第一个加号时,st列表的值为["1","0","1","0","B"],读到第二加号时,st的值是 ["1","D","H"],读到最后‘=’号时,st的值是["1", "0","9","D"]。(1)①st列表的最后一位是进制编号,读取st最后一位,通过字典dic得到进制值。②使用权值法把st列表中保存的进制数转化为十进制数。③读取到加数的每一位数字,都保存在st列表中的相应位置。(2)由于式子中的最后一位不是‘＋’或者‘=’,所以st列表中的最后一个数字没有加上,故和是68。
15. 为便于计算表达式的值,波兰数学家提出了将运算符置于运算对象之后的表示方法,即不需要考虑运算符的优先级。下面的Python程序段实现了对逆波兰式的计算(假定逆波兰式中的运算对象均为一位正整数,且运算只有加减乘除),当输入“682－2*3/＋”时,输出“10”。请在画线处填入合适的代码。
st=[0]*100;top=－1
s=input("请输入逆波兰式:")
i=0
while i　　if "0" <= s[i] <= "9":　#数字字符
　　　　top＋=1
　　　　st[top]= ①　int(s[i])或 ord(s[i])－48　
　　else:
　　　　x=st[top];top－=1
　　　　y=st[top];top－=1
　　　　if s[i]=="＋":　　　#加法运算　　
　　　　　　top＋=1;st[top]=x＋y
　　　　elif s[i]=="－":　　#减法运算　　
　　　　　　top＋=1; ②　st[top]=y－x　
　　　　elif s[i]=="*":　　#乘法运算　　
　　　　　　top＋=1;st[top]=x*y
　　　　else:　　　　　　　#除法运算　　
　　　　　　top＋=1;st[top]=int(y/x)
　　i=i＋1
print(③　st[top]　)　　#输出最后的运算结果
【解析】 本题算法利用栈实现对逆波兰式的计算。当遇到运算对象时进行进栈操作,遇到运算符时从栈中取出两个运算对象,运算结果再入栈,重复此操作,直到逆波兰式结束,最后输出栈顶元素。 ①此处要将对应的数字字符表达的数值进行入栈操作。②此处将减法运算的结果进行入栈操作,由于y是被减数,x是减数,运算结果为y－x。③此处最后输出栈顶元素st[top]。(共29张PPT)
三、 栈及其基本操作
第三章　字符串、队列和栈
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 栈s的初始状态为空,经过一系列入栈、出栈操作后,元素的入栈顺序为a,b,c,d,e,f,g, 出栈顺序为b,e,d,c,f,a,g,则栈s的容量至少是(　　)
A. 2 B. 3
C. 4 D. 5
【解析】 本题考查栈的知识。b出时,a在;e在栈顶时,栈内有acde,栈s的容量至少是4,C正确。
C
2. 某括号序列中,若左括号出现的顺序及个数与右括号保持一致,则称该序列中的括号是匹配的。例如,序列“())(”中的括号是不匹配的,可将其中第3个、第4个括号修改为“()”使其重新匹配。现给出一个长度为偶数的不匹配序列,为使其重新匹配,统计最少需要修改的括号数。实现上述功能的Python程序段如下:
s = input()　　# 输入括号序列,序列中仅包含“(”和“)”两种字符
top = －1; ans = 0
for i in range(len(s)):
　　if s[i] == "(":
　　　　top ＋= 1
　　else:
　　　　if 　(1)　:
　　　　　　top ＋= 1
　　　　　　ans ＋= 1
　　　　else:
　　　　　　　(2)　
ans ＋= 　(3)　
上述程序段的方框处可选代码如下:
①top != －1 　②top == －1 　③top ＋= 1 　④top －= 1 　⑤top // 2 　
⑥(top ＋ 1)// 2
则方框处的代码依次是(　　)
A. ①③⑥ B. ①④⑤
C. ②④⑤ D. ②④⑥
【解析】 本题考查栈及Python综合知识。观察程序段可知,程序遇到左括号的时候top＋1,为了匹配top会－1,而ans是最少修改的次数。该程序算法思想为:若遇到左括号top会累加,否则是遇到右括号执行else部分,else部分中若top=－1,则说明是第一次遍历遇到了右括号,为了匹配得先改成左括号,所以ans会加1,故(1)处答案为②top ==－1;否则说明有多个左括号,现在遇到了右括号为了匹配则会使top－1,故(2)处答案为④top －=1;(3)处用极值法思考会更快,由于是偶数长度,而为了使左括号出现的顺序及个数与右括号保持一致,若top=－1说明刚好匹配,故⑥(top ＋ 1)//2=0。D正确。
D
3. 元素1、2、3、4、5依次入栈,假设出栈序列为X、3、Y、Z、4。下列关于X、Y、Z的叙述,正确的是(　　)
A. X不可能为1 B. Y不可能为2
C. Z不可能为5 D. X或Y的值比Z小
【解析】 本题考查栈的操作相关知识。根据入栈和出栈顺序,当1入栈,1出栈的时候符合X是第一个出栈的,A错误。当1入栈,X=1出栈,2入栈－3入栈－3出栈,Y=2出栈,4入栈－5入栈,Z=5出栈,4出栈符合题目要求,故Y的值可能为2,B错误。1入栈－2入栈－X=2出栈－3出栈;接着Y=1出栈－4入栈－5入栈,才能Z=5出栈,最后4出栈也符合题目出入栈要求,C错误。
D
4. 有一个入栈序列为e1,e2,e3,e4,下列选项中,可能的出栈序列是(　　)
A. e2,e4,e3,e1 B. e3,e1,e4,e2
C. e3,e4,e1,e2 D. e4,e3,e1,e2
【解析】 本题考查栈知识。B中e3先出栈,下面还有e2,e1不能紧跟着出栈,错误。C、D同理,错误。e1、e2依次入栈,e2首先出栈,e3、e4再依次入栈,然后e4、e3、e1依次出栈,所以出栈序列为:e2,e4,e3,e1,A正确。
A
5. 用一个带盖的玻璃筒来放取乒乓球,放、取只能在带盖的一端进行(另一端为封闭状态),且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4,则取出球的编号序列不. 可. 能. 是(　　)
A. 1、2、3、4 B. 2、3、4、1
C. 4、2、3、1 D. 3、2、1、4
【解析】 本题考查栈知识。题目描述的乒乓球进出过程,符合栈的特点。根据栈的后进先出的特点可知,不可能的出球编号序列是:4、2、3、1,C正确。
C
6. 下列关于数据结构的说法,正确的是(　　)
A. 队列和栈都是操作受限的线性表
B. 链表必定有1个头指针和1个尾指针
C. 字符串中不能存储空格字符
D. 数组元素的数据类型可以不一致
【解析】 本题考查数据结构相关知识。链表一定有头指针,尾指针不是必需的,B错误。空格字符和其他字符没什么区别,字符串中可以存储,C错误。根据数组的定义,数组中的元素类型必须一致,D错误。
A
7. 某栈的入栈顺序为“abc”,出栈顺序为“bca”,则经过的操作为(　　)
A. 入栈、出栈、入栈、出栈、入栈、出栈
B. 入栈、入栈、出栈、入栈、出栈、出栈
C. 入栈、入栈、入栈、出栈、出栈、出栈
D. 入栈、出栈、入栈、入栈、出栈、出栈
【解析】 根据栈“先进后出、后进先出”的特点可以模拟:a入栈、b入栈、b出栈、c入栈、c出栈、a出栈,B正确。
B
8. 对栈进行操作时,若进栈的元素顺序是“A、B、C、D”,则出栈的顺序不. 可. 能. 是
(　　)
A. “A、B、C、D” B. “D、C、B、A”
C. “D、C、A、B” D. “C、D、B、A”
【解析】 出栈的规则是“先进后出”或“后进先出”。根据此特点可知,“D、C、A、B”的出栈顺序是不可能的,C符合题意。
C
9. 用Python列表自带的函数和方法来模拟栈,代码如下:
import random
a=[1,2,3,4,5]
stack=[a[0]]
i=1
res=[]
while i　　if random.randint(0,1)==0 or len(stack)==0:
　　　　stack.append(a[i])
　　else:
　　　　res.append(stack.pop())
　　　　i－=1
　　i＋=1
while len(stack)>0:
　　res.append(stack.pop())
print(res)
执行该程序段后,结果不. 可. 能. 为(　　)
A. [1, 2, 3, 4, 5] B. [2, 1, 4, 3, 5]
C. [1, 5, 4, 3, 2] D. [1, 4, 2, 3, 5]
【解析】 栈遵循“先进后出”的规则,1先入栈,然后出栈,接着2,3,4入栈,4出栈,此时栈顶元素为3,不可能2先出栈,D符合题意。
D
关键能力练
10. 地面上有标号为 A、B、C的3根细柱,在A柱上放有 10个直径相同且中间有孔的圆
盘,从上到下依次编号为 1,2,3,…,将 A柱上的部分圆盘经过B柱移入 C柱,也可以在 B柱上暂存。如果 B柱上的操作记录如下:“进,进,出,进,进,出,出,进,进,出,进,出,出”,
那么在 C柱上,从下到上的盘子的编号为(　　)
A. 2 4 3 6 7 5 B. 2 4 1 2 5 7
C. 2 4 3 1 7 6 D. 2 4 3 6 5 7
【解析】 本题考查栈的知识。“进进”表示将A柱上的1、2先后移入B柱上,2在1的上面,接着“出”表示将B柱上的2移入C柱上;同理下一组“进进”,此时B柱从上到下依次是4、3、1,“出出”表示将B柱上的4、3移入C柱上,此时C柱从上到下依次是3、4、2;下一组“进进出”后,C柱从上到下依次是6、3、4、2;最后一组“进出出”后,C柱从上到下依次是5、7、6、3、4、2,即2 4 3 6 7 5,A正确。
A
11. 利用栈的“先进后出”的特点可以实现数的进制转换。有如下Python程序段,实现的是十进制数转换为十六进制数的功能,运行界面如图所示。
请输入十进制整数:466
其十六进制数为:1 D 2
请回答下列问题:
(1)十进制数55,其十六进制数为__________。
37
(2)请在画线处填入合适的代码。
s=[""]*100
top=－1
n=int(input("请输入十进制整数: "))
while n>0:
　　top＋=1
　　r=n%16
　　if r>9:
　　　　①______________________
　　else:　　
　　　　s[top]=r
　　②__________
print("其十六进制数为:",end=" ")
while ③__________:
　　print(s[top],end=" ")
　　top－=1
s[top]=chr(r＋55)
n=n//16
top >－1
【解析】 本题考查栈的应用。利用除16取余倒排法解题。(1)十进制数55,其十六进制数为37。(2)①top是栈顶,该处功能是实现将取得的余数进栈操作。若余数大于9,则应该将其转换为相应的A~F的大写英文字符,利用数字和ASCII码的规律可知,10加上55,对应字符恰好为英文字符“A”。因此答案是chr(r＋55)。②每次取余后,n都要被16整除,因此更新n的值为新值,直到n=0为止。③将所有得到的余数出栈,top指针每次减1,直到top=－1结束,此时所有数据出栈完毕。
12. 在数学算式“(9÷(5－2)＋3)* 6”中,位置1和位置4有左括号“(”,位置8和位置11有右括号“)”。 位置1的左括号与位置11的右括号相匹配,位置4的左括号与位置8的右括号相匹配。而对于数学算式“a(b－c))”,位置8的右括号没有可匹配的左括号。设计一个程序,判断输入的数学算式中的括号(只有小括号)是否匹配。实现上述功能的Python代码如下,运行界面如图所示。请在画线处填入合适的代码。
请输入数学算式:(9÷(5－2)＋3)*6
括号匹配
st=[""]*100
top=①__________
flag=True
s=input("请输入数学算式: ")
for i in range(len(s)):
　　if s[i]=="(":
　　　　top=top＋1
　　　　②________________
　　elif s[i]== ")":
　　　　if top==－1:
　　　　　　flag=False
　　　　　　break
　　　　else:
　　　　　　③________________
if top>=0:
　　flag=False
if flag:
　　print("括号匹配")
else:
　　print("括号不匹配")
－1
st[top]=s[i]
top=top－1
【解析】 本题考查栈的应用知识。①栈顶的初值一般初始化为－1。②本题的意图是利用栈来实现对括号的配对检查,当出现一个左括号时将其压栈处理,若检测到右括号时进行出栈处理。③若检查到最后来到top=－1,则表明左右括号匹配,否则不匹配。
13. 例如,“CBAABC”称为回文字符串,而“ABC”则不是回文字符串。可以利用栈来检查是否为回文字符串,小王利用Python编写如下程序实现上述功能,运行界面如图所示。请在画线处填入合适的代码。
请输入字符串:12321
字符串:12321 是回文字符串
st=[""]*100
top=－1
①_____________
s=input("请输入字符串:")
k=len(s)//2
for i in range(k):
　　top＋=1
　　st[top]=s[i]
if ②______________:
　　k=k＋1
for i in range(k,len(s)):
　　ch=st[top]
　　top－=1
　　if ③__________:
　　　　　flag=False;break;
if flag:
　　　print("字符串:",s,"是回文字符串")
else:
　　　print("字符串:",s,"不是回文字符串")
flag=True
len(s)%2==1
ch!=s[i]
【解析】 本题考查利用Python的栈实现检查回文字符串的目的。①从代码看,此处需要实现变量flag的初始化,且其值为True。②k值是字符串长度的一半,若字符串长度为奇数,则k值加1,从而避免将奇数字符的最中间的字符进行比较。③利用栈的功能将前一半的字符按顺序入栈,然后将后一半的字符串和出栈后的字符进行逐个比较,只要有一个字符不同就说明不是回文串。最后检查完毕后,若flag依然是True,则表明是回文串。
14. 自从学习了不同进制之后,小明设计了一个计算不同进制数的加法器,并用Python编程实现。输入一个加法算式,加数可以是十进制数、二进制数或者十六进制数,程序的功能是输出它们的和。例如,输入形如“1010B＋1DH＋109D=”的加法算式后,执行程序输出“和是148”的结果。实现上述功能的Python程序如下:
s=input( 输入一个混合进制的加法算式: )
dic={ B :2, D :10, H :16}
st=[ ]*100
top, i, x, m=－1, 0, 0, 0
while i　　if s[i]== ＋ or s[i]== = :
　　　　m=①_______________
　　　　top=top－1
　　　　t=0
　　　　while top!=－1:
　　　　　　if st[top]>= A and st[top]<= F :
　　　　　　　　st[top]=ord(st[top])－ord( A )＋10
dic[st[top]]
　　else:
　　　　　　　　st[top]=int(st[top])
　　　　　　②____________________
　　　　　　t=t＋1
　　　　　　top=top－1
　　else:
　　　　③_______________
　　　　st[top]=s[i]
　　i=i＋1
print( 和是 ,x)
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)若输入“1011B＋2DH＋178D”,输出的结果是__________。
　　　　
x=x＋st[top]*m**t
top=top＋1
和是68
【解析】 本题考查栈的应用。根据代码可知，st列表中保存着当前加数的每一位。如对于式子“1010B＋1DH＋109D=”,当读到第一个加号时,st列表的值为["1","0","1","0","B"],读到第二加号时,st的值是 ["1","D","H"],读到最后‘=’号时,st的值是["1", "0","9","D"]。(1)①st列表的最后一位是进制编号,读取st最后一位,通过字典dic得到进制值。②使用权值法把st列表中保存的进制数转化为十进制数。③读取到加数的每一位数字,都保存在st列表中的相应位置。(2)由于式子中的最后一位不是‘＋’或者‘=’,所以st列表中的最后一个数字没有加上,故和是68。
15. 为便于计算表达式的值,波兰数学家提出了将运算符置于运算对象之后的表示方法,即不需要考虑运算符的优先级。下面的Python程序段实现了对逆波兰式的计算(假定逆波兰式中的运算对象均为一位正整数,且运算只有加减乘除),当输入“682－2*3/＋”时,输出“10”。请在画线处填入合适的代码。
st=[0]*100;top=－1
s=input("请输入逆波兰式:")
i=0
while i　　if "0" <= s[i] <= "9":　#数字字符
　　　　top＋=1
　　　　st[top]= ①______________________________
　　else:
　　　　x=st[top];top－=1
　　　　y=st[top];top－=1
　　　　if s[i]=="＋":　　　#加法运算　　
　　　　　　top＋=1;st[top]=x＋y
　　　　elif s[i]=="－":　　#减法运算　　
　　　　　　top＋=1; ②_______________
　　　　elif s[i]=="*":　　#乘法运算　　
　　　　　　top＋=1;st[top]=x*y
　　　　else:　　　　　　　#除法运算　　
　　　　　　top＋=1;st[top]=int(y/x)
　　i=i＋1
print(③__________)　　#输出最后的运算结果
int(s[i])或 ord(s[i])－48
st[top]=y－x
st[top]
【解析】 本题算法利用栈实现对逆波兰式的计算。当遇到运算对象时进行进栈操作,遇到运算符时从栈中取出两个运算对象,运算结果再入栈,重复此操作,直到逆波兰式结束,最后输出栈顶元素。 ①此处要将对应的数字字符表达的数值进行入栈操作。②此处将减法运算的结果进行入栈操作,由于y是被减数,x是减数,运算结果为y－x。③此处最后输出栈顶元素st[top]。

展开更多......

收起↑