tags: [408大题]
大题笔记¶
数据结构¶
2009统考真题¶
已知带头结点的单链表,节点结构为data
和link
,头指针为list
。在不改变链表的前提下,设计高效算法查找倒数第k个节点(k为正整数),若成功则输出data
并返回1,否则返回0。
要求:
- 描述算法的基本设计思想。
- 描述算法的详细实现步骤。
- 用C/C++/Java实现算法(需注释关键部分)。
2010统考真题¶
设将 \(n\)(\(n > 1\))个整数存放到一维数组 \(R\) 中。设计一个在时间和空间两方面都尽可能高效的算法。将 \(R\) 中保存的序列循环左移 \(p\)(\(0 < p < n\))个位置,即将 \(R\) 中的数据由 \((X_0, X_1, \cdots, X_{n - 1})\) 变换为 \((X_p, X_{p + 1}, \cdots, X_{n - 1}, X_0, X_1, \cdots, X_{p - 1})\)。
要求: 1. 给出算法的基本设计思想。 2. 根据设计思想,采用 C 或 C++ 或 Java 语言描述算法,关键之处给出注释。 3. 说明你所设计算法的时间复杂度和空间复杂度。
最暴力的办法, 创建一个长度为 \(n\) 的数组Array
第一步先将原数组的 \(0\sim p-1\) 对应的数,复制到Array中的 \(n-p\sim n-1\) 的位置上
再将原数组的 \(p\sim n-1\) 对应的数,复制到Array中的 \(0\sim n-p-1\) 的位置上
时间复杂度 \(O(N)\)
空间复杂度 \(O(N)\)
参考代码
优化 显然时间复杂度是不可能再降低了(在数量级上),由于至少要移动每个结点一次. 只能考虑空间复杂度的优化,显然是需要考虑一个原地操作(\(O(1)\))
考虑这一个例子 \((1,2,3,4,5), p=2\) 其结果应该是 \((3,4,5,1,2)\) 如果将 \((1,2)\) 和 \((3,4,5)\) 看成两部分,操作的结果应该是反转这两部分,这就提示了可以考虑反转数组(原地O(1)), 且如果此时这两部分为 \((2,1)\) \((5,4,3)\) 则只需进行一次整体反转即可,而那两块是块内反转
故,最终的算法思路为
- 反转前p=2个元素 \((2,1 , 3, 4, 5)\)
- 反转后n-p=3个元素 \((2, 1, 5, 4, 3)\)
- 再整体反转就得到结果 \((5, 4, 3, 2, 1)\)
测试连接 leetcode 轮转数组 leetcode上这道题是右移,且要注意边界处理.其余完全一样
参考实现
C++ | |
---|---|
2011统考真题¶
- 定义升序序列\(S\)的中位数:长度为\(L(L \geq 1)\)的升序序列\(S\),第\(\left\lfloor \frac{L}{2} \right\rfloor\)个位置的数为中位数。
- 示例:\(S_1 = (11,13,15,17,19)\)的中位数为15;\(S_2 = (2,4,6,8,20)\)的中位数为8;\(S_1\)和\(S_2\)合并后的中位数为11。
- 问题:有两个等长升序序列\(A\)和\(B\),设计高效算法找出它们的中位数。
要求:
1. 给出算法的基本设计思想。
2. 用C/C++/Java描述算法,关键处加注释。
3. 说明时间复杂度和空间复杂度。
暴力解法也很好想,合并两个序列(这一步就可以确定总数为偶数还是奇数),如果是奇数返回中间值;如果是偶数返回中间两数的平均数.
时间复杂度为 \(O(n)\) 空间复杂度 \(O(n)\) 其中n为序列长度
参考代码
C++ | |
---|---|
优化 这个优化是比较显然的,本质是一个查找问题,在加上数组是有序的很容易想到是二分.
时间复杂度是 \(O(log(n))\)
空间复杂度 \(O(1)\)
2012统考真题¶
题目:采用带头结点的单链表存储单词,共享相同后缀。如"loading"和"being"的存储映像如下图。设计高效算法找出str1
和str2
共同后缀的起始位置(如图中字符i
所在节点)。
要求: 1. 给出算法的基本设计思想。 2. 用C/C++/Java实现算法(需注释关键部分)。 3. 说明算法时间复杂度。
2013统考真题¶
- 定义主元素:整数序列\(A = (a_0, a_1, \dots, a_{n-1})\)中,若存在\(x\)使得\(a_{p1} = a_{p2} = \dots = a_{pm} = x\)且\(m > n/2\)(\(0 \leq p_k < n\)),则\(x\)为主元素。
- 示例:
- \(A = (0,5,5,3,5,7,5,5)\)的主元素为5;
- \(A = (0,5,5,3,5,1,5,7)\)无主元素。
- 问题:设计高效算法找出主元素,存在则输出该元素,否则输出-1。
要求:
1. 给出算法基本设计思想。
2. 用C/C++/Java描述算法,关键处加注释。
3. 说明时间复杂度和空间复杂度。
参考代码
2014统考真题¶
题目:二叉树T(二叉链表存储),叶节点的weight
为非负权值,求带权路径长度(WPL)之和。
要求:
- 给出算法的基本设计思想。
- 定义二叉树节点的数据类型(C/C++)。
- 实现算法并注释关键部分。
2015统考真题¶
题目:单链表节点结构为[data|link]
(|data| ≤ n
),删除所有绝对值相等的节点,仅保留第一次出现的节点。
示例:
- 输入:
head → 21 → -15 → -15 → -7 → 15 → NULL
- 输出:
head → 21 → -15 → -7 → NULL
要求:
- 给出算法的基本设计思想。
- 定义单链表节点的数据类型(C/C++)。
- 实现算法并注释关键部分。
- 说明时间复杂度和空间复杂度。
2016统考真题¶
题目 已知由 \(n(n\geq 2)\) 个整数构成的集合 \(A=\{a_k\mid 0\leq k < n\}\), 将其划分为两个不相交的集合 \(A_1,A_2\) 元素个数分别为 \(n_1,n_2\), \(A_1,A_2\) 中的元素之和分别是 \(S_1, S_2\). 设计一个尽可能高效的划分算法,满足 \(\left|n_1-n_2\right|\) 最小且 \(\left|S_1-S_2\right|\) 最大.
要求
- 给出算法基本思路
- 根据设计思想,采用C/C++语言描述算法,关键之处给出注释.
- 说明你所设计算法的平均时间复杂度和空间复杂度.
2017统考真题¶
题目:将表达式树(二叉树)转换为等价的中缀表达式(通过括号反映计算次序)。
示例:
- 输入树1 → 输出:
(a + b) * (c * (-d))
- 输入树2 → 输出:
(a * b) + (-(c - d))
节点定义:
要求:
- 给出算法的基本设计思想。
- 实现算法并注释关键部分。
2018统考真题¶
- 问题:给定含\(n\)(\(n \geq 1\))个整数的数组,设计高效算法找出未出现的最小正整数。
- 示例:
- \([-5,3,2,3]\)的最小未出现正整数为1;
- \([1,2,3]\)的最小未出现正整数为4。
要求:
- 给出算法基本设计思想。
- 用C/C++描述算法,关键处加注释。
- 说明时间复杂度和空间复杂度。
参考代码
2019统考真题¶
题目:带头结点的单链表L = (a1, a2, ..., an)
,重新排列为L' = (a1, an, a2, an-1, a3, an-2, ...)
,空间复杂度要求O(1)。
要求:
- 给出算法的基本设计思想。
- 用C/C++实现算法(需注释关键部分)。
- 说明时间复杂度。
2020统考真题¶
- 定义三元组距离:\(D = |a-b| + |b-c| + |c-a|\),其中\(a,b,c\)为正数。
- 给定三个升序数组\(S_1, S_2, S_3\),计算所有可能的三元组\((a \in S_1, b \in S_2, c \in S_3)\)的最小距离。
- 示例:
- \(S_1 = \{-1,0,9\}\),\(S_2 = \{-25,-10,10,11\}\),\(S_3 = \{2,9,17,30,41\}\);
- 最小距离为2,对应三元组\((9,10,9)\)。
要求:
- 给出算法基本设计思想。
- 用C/C++描述算法,关键处加注释。
- 说明时间复杂度和空间复杂度。
参考代码
2021统考真题¶
题目:无向连通图G(邻接矩阵存储),当度为奇数的顶点数≤2时,存在包含所有边的EL路径(长度为|E|)。判断G是否存在EL路径。
C | |
---|---|
要求:
- 给出算法的基本设计思想。
- 实现算法并注释关键部分。
- 说明时间复杂度和空间复杂度。
2022统考真题¶
题目:非空二叉树T采用顺序存储(数组SqBiTNode[MAX_SIZE]
,ElemNum
为实际占用元素数),不存在的节点用-1
表示。判断是否为二叉搜索树。
示例:
- T1:
[40, 25, 60, -1, 30, -1, 80, -1, -1, 27]
(ElemNum=10) - T2:
[40, 50, 60, -1, 30, -1, -1, -1, -1, 35]
(ElemNum=11)
要求:
- 给出算法的基本设计思想。
- 实现算法并注释关键部分。
2023统考真题¶
题目:有向图G(邻接矩阵存储),出度>入度的顶点称为K顶点。输出所有K顶点并返回个数。
数据结构:
C | |
---|---|
示例: - 顶点a和b为K顶点(出度>入度)。
要求:
- 给出算法的基本设计思想。
- 实现算法并注释关键部分。