跳转至

tags: [408大题]

大题笔记

数据结构

2009统考真题

已知带头结点的单链表,节点结构为datalink,头指针为list。在不改变链表的前提下,设计高效算法查找倒数第k个节点(k为正整数),若成功则输出data并返回1,否则返回0。

要求

  1. 描述算法的基本设计思想。
  2. 描述算法的详细实现步骤。
  3. 用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"的存储映像如下图。设计高效算法找出str1str2共同后缀的起始位置(如图中字符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)之和。

要求

  1. 给出算法的基本设计思想。
  2. 定义二叉树节点的数据类型(C/C++)。
  3. 实现算法并注释关键部分。

2015统考真题

题目:单链表节点结构为[data|link]|data| ≤ n),删除所有绝对值相等的节点,仅保留第一次出现的节点。

示例

  • 输入:head → 21 → -15 → -15 → -7 → 15 → NULL
  • 输出:head → 21 → -15 → -7 → NULL

要求

  1. 给出算法的基本设计思想。
  2. 定义单链表节点的数据类型(C/C++)。
  3. 实现算法并注释关键部分。
  4. 说明时间复杂度和空间复杂度。

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|\) 最大.

要求

  1. 给出算法基本思路
  2. 根据设计思想,采用C/C++语言描述算法,关键之处给出注释.
  3. 说明你所设计算法的平均时间复杂度和空间复杂度.

2017统考真题

题目:将表达式树(二叉树)转换为等价的中缀表达式(通过括号反映计算次序)。

示例

  • 输入树1 → 输出:(a + b) * (c * (-d))
  • 输入树2 → 输出:(a * b) + (-(c - d))

节点定义

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

要求

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

2018统考真题

  • 问题:给定含\(n\)\(n \geq 1\))个整数的数组,设计高效算法找出未出现的最小正整数。
  • 示例:
    • \([-5,3,2,3]\)的最小未出现正整数为1;
    • \([1,2,3]\)的最小未出现正整数为4。

要求

  1. 给出算法基本设计思想。
  2. 用C/C++描述算法,关键处加注释。
  3. 说明时间复杂度和空间复杂度。
参考代码

2019统考真题

题目:带头结点的单链表L = (a1, a2, ..., an),重新排列为L' = (a1, an, a2, an-1, a3, an-2, ...),空间复杂度要求O(1)。

要求

  1. 给出算法的基本设计思想。
  2. 用C/C++实现算法(需注释关键部分)。
  3. 说明时间复杂度。

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

要求

  1. 给出算法基本设计思想。
  2. 用C/C++描述算法,关键处加注释。
  3. 说明时间复杂度和空间复杂度。
参考代码

2021统考真题

题目:无向连通图G(邻接矩阵存储),当度为奇数的顶点数≤2时,存在包含所有边的EL路径(长度为|E|)。判断G是否存在EL路径。

C
1
2
3
4
5
typedef struct {
    int numVertices, numEdges;      // 顶点数和边数
    char VerticesList[MAXV];        // 顶点表
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

要求:

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

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)

要求

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

2023统考真题

题目:有向图G(邻接矩阵存储),出度>入度的顶点称为K顶点。输出所有K顶点并返回个数。

数据结构

C
1
2
3
4
5
typedef struct {
    int numvertices, numEdges;      // 顶点数和有向边数
    char verticesList[MAXV];        // 顶点表
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

示例: - 顶点a和b为K顶点(出度>入度)。

要求

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