# 数据结构·知识综述 识别卡 2.0

- **层级**: L4 · 系统性前沿层（课标骨架填充，待终裁）
- **状态**: pending（骨架填充 · 待设计者终裁）
- **领域**: 计算机科学
- **教育层级**: E4（大学）· 分布：骨架 19 知识点 / 内容 19 条

## 核心主张

数据结构（课标骨架 19 知识点填充）：现象+规律，简单词汇，规律性出现即知识……

## 条件空间

- **观测位置**: 数据结构（大学层）外部观测位
- **观测工具**: 课标骨架 + 现象规律性判定
- **时间窗口**: (0.0, 9999999999.0)
- **存在约束**: 大学学段知识按课标骨架定位；通用现象/规律不受版权保护，开源非盈利知识库提取知识点而非复制教材表达

## 出招

- **触发**: 涉及数据结构议题
- **行动**: 以数据结构知识点（大学层）回应
- **克制**: 越级使用高于大学层级的未学概念

## 知识点内容（按骨架填充）

### B树与B+树

B树：多路平衡搜索树，每个节点多关键字。B+树：内节点只存索引、叶子存数据且链表相连。B+树适合磁盘存储（扇区大小匹配）、数据库索引。

### 二分查找

二分查找：有序数组中查找，每次减半，O(logn)。条件：数组有序。变体：查找边界、旋转数组。二分答案（最大化最小值）。

### 二叉搜索树

二叉搜索树（BST）：左子树小于根、右子树大于根。查找、插入、删除O(h)。中序遍历有序。BST退化为链表（插入有序数据）——需要平衡。

### 二叉树

二叉树：每个节点至多两个子树。遍历：前序、中序、后序、层序。二叉树性质（第i层最多2的(i-1)次方节点）。完全二叉树、满二叉树。

### 哈希表

哈希表：键映射到桶（哈希函数）。冲突解决：链地址法、开放寻址。负载因子与扩容。哈希表查找平均O(1)。应用：字典、缓存、去重。

### 图表示与遍历

图：顶点+边。表示：邻接矩阵（稠密）、邻接表（稀疏）。遍历：深度优先DFS（栈/递归）、广度优先BFS（队列）。遍历应用：连通性、路径。

### 堆

堆：完全二叉树，父节点大于（最大堆）或小于（最小堆）子节点。堆操作：插入、删除堆顶O(logn)。堆排序、优先队列、Top-K问题。

### 复杂度分析

时间复杂度：算法运行时间随输入规模的增长（大O记号：O(1)、O(logn)、O(n)、O(nlogn)、O(n方)）。空间复杂度：额外内存。复杂度决定算法可行性。

### 字符串匹配

字符串匹配：在主串中找模式串。朴素算法O(nm)。KMP算法（前缀函数）O(n+m)。BM算法。字符串匹配是文本处理基础（搜索、编辑）。

### 平衡树

平衡树：保持树高O(logn)。AVL树（严格平衡，旋转）、红黑树（近似平衡，颜色约束）。平衡树保证最坏情况性能。STL map/set用红黑树。

### 并查集

并查集：不相交集合的合并与查询。路径压缩、按秩合并——接近O(1)摊还。应用：连通分量、Kruskal、动态连通性。

### 拓扑排序

拓扑排序：有向无环图（DAG）的线性排序，每条边u→v中u在前。Kahn算法（入度）。应用：课程安排、任务依赖。环检测。

### 数组与链表

数组：随机访问O(1)、插入删除O(n)。链表：插入删除O(1)（已知位置）、随机访问O(n)。单链表、双链表、循环链表。选择依据：访问vs修改频率。

### 最小生成树

最小生成树（MST）：连接所有顶点且总权最小的树。Prim算法（加点）、Kruskal算法（加边，并查集）。MST应用：网络布线、聚类。

### 最短路径

最短路径：Dijkstra（非负权，贪心）、Bellman-Ford（可负权）、Floyd（所有对，动态规划）。应用：导航、网络路由。

### 栈与队列

栈：后进先出（LIFO），操作push/pop。应用：函数调用、表达式求值、括号匹配。队列：先进先出（FIFO），操作enqueue/dequeue。应用：任务调度、BFS。

### 比较排序

比较排序：冒泡、选择、插入（O(n方)）、希尔、归并（O(nlogn)）、快速排序（平均O(nlogn)，最坏O(n方)）、堆排序（O(nlogn)）。稳定性。

### 线性时间排序

线性时间排序：计数排序（范围小）、基数排序（按位）、桶排序（分布均匀）。非比较排序，条件：数据范围/分布可假设。

### 跳表与Trie

跳表：多层链表加速查找，O(logn)。Redis有序集合用跳表。Trie（前缀树）：字符串集合的树结构，前缀查询。应用：自动补全、词典。

## 识别卡明细

- **observation_position**: 从数据结构（大学层）结构端透视
- **existence_preset**: 默认存在预设：大学学段知识按课标骨架存在
- **irreducible_start**: 不可约起点：数据结构的核心概念
- **observation_method**: 有效观测方式：课标骨架知识点 + 现象规律性格式
- **time_causality**: 时间与因果结构：按课标学段递进（大学）
- **condition_boundary**: 边界：数据结构知识点按课标骨架定位学段；具体数值/例题以教材为准
- **consistency**: 自洽性评估：知识点内容为现象+规律格式，待人工审校
- **protocol_mapping**: 可映射协议概念：数据结构与条件论知识图谱的接口
- **silent_preset**: 沉默预设：知识点内容为通用现象/规律，不声称终极解释

## 关系

- 课标骨架（similar）：数据结构与 knowledge_skeleton.json 的 大学 学段对应