华东师范大学《数据结构》2023-2024学年第一学期期末试卷

华东师范大学《数据结构》2023-2024学年第一学期期末试卷院(系)：__________班级：__________学号：__________姓名：__________考试时间：120分钟满分：100分考试形式：闭卷题号一二三四五总分得分批阅人一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题给出的四个选项中，只有一项是符合题目要求的，请将正确答案的序号填在题干后的括号内。以下数据结构中，属于非线性结构的是（）

A.栈B.队列C.二叉树D.线性表

在一个具有n个元素的有序数组中，使用二分查找查找一个特定元素，若查找不成功，最多需要比较多少次？（）

A.log₂(n)B.log₂(n)-1C.log₂(n)+1D.n

栈的操作遵循的原则是（）

A.先进先出B.先进后出C.随机进出D.后进后出

在动态数组的实现中，当数组容量不足时需要进行扩容。关于动态数组的扩容策略，以下描述哪一项是不正确的？（）

A.常见的扩容策略是按照一定的比例增加数组的容量，如扩大为原来的两倍

B.扩容操作会涉及到数据的复制，可能会影响性能

C.为了避免频繁扩容，可以在创建动态数组时预留一定的额外空间

D.扩容操作的时间复杂度总是O(n)，其中n是数组中的元素数量

二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为（）

A.DEBFCAB.DBEFCAC.DEBCFAD.DFEBCA

考虑一个在线投票系统，需要实时统计每个选项的投票数量，并能够快速返回得票最多的选项。以下哪种数据结构可以有效地支持这个功能？（）

A.数组，存储每个选项的票数B.链表，记录投票信息

C.哈希表，将选项作为键，票数作为值D.最大堆，始终保持最大票数在堆顶

在单链表中，删除一个节点时，需要修改其前驱节点的（）

A.数据域B.指针域C.既修改数据域也修改指针域D.无需修改

图的邻接矩阵表示法适用于（）

A.稀疏图B.稠密图C.无向图D.有向图

以下排序算法中，时间复杂度不受数据初始状态影响，始终为O(n²)的是（）

A.冒泡排序B.快速排序C.归并排序D.堆排序

哈希表的查找效率主要取决于（）

A.哈希函数的设计B.哈希表的大小C.冲突解决方法D.以上都是

队列的进出原则是（）

A.先进先出B.先进后出C.随机进出D.后进后出

一棵深度为k的完全二叉树，至少有（）个节点

A.2ᵏ⁻¹B.2ᵏ-1C.2ᵏD.2ᵏ⁺¹-1

在图的深度优先遍历（DFS）中，使用的辅助数据结构是（）

A.栈B.队列C.数组D.链表

以下关于堆排序的描述，正确的是（）

A.堆排序是稳定排序B.堆排序的时间复杂度为O(nlog₂n)

C.堆排序不需要额外空间D.堆排序适用于所有数据场景

串的模式匹配中，KMP算法的核心是（）

A.减少比较次数B.快速定位模式串的起始位置

C.构建next数组D.避免回溯

二、填空题（本大题共10小题，每空1分，共15分）请将正确答案填在横线上。数据结构是指数据元素之间的相互关系，包括数据的__________、__________和运算。栈和队列都是__________结构，栈的操作端称为__________，队列的两端分别称为队头和队尾。二叉树中，度为0的节点（叶子节点）个数比度为2的节点个数多__________个。图的遍历分为__________和__________两种基本方式。排序算法中，__________排序和__________排序是稳定排序。单链表中，头指针的作用是__________，头节点的作用是__________。哈希表的冲突解决方法主要有__________和__________两种。一棵具有n个节点的二叉树，其高度最小为__________（假设根节点高度为1）。串是由__________组成的有限序列，空串是指__________的串。在无向图中，若从顶点u到顶点v有路径，则称u和v是__________的。三、简答题（本大题共3小题，共15分）（5分）比较计数排序和冒泡排序在处理大量重复数据时的效率，并说明原因。（5分）论述伸展树在处理海量数据时的局限性和改进方向。（5分）解释图的连通分量是什么，以及如何找出一个图的所有连通分量。四、算法设计题（本大题共2小题，共20分）（10分）设计一个算法，利用栈实现单链表的逆序输出（要求：给出算法思想、伪代码，并说明时间复杂度和空间复杂度）。（10分）设计一个算法，判断一棵二叉树是否为完全二叉树（要求：给出算法思想、伪代码，并说明时间复杂度和空间复杂度）。五、综合应用题（本大题共2小题，共20分）（10分）某快递公司的包裹跟踪系统需要对包裹的运输路径和状态进行管理，包裹信息包括包裹编号、寄件人、收件人、运输节点（如分拣中心、配送站）、当前状态（如在途、分拣中、已送达）。请设计合适的数据结构，实现以下功能：

（1）添加新包裹信息；

（2）根据包裹编号查询包裹的所有运输节点和当前状态；

（3）更新包裹的当前状态和运输节点；

（4）删除已送达且超过30天的包裹信息。

要求：说明所选数据结构的理由，给出核心操作的伪代码。

（10分）已知一个图的邻接矩阵表示如下（行和列分别对应顶点v₀、v₁、v₂、v₃、v₄）：

01010

10100

01011