A3阶段 第六课 习题课-基础数据结构

2025年6月28日

学习时长

约1.6小时

难度

A3阶段/CSP-J

标签

数据结构

讲师

王骏峣

基础数据结构

线性数据结构

  1. 数组
  2. 栈
  3. 队列
  4. vector

栈

特性：先进后出 前往查看具体内容 用处：

  1. 题目描述符合先进后出性质
  2. 括号匹配问题
  3. 表达式求值问题

队列

特性：先进先出，类比生活中的排队 前往查看具体内容 用处：

  1. 题目描述符合先进先出的性质
  2. 广度优先遍历(BFT)

vector

特性：是可变长数组 前往查看具体内容 用处：

  1. 邻接表
  2. 网格图中使用的总各自数量有限，但n,m较大

非线性数据结构

  1. 树
  2. 图

树

特性：由n个点和n-1条边构成的连通结构 前往查看具体内容

栈

特性：由若干个节点和若干条节点之间的边构成(类比生活中的地图) 前往查看具体内容 图的存储

存储方式 优势 劣势
邻接矩阵 O(1)回答某两个点之间是否有边 需要n2的内存，访问某个点的所有出边需要O(n)的时间复杂度
邻接表 内存占用为O(m) 回答某两个点之间是否有边相连需要O(logn)的时间复杂度
n>5000绝对不要用邻接矩阵 图的遍历 需要求无权图单源最短路用广度优先遍历，否则建议用深度优先遍历

第一题 「Wdoi-4」兔已着陆【必做】

前往

第二题 [NOIP2002 普及组] 选数

前往

第三题 [GESP202409 七级] 小杨寻宝

前往

第三题 [COCI2014-2015#3] DOM

前往