资源简介

2023-2024学年高二上学期浙教版(2019)选修一5.1 数据结构与算法的关系
一、选择题
1．有1个队列，队首指针head=2，队尾指针tail=3，经过一系列出队入队后，队首指针head=3，队尾指针tail=6，则该队列经历的出队和入队操作次数分别为（ ）
A．1 3 B．1 4 C．2 3 D．2 4
2．定义如下函数：
def f (x, n):
if n == 0:
return 1
return x * f (x, n - 1)
该函数的时间复杂度为（ ）
A．0(1) B．0(log2n) C．0(n) D．0(xn)
3．递归算法的函数调用时，处理参数和返回地址通常使用的数据结构是（ ）
A．数组 B．队列 C．栈 D．链表
4．在二次探测的哈希表中，当发生哈希冲突时，我们会（ ）
A．停止查找 B．重新选择哈希函数
C．以二次函数的形式探测新的位置 D．删除冲突的元素
5．有如下 Python程序，用于判断链表是否为回文链表（回文链表是指正序遍历和逆序遍历得到的结点顺序一致的链表），则划线处代码是（ ）
a=[[1,1],[2,2],[8,3],[2,4],[1,-1]]
st=[];head=0;flag=True
slow, fast=head, head
while ① :
st.append (a[slow][o])
slow=a[slow][1]
fast=a[a[fast][1]][1]
if ② :
slow=a[slow][1]
while slow!=-1:
if st.pop () !=a[slow][0]:
flag=False
slow=a[slow][1]
if flag:
print("是回文链表!")
else:
print("不是回文链表!")
A．①fast!=-1 or a[fast][1]!=-1 ②fast!=-1 B．①fast!=-1 or a[fast][1]!=-1 ②a[fast][1]!=-1
C．①fast!=-1 and a[fast][1]!=-1 ②fast!=-1 D．①fast!=-1 and a[fast][1]!=-1 ②a[fast][1]!=-1
6．树结构是一种具有层次关系的非线性结构。树是由n(n≥0)个节点组成的有限集合，如图所示，下列说法错误的是( )
A．任何一个非空树均仅有一个称为根的节点，如图中A,n=0时为空树
B．当n>0时，其余节点可分为m ( m≥0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树
C．节点A为根节点，B、C、D为A的子树的根节点，同理，E、F、G是B的子树的根节点，B是E、F、G的父节点
D．在树结构中，数据元素之间是一对一的关系
7．数据结构中栈和队列的共同特点是（ ）
A．处理数据时满足先进后出 B．处理数据时满足先进先出
C．只允许在端点处插入和删除数据 D．没有共同点
8．用对分查找法从列表[2、4、6、8、15、16、27、33、55]中找到数据16的最少查找次数是（ ）次。
A．2 B．3 C．4 D．6
9．什么是时间复杂度（ ）
A．程序执行所需的时间 B．程序执行所需的内存
C．描述算法运行时间随输入大小增长的趋势 D．程序的输出结果
10．数据结构在程序设计中的作用不包括（ ）
A．提高程序运行效率 B．方便数据的存储和检索 C．增加代码的复杂度 D．有助于算法设计
11．队列Q从队首到队尾的元素依次为0，1，2，3，约定：A操作是指队首元素出队，P操作是指队首元素出队后立即从队尾入队，经过APA系列操作后，队列中队首到队尾的元素依次为（ ）
A．3，0，2 B．2，0 C．3，1 D．1，3，0
12．线性结构数据之间的关系是（ ）
A．一对一 B．多对多 C．一对多 D．多对一
13．全国航运图属于（ ）
A．线性结构 B．树结构 C．图结构 D．以上均不是
14．下列有关数组的描述，错误的是（ ）
A．数组是由相同数据类型的变量组成的一个序列
B．数组中的每个元素按照下标顺序依次存储
C．二维数组中的元素在内存中的存储方式有行优先存储和列优先存储两种
D．在数组中进行插入、删除操作时无需移动数据元素
15．关于数据结构的描述，以下选项中错误的是( )
A．数据结构指相互有关联的数据元素的集合
B．数据的存储结构有顺序存储、链接存储、索引存储和散列存储
C．数据结构不可以直观地用图形表示
D．数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型
二、填空题
16．下列查找算法中，适用于无序数组的是 。
17．在哈希表中，为了避免哈希冲突，通常需要使用解决冲突的方法，如线性探测、二次探测和开放寻址法等。这些方法的共同目标是 。
18．在快速排序算法中，为了避免最坏情况的发生，通常采用 方法选择基准元素。
19．小明同学所在城市的地铁线路局部图，如图所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1，停靠站时间忽略不计；换乘地铁的用时也都相等，记为t2。
（1）如果t1＝t2，小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线。
（2）设t1＝2min，t2＝lmin，则小明从A站出发到达B站的最短用时为 min。
三、操作题
20．假设你正在设计一个小型音乐播放器，需要实现一个功能：根据歌曲名称或歌手名字快速检索歌曲信息（包括歌名、歌手、时长）。请仅使用基础数据结构（如数组、链表）来设计解决方案。
问题:
（1）你会选择哪种基础数据结构来存储歌曲信息，并说明如何组织这些数据结构以支持按名称或歌手检索？
（2）设计一个基础的查询算法，使得当用户根据歌名或歌手名查询时，系统能尽可能快速响应。简述算法思路，并讨论其时间复杂度。
21．有个火车站的铁轨调度方法如下：火车从一方1,2,3,4…依次进入，由于每个火车皮要去的目标车站不一样，想让车皮到站后能以最少的时间从火车上脱离，就让最近到的车皮放在整列火车的最后。因此需要转换站来达成这样的目标，转换站只能在同一个地方进与出。例如有四个车皮1,2,3,4进入，2,4,3,1到站，即2号车皮目的地最远，4号车皮倒数第二远，3号车皮倒数第三远，1号车皮最近。
为了能快速指挥车辆进出站转换，小王编写例如下程序
a=[1,2,3,4,5,6] #待车皮进站
b=[3,2,1,6,5,4] #出站顺序
stack=[0]*len(a)
top=0
stack[top]=a[0]
s=str(a[0])+"进"
ha=1;hb=0
while :
while top>-1 and :
s=s+str(stack[top])+"出"
top-=1
if hatop+=1
stack[top]=a[ha]
s=s+str(a[ha])+"进"
ha+=1
elif ha==len(a) and top>-1 and :
print("无法调度")
break
if top==-1:
print(s)
代码显示结果：1进2进3进3出2出1出4进5进6进6出5出4出
(1)修改加框处代码
(2)将划线处代码补充完整，使功能完善
四、简答题
22．数组的特点？
23．队列的特点？
参考答案：
1．A
2．C
3．C
4．C
5．C
6．D
7．C
8．B
9．C
10．C
11．C
12．A
13．C
14．D
15．C
16．顺序查找
17．减少哈希冲突对查找效率的影响。
18．随机选择
19． A-L-K-H-G-B 或 A-L-K-J-I-B 12
20．（1）数据结构选择与组织：
①歌曲信息存储：使用数组存储所有歌曲信息，每个元素包含歌曲的详细信息（歌名、歌手、时长）。
②按歌名索引：由于数组不利于直接按名称查找，可以额外创建一个基于歌名的有序数组。此数组按照歌名排序，每个元素存储指向原歌曲信息数组中对应歌曲的索引。
③按歌手名索引：同样，创建一个按歌手名排序的数组，每个元素也是一个链表头节点，链表中存储该歌手的所有歌曲在歌曲信息数组中的索引。这样，每个歌手的歌曲通过链表相连，可以快速遍历。
（2）查询算法：
①按歌名查询：使用二分查找法在按歌名排序的数组中查找目标歌名的索引，然后通过索引在原歌曲信息数组中找到歌曲信息。时间复杂度为O(log n)。
②按歌手名查询：首先在按歌手名排序的数组中使用二分查找法定位到目标歌手。找到后，遍历该歌手链表中的所有索引，在原歌曲信息数组中获取所有该歌手的歌曲信息。二分查找的时间复杂度为O(log n)，链表遍历最坏情况为O(m)，其中m为该歌手的歌曲数量，总的时间复杂度接近O(log n+m)。
21． top>-1 and hb<=len(b) stack[top]==b[hb] hb+=1 stack[top]!=b[hb]
22．不仅需要描述数据对象本身，还需要描述数据所处的位置或者数据之间的前后顺序关系
23．先进先出，不能插队

展开更多......

收起↑