真题回忆

此页面收集了数据结构与算法课程的真题回忆。请读者自行取用。

2026 年数据结构题目回忆

本资料基于同学们考后回忆整理。未收录的题目（如选择题第 3、5、6、7、9、10、11 题等）暂无回忆内容，可能是因为难度较低或者没什么特点。

一、选择题

第 1 题

单链表，给出指向节点 P 的指针（不是头结点），现在要将节点 s 插在 p 前面，如何操作。

第 2 题

已知递归函数 F，F(0) = -3, F(1) = -2, F(2) = -1，F(n) = F(n-1) + F(n-2) - F(n-3)，for n ≥ 3，则 F(10) = ( )。

第 4 题

下面不是哈希函数设计的主要目标的是。

第 8 题

下面不是分治算法的要求的是。

第 12 题

下列算法可以求解带负权图、单源最短路的是。

第 13 题

PageRank 算法是干什么的。

第 14 题

Floyd 算法的本质。

第 15 题

给一个布尔表达式，判断是否存在一组解使得其成真，这是什么类型问题。

二、判断题

判断题 9

可达性分析可用于死代码检测和依赖分析。

判断题 10

最大流问题中可使用 BFS 或者 DFS 找增广路。

三、简答题

简答题 1

分治算法优化矩阵相乘，需要计算七次，附加的复杂度为 O(n²)，写出时间复杂度的推导式，并用主定理法求出该方法的时间复杂度。如果不优化，求出对应的时间复杂度，将这两个复杂度进行比较。

简答题 2

判断两个链表是否相交（有无公用的结点），设计一个算法（描述算法），求时间复杂度，求空间复杂度，并证明算法正确性。

简答题 3

分治、动态规划、贪心，分别的核心思想、局限性、举 1-2 个例子。

简答题 4

一个图，点集为 ABCDEF，边集为 A-B, A-C, B-C, B-D, C-D, D-E, D-F, E-F，从大到小对六个点排序，依据分别为度中心度 (Degree Centrality)、接近中心度 (Closeness Centrality)、介数中心度 (Betweenness Centrality)。

四、综合大题

本题给了一个超长的背景，但实际上几乎不需要看这个背景。

第 1 问：系统有 100 万个节点，500 万条路线，10 亿次查询，问（1）用什么节点存储结构，时间复杂度为（2）快速查询相邻节点，而且要省空间（3）支持范围查询和磁盘存储，用什么。

第 2 问：要用尽可能少的成本连接其所有的点，这是什么算法问题，用什么算法，什么复杂度？

第 3 问：从运输节点 A 往外运输东西，分两种情况 1. 每条路的成本都是正的 2. 存在路的成本为负数。问不同的情况下，用什么算法？复杂度为？

第 4 问：从运输节点往灾区运物资，每条路的运输量有上限，最多运多少物资？这是什么算法问题。

第 5 问：找到两个节点之间最近的公共运输节点，什么算法？朴素算法的复杂度是？怎么用预处理优化？优化之后的复杂度为？

第 6 问：一个运输机，第 i 次任务的重量为 w_i，创造价值为 p_i，求可以得到的最大价值。这是什么算法问题？写出状态转移方程。

第 7 问：一个年度检测，每个节点走一次，最后回到原点，这是什么算法问题？用回溯法解决。复杂度是？

第 8 问：对于上一题的回路，存不存在一条回路长度 ≤ k？请问这个问题是什么类型的问题，是 P, NP, NPC, NP-hard？