数据结构大题

总览

算法题

2009 链表
2010 顺序表
2011 顺序表
2012 链表
2013 顺序表
2014 二叉树遍历
2015 链表
2016 交换排序
2017 二叉树遍历
2018 顺序表
2019 链表
2020 顺序表
2021 图的存储
2022 二叉树遍历
2023 图的存储
2024 图的应用

应用题

2009 图的应用
2010 散列表
2011 图的应用
2012 树的应用
2013 顺序查找
2014 图的应用
2015 图的存储
2016 二叉树概念
2017 图的应用
2018 图的应用
2019 队列
2020 树的应用
2021 归并/基数/计数排序
2022 选择排序
2023 外部排序
2024 散列表

2009

算法题：链表
应用题：图的应用

2010

算法题：顺序表
应用题：散列表

2011

算法题：顺序表
应用题：图的应用

2012

算法题：链表
应用题：树的应用

2013

算法题：顺序表
应用题：顺序查找

2014

算法题：二叉树遍历
应用题：图的应用

2015

算法题：链表
应用题：图的存储

2016

算法题：交换排序
应用题：二叉树概念

2017

算法题：二叉树遍历
应用题：图的应用

2018

算法题：顺序表
应用题：图的应用

2019

算法题：链表
应用题：队列

2020

算法题：顺序表
应用题：树的应用

2021

算法题：图的存储
应用题：归并/基数/计数排序

2022

算法题： 二叉树遍历
应用题： 选择排序

2023

算法题：图的存储
应用题：外部排序

2024

算法题：图的应用
应用题：散列表

线性表——顺序表示

1.

注意：使用倒转的方法进行三次循环，或者更易想到的是借助辅助数组

2.

注意：另解更易想到，但时间复杂度会高一点为O（n）

3.

注意：经典算法，但不需要死磕最优解

4.

注意：观察要求是在空间上最优还是时间上最优，这道题运用了桶排序的思想

5.

注意：具体问题具体分析，转换为已知的问题，化繁为简

线性表——链式表示

1.

注意：快慢指针

2.

注意：还是快慢指针，或者使用头插法倒置，寻找到第一个下一位指针不同的节点即为所求节点，但这会破坏链表，时间复杂度一致

3.

注意：使用辅助数组记录是否出现过，进行时间上的优化

4.

注意：快慢指针（确定中间节点）+倒排（使用了头插法）+交错遍历合并链表

倒排过程中可以将p看成头指针，r是暂存指针，q->next = p->next;是将对象指针插到头节点之后（即该链表的最前面）；p->next = q;是重新确定头指针

交错遍历合并链表过程中q->next = s->next;是将q节点放到s节点的下一节点之前，s->next = q;是将s放到q之前

队列

1.

注意：循环队列

树与二叉树——二叉树的概念

1.

注意：

（1）有m个非叶节点，那么就有mk个由非叶节点的孩子，去除掉非叶节点（根节点除外，除了根节点外其他非叶节点也是非叶节点的孩子节点）（m-1），即为叶节点

树与二叉树——二叉树的遍历与线索二叉树

1.

注意：两种方法计算WPL

2.

注意：中序遍历的变式

3.

注意：！！

解法一的优化版：

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。

使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数，对二叉树进行中序遍历。若当前遍历的结点值小于等于 val，则算法返回 false，否则，将 val 的值更新为当前结点的值。

2）算法实现

// val 存储中序遍历中访问到的最大值
// 返回值：当前子树是否为 BST
bool solve(SqBiTree *tree, int k, int *val) {
  if (k >= tree->ElemNum) {
    // 空结点
    return true;
  }
  // 判断左子树是否为 BST
  bool ret = solve(tree, 2*k+1, val);
  if (!ret) {
    return false;
  }
  int cur_val = tree->SqbiTNode[k];
  if (cur_val == -1) {
    // 空结点
    return true;
  }
  // 判断中序序列是否递增
  if (cur_val > *val) {
    *val = cur_val;
  } else {
    return false;
  }
  // 判断右子树是否为 BST
  ret = solve(tree, 2*k+2, val);
  if (!ret) {
    return false;
  }
  return true;
}

树与二叉树——树的应用

1.

注意：（1）

2.

注意：（1）（3）

图——图的存储与基本操作

1.

2.

3.

图——图的应用

1.

2.

注意：（1）（3）关键路径的求法和暴力枚举

3.

注意：计算机网络与数据结构融合

4.

注意：（2）

5.

注意：（1）（3）

6.

注意：拓朴排序是否唯一

查找——顺序查找和折半查找

1.

注意：（2）

查找——散列表

1.

注意：（1）的装填因子（2）的查找失败次数

2.

排序——交换排序

1.

注意：快速排序

排序——选择排序

1.

注意：即维护一个当前状态下满足条件的数据结构

排序——归并排序，基数排序，计数排序

1.

注意：分析（3）

排序——外部排序

1.

注意