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)\)

参考代码

C++
void solution(vector<int> &R, int n, int p) {
    vector<int> array(n);  // 创建大小为 n 的 vector

    for (int i = 0; i < p; ++i) {
        array[n - p + i] = R[i]; // 将 R[0..p-1] 复制到 array[n-p..n-1]
    }

    for (int i = p; i < n; ++i) {
        array[i - p] = R[i];  // 将 R[p..n-1] 复制到 array[0..n-p-1]
    }

    for (int i = 0; i < n; i++) R[i] = array[i]; // 将结果复制回 R
}

优化显然时间复杂度是不可能再降低了(在数量级上),由于至少要移动每个结点一次. 只能考虑空间复杂度的优化,显然是需要考虑一个原地操作(\(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++
void reverse(vector<int> &R, int l, int r) {
    // 反转 l...r 内的元素
    while (l < r) {
        std::swap(R[l++],R[r--]);
    }
}

void solution(vector<int> &R, int n, int p) {
    // step 1 反转前p个元素
    reverse(R, 0, p - 1);
    // step 2 反转后n-p个元素
    reverse(R, p, n - 1);
    // step 3 反正整个数组
    reverse(R, 0, n - 1);
}

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\)，设计高效算法找出它们的中位数。

leetcode 4.寻找两个正序数组的中位数

要求：
1. 给出算法的基本设计思想。
2. 用C/C++/Java描述算法，关键处加注释。
3. 说明时间复杂度和空间复杂度。

暴力解法也很好想,合并两个序列(这一步就可以确定总数为偶数还是奇数),如果是奇数返回中间值;如果是偶数返回中间两数的平均数.

时间复杂度为 \(O(n)\) 空间复杂度 \(O(n)\) 其中n为序列长度

参考代码

C++
int solution(vector<int> &A, vector<int> &B) {
    int n = A.size();
    vector<int> array(2 * n);

    int k = 0, i = 0, j = 0;
    while (i < n && j < n) {
        if (A[i] <= B[j]) array[k++] = A[i++];
        else array[k++] = B[j++];
    }

    if (i < n) array[k++] = A[i++];
    if (j < n) array[k++] = B[j++];

    return  array[n];
}

优化这个优化是比较显然的,本质是一个查找问题,在加上数组是有序的很容易想到是二分.

时间复杂度是 \(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))

节点定义：

C
typedef struct node {
    char data[10];        // 操作数或操作符
    struct node *left, *right;
} BTree;

要求：

给出算法的基本设计思想。
实现算法并注释关键部分。

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
typedef struct {
    int numVertices, numEdges;      // 顶点数和边数
    char VerticesList[MAXV];        // 顶点表
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

要求:

给出算法的基本设计思想。
实现算法并注释关键部分。
说明时间复杂度和空间复杂度。

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
typedef struct {
    int numvertices, numEdges;      // 顶点数和有向边数
    char verticesList[MAXV];        // 顶点表
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

示例： - 顶点a和b为K顶点（出度>入度）。

要求：

给出算法的基本设计思想。
实现算法并注释关键部分。