资源简介

一、 数据结构与算法效率
1. 算法的空间复杂度是指(　C　)
A. 算法所处理的数据量大小的度量
B. 算法程序中语句或指令条数多少的度量
C. 算法在运行过程中临时占用存储空间大小的度量
D. 算法的输入和输出数据所占用的存储空间大小的度量
【解析】 本题考查空间复杂度的知识。算法的空间复杂度是指算法在运行过程中临时占用存储空间大小的度量,C正确
2. 算法的时间复杂度是指(　D　)
A. 算法所用的程序占用空间的大小
B. 一般需要精确测量,其单位时间是秒
C. 算法的时间复杂度和空间复杂度成正比
D. 算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数
【解析】 本题考查时间复杂度知识。算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数,一般没必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级,采用大O记法,D正确。
3. 下面这段Python代码的时间复杂度是(　A　)
n=100
a=50
c=a*n
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查程序复杂度知识。程序采用顺序结构,故时间复杂度是O(1),A正确。
4. 有如下自定义函数,其中列表a的元素按递增的顺序排列:
def fun(a,x):
　　L,R=0,len(a)－1
　　while L<=R:
　　　　n=(L＋R)//2
　　　　if a[m]==x:
　　　　　　return m
　　　　elif a[m]　　　　　　L=m＋1
　　　　else:
　　　　　　R=m－1
　　　　return None
则函数fun()的算法时间复杂度是(　B　)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查时间复杂度的知识。二分查找的时间复杂度是O(log2n),B正确。
5. 下列关于算法效率的说法,错误的是(　C　)
A. 同一个问题采用不同的算法,其算法效率可能不同
B. 算法效率的高低可由算法复杂度来度量
C. 评价算法效率优劣时,只需评价时间复杂度即可
D. 数据结构的不同选择会影响算法的运行效率
【解析】 本题考查算法效率知识。评价算法效率优劣时,不仅要看评价时间复杂度,有时候还要看空间复杂度,两者都需要评估,C符合题意。
6. 下面这段Python代码的时间复杂度是(　C　)
import random
n=int(input("请输入随机数个数n:"))
d=[]
for i in range(n):
　　d.append(random.randint(1,100))
print(d)
key=int(input("请输入需要查找的数:"))
for i in range(len(d)):
　　if key==d[i]:
　　　　print("查找成功!索引号为:",i)
　　　　break
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查Python程序的复杂度计算。程序采用单循环结构,故时间复杂度是O(n),C正确。
7. 下列关于数据结构的说法,正确的是(　D　)
A. 常见的线性关系数据结构有数组、队列、栈和树等
B. 数组和链表在操作时,其存储空间固定不变
C. 链表在访问、插入和删除元素时,算法效率比数组高
D. 栈是一种先进后出的线性表结构
【解析】 本题考查数组、链表、队列、栈和树的数据结构知识。树是非线性结构,A错误。链表的存储空间不固定,B错误。数组的访问效率高于链表,链表的插入和删除效率高于数组,C错误。
8. 下面这段Python代码的时间复杂度是(　C　)
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)
【解析】 本题考查程序复杂度知识。程序采用一重循环结构,且执行次数与问题规模n呈线性增大关系,故时间复杂度是O(n),C正确。
9. 下面这段Python代码的时间复杂度是(　D　)
s=0;n=100
for i in range(1,n＋1):
　　for j in range(1,n＋1):
　　　　s＋=1
print(s)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查程序复杂度知识。程序采用两重循环结构,且执行次数与问题规模n2呈线性增大关系,故复杂度是O(n2),D正确。
10. 有如下自定义函数:
def fun(a,p,x):
　　n=len(a)
　　a.append(x)
　　for i in range(n,p,－1):
　　　　a[i]=a[i－1]
　　a[p]=x
　　return a
则函数fun()的算法时间复杂度是(　C　)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查程序复杂度知识。程序采用一重循环结构,且执行次数与问题规模n呈线性增大关系,故复杂度是O(n),C正确。
11. 下列关于时间复杂度之间的大小关系,正确的是(　B　)
A. O(1)< O(n)< O(n2)< O(log2n)
B. O(1)< O(log2n)< O(n)< O(n2)
C. O(log2n)< O(1)< O(n)< O(n2)
D. O(n2)< O(n)< O(log2n)< O(1)
【解析】 一般而言,时间复杂度的耗时从小到大的排序如下:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!)。B正确。
12. 某超市举办特卖活动,对n种商品进行限定打折大优惠,顾客可通过一体机输入所选商品的条形码信息,查询哪些商品能参加本次特卖。将n种商品的条形码信息存入数组a;将顾客所选商品信息存入数组b,其中b[i][0]表示某种商品的条形码信息,b[i][1]表示该种商品的名称。查询过程的Python程序部分代码如下:
p = len(b)
i = 0
while i < p:
　　for j in range(n):
　　　　if b[i][0]==a[j]:
　　　　　　print(b[i][1])
　　i = i ＋ 1
下列说法中,错误的是(　C　)
A. 该程序采用了枚举算法
B. p值越大,程序运行时间越长
C. n值的大小与该程序的算法效率无关
D. 将原用数组存储的数据改用链表存储,会占用更多存储单元
【解析】 本题考查枚举算法、数据结构与算法效率等知识。本程序是一个枚举算法,A不符合题意。p的值越大则需要枚举的项越多,则需要运行的时间越长,B不符合题意。n的值越大,所需对比的数量越多,所需要的时间也越多。所以n值的大小与程序运行效率有关,C符合题意。如果数据采用链表存储,则需要增加一个存储下一个元素的指针域,因此所需要的存储空间会比数组多,D不符合题意。
13. 小明学习了算法后,写了以下两段代码来求斐波那契数列的第6项:
算法一 a=1;b=1 for i in range(2,6): 　　c=a＋b 　　a=b 　　b=c print(c) 算法二 def f(n): 　　if n==1 or n==2: 　　　　return 1 　　else: 　　　　return f(n－1)＋f(n－2) print(f(6))
下列说法中,正确的是(　C　)
A. 两种算法的时间复杂度均为O(1)
B. 算法一是迭代算法,算法二是递归算法,相比之下,算法二的时间效率更高
C. 执行算法二代码,f(4)共被调用了2次
D. 执行算法一代码,当i=4这一遍循环刚结束时,a的值为5
【解析】 本题考查算法阅读和算法效率问题。算法一(迭代)的时间复杂度为O(n),算法二(递归)的时间复杂度为O(2n),因此算法一的时间效率高,A、B错误。执行算法二代码,f(6)=f(5)＋f(4)=f(4)＋f(3)＋f(4)=…,由此可见f(4)被调用了2次,C正确。执行算法一代码,列出变量表:当i=4这遍循环刚结束时,a=3,D错误。(共18张PPT)
一、 数据结构与算法效率
第五章　数据结构与算法
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 算法的空间复杂度是指(　　)
A. 算法所处理的数据量大小的度量
B. 算法程序中语句或指令条数多少的度量
C. 算法在运行过程中临时占用存储空间大小的度量
D. 算法的输入和输出数据所占用的存储空间大小的度量
【解析】 本题考查空间复杂度的知识。算法的空间复杂度是指算法在运行过程中临时占用存储空间大小的度量,C正确。
C
2. 算法的时间复杂度是指(　　)
A. 算法所用的程序占用空间的大小
B. 一般需要精确测量,其单位时间是秒
C. 算法的时间复杂度和空间复杂度成正比
D. 算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数
【解析】 本题考查时间复杂度知识。算法在计算机上运行所花费的时间,是指算法中包含简单操作的次数,一般没必要精确计算出算法的时间复杂度,只要大致计算出相应的数量级,采用大O记法,D正确。
D
3. 下面这段Python代码的时间复杂度是(　　)
n=100
a=50
c=a*n
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查程序复杂度知识。程序采用顺序结构,故时间复杂度是O(1),A正确。
A
4. 有如下自定义函数,其中列表a的元素按递增的顺序排列:
def fun(a,x):
　　L,R=0,len(a)－1
　　while L<=R:
　　　　n=(L＋R)//2
　　　　if a[m]==x:
　　　　　　return m
　　　　elif a[m]　　　　　　L=m＋1
　　　　else:
　　　　　　R=m－1
　　　　return None
则函数fun()的算法时间复杂度是(　　)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查时间复杂度的知识。二分查找的时间复杂度是O(log2n),B正确。
B
5. 下列关于算法效率的说法,错. 误. 的是(　　)
A. 同一个问题采用不同的算法,其算法效率可能不同
B. 算法效率的高低可由算法复杂度来度量
C. 评价算法效率优劣时,只需评价时间复杂度即可
D. 数据结构的不同选择会影响算法的运行效率
【解析】 本题考查算法效率知识。评价算法效率优劣时,不仅要看评价时间复杂度,有时候还要看空间复杂度,两者都需要评估,C符合题意。
C
6. 下面这段Python代码的时间复杂度是(　　)
import random
n=int(input("请输入随机数个数n:"))
d=[]
for i in range(n):
　　d.append(random.randint(1,100))
print(d)
key=int(input("请输入需要查找的数:"))
for i in range(len(d)):
　　if key==d[i]:
　　　　print("查找成功!索引号为:",i)
　　　　break
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查Python程序的复杂度计算。程序采用单循环结构,故时间复杂度是O(n),C正确。
C
7. 下列关于数据结构的说法,正确的是(　　)
A. 常见的线性关系数据结构有数组、队列、栈和树等
B. 数组和链表在操作时,其存储空间固定不变
C. 链表在访问、插入和删除元素时,算法效率比数组高
D. 栈是一种先进后出的线性表结构
【解析】 本题考查数组、链表、队列、栈和树的数据结构知识。树是非线性结构,A错误。链表的存储空间不固定,B错误。数组的访问效率高于链表,链表的插入和删除效率高于数组,C错误。
D
8. 下面这段Python代码的时间复杂度是(　　)
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)
【解析】 本题考查程序复杂度知识。程序采用一重循环结构,且执行次数与问题规模n呈线性增大关系,故时间复杂度是O(n),C正确。
C
9. 下面这段Python代码的时间复杂度是(　　)
s=0;n=100
for i in range(1,n＋1):
　　for j in range(1,n＋1):
　　　　s＋=1
print(s)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查程序复杂度知识。程序采用两重循环结构,且执行次数与问题规模n2呈线性增大关系,故复杂度是O(n2),D正确。
D
关键能力练
10. 有如下自定义函数:
def fun(a,p,x):
　　n=len(a)
　　a.append(x)
　　for i in range(n,p,－1):
　　　　a[i]=a[i－1]
　　a[p]=x
　　return a
则函数fun()的算法时间复杂度是(　　)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题考查程序复杂度知识。程序采用一重循环结构,且执行次数与问题规模n呈线性增大关系,故复杂度是O(n),C正确。
C
11. 下列关于时间复杂度之间的大小关系,正确的是(　　)
A. O(1)< O(n)< O(n2)< O(log2n)
B. O(1)< O(log2n)< O(n)< O(n2)
C. O(log2n)< O(1)< O(n)< O(n2)
D. O(n2)< O(n)< O(log2n)< O(1)
【解析】 一般而言,时间复杂度的耗时从小到大的排序如下:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!)。B正确。
B
12. 某超市举办特卖活动,对n种商品进行限定打折大优惠,顾客可通过一体机输入所选商品的条形码信息,查询哪些商品能参加本次特卖。将n种商品的条形码信息存入数组a;将顾客所选商品信息存入数组b,其中b[i][0]表示某种商品的条形码信息,b[i][1]表示该种商品的名称。查询过程的Python程序部分代码如下:
p = len(b)
i = 0
while i < p:
　　for j in range(n):
　　　　if b[i][0]==a[j]:
　　　　　　print(b[i][1])
　　i = i ＋ 1
下列说法中,错. 误. 的是(　　)
A. 该程序采用了枚举算法
B. p值越大,程序运行时间越长
C. n值的大小与该程序的算法效率无关
D. 将原用数组存储的数据改用链表存储,会占用更多存储单元
【解析】 本题考查枚举算法、数据结构与算法效率等知识。本程序是一个枚举算法,A不符合题意。p的值越大则需要枚举的项越多,则需要运行的时间越长,B不符合题意。n的值越大,所需对比的数量越多,所需要的时间也越多。所以n值的大小与程序运行效率有关,C符合题意。如果数据采用链表存储,则需要增加一个存储下一个元素的指针域,因此所需要的存储空间会比数组多,D不符合题意。
C
13. 小明学习了算法后,写了以下两段代码来求斐波那契数列的第6项:
算法一 a=1;b=1 for i in range(2,6): 　　c=a＋b 　　a=b 　　b=c print(c) 算法二
def f(n):
　　if n==1 or n==2:
　　　　return 1
　　else:
　　　　return f(n－1)＋f(n－2)
print(f(6))
下列说法中,正确的是(　　)
A. 两种算法的时间复杂度均为O(1)
B. 算法一是迭代算法,算法二是递归算法,相比之下,算法二的时间效率更高
C. 执行算法二代码,f(4)共被调用了2次
D. 执行算法一代码,当i=4这一遍循环刚结束时,a的值为5
【解析】 本题考查算法阅读和算法效率问题。算法一(迭代)的时间复杂度为O(n),算法二(递归)的时间复杂度为O(2n),因此算法一的时间效率高,A、B错误。执行算法二代码, f(6)=f(5)＋f(4)=f(4)＋f(3)＋f(4)=…,由此可见f(4)被调用了2次,C正确。执行算法一代码,列出变量表:当i=4这遍循环刚结束时,a=3,D错误。
C

展开更多......

收起↑