资源简介

专题二　检测卷
一、选择题(本大题共12小题,每小题2分,共24分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)
1.下列有关数组的描述,错误的是(　　)
A.数组是由相同数据类型的变量组成的一个序列
B.数组中的每个元素按照下标顺序依次存储
C.二维数组中的元素在内存中的存储方式有行优先存储和列优先存储两种
D.在数组中进行插入、删除操作时无需移动数据元素
2.下列有关链表的描述,错误的是(　　)
A.链表是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构
B.链表中的头指针是链表的入口,只有通过头指针才能进入链表
C.同一个链表中的每个节点的结构可以不同
D.链表占用的空间不固定,可以根据需要增加或减少节点
3.在Python中,若需将100位学生的姓名分别存储在数组元素name[0]～name[99]中,则下列创建方法正确的是(　　)
A.name[0:99]="" B.name[100]=""
C.name=[0 for i in range(100)] D.name=[""]*100
4.使用如下Python语句来定义数组b:
b=[i*2 for i in range(10)]
则执行语句print(b[5]),输出的结果是(　　)
A.0 B.8 C.10 D.12
5.使用如下Python语句来定义二维数组a:
a=[[i*i for i in range(3)]for j in range(5)]
则该二维数组的行数和列数分别为(　　)
A.3　5 B.5　3 C.4　6 D.6　4
6.有如下Python程序段:
s=input("请输入字符串:")
n=len(s)
i,j=0,n-1
result=""
while i=n∥2:
if s[i]>s[j]:
result+=s[i];j-=1
elif s[i]result+=s[j];i+=1
else:
i+=1;j-=1
print(result)
执行该程序段,分别输入下列选项中的字符串,输出结果不为555的是(　　)
A.51234 B.12535 C.54321 D.55123
7.设a是一个8×10的二维数组(8行10列),若按列优先的顺序存储数组元素,则数组元素a[5][5]前面共有元素的个数为(　　)
A.45 B.46 C.53 D.55
8.数组元素a[0]～a[n-1]已按升序排列,现要将a[pos](0≤pos≤n-1)的值减2,并保持数组的有序性不变。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
t=a[pos]-2
i=pos
while　　　　　:
a[i]=a[i-1]
i -=1
a[i]=t
　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　
A.i>0 B.i>0 and tC.i>=0 and t0 and a[i]9.有一单向链表,链表结构如下图所示:
现要在尾指针p所指节点之后插入新节点r(r指针所指节点),则应进行的操作为(　　)
A.p.next=r B.r.next=p
C.p.next=r;r.next=null D.r.next=p;r.next=null
10.有一单向链表,每个节点由数据域data和指针域next组成,链表结构如下图所示:
现要删除头节点后面的一个节点(数据域为data2的节点),则应进行的操作是(　　)
A.head=head.next B.head.next=data3
C.head=head.next.next D.head.next=head.next.next
11.有如下Python程序段:
a=[3,2,4,1,3,2,5,3]
n=len(a)
last=[-1]*n
cur=[-1]*n
for i in range(n):
last[i]=cur[a[i]]
cur[a[i]]=i
i=0;j=0;ans=0
while jwhile jj+=1
if j-i>ans:
ans=j-i
i+=1
print(ans)
执行该程序段,最后输出的结果是(　　)
　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　
A.3 B.4 C.5 D.6
12.有如下Python程序,其功能为删除无序链表(元素个数大于等于2)中的重复元素。
def dele(a,head):
pre=head
p=a[head][1]
while p!=-1:
q=head
flag=False
while 　　　　①　　　　:
if a[q][0]==a[p][0]:
　　　　②　　　
p=a[p][1]
flag=True
break
q=a[q][1]
　　　　if not flag:
pre=p
p=a[p][1]
a=[[0,3],[1,2],[1,4],[0,1],[0,5],[2,-1]]
dele(a,0)
可选语句有:
①q!=-1　　②q!=p　　③a[pre][1]=a[p][1]　　④a[pre][1]=a[q][1]
则划线①②处应填入的正确代码依次为(　　)
A.②④ B.②③ C.①④ D.①③
二、非选择题(本大题共3小题,其中第13小题6分,第14小题9分,第15小题11分,共26分)
13.下列程序的功能是将两个存放升序数据的数组合并为一个新数组,要求新数组中的数据仍保持
有序。
实现上述功能的程序如下,请在程序划线处填入合适的代码。
#输入一个升序数据序列,并存储在数组a中,代码略
#输入一个升序数据序列,并存储在数组b中,代码略
n1=len(a)
n2=len(b)
c=[0]*(n1+n2)　#存放合并后的数据
k=i=j=0
while　　　　　①　　　　　　:　#a、b数组均有数据时
　if a[i]<=b[j]:
　　　　　　　②　　　
　　　i+=1
　　　k+=1
　else:
　　　　c[k]=b[j]
　　　　j+=1
　　　　k+=1
while i　c[k]=a[i]
　i+=1
　k+=1
while j　　　　　③　　　
　j+=1
　k+=1
print('合并后数组c中的元素为:',c)
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　;(2分)
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　。(2分)
14.某工厂生产的产品包含n个(编号为0～n-1)组件,其组装可由多名工人共同协作完成。组装时每个组件都不可遗漏并能按序完成,有些组件存在前置组件(以下简称“前置”),即安装有先后顺序。例如,某产品有6个组件,如图a所示,组件3的前置是组件1和组件2,即安装组件3需要在组件1和组件2完成之后。若 0～5号组件的组装所需单位时间分别为2,5,2,4,3,5,则在工人数量不限的情况下,所有组件安装完成最短需要14个单位时间。
　　为了梳理产品组件的组装顺序,并计算所有组件安装完成所需的最短时间,编写程序模拟组装过程:先同时组装前置总数为0的组件,完成后更新每个组件的前置总数,再重复以上步骤,直至所有组件安装完毕,程序运行结果如图b所示,请回答下列问题:
(1)图a所示产品的1号组件组装时间若缩短为3个单位时间,其他组件组装时间保持不变,则所有组件安装完成所需最短时间为　　　　　　　个单位时间。 (1分)
(2)定义如下cal(a,n)函数,参数a列表的每个元素包含两项,a[i][1]是组件编号,a[i][0]是a[i][1]的前置编号,例如a中某个元素值为[2,3],表示组件2是组件3的前置。该函数的返回值是列表s和列表pre,其中s记录所有组件的相互关系,pre[i]记录初始情况下组件i的前置总数。
def cal(a,n):
pre=[0]*n
s=[[0 for i in range(n)]for j in range(n)] #创建n×n的二维数组s,元素初始值
为0
for i in range(len(a)):
x,y=a[i][0],a[i][1]
s[x][y]=1
pre[y]=　　　　　　　　　　　　(2分)
return pre,s
(3)定义如下proc(n,s,pre)函数,该函数的返回值是列表v,v[i]代表从开始到组件i完成组装所需的最短时间。请在划线处填入合适的代码。
def proc(n,s,pre):
head=tail=0
que=[0]*n
for i in range (n):
if pre[i]==0:
que[tail]=i
tail+=1
while headx=que[head]
head+=1
for i in range(n):
if s[x][i]==1:
pre[i]-=1
if pre[i]==0:
que[tail]=i
tail+=1
v[i]=max(v[i],　　①　　)
　　return v

组装编号0～n-1的单个组件所需时间存入t列表,组件前置关系存入a列表,如图a,所需时间
t=[2,5,2,4,3,5]
a=[[0,2],[2,3],[1,3],[3,5],[4,5]]

n=len(t)
print("编号为0～"+str (n-1)+"的组件组装所需单位时间分别为:",t)
v=t[:]
pre,s=ca1(a,n)
v=proc(n,s,pre)
data=[0]*n
result=[i for i in range(n)]　#创建列表result=[0,1,2,…,n-1]
for i in range(n):
data[i]=v[i]-t[i]　#data[i]表示组件i开始安装时间
for i in range(n-1):#按组件开始安装时间升序排序,开始安装时间相同时按组件序号升序
for j in range(n-1-i):
if data[result[j]]>data[result[j+1]]:
　　　　②　　　
print("组件组装顺序:",result,",安装完成所需最短时间:",max(v))
程序划线①处应填入的代码为:　;(2分)
程序划线②处应填入的代码为:　。(2分)
(4)以下选项与第(3)题加框处代码功能相同的是　　　　(多选,填字母)。(2分)(注:全部选对的得2分,选对但不全的得1分,不选或有选错的得0分)
A.head!=tail B.headC.tail<=n D.len(que)>0
15.某公司有一个会议室,为了避免使用冲突,公司收集各部门提交的预约申请(可以申请在第1天至第m天使用),每一条预约申请包含序号(按照申请时间从1开始依次编号)、重要度、最早使用时间、最晚使用时间、连续使用天数等5个数据项。如某预约申请为[1,5,3,6,2],表示其序号为 1,重要度为 5,可以在第3天至第6天中安排任意2天连续使用会议室。按如下规则安排会议室的使用:优先安排重要度大的预约申请;若重要度相同,按照序号从小到大依次安排;若申请的时间段内存在多个符合条件的区间,则从最早的时间开始安排;若在申请的时间段内无法满足,则输出预约失败的申请信息。
　　例如当m为9 时,有五个预约申请如图a所示,按上述规则安排会议室,除预约四外,其余均可满足,安排结果如图b所示。
图a
第1天 第2天 第3天 第4天 第5天 第6天 第7天 第8天 第9天
预约二 预约一 预约五 预约三
图b
　　编写程序:读取各部门预约申请,按照上述规则安排会议室,分别输出预约成功的会议室使用时间段、预约失败的申请信息。
(1)若将图 a 中预约四的重要度调整为 5,则预约三的安排时间从第　　 　　天开始。(1分)
(2)定义如下order_sort(order) 函数,order 列表的每个元素数据项依次为序号、重要度、最早使用时间、最晚使用时间、连续使用天数,列表已按序号升序排列。函数功能是将预约申请按照重要度降序排列,并返回order。
def order_sort(order):
i=1
n=len(order)
while i　 k=0
for j in range(n-i):
if order[j][1]order[j],order[j+1]=order[j+1],order[j]
k=j
i=n-k
　　return order
若order列表中的order[0][1],order[1][1],order[2][1],…,order[6][1]的值依次为:9,8,3,2,6,5,1。
请回答下列问题:
①调用函数 order_sort(order)后,加框处语句的执行次数为　　　　　　。(2分)
②若将加框处语句k=0 修改为k=n-1,则对函数返回结果　　　　(单选,填字母:A.有影响/ B.无影响)。(2分)
(3)实现会议室安排的 Python 程序如下,程序运行结果示例如图c所示,请在划线处填入合适的代码。
序号2:使用从2～2天 序号1:使用从3～4天 序号3:使用从6～8天 序号5:使用从5～5天 序号4:预约失败
图c
def organize(order,m):
heads=[0,-1]
res=[[1,m,-1]]
for i in 　　　　①　　　　:
p=heads[0]
flag =False
while p!=-1:
if res[p][1]>=order[i][2]:
st =max(order[i][2],res[p][0])
ed=min(order[i][3],res[p][1]) #min(a,b)返回a和b中的较小值
if　　　　　②　　　　　:
　ed=st+order[i][4]-1
flag=True
break
　　　　　elif res[p][0]>order[i][3]:
break
q=p
p=res[p][2]
　　　if flag:
#输出该条预约申请的安排结果,代码略
if st==res[p][0] and ed ==res[p][1]:
if p==heads[0]:
heads[0]=res[p][2]
　 else:
　　　　　　　③　　　　　
elif st==res[p][0]:
res[p][0]=ed+1
elif ed==res[p][1]:
res[p][1]=st-1
else:
res.append([ed+1,res[p][1],res[p][2]]) #为列表res追加一个元素
res[p][1]=st-1
res[p][2]=len(res)-1
　　　else:　#记录预约失败的申请信息
order[i].append(-1)
order[i][5]=heads[1]
heads[1]=i
#输出预约失败的申请信息,代码略
读取天数m;读取预约申请信息存入order列表,每个元素包含序号、重要度、最早使用时间、最晚使用时间、连续使用天数5个数据项,已按序号升序排列,代码
order =order_sort(order)
organize(order,m)
程序划线①处应填入的代码为:　 ;(2分)
程序划线②处应填入的代码为:　 ;(2分)
程序划线③处应填入的代码为:　 。(2分)
专题二　检测卷
一、选择题
1.D　
2.C　解析:同一个链表中的每个节点的结构均相同,因此错误的是C选项,故答案为C。
3.D　4.C　
5.B　解析:本题中使用间接定义的方式来创建二维数组a,j表示二维数组的行数,i表示二维数组的列数,因此该二维数组的行数为5行,列数为3列,故答案为B。
6.B　解析:本题主要考查的是字符串。该程序段的作用是将字符串s中左半部分与右半部分按照从大到小的顺序交替排列,生成一个新的字符串result。输入s字符串为12535时,输出结果为55,因此答案为B。
7.A　解析:该二维数组是按列优先的顺序存储数据元素,该数组共8行10列,数组元素a[5][5]前面有0~4列,共5列,即有5*8=40个元素,第5列前面有0~4行的元素,因此总数为40+5=45个,故答案为A。
8.B　解析:本题主要考查的是数组及插入排序算法思想。代码需要填写的是循环判断条件,首先根据a[i]=a[i-1]的赋值关系,确定需要被比较的元素是a[i-1],已知数组已升序排序,故条件应为t0。用and连接两个条件,因此答案为B。
9.C　
10.D　解析:要删除头节点后面的一个节点(数据域为data2的节点),只需将头节点的next指针指向下一个节点的下一个节点即可,即head.next=head.next.next,因此答案为D。
11.C　解析:本题主要考查链表。
首先分析代码第一个循环,在简单模拟几个值之后,可以看出cur[k]是k值的头指针,指向 k 值在数组a中最后一次出现的位置,last 为链表指针域,last[p]指向 a[p]值上一次在数组 a 中出现的位置。整个过程就是按元素执行链表头插入。根据第一个for循环后可以得到last 和 cur数组的值last=[-1,-1,
-1,-1,0,1,-1,4],cur=[-1,3,5,7,2,6,-1,-1]。模拟执行第二段 while 循环后发现是在寻找一个最长区间(根据 if 语句判断)i为区间左边界,j 为区间右边界,j不断扩展直到遇到重复元素(即 last[j] >= i)内循环结束,接下来判断区间是否比之前的ans大,若大则更新。由此分析出程序功能为寻找a数组中无重复元素的最长子序列长度。a 数组为a=[3,2,4,1,3,2,5,3],最长无重复子序列为4,1,3,2,5。长度为5。故答案为C。
12.B　解析:本题主要考查的是链表操作。由pre=p,p=a[p][1],可知pre是p的前驱,删除是删除后继节点,因此②处是删除后继p节点,选③;从q=head,p=a[head][1],可知①处语句为q!=p,否则if a[q][0]==a[p][0]必然成立,因此①处选②,故答案为B。
二、非选择题
13.①i解析:本题主要考查的是数组的综合应用。程序①处的条件是数组a和b均有数据时,i指向a数组,j指向b数组,因此①处代码为i14.(1)13　(2)pre[y]+=1　(3)①t[i]+v[i]　②result[j],result[j+1]=result[j+1],result[j]
(4)AB
解析:本题考查数据的链式存储、队列算法实现和冒泡算法思想。
(1)根据算法描述,可以整理为0→2→3→5,1→3→5,4→5三条队列,在组件3前面有两个并行的任务链,1号组件组装时长若缩短为3个单位时间,其时间分为2+2,3,较长时间为4,组件3的时间为4,合计为8,而组件4所需时间为3,因此总共所需时间为8+5=13。
(2)函数cal统计各个组件的前置总数,组件y的前置是组件x,因此组件y的前置总数pre[y]等于自身加1。
(3)组装编号0~n-1的单个组件所需时间存入t列表,函数proc功能是计算每个组件i从开始到组件i完成组装所需的最短时间v[i],此处更新i组件的组装最短时间v[i],即取v[i]以及t[i]+v[i]中的最大值,故①处代码为t[i]+v[i]。
data[i]表示组件i开始安装时间,result存储的是从小到大排列的组件序号,当条件data[result[j]]>
data[result[j+1]]成立就交换两个索引位置。若data[result[j]]和data[result[j+1]]相等,本身也是按序号排列的,则无需交换,故②处代码为result[j],result[j+1]=result[j+1],result[j]。
(4)que队列中保存组装前置总数为0的组件,head是左端点,tail是尾节点,一共有n个组件,因此与加框处代码功能相同的是head!=tail和head15.(1) 7　(2)①3　②A　(3)①range(len(order))
②ed-st+1>=order[i][4]　③res[q][2]=res[p][2]
解析:本题主要考查算法综合应用,涉及排序、链表操作等。
(1)根据题意所得,若将图a中预约四的重要度调整为5,则根据预约重要程度排序后的结果为2,1,4,3,5,则预约三的安排时间从第7天开始,安排结果如下所示:
第1 天 第2 天 第3 天 第4 天 第5 天 第6 天 第7 天 第8 天 第9 天
预约二 预约一 预约四 预约三
(2)本题考查冒泡排序的优化,原始数据为 9,8,3,2,6,5,1,根据代码可得,第一轮排序结果为9,8,3,6,5,2,1;第二轮为9,8,6,5,3,2,1,第三轮因为数据已经有序,循环结束,所以加框处语句的执行次数为3。若将加框处的代码改为 k=n-1;当数据已经有序时,k 的值不变,循环无法结束,故选A。
(3)①处外循环主要用来遍历数组order,循环遍历i表示各个元素的索引,所以①处答案为range(len(order))。②处分析代码段可得,res链表存储依然能被预约的空闲时间段。内循环通过遍历链表res 查找索引为i的预约能否被安排,当res[p][1]>=order[i][2],即当前空闲时间段的结束时间大于等于当前预约记录的最早使用时间,st表示当前空闲时间段的开始时间与当前预约记录的最早使用时间的较大值,ed 表示当前空闲时间段的结束时间与当前预约记录的最晚使用时间的较小值。如果空闲区间能够包含当前预约记录的使用时间段,则表示预约成功。因此②处答案为ed-st +1>=order[i][4]。③处分析代码段可得,输出该条预约申请的安排结果后,需要在链表res中删除p指向的空闲时间段,q为p的前驱节点,因此答案为 res[q][2]=res[p][2]。

展开更多......

收起↑