遂宁职业学院《数据结构（Python）》2023‑2024学年第一学期期末模拟试卷

遂宁职业学院《数据结构（Python）》2023‑2024学年第一学期期末模拟试卷遂宁职业学院《数据结构（Python）》2023‑2024学年第一学期期末模拟试卷（适配该校高职难度，含参考答案）一、单项选择题（每题2分，共30分）下列不属于线性结构的是（）

A.顺序表B.栈C.二叉树D.队列栈的特点是（）

A.先进先出B.先进后出C.随机存取D.按关键字存取在Python中用list模拟栈，弹出栈顶元素使用（）

A.append()B.pop()C.insert()D.remove()循环队列主要为了解决顺序队列的什么问题（）

A.溢出B.假溢出C.时间复杂度过高D.元素重复单链表中，增加头结点的目的是（）

A.方便运算统一处理空表和非空表B.加快查找速度

C.节省存储空间D.便于释放结点长度为n的顺序表，删除第一个元素，平均移动元素次数为（）

A.nB.n‑1C.n/2D.(n‑1)/2一棵二叉树第k层最多结点数（k≥1）（）

A.2k‑1B.2k二叉树的中序遍历顺序是（）

A.根‑左‑右B.左‑根‑右C.左‑右‑根D.右‑左‑根下面排序算法属于稳定排序的是（）

A.快速排序B.简单选择排序C.冒泡排序D.堆排序顺序查找的时间复杂度（）

A.O(1)B.O(logn)C.O(n)D.O(二分查找（折半查找）要求查找表必须（）

A.链式存储B.有序且顺序存储C.无序D.元素唯一下面时间复杂度最好为O(nlogn)的排序（）

A.冒泡B.归并排序C.直接插入D.简单选择在单链表p结点后插入s结点，正确操作（）

A.s.next=p;p.next=s

B.s.next=p.next;p.next=s

C.p.next=s;s.next=p

D.p.next=s.next;s.next=p队列在Python中，若用列表模拟，队尾入队append，队头出队最好使用（）

A.pop(0)B.pop()C.delD.remove一棵具有n个结点的二叉树，叶子结点数为n0，度为2结点n2，则关系（）

A.n0=n2+1B.n0=n2C.n0=n2‑1D.无确定关系二、判断题（每题1分，共10分，对√错×）栈和队列都是受限的线性表。（）顺序表的随机访问效率低于链表。（）链表不需要连续内存空间。（）完全二叉树一定是满二叉树。（）二分查找可以用于无序顺序表。（）冒泡排序最好情况时间复杂度O(n)。（）一个二叉树的叶子结点只能出现在最后一层。（）循环链表的尾结点next指向头结点。（）时间复杂度O(n2)栈可以用来实现递归函数。（）三、填空题（每空2分，共20分）数据结构研究三要素：逻辑结构、\\\\\\\\、运算。队列的特性是\\\\\\\\。单链表每个结点包含数据域和\\\\\\\\。一棵二叉树有10个度为2的结点，则叶子结点\\\\\\__个。直接插入排序最坏时间复杂度\\\\\\\\。二叉树三种遍历：前序、中序、\\\\\\\\。循环队列中，判断队列为空条件front\\\\\\\\rear。算法五大特性：有穷性、确定性、\\\\\\\\、输入、输出。顺序表插入元素，最好情况时间复杂度\\\\\\\\。哈希查找通过\\\\\\__直接定位元素存储位置。四、简答题（每题6分，共18分）简述顺序表与单链表优缺点对比。栈和队列的区别，各举一个实际应用场景。什么是稳定排序？举例一个稳定排序、一个不稳定排序。五、编程题（共22分）1.（10分）使用Python列表实现栈类Stack，实现push入栈、pop出栈、is_empty判空方法。

2.（12分）编写Python函数，实现冒泡排序，对列表进行升序排序。参考答案一、单选（每题2分，30分）1.C2.B3.B4.B5.A

6.D7.A8.B9.C10.C

11.B12.B13.B14.A15.A二、判断（每题1分，10分）1.√2.×3.√4.×5.×

6.√7.×8.√9.×10.√三、填空（每空2分，20分）1.存储结构（物理结构）

2.先进先出（FIFO）

3.指针域（next域）

4.11

5.O(n2)

6.后序

7.等于(==)

8.可行性

9.四、简答（每题6分，18分）1.顺序表：

优点：连续内存，支持随机访问，访问速度快；

缺点：插入删除需要移动大量元素，扩容需要重新分配内存，长度受限制。

单链表：

优点：插入删除只需修改指针，无需移动元素；动态分配内存；

缺点：不能随机访问，查找需要遍历，额外存储指针域，内存开销更大。2.栈：先进后出；队列：先进先出。

栈应用：函数递归调用、表达式括号匹配；

队列应用：消息排队、任务调度。3.稳定排序：两个相等关键字排序完成后，相对先后次序保持不变。

稳定：冒泡排序；不稳定：快速排序。五、编程题（22分）1、栈实现（10分）python

classStack:

def__init__(self):

self.items=[]

defpush(self,val):

self.items.append(val)

defpop(self):

ifself.is_empty():

returnNone

returnself.items.pop()

defis_empty(self):

returnlen(self.items)==02、冒泡排序（12分）python

defbubble_sort(lst):

n=len(lst)

foriinrange(n-1):

flag=False

forjinrange(n-1-i):

iflst[j]>lst[