资源简介

第七单元　数据结构与算法
信息技术(50分)
一、选择题(本大题共12小题，每小题2分，共24分。每小题列出的四个备选项中只有一个是符合题目要求的，不选、多选、错选均不得分)
1.定义如下递归函数：
def f(a，n)：
n＝n－1
if n＝＝0：
return a
else：
return f(a－1，n)＋f(a＋1，n)
print(f(5，3))
程序运行后﹐输出的结果是(　　)
A.10 B.20
C.30 D.40
2.定义如下函数：
def f(s)：
if len(s)＝＝1：
return s[0]
elif len(s)＝＝2：
return s[0]＋s[1]
else：
return f(s[0：len(s)//3])＋f(s[len(s)//3：len(s)])
执行语句s＝f([1，2，3，4，5，6])，函数f被调用的次数是(　　)
A.3 B.5
C.7 D.15
3.定义如下函数：
def jc (n)：
if n＝＝l：　#①
return n
return n*jc(n－1)　#②
执行语句x＝jc(5)，下列说法正确的是(　　)
A.x的计算结果为120
B.程序执行完毕，①处代码共执行1次
C.程序执行完毕，②处代码共执行5次
D.如果①处代码改成n<2，程序将无法正常执行
4.有如下Python程序段：
def f(s)：
if len(s)＝＝1：
return True
elif len(s)＝＝2：
return s[0]＝＝s[1]
elif s[0]＝＝s[－1]：
return f(s[1：－1])
else：
return False
print(f(″1234321″))
执行该程序段后，下列说法正确的是(　　)
A.输出结果为False
B.函数f运用了迭代算法
C.函数f的调用次数为4
D.函数f的时间夏杂度为O(n2)
5.采用冒泡排序算法对数据序列“8，7，2，3，9，6，5”完成升序排序，排序2趟后，正确的顺序是(　　)
A.2，3，8，7，5，6，9 B.2，3，8，7，9，6，5
C.2，3，5，6，7，8，9 D.2，3，7，5，6，8，9
6.采用冒泡排序算法对数据序列“2，3，4，5，1，0”完成升序排序，则需要交换的次数为(　　)
A.9次 B.12次 C.15次 D.18次
7.下列代码采用冒泡排序对a列表中的n个数据升序排序，则①②两处不可用的选项是(　　)
for i in range(①________)：
for j in range(②________)：
if a[j] 　　　 　a[i]，a[j－1]＝a[j－1]，a[j]
A.①1，n 　　 ②n－1，i－1，－1
B.①n，1，－1 　　 ②1，i－1
C.①1，n 　　 ②1，n－i＋1
D.①0，n－1 　　 ②n－1，i－1
8.有如下Python程序段：
s＝″ccbbac″
a＝[i for i in range(6)]
for i in range(5)：
for j in range(5－i)：
if s[a[j]]>s[a[j＋1]]：
　 　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
运行该程序段输出的结果为(　　)
A.[4，3，2，5，1，0] B.[4，5，3，2，1，0]
C.[4，2，3，0，1，5] D.[4，3，2，5，0，1]
9.某排序算法的Python程序段如下：
'读取n个整数，依次存入a[1]到a[n]中，代码略
for i in range(1，n－1)：
for j in range(n，i＋1，－1)：
if a[j]>a[j－1]：
　　 　　a[j]，a[j]＝a[j－1]，a[j－1]
执行上述程序段，下列说法正确的是
A.交换过位置的数据，可能会再回到其初始位置
B.执行完成后，数组元素a[1]到a[n]从小到大排列
C.若n为6，整个排序过程总的比较次数是30
D.整个排序过程总的交换次数至少为1
10.某对分查找算法的Python程序段如下：
key＝int(input(″请输入待查数据值：″))
d＝[17，18，20，23，24，25，28，32，34，35]
f＝False；s＝″″
i＝0；j＝len(d)－1
while i<＝j：
m＝(i＋j)//2
s＝s＋″，″＋str(d[m])
if d[m]＝＝key：
f＝True
break
if keyj＝m－1
else：
i＝m＋1
print(s)
输入待查数据值为23，执行该程序段，则输出的结果是(　　)
A.25，20，24，23 B.24，18，20，23
C.25，20，23 D.24，20，23
11.有如下Python程序段：
key＝int(input(″请输入任意一个整数：″))
a＝[12，18，22，27，36，45]
ans＝0
i＝0；j＝len(a)－1
while i<＝j：
m＝(i＋j＋1)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
ans＋＝a[m]
print(ans)
执行以上程序段，输入任意的key值，则ans的值不可能是(　　)
A.45 B.57
C.67 D.72
12.有如下对分查找程序，a为按非降序排序的整型数组；
import random
key＝random.randint(0，4)*2＋20
a＝[12，14，15，15，19，x，20，24，y，26]
c＝0
i＝0；j＝len(a)－1
while i<＝j：
m＝(i＋j)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
c＋＝1
测试所有可能的key值，程序执行后c均等于4，下列正确的x，y值可以为(　　)
A.19，25 B.20，26
C.20，25 D.20，24
二、非选择题(本大题共3小题，其中第13小题7分，第14小题10分，第15小题9分，共26分)
13.小T编写了一个Python程序功能如下：输入需随机生成的坐标点数量，经过程序执行后，自动生成并显示相应数量的途经点坐标(坐标值为大于等于1小于10的实数，四舍五入保留一位小数)，试图求出平面坐标系中一端(最左和最右的点称为端)出发，按照一定的规则途经所有点到达另一端的路径长度(四舍五入保留一位小数)。程序执行界面如图所示。
(1)实现上述功能的Python程序如下，将划横线部分的代码补充完整。
from random import*
from math import*
data＝[[0，0] for i in range(100)]
k＝int(input(″请输入点的个数″))　#产生k个点的随机坐标
for i in range(k)：
data[i][0]＝randint(0，90)/10＋1
data[i][1]＝randint(0，90)/10＋1
print('x：'，data[i][0]，' y：'，data[i][1])
flag＝False ; i＝0
while i<＝k－2 and not flag：
flag＝True
j＝0
while ①________：
if data[j][0]*100＋data[j][1]>data[j＋1][0]*100＋data[j＋1][1]：
　　 　　data[j]，data[j＋1]＝data[j＋1]，data[j]
　　　 　flag＝False
j＋＝1
②________
s＝0；length＝0
for i in range(k－1)：
x1＝③________　#y1的计算方式同x1，代码略
length＝sqrt(x1＋y1)
s＋＝length
print(″路径长度是：″，④________)
(2)由程序看，访问坐标系中所有点的规则是________(单选，填字母：A.左上到右下/B.左下到右上/C.右下到左上/D.右上到左下)。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
14.某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以送到B车间加工。为了使得总加工时间最短，我们可以将这n个产品分为两类，第一类在A车间加工时长少于在B车间加工时长，第二类在A车间加工时长不少于在B车间加工时长。第一类应将在A车间花费时间少的产品排在前面，第二类应将在B车间花费时间少的产品排在后面，然后先处理所有第一类产品，再处理第二类产品。可以证明，这样排序后所有产品加工完成花费的总时间最少。例如有4种产品，它们在A车间加工时长分别为3、5、8、4，在B车间加工时长分别为6、1、2、7，产品分类、排序、合并、计算时长的过程如第15题图所示，最后得出总时长为21。(每个产品在B车间开始加工需同时满足它在A车间加工完并且B车间已加工完上一个产品这两个条件)。
编写程序模拟工厂对这n个产品的处理过程，计算总加工时间。请回答下列问题：
(1)由题意可知，若3种产品在A车间加工时长分别为5、7、3，B车间加工时长分别为6、1、2，则总加工时长为________。
(2)小华先编写了如下将第一类产品排序的函数：
def sort1(a，b)：　#参数a、b的元素分别表示每个产品在A、B车间的加工时长。
n＝len(a)
for i in range(n－1)：
for j in________：
　　　　 if a[j]>a[j＋1]：
　　　　 　　a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　 　　b[j]，b[j＋1]＝b[j＋1]，b[j]
划线处可以填写的代码有________(多选，填字母。全部选对的得2分，选对但不全的得1分，不选或有选错的得0分)
A.range(n－1－i) B.range(n－1，i，－1)
C.range(i，n－1) D.range(n－2，i－1，－1)
(3)小强编写了如下将第二类产品排序的函数：
def sort2(a，b)：　#参数a、b的元素分别表示每个产品在A、B车间的加工时长。
n＝len(a)
for i in range(1，n)：
k1，k2＝a[i]，b[i]
j＝i－1
while________：
　 　　　a[j＋1]，b[j＋1]＝a[j]，b[j]
　 　　　j－＝1
　　　　a[j＋1]，b[j＋1]＝k1，k2
①请在划线处填入合适的代码。
②此程序时间复杂度为________。(单选，填字母)
A.O(1) B.O(n)
C.O(n2) D.O(nlog2n)
(4)小张结合前两位同学的程序，计算产品加工总时长。请在划线处填入合适的代码。
'''
读取n个产品在A、B两车间加工的时间，根据题目要求分为两类，第一类产品在A、B两车间加工的时间分别存储在列表a1和列表b1中，并通过sort1()函数排序，第二类产品在A、B两车间加工的时间分别存储在列表a2和列表b2中，并通过sort2()函数排序，代码略
'''
a＝a1＋a2
b＝b1＋b2
n＝len(a)
k，t＝0，0　#k为A加工时间，t为B加工时间
for i in range(n)：
k＋＝a[i]
if ①________：
t＝k
②________
print(″总加工时长最短为：″，t)
15.进入新学期第一天，班主任老师将班上N个同学(学号为1－N)排成一排，分配座位。从排队到分配座位步骤如下：
步骤一：先将1号同学安排进队；
步骤二：2～N号同学由老师依次指定入队位置，如学号为i的同学由老师指定站在队中某位同学的左侧或右侧；
步骤三：所有同学按照上述方法入队完毕后，2人一组的方式依次分配到四个组别中；步骤四：输出每组学生的名单。
请回答下列问题。
(1)若某班有4位同学，学号为1～4，完成步骤一后，执行步骤二的指令3次，每次指令包含两个整数k和p(p为0或1)。若p为0，则表示插在k号同学的左侧，p为1则表示插在k号同学的右侧。若三条指令分别为10、21、10，则执行指令后队伍从左到右学号分别为：________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def insert(k，x)：
R[x]＝R[k]
L[x]＝k
①________
R[k]＝x
L＝[0]*100；R＝[0]*100
insert(0，1)　#0的右边插入1号同学
#info列表存储各学生姓名和学号，格式如[[″张三″，1]，[″李四″，2]…]，代码略
n＝len(info)
for i in range(2，n＋1)：
k＝int(input(″请问插入在几号同学旁边？″))
p＝int(input(″请输入该同学的左侧还是右侧″))
if p＝＝0：
②________
else：
insert(k，i)
q＝[[]for i in range(4)]
i＝m＝0
③________
while x！＝0：
q[i].append(x)
m＝m＋1
if m%2＝＝0：
④________
x＝R[x]
for i in range(4)：
for j in q[i]：
print(info[j－1][0]，end＝″ ″)
print()
第七单元　数据结构与算法
1.B　[f(5，3)＝f(4，2)＋f(6，2)＝f(3，1)＋f(5，1)＋f(5，1)＋f(7，1)＝20。]
2.C　[s的长度为6，f(s)返回f([1，2])＋f([[3，4，5，6]])，调用2次，函数f([1，2])值为3，调用1次。f([[3，4，5，6]])返回f([[3，4])＋f([[5，6]])，调用2次。f([[3，4])和f([[5，6]])各调用1次，共调用7次。]
3.A　[本题考查递归的应用。该程序实现计算n的阶乘。A选项jc(5)＝5*4*3*2*1＝120。B选项函数调用5次，该语句执行5次。C选项执行4次。D选项n<2和n＝＝1是等效的。]
4.C　[本题考查函数递归的分析和理解。该程序段的功能是利用递归判断一个字符串是否是“回文串”。A选项″1234321″是回文串。B选项该函数内部调用了自身，是递归算法。C选项f(″1234321″)→f(″23432″)→f(″343″)→f(″4″)→True，调用4次。D选项程序内部只调用本身一次，算法复杂度是O(n)。]
5.A　[本题考查冒泡排序的算法思想。从后往前依次比较相邻两个位置数据的大小，并把较小数据换到前一位置。排序结果为2，3，8，7，5，6，9。从前往后冒泡的结果为2，3，7，6，5，8，9。]
6.A　[本题考查教材上的冒泡排序算法基本原理。第一趟交换5次，序列为“0，2，3，4，5，1，”。第二趟交换4次，序列为“0，1，2，3，4，5”。至此数据已经有序，无需交换。共交换9次。所以答案为A。]
7.B　[本题考查冒泡排序的算法思想。当i＝n时，j in range(1，n－1)，当j为最后一个值n－2时(range右边为开区间，n－1取不到)，a[n－2]与a[n－3]比较大小，缺少a[n－1]与a[n－2]比较大小，不能完成所有n个数据的升序排序。]
8.C　[本题考查索引排序。数组a存储的0～5的索引位置，程序实现从前往后冒泡，当条件s[a[j]]>s[a[j＋1]]成立时交换，实现升序排列，因此排序后的结果是abbccc，找到这些字母的索引位置。]
9.A　[本题考查冒泡排序算法思想。算法实现从左往右降序排列。A选项例如某个数后面有2个数，且一个数大他小，一个数比他大，当大的数往前交换后，第2次比他小的数又把换回来了。总的比较次数为n*(n－1)/2＝15。D选项如果原数据已经有序了，不会发生交换。]
10.B　[本题考查对分查找。根据对分查找的特点、中点位置取值(i＋j)//2是偏左的，最后输出的应该24、18、20、23。]
11.A　[本题考查二分查找，找到后不退出，直到i>j为止后退出，ans记录的是查找过程中所访问到的数之和。]
12.D　[c表示查找次，查找到结果后并没有结束循环，画出如图所示二叉树，x的值介于20和24之间，但要查找4次，x的值必定为20。y的值介于24和26之间，但要查找4次，y的的值不能为26。由于查找的key是偶数，若y的值为25，须查找5次。]
13.(1)①j<＝k－i－2或者j解析　本题考查冒泡算法。(1)本程序实现从前往后冒泡，后面的数据先有序，flag表示某趟排序是否有数据交换的标志，若有没有数据交换，提前结束排序。①坐标值为大于等于1小于10的实数，将x的坐标*100，意味着扩大x坐标的权重，即x是主关键字，若产生两个x相等，那么再加上y坐标。从前往后冒泡，每次是i的对称位置k－i－1有序，由于比较对象为j和j＋1，因此内循环的终点为k－i－2。②外循环i每次加1。③k个点，只有k－1条线段，因此循环k－1次。每次利用两点距离公式进行求线段长度。④四舍五入保留一位小数显示路径长度。(2)以x为主关键字升序，y为次关键字升序，因此是从左下向右上形成路径。
14.(1)16　(2)AD　(3)①j>＝0 and k2>b[j]　②C (4)①t解析　本题考查排序相关概念及算法时间复杂度。(1)根据划分标准将3种产品分别编号为①②③，加工顺序为①③②，加工时间段为：产品①0－5，5－11；产品③5－8，11－13；产品②8－15，15－16，总加工时长为16。(2)内循环表示扫描方向，若从左向右排序，比较对象为a[j]和a[j＋1]，左端点固定为0，第i趟排序右端点为n－1－i，当j＋1达到n－1－i时，j的值为n－2－i，由于该位置取不到，因此range值为(0，n－1－i)。若从右向左排序，右端点(j＋1的值)固定为n－1，左端点为i，因此range值为(n－2，i－1，－1)。(3)①对第二类产品按在B车间的加工时长做插入排序。内层循环寻找插入位置，将比k2小的元素依次右移一位，关注j的边界不能小于0，此时j＋1处即为插入位置，对b[j＋1]赋值为k2。②插入排序的时间复杂度为O(n^2)。(4)计算总加工时长，累加产品时长，k为A加工时间，t为B加工时间；根据输出最后的结果为t即为总时长，如果当前产品A车间加工的时长大于B车间加工时长，那当前产品进入B车间开始加工的时间即t＝k，故①处为t15.(1)2341　(2)①L[R[k]]＝x　②insert(L[k]，i)　③x＝R[0]　④i＝(i＋1)%4
解析　本题考查索引数组和双向链表的知识。(1)在1左侧插入2，队伍为21，在2的右侧插入3为231，在1的左侧插入4，队伍为2314。(2)①在学号k的右侧插入x，则x的左侧是k，右侧是原k的右侧，同时要修改k的右侧指向。②insert程序的功能是在k的右侧插入x，那么现在在x的左侧插入意味着在k的前一个数L[k]的右侧插入x。③由于0没有存放学号，但他的右侧是第1个学号，因此当前节点从R[x]开始遍历各个元素。④i表示组别，共有4组，其值从0，1，2，3循环变化。

展开更多......

收起↑