资源简介

专题三　检测卷
一、选择题(本大题共12小题,每小题2分,共24分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)
1.下列有关字符串的描述,正确的是(　　)
A.字符串的负索引从字符串的末端开始编号,第一个位置为-1
B.字符串的长度是指字符串中所包含的字符个数,但不包括空格
C.字符串的元素个数是有限的,只能由1个或多个字符组成
D.字符串的正索引的第一个位置为1
2.下列对队列的描述,正确的是(　　)
A.队列的特点是先进后出
B.在队列中,允许插入的一端称为队首,允许删除的一端称为队尾
C.刚建立的队列,队首指针和队尾指针均为0
D.出队操作时,先将队首指针加1,然后再将队首元素出队
3.下列对栈的描述,正确的是(　　)
A.栈的特点是后进后出
B.栈仅允许在表的一端进行插入或删除操作
C.入栈操作时,将把数据元素压入栈底
D.出栈操作时,先将栈顶指针加1,然后将栈顶元素取出
4.18位二代身份证号的编码规则为“六位地址码+八位出生日期+三位数字顺序码和一位数字校验码”,如330425198002160052,下列选项中,能正确从身份证号中获取出生日期信息的是(　　)
A.s[7:14] B.s[7:15]
C.s[6:13] D.s[6:14]
5.为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要打印的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据打印。该缓冲区的逻辑结构是(　　)
A.树 B.队列 C.图 D.栈
6.小王在使用队列解决问题的过程中,初始时,队列为空,队列的首指针和尾指针分别为head、tail,接着小王开始进行了一系列的操作,操作序列为:入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队,则操作结束时head和tail的值分别为(　　)
A.4　7 B.4　8
C.5　7 D.5　8
7.栈S从栈底到栈顶的元素依次为2,4,队列Q从队首到队尾的元素依次为1,3。约定:A操作是取出栈顶元素x和队首元素y,将x和y相加后入队;M操作是取出栈顶元素x和队首元素y,将x和y相乘后入栈。则经过MAM系列操作后,栈顶元素为(　　)　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　
A.14 B.20 C.26 D.28
8.某浏览器的“后退”功能按钮用类似栈的数据结构实现(假设栈容量为 3):每打开新网站就会将上次的浏览记录压入“栈”中;栈满时,再新增浏览记录,则从“栈”底删除较早的记录;点击“后退”按钮时则从“栈”顶中弹出最近浏览的记录。若用一位数字表示每次打开的网站,用大写字母“B”表示点击“后退”按钮,如“1,2,B,3”操作后“栈”顶的网页是“1”。那么经过“1,2,3,4,B,5,6,B,B,B”操作后,当前浏览的网页是(　　)
A.2 B.3 C.5 D.1
9.元素x1、x2、x3、x4、x5、x6依次入栈,若第1个出栈的元素是x4,则不可能是第3个出栈的元素是(　　)
A.x1 B.x2
C.x3 D.x5
10.某诊所叫号系统中,利用队列来储存当前正在排队病人的编号,head指向队首元素,tail指向队尾元素的下一个位置。若当前没有病人,则head与tail的关系是(　　)
A.head!=tail B.head>tail
C.head==tail D.head11.在程序运行过程中,函数调用会按照“栈”的机制入栈和出栈。假设有一个程序依次调用了以下函数(入栈):main → Config → Network → Service → Status。在执行过程中,函数按照以下顺序完成并返回(出栈):Config → Service → Network → main → Status。栈容量至少是(　　)
A.2 B.3 C.4 D.5
12.下列程序的功能是在一个循环队列中进行入队操作,输入“+n”表示入队操作,入队元素为n,输入“-”表示出队操作,输入“@”时表示操作结束,部分程序如下:
m=int(input('please input m:')) #输入队列的规模m
que=['']*m
head=tail=0
data=input('please input data:')
while data!='@':
　　if data[0]=="+":
　　　que[tail]=data[1:]
　　　　　　
则程序中划线处应填入的代码为(　　)
A.head+=1 B.tail+=1
C.tail=(tail+1)%m D.tail=tail%m+1
二、非选择题(本大题共4小题,其中第13小题6分,第14小题4分,第15小题8分,第16小题8分,共26分)
13.回文子串。输入一个字符串,输出所有长度至少为2的回文子串,并统计回文子串的个数。说明:两个不同位置的相同回文子串,统计时算两个。程序运行界面如下图所示:
请输入字符串:121ababa
121
aba
bab
aba
ababa
字符串中共有回文子串数为··5
s=input('请输入字符串:')
n=len(s)
cnt=0
for i in range(2,n+1):　# i为子串长度
　　for j in range(　　　①　　　):
　　　substr=s[j:j+i]
　　　if　　　　②　　　　:　# 判断回文
　　　　　print(substr)
　　　　　　　　　③　　　
print('字符串中共有回文子串数为:',cnt)
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　。(2分)
14.进制转换。用数组模拟栈操作的Python程序段如下:输入一个十进制数整数,将十进制数转化为八进制数。程序运行界面如下:
请输入整数:100
100转换为八进制数为··144
实现上述功能的程序如下,请在划线处填入合适的代码。
s=[-1]*100
top=-1
x=int(input('请输入整数:'))
n=x
while x>0:
　　r=x%8
　　　　　　①　　　
　　s[top]=r
　　x=x∥8
print(n,'转换为八进制数为:',end='')
while top>=0:
　　print(s[top],end="")
　　　　　　②　　　　
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　。(2分)
15.在雪地里有n个小朋友滚了n个小雪球,小明决定把所有的小雪球滚成一个大雪球,每次可以把任意两个小雪球滚到一起,消耗的体力等于这两个雪球的质量之和,n个雪球经过n-1次滚合之后,最终变成了一个大雪球。小明在滚合雪球时消耗的总体力等于每次滚合所耗体力之和。现需要设计出滚合的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值。
　　例如有5个雪球,质量依次为1,2,3,4,5,可以先将质量为1,2的两个雪球滚合,新雪球的质量为3,耗费体力3,一次滚合之后,五个雪球变成了四个,数目依次为3,3,4,5,接下来将质量为3,3的两个雪球滚合,耗费体力6,再将质量为4,5的两个雪球滚合,耗费体力9,最后将质量为6,9的两个雪球滚合,耗费体力15,小明耗费的总体力为3+6+9+15,即33。请回答下列问题。
(1)现有6个小雪球,它们的质量依次为1,3,5,7,2,6,则滚成一个大雪球所耗费的总体力为　　　　。
(2分)
(2)定义如下sort(lst)函数,参数lst存储了每个雪球的质量。函数的功能是对lst中的元素进行升序
排序。
def sort(lst):
for i in range(1,n):
for j in range(0,n-i):
if lst[j]>lst[j+1]:
lst[j],lst[j+1]=lst[j+1],lst[j]
　　return lst
调用函数,若lst为[4,8,3,9,2,7],则加框处的语句执行的次数为　　　　。(2分)
(3)主程序如下,请在程序划线处填入合适的代码。
#读入所有雪球的质量,并存入列表a中,代码略
n=len(a)
sort(a)
w=0
headA=0
headB=tailB=0
while headAt=0
for i in range(2):
　　　 if headAif headBif a[headA]t+=a[headA]
headA+=1
else:
t+=a[headB]
headB+=1
　　　　　else:
t+=a[headA]
headA+=1
　　　 else:
　　　　　t+=a[headB]
　　　　　headB+=1
　　w+=t
　　　　　　②　　　
　　tailB+=1
print("耗费的总体力为:",w)
程序划线①处应填入的代码为:　;(2分)
程序划线②处应填入的代码为:　。(2分)
16.计算由“*”围成的图形的面积。计算由“*”、“.”组成的n*n(n≤100)图形的面积,面积的计算方法是统计“*”所围成的闭合曲线中“.”的数目。如图a所示,在10*10的二维数组中,“*”围住了15个“.”,因此面积为15。
解决此问题的算法思想:先统计出图中“*”的个数;然后从左上角的字符开始,分别从上下左右四个方向进行遍历出由“.”组成的字符,并依次入队,直到搜索完毕;图形的面积为:图形的总面积减去“*”的字符数,再减去进队列的元素个数。
特殊情况处理:当无法搜索到除左上角外的其余三个角上的“.”时,则先在整个图形外面围一圈“.”来
处理。
实现上述功能的Python程序如下,请回答下列问题。
#图形字符从文本文件中读取
file=open("area.txt","r")
flines=file.readlines()
n=0
a=[["." for i in range(100)]for j in range(100)]
for line in flines:
　s=list(line.strip("\n"))
　print(s)
　for j in range(len(s)):
　　if s[j]=="*" or s[j]==".":
　　　　　a[n][j]=s[j]
　　n+=1
sumx=0
d=[[-1,0,1,0],[0,1,0,-1]]　#上右下左四个方向的x、y坐标的增量
for i in range(1,n+1):
　　for j in range(1,n+1):
　　if a[i][j]=="*":
　　　　sumx+=1
x=y=0
head=tail=0
que=[[0 for i in range(1000)]for j in range(2)]
tail=tail+1
que[0][tail]=x
que[1][tail]=y
a[0][0]="∕"　#将已访问的元素的值修改为“/ ”,防止重复访问
while 　　　　①　　　　:
　　for f in range(0,4):
　　　x=que[0][head]+d[0][f]
　　　　　　　②　　　
　　　if n+1>=x>=0 and n+1>=y>=0:
　　　　　if a[x][y]==".":
　　　　　　　tail+=1
　　　　　　　a[x][y]="∕"
　　　　　　　que[0][tail]=x
　　　　　　　que[1][tail]=y
　head=head+1
print('area=',　　　　③　　　　)
(1)如图b所示,由“*”围成的图形的面积为　　　　　　　　　　。(2分)
(2)请在划线处填入合适的代码:
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　。(2分)
专题三　检测卷
一、选择题
1.A　
2.C　解析:队列的特点是先进先出,因此A选项错误;允许插入的一端称为队尾,允许删除的一端称为队首,因此B选项错误;出队操作时,先将队首元素出队,然后将队首指针加1,因此D选项错误;刚建立的队列,队首指针和队尾指针均指向下标为0的元素,即队首指针和队尾指针均为0,因此答案为C。
3.B　
4.D　解析:身份证号中第7~14位表示出生日期,在字符串中的索引值为6~13,字符串切片操作时,只能取到终点位置的前一个,因此要获取出生日期信息的正确表示为s[6··14],故答案为D。
5.B　解析:要打印的数据是按照先进先出的原则存储在缓冲区中的,因此该缓冲区的逻辑结构是队列,故答案为B。
6.A　解析:初始时,队列为空,队首指针head和队尾指针tail的值均为0,队列不为空时,队首指针指向队首元素,队尾指针指向队尾元素的下一个位置,本题中共进行了7次入队操作和4次出队操作,因此最终head和tail的值分别为4、7,因此答案为A。
7.A　解析:本题主要考查栈、队列思想的相关知识。根据栈和队列的思想,结合题目的要求经过M操作时,x=4,y=1,x*y=4 重新入栈;再进行A操作时,x=4,y=3,x+y=7 重新入队;最后进行 M 操作时,x=2,y=7,x*y=14 重新入栈。所以栈顶元素是14,因此答案为A。
8.A　解析:本题主要考查栈的特点与应用。按题意模拟:1,2,3,4 操作后,当前浏览网页是4,栈顶元素是3,因此B操作会把网页3弹出并浏览。操作5,6过后,当前浏览网页是6,栈顶元素是5。后面的三次B操作依次弹出浏览的是5,3,2,因此答案为A。
9.A　解析:由于第1个出栈的元素是x4,此时,栈中从栈顶到栈底的元素分别为x3、x2、x1,因此元素x1最早为第4个出栈,故答案为A。
10.C　解析:head、tail分别是队首和队尾指针,当队列为空时,指针head和tail指向同一个位置,因此答案为C。
11.B　解析:本题主要考查的是栈操作。栈的特点是先进后出,模拟入栈和出栈过程:入栈顺序为main→Config→Network→Service→Status;出栈顺序为Config→Service→Network→main→Status。在模拟过程中,栈的最大深度出现在[main,Network,Service]时,深度为3,因此B选项正确,故答案为B。
12.C　解析:循环队列中的tail指针、head指针每次移动时,都对队列元素的个数取模运算,“+”表示进行入队操作,因此划线处代码为tail=(tail+1)%m,故答案为C。
二、非选择题
13.①n-i+1或0,n-i+1或0,n-i+1,1　②substr == substr[····-1]　③cnt=cnt+1
解析:本题主要考查的是字符串的综合应用。本题采用枚举算法,枚举长度为2至n的所有子串,然后再对子串进行回文判断。i表示子串长度,j表示取长度为i的子串时的起始位置,字符串总长度为n,因此j=n-i+1,故①处的代码为n-i+1 或0,n-i+1或0,n-i+1,1;substr表示取出的子串,回文子串的判断方法为:若子串substr进行反转操作后与原子串相同,则为回文串,否则不是回文串。将子串substr进行反转操作的代码为substr[····-1],因此②处代码为substr == substr[····-1];程序③处代码的功能为统计回文子串的个数,根据下面的print语句,可知回文子串的个数存储在变量cnt中,因此③处代码为cnt=cnt+1。
14.①top=top+1　②top=top-1
解析:本题主要考查的是栈的应用。将十进制数转换为八进制数时,每次将除8的余数存放在栈s中,最后将栈中的元素输出就是十进制数对应的八进制数。入栈操作时,先将栈顶指针加1,然后将元素压入栈中,因此程序①处代码为top=top+1;而出栈时,先将栈顶元素出栈,然后将栈顶指针减1,因此程序②处代码为top=top-1。
15.(1)57　(2)8　(3)①headB+1解析:(1)滚成一个大雪球所耗费的总体力为(1+2)+(3+3)+(5+6)+(6+7)+(11+13)=57,故答案为57。
(2)本题主要考查的是冒泡排序。将lst列表中的数据进行升序排序,数据交换次数为8次,故答案为8。
(3)本题主要考查的是队列的综合应用。本题的算法思想是:本题应用双队列的思想(2个队列均保存在a列表中,headA,headB分别指向队列A和队列B),队列A和队列B中的数据都保持升序,每次挑选两个最小数据进行合并,合并后的值加入队列B中,当队列A的数据中无数据,且B队列中只有一个数据时,算法结束。因此①处代码为headB+116.(1) 12　(2)①start<=tail　②y=que[1][head]+d[1][f]　③(n+2)*(n+2)-sumx-tail
解析:本题主要考查的是队列的综合应用。(1)由*围成的“.”共有12个,因此面积为12。(2)遍历图中所有连通的“.”字符,并依次进队,并模拟出队,head为队首指针,tail为队尾指针,直到队列为空,遍历结束,因此①处代码为start<=tail;②处代码的功能是计算遍历到的节点的y坐标,因此②处代码为y=que[1][head]+d[1][f];③处的功能是计算面积,由于图形外面先围了一圈“.”,因此面积为(n+2)*(n+2)-sumx-tail。

展开更多......

收起↑