资源简介

第五章数据结构与算法
一、 选择题(本大题共12小题,每小题列出的四个备选项中只有一个是符合题目要求的)
1. 下列关于算法效率的说法,错误的是(　B　)
A. 时间复杂度只要大致计算出相应的数量级,采用大O记法
B. 算法的时间复杂度一般需要精确测量,其单位时间是秒
C. 算法的空间复杂度是算法在运行过程中占用的存储空间
D. 算法的时间复杂度是算法在计算机上运行所花费的时间
【解析】 本题考查算法效率的知识。算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数,一般没必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级,采用大O记法。算法的空间复杂度是指算法在运行过程中占用的存储空间,B符合题意。
2. 有如下Python程序段:
n=int(input())
s=0
for i in range(1,n＋1):
　　s＋=i
print(s)
上述程序的算法复杂度为(　C　)
A. O(1)
B. O(log2n)
C. O(n)
D. O(n2)
【解析】 本题算法中实现的功能是求1＋2＋3＋…＋n的和,其执行次数显然与问题规模n呈线性增长关系,因此其时间复杂度为O(n),C正确。
3. 有如下Python程序段:
def f(x):
　　if x == 1 :
　　　　return 1
　　else :
　　　　return x * f (x － 1)
s = 0
for i in range(1 , 6):
　　s ＋= f (i)
print (s)
执行该程序段后,变量s的值是(　D　)
A. 33 B. 34
C. 154 D. 153
【解析】 本题考查递归算法。
x 1 2 3
f(x) 1 2*1 3*2*1
x 4 5 6
f(x) 4*3*2*1 5*4*3*2*1 6*5*4*3*2*1
通过自定义函数关键代码x*f(x－1)发现该函数是通过递归算法去实现x的阶层。后面的循环是把1到5的阶层进行累加,1!＋2!＋3!＋4!＋5!=1＋2＋6＋24＋120=153,D正确。
4. 小张设计了一个算法求n的阶乘n!。算法思想如下:先把n!转换为n*(n－1)!,而(n－1)!又可以转换为(n－1)*(n－2)!,如此继续,直到求解2*1!,而1!=1,然后又通过1!求解2!的值,继而求解3!的值,如此继续,最终求出n!的值。小张采用的算法是(　B　)
A. 迭代算法
B. 递归算法
C. 枚举算法
D. 解析算法
【解析】 本题考查递归算法思想。本题中求n!采用“大事化小,小事化了”的方法,符合递归算法的基本思想,B正确。
5. 一个球从某一高度h(单位:米)落下,每次落地后反弹回原来高度的一半再落下。编程计算球在第10次落地时,经过的距离s,程序代码段如下:
h=20.0;s=h
for i in range(9):
　　　　　　
print(s)
方框中的代码由以下三部分组成:
①l=h*2　②h=h/2　③s=s＋l
下列选项中,代码顺序正确的是(　B　)
A. ①②③
B. ②①③
C. ③①②
D. ②③①
【解析】 本题考查枚举算法和迭代算法思想。python语言中,使用变量需要先定义后使用,因此③在①之后。第一次落地,经过的距离为h,即s的初值,后续落地都是先上升后落下,经过的是2段路程,上升距离是原高度h的一半,这个过程可以用②①表示。B正确。
6. 斐波那契数列是指除了数列的第1项和第2项,接下来的每一项都等于其前两项之和,如1,1,2,3,5,8,13,…,下列程序能够根据输入的n(n≥2),计算并输出斐波那契数列的第n项。
n=int(input("请输入求取斐波那契数列的第n项(n≥2):"))
a,b=1,1
i=3
while i<=n:
　　　　①　　
　　a=b
　　b=c
　　i＋=1
print("第"＋str(n)＋"项的值为"＋ 　　②　　)
下列选项中,正确的代码是(　B　)
A. ①b=a＋c　②str(a)
B. ①c=a＋b　②str(b)
C. ①c=a＋b　②str(a)
D. ①b=a＋c　②str(b)
【解析】 迭代过程中,新的值c为前两项a,b的和,①填c=a＋b,模拟发现,循环处理一次,第i项的新值保存在b中,最后输出第n项的值,需要将b转换为字符串类型再进行字符串连接。B正确。
7. 有如下优化后的冒泡排序Python程序段,引入变量flag,当排序进行到某一轮时,若无数据交换,则表示序列已经升序,根据flag的值结束循环。
a=[9,2,4,6,7,8]
c=0
for i in range(len(a)－1):
　　　　　
　　for j in range(len(a)－i－1):
　　　　if 　　　　:
　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
　　　　　　　　　
　　　　　　c=c＋1
　　if flag==False:
　　　　　　　
①flag=False　②flag=True　③a[j]>a[j＋1]　④a[j]程序运行后,c=5,画线处依次填入语句的顺序是(　D　)
A. ②③①⑤
B. ③①②⑥
C. ②④①⑥
D. ①③②⑤
【解析】 本题考查冒泡排序的优化。由if flag==False:语句可知,循环状态有变化,可推理出跳出循环。内层j循环表示排序进行中,循环不能停止,故flag=True。本题也可采用模拟算法,根据c的值来推算。D正确。
8. 有如下Python程序:
n = len(a)
k = 1
for i in range(2):
　　for j in range(i, n－1, 2):
　　　　if a[j] * k < a[j＋1] * k:
　　　　　　a[j], a[j＋1] = a[j＋1], a[j]
　　　　k = －k
如初始a= [10, 16, 18, 14, 20, 3, 12, 1],则程序运行后a的值是(　C　)
A. [16, 10, 18, 14, 20, 3, 1, 12]
B. [16, 14, 10, 18, 20, 1, 3, 12]
C. [16, 14, 10, 18, 20, 3, 1, 12]
D. [16, 10, 14, 18, 20, 3, 1, 12]
【解析】 本题考查循环语句、列表的应用和对类似排序算法的理解。当外层循环i=0时,内层循环对j=0、2、4、6偶数位上的数与其相邻数做比较,且当j=0、4时,将大的数交换到前面,小的数交互到后面;当j=2、6时,将小的数交换到前面,大的数交换到后面。因此i=0时,内层循环结果为[16,10,14,18,20,3,1,12]。当i=1时,内层循环j=1、3、5,初始k仍为正1,因此,当j=1、5时,大的在前小的在后;当j=3时,小的在前大的在后。结果为[16,14,10,18,20,3,1,12],C正确。
9. 有如下Python程序:
import random
n=random.randint(1,4)
a=[7,2,7,3,9,4]
for i in range(1,n):
　　for j in range(0,6－i):
　　　　if a[j]　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
执行该程序段后,数组a中的元素不可能为(　A　)
A. 9,7,7,4,3,2
B. 7,7,3,9,4,2
C. 7,9,7,4,3,2
D. 7,2,7,3,9,4
【解析】 本题考查冒泡排序,随机数和range函数。n 的范围是[1,4],当n=1时,range(1,1),循环次数为0。把n=2,3,4,循环1、2、3次的结果分别写出来,A符合题意。
10. 有如下Python程序:
a=[98,25,13,8,56]
for i in range(1,5):
　　　j = i; key = a[j]
　　　while a[j－1] < key and j > 0:
　　　　　　　a[j] = a[j － 1]
　　　　　　　j = j － 1
　　　a[j] = key
执行该程序段后,列表a的值是(　B　)
A. [8,13,25,56,98]
B. [98,56,25,13,8]
C. [56,25,13,8,98]
D. [98,8,13,25,56]
【解析】 本题考查插入排序算法。完整进行插入排序后,数据实现降序排序。B正确。
11. 有如下Python程序:
a=[53, 55, 59, 62, 63, 68, 81, 91]
key=int(input( 请输入查找数: ))
i,j=0,7
s=
while i<=j:
　　m=(i＋j＋1)//2
　　s＋=str(m)
　　if a[m]>key:
　　　　j=m－1
　　else:
　　　　i=m＋1
print(s)
执行该程序后,输出的结果不可能是(　C　)
A. 4210 B. 467
C. 4123 D. 423
【解析】 本题考查二分查找。将每次循环所去取的中点绘制成如图所示的二叉树。
利用该二叉树可知,输出结果可能是4210,421,423,465,467,共5种。C符合题意。
12. 有如下Python程序段:
i=0;j=len(a)－1;route=[]
while i<=j:
　　m=(i＋j＋1)//2
　　if a[m]　　　　j=m－1
　　else:
　　　　i=m＋1
　　route.append(a[m])
print(route)
已知key为58且数组a为降序排列,执行该程序段后,输出的结果为[47,58,58]。下列关于数组a的说法,错误的是(　A　)
A. 数组a的元素个数可能为5
B. 数组a可能为[59,58,58,47,43,19]
C. 数组a中至少有2个元素的值为58
D. 若key为47,则输出结果中的元素个数可能为3
【解析】 本题考查二分查找。由代码可知,找到key值向右继续查找,直到i>j。已知输出结果为[47,58,58]且数组a为降序,因此要使得能第2次就找到58,在47左边必然至少有3个元素,为了第1次查找找到47,47右边必然至少为2个元素,因此数组a至少有6个元素。当47右边有2个元素且都比47小的时候,key为47,输出结果为3个元素。A符合题意。
二、 非选择题(本大题共3小题)
13. 小王通过“问卷星”收集到一些学生数据,如图1所示。在按关键字“用户名”进行排序的过程中,对数据进行整理,删除重复数据,处理结果如图2所示。
图1　　
图2
(1)实现上述功能的Python程序如下,请在画线处填入合适的代码。
(2)加框处的程序代码有错误,请改正。
a=[]
csv_file=open("xuehao.csv", "r", encoding= utf－8 )
flines=csv_file.readlines()　# 将文件中所有数据按行读入 flines 中
csv_file.close()　　　　　　# 关闭文件
# 将每个数据行中的各项信息以“,”作为分隔符切割成字符串存入列表a中
for line in flines:　　　　
　　tmp=list(line.strip("\n").split(","))
　　a.append(tmp)
n=len(a)
i=1;m=n－1　　　#变量m表示删除重复数据后的实际数据个数
while i　　for j in range(m,i,－1):
　　　　if ①　a[j][4]　　　　　　a[j],a[j－1]=a[j－1];a[j]
　　　　elif a[j][4]=a[j－1][4]:
　　　　　　a[j－1]=a[m]　　#改错
　　　　　　②　m－=1或m=m－1　
　　i＋=1
for i in range(m＋1):
　　print(a[i])
【答案】 (2)a[j]=a[m]
【解析】 本题主要考查数据整理、冒泡排序以及Python程序的综合应用。(1)①题干中“在按关键字用户名”进行排序,由图2可知是升序排序及此处下一行的代码,可知此处填a[j][4]14. 某排序算法如下:使用二分查找思想在已排序序列中找到合适位置并插入,将所有待排序数据全部插入后即完成排序。实现该算法的程序如下:运行程序后先显示待排序数据,然后输出升序排序后的数据。程序的运行结果如图所示。
－－－－－－－－－－－－待排序数据－－－－－－－－－－－－－
[52,24,86,85,96,31,91,15]
－－－－－－－－－－－－排序后数据－－－－－－－－－－－－－
[15,24,31,52,85,86,91,96]
实现上述功能的Python程序如下,请在画线处填入合适的代码。
import random
n = 8
a=[random.randint(10,99)for i in range(n)]　#生成n个随机数
print("－－－－－－－－－－－待排序数据－－－－－－－－－－－－")
print(a)
print("－－－－－－－－－－－排序后数据－－－－－－－－－－－－")
for i in range(1,n):
　　tmp = ①　a[i]　
　　L = 0
　　②　R=i－1　
　　while L <= R:
　　　　m = (L ＋ R)//2
　　　　if tmp <= a[m]:
　　　　　 R = m － 1
　　　　else:
　　　　　 L = m ＋ 1
　　for j in range(i － 1 ,L－1, －1):
　　　　a[j ＋ 1] = a[j]
　　③　a[L]=tmp　
print(a)
【解析】 本题考查二分查找插入算法。先使用二分查找算法快速找到待插入的位置,然后从后往前逐个移动位置,最后再插入数据元素。①待插入序列的最后一个数是i－1,待插入的数是a[i]。②插入的位置右边界应该是i－1。③二分查到待插入的正确位置是L,移动完数据后在L位置插入待插入数据即可实现排序。
15. 编写程序实现如下功能:在列表a中生成n(n=10)个可重复的随机整数,按升序排列并输出。输入一个整数,采用二分查找法在列表a中查找该数key。若找到,则从列表a中删除该数(该数后面的元素都前移,若有多个相同的数,则删除相同数中下标最小的那个),并显示删除后的结果;否则,显示“该数未找到”。程序运行界面如图所示,实现上述功能的Python代码如下。
原始数据为:[11,11,12,14,15,15,15,16,17,17]
请输入删除的值key=14
删除后数据:[11,11,12,15,15,15,16,17,17]
a=[11,11,12,14,15,15,15,16,17,17]
print("原始数据为:",a)
n=len(a)
key = int(input("请输入删除的值key="))
L = 0 ; R = n
while L <= R:
　　m = (L ＋ R)//2
　　if key > a[m]:　　　#改错
　　　　R = m － 1
　　else:
　　　　L = m ＋ 1
x = L
if ①　a[x]!=key　or x > n:
　　print("该数未找到")
else:
　　for i in range(x＋1,n):
　　　　②　a[i－1]=a[i]　
　　a.pop(n－1)　　　　　　#删除列表中位置n－1的元素
　　print("删除后数据:",str(a))
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处的程序代码有错误,请改正。
【答案】 (2)key<=a[m]
【解析】 本题考查二分查找及删除列表数据操作。(1)①若列表a下标为x位置上的值不是key,则表明查找失败。②从列表下标x的下一个位置开始,依次用当前数替换前一个数,从而实现删除x所在位置数据key的目的。注意：方向不能相反,否则有效数据将被覆盖。(2)根据题目要求,需要找到与key相同数中的最小下标,结合升序列表得到结果。第五章数据结构与算法
一、 选择题(本大题共12小题,每小题列出的四个备选项中只有一个是符合题目要求的)
1. 下列关于算法效率的说法,错误的是(　　)
A. 时间复杂度只要大致计算出相应的数量级,采用大O记法
B. 算法的时间复杂度一般需要精确测量,其单位时间是秒
C. 算法的空间复杂度是算法在运行过程中占用的存储空间
D. 算法的时间复杂度是算法在计算机上运行所花费的时间
2. 有如下Python程序段:
n=int(input())
s=0
for i in range(1,n＋1):
　　s＋=i
print(s)
上述程序的算法复杂度为(　　)
A. O(1)
B. O(log2n)
C. O(n)
D. O(n2)
3. 有如下Python程序段:
def f(x):
　　if x == 1 :
　　　　return 1
　　else :
　　　　return x * f (x － 1)
s = 0
for i in range(1 , 6):
　　s ＋= f (i)
print (s)
执行该程序段后,变量s的值是(　　)
A. 33 B. 34
C. 154 D. 153
4. 小张设计了一个算法求n的阶乘n!。算法思想如下:先把n!转换为n*(n－1)!,而(n－1)!又可以转换为(n－1)*(n－2)!,如此继续,直到求解2*1!,而1!=1,然后又通过1!求解2!的值,继而求解3!的值,如此继续,最终求出n!的值。小张采用的算法是(　　)
A. 迭代算法
B. 递归算法
C. 枚举算法
D. 解析算法
5. 一个球从某一高度h(单位:米)落下,每次落地后反弹回原来高度的一半再落下。编程计算球在第10次落地时,经过的距离s,程序代码段如下:
h=20.0;s=h
for i in range(9):
　　　　　　
print(s)
方框中的代码由以下三部分组成:
①l=h*2　②h=h/2　③s=s＋l
下列选项中,代码顺序正确的是(　　)
A. ①②③
B. ②①③
C. ③①②
D. ②③①
6. 斐波那契数列是指除了数列的第1项和第2项,接下来的每一项都等于其前两项之和,如1,1,2,3,5,8,13,…,下列程序能够根据输入的n(n≥2),计算并输出斐波那契数列的第n项。
n=int(input("请输入求取斐波那契数列的第n项(n≥2):"))
a,b=1,1
i=3
while i<=n:
　　　　①　　
　　a=b
　　b=c
　　i＋=1
print("第"＋str(n)＋"项的值为"＋ 　　②　　)
下列选项中,正确的代码是(　　)
A. ①b=a＋c　②str(a)
B. ①c=a＋b　②str(b)
C. ①c=a＋b　②str(a)
D. ①b=a＋c　②str(b)
7. 有如下优化后的冒泡排序Python程序段,引入变量flag,当排序进行到某一轮时,若无数据交换,则表示序列已经升序,根据flag的值结束循环。
a=[9,2,4,6,7,8]
c=0
for i in range(len(a)－1):
　　　　　
　　for j in range(len(a)－i－1):
　　　　if 　　　　:
　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
　　　　　　　　　
　　　　　　c=c＋1
　　if flag==False:
　　　　　　　
①flag=False　②flag=True　③a[j]>a[j＋1]　④a[j]程序运行后,c=5,画线处依次填入语句的顺序是(　　)
A. ②③①⑤
B. ③①②⑥
C. ②④①⑥
D. ①③②⑤
8. 有如下Python程序:
n = len(a)
k = 1
for i in range(2):
　　for j in range(i, n－1, 2):
　　　　if a[j] * k < a[j＋1] * k:
　　　　　　a[j], a[j＋1] = a[j＋1], a[j]
　　　　k = －k
如初始a= [10, 16, 18, 14, 20, 3, 12, 1],则程序运行后a的值是(　　)
A. [16, 10, 18, 14, 20, 3, 1, 12]
B. [16, 14, 10, 18, 20, 1, 3, 12]
C. [16, 14, 10, 18, 20, 3, 1, 12]
D. [16, 10, 14, 18, 20, 3, 1, 12]
9. 有如下Python程序:
import random
n=random.randint(1,4)
a=[7,2,7,3,9,4]
for i in range(1,n):
　　for j in range(0,6－i):
　　　　if a[j]　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
执行该程序段后,数组a中的元素不可能为(　　)
A. 9,7,7,4,3,2
B. 7,7,3,9,4,2
C. 7,9,7,4,3,2
D. 7,2,7,3,9,4
10. 有如下Python程序:
a=[98,25,13,8,56]
for i in range(1,5):
　　　j = i; key = a[j]
　　　while a[j－1] < key and j > 0:
　　　　　　　a[j] = a[j － 1]
　　　　　　　j = j － 1
　　　a[j] = key
执行该程序段后,列表a的值是(　　)
A. [8,13,25,56,98]
B. [98,56,25,13,8]
C. [56,25,13,8,98]
D. [98,8,13,25,56]
11. 有如下Python程序:
a=[53, 55, 59, 62, 63, 68, 81, 91]
key=int(input( 请输入查找数: ))
i,j=0,7
s=
while i<=j:
　　m=(i＋j＋1)//2
　　s＋=str(m)
　　if a[m]>key:
　　　　j=m－1
　　else:
　　　　i=m＋1
print(s)
执行该程序后,输出的结果不可能是(　　)
A. 4210 B. 467
C. 4123 D. 423
12. 有如下Python程序段:
i=0;j=len(a)－1;route=[]
while i<=j:
　　m=(i＋j＋1)//2
　　if a[m]　　　　j=m－1
　　else:
　　　　i=m＋1
　　route.append(a[m])
print(route)
已知key为58且数组a为降序排列,执行该程序段后,输出的结果为[47,58,58]。下列关于数组a的说法,错误的是(　　)
A. 数组a的元素个数可能为5
B. 数组a可能为[59,58,58,47,43,19]
C. 数组a中至少有2个元素的值为58
D. 若key为47,则输出结果中的元素个数可能为3
二、 非选择题(本大题共3小题)
13. 小王通过“问卷星”收集到一些学生数据,如图1所示。在按关键字“用户名”进行排序的过程中,对数据进行整理,删除重复数据,处理结果如图2所示。
图1　　
图2
(1)实现上述功能的Python程序如下,请在画线处填入合适的代码。
(2)加框处的程序代码有错误,请改正。
a=[]
csv_file=open("xuehao.csv", "r", encoding= utf－8 )
flines=csv_file.readlines()　# 将文件中所有数据按行读入 flines 中
csv_file.close()　　　　　　# 关闭文件
# 将每个数据行中的各项信息以“,”作为分隔符切割成字符串存入列表a中
for line in flines:　　　　
　　tmp=list(line.strip("\n").split(","))
　　a.append(tmp)
n=len(a)
i=1;m=n－1　　　#变量m表示删除重复数据后的实际数据个数
while i　　for j in range(m,i,－1):
　　　　if ①　 　:
　　　　　　a[j],a[j－1]=a[j－1];a[j]
　　　　elif a[j][4]=a[j－1][4]:
　　　　　　a[j－1]=a[m]　　#改错
　　　　　　②　 　
　　i＋=1
for i in range(m＋1):
　　print(a[i])
14. 某排序算法如下:使用二分查找思想在已排序序列中找到合适位置并插入,将所有待排序数据全部插入后即完成排序。实现该算法的程序如下:运行程序后先显示待排序数据,然后输出升序排序后的数据。程序的运行结果如图所示。
－－－－－－－－－－－－待排序数据－－－－－－－－－－－－－
[52,24,86,85,96,31,91,15]
－－－－－－－－－－－－排序后数据－－－－－－－－－－－－－
[15,24,31,52,85,86,91,96]
实现上述功能的Python程序如下,请在画线处填入合适的代码。
import random
n = 8
a=[random.randint(10,99)for i in range(n)]　#生成n个随机数
print("－－－－－－－－－－－待排序数据－－－－－－－－－－－－")
print(a)
print("－－－－－－－－－－－排序后数据－－－－－－－－－－－－")
for i in range(1,n):
　　tmp = ①　 　
　　L = 0
　　②　 　
　　while L <= R:
　　　　m = (L ＋ R)//2
　　　　if tmp <= a[m]:
　　　　　 R = m － 1
　　　　else:
　　　　　 L = m ＋ 1
　　for j in range(i － 1 ,L－1, －1):
　　　　a[j ＋ 1] = a[j]
　　③　 　
print(a)
15. 编写程序实现如下功能:在列表a中生成n(n=10)个可重复的随机整数,按升序排列并输出。输入一个整数,采用二分查找法在列表a中查找该数key。若找到,则从列表a中删除该数(该数后面的元素都前移,若有多个相同的数,则删除相同数中下标最小的那个),并显示删除后的结果;否则,显示“该数未找到”。程序运行界面如图所示,实现上述功能的Python代码如下。
原始数据为:[11,11,12,14,15,15,15,16,17,17]
请输入删除的值key=14
删除后数据:[11,11,12,15,15,15,16,17,17]
a=[11,11,12,14,15,15,15,16,17,17]
print("原始数据为:",a)
n=len(a)
key = int(input("请输入删除的值key="))
L = 0 ; R = n
while L <= R:
　　m = (L ＋ R)//2
　　if key > a[m]:　　　#改错
　　　　R = m － 1
　　else:
　　　　L = m ＋ 1
x = L
if ①　 　or x > n:
　　print("该数未找到")
else:
　　for i in range(x＋1,n):
　　　　②　 　
　　a.pop(n－1)　　　　　　#删除列表中位置n－1的元素
　　print("删除后数据:",str(a))
请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处的程序代码有错误,请改正。

展开更多......

收起↑