数据结构
2019-06-25 15:38:36 0 举报AI智能生成
数据结构考研复习大纲
作者其他创作
大纲/内容
基本概念
数据结构概念
三要素
逻辑结构
线性
非线性
树
图
存储（物理）结构
顺序存储
链接存储
散列（hash）存储
索引存储
数据的运算
算法概念
特定问题的求解步骤，
是指令的有限序列
五个特性
确定性
有穷性
可行性
输入
输出
评价
正确
可读性
健壮性
效率与低存储量需求
时空复杂度
线性结构
操作
插入
删除
查找
顺序表
基本操作
插入
移动次数n/2
删除
移动次数(n-1)/2
查找
移动次数(n+1)/2
定义
链表
单链表
头节点的作用
循环链表
双向链表
静态链表
线性表的应用
栈
定义
操作
进栈
出栈
判空
共享栈
栈顶指针设置
应用
表达式求值
中缀改后缀
后缀求值
手动模拟方法
括号匹配
树、图的遍历
队列
定义
操作
进出队
判空、判满
队头、队尾指针的设置
顺序队列
循环队列
判满语句
插入语句
其他解决假溢出方法
加计数变量
加标志位
链队
特殊矩阵的存储
上下三角
对称矩阵
三对角阵
稀疏矩阵
重点题型
树形结构
树的概念
度
高度、深度
节点与度的关系
树、二叉树、森林
满、完全二叉树
定义
性质
树、森林、二叉树的转换
树的遍历
先序
中序
后序
层次
线索二叉树
构造过程及结构
定义
空指针问题
树的应用
二叉排序树
平衡二叉树
哈夫曼树
重点题型
图结构
图的基本概念
无向图、有向图（都不能为空）
完全图、连通图
子图
连通分量、强连通分量
极大连通子图
极小连通子图
网
路径
回路
简单回路
简单路径
路径和路径长度
图的存储
邻接矩阵
出度-行
入度-列
邻接表
邻接多重表
无向图
十字链表
有向图
图的遍历
广度优先
深度优先
图的应用
最小生成树
生成树
最小生成树
普里姆算法
克鲁斯卡尔算法
最短路径
狄杰斯特拉算法
弗洛伊德算法
拓扑排序
关键路径
重点题型
数组与广义表
数组
基本操作
查找
修改
多维数组表示法
A[0..a,0..b]
a+1行，b+1列
A[a][b]
a行b列
A[x:y,i:j，~，~]
有几个逗号就有几行，每一行是从x到y、i到j的整数
矩阵存储
三元组
十字链表
广义表
求给定表头表尾的表达式值
注意是否加括号，即表头可原子可表，表尾只能是表
给定广义表中元素，写取出步骤
求长度、深度
注意递归定义
e.g:A=(a,A)
动态存储
二叉树表示
先画树形图，再转换成二叉树即可
结构图
计算储存地址
普通矩阵
对称矩阵
三角阵
三（n）对角阵
排序&查找
排序
交换排序
冒泡排序
快速排序
选择类排序
简单选择排序
堆排序
插入排序
直接插入
时空复杂度
空间：O(1)
时间：O(n^2)
折半插入
时空复杂度
空间：O(1)
时间：O(n^2)
希尔排序
时空复杂度
空间：O(1)
时间：～
其他排序
归并排序
外部排序
最佳归并树
基数排序
稳定性：
稳定
不稳定
快、希、选、堆
查找
线性结构
顺序查找
折半查找
分块查找
非线性结构
二叉排序树
平衡二叉树
散列查找
构造散列函数
直接定址
除留余数法
······
冲突处理
开放定址法（公式？）
线性探测
平方探测法
再散列
伪随机数
拉链法
性能分析
散列函数
冲突处理方法
装填因子
B树
重要计算
ASL（成功、失败）
重点题型
其他知识点总结
英语缩写
收藏
职业：大专
0 条评论
下一页
