期末数据结构复习的一点笔记

选择 2*10
填空 1*20
主要形式为概念题和计算题

算法应用题 
二叉树序遍历、哈夫曼树、最短路、最小生成树、拓扑序、关键路径
画图解决问题+概述算法思路+复杂度分析

程序填空题
二叉树序遍历、拓扑排序、堆排序

暂未包含：
程序阅读&程序设计

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

1、绪论

• 数据，对客观事物的符号表示，图像声音等。

  数据元素是数据的基本单位，如学生记录。

  数据项是不可分割的最小单位，如姓名学号。

  数据对象是具有相同性质的数据元素的集合。

  数据结构是互相之间存在关系的数据元素的集合。数据结构={D、R}构成。

  数据结构三要素：逻辑结构、存储结构、数据运算 （罗村树）

• 逻辑结构分4类：线性，树，图，集合。

  逻辑结构包括线性（线性表、栈、队列）和非线性（树、图、集合）结构。线性结构的特点：所有成员处于一个序列，有且仅有一个直接前驱和后继。

  存储结构包括顺序、链式、索引、散列存储。 （顺联锁伞）

• 算法的五个特征：有穷性、确定性、可行性、输入、输出 （有缺课出入）

2、线性表、栈和队列、串

线性表

按照存储结构的不同，分为顺序存储和链式存储分为2类。

1、顺序表（vector）
定义：由相同类型的数据元素构成。 每个元素有且仅有一个前驱和后继。
特点：由一组地址连续的存储单元依次存储。

2、链表
单链表：一个指针指向后继节点。
双链表：两个指针指向前驱和后继节点。
循环链表：没有指向null，判空条件为next指针等于头指针。



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

栈和队列

操作受限的线性表

1、栈
后进先出，可以顺序和链式存储。
共享栈，即对顶栈。

2、队列
先进先出，可以顺序和链式存储。
循环队列：fr==ed


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

串

有多个字符组成的有限序列。
串是一种特殊的线性表，特殊性体现在数据元素可以是字符。

1、模式匹配算法：
简单匹配，求子串在主串中的位置
改进匹配：KMP算法及优化

2、矩阵的压缩存储：
对称矩阵，上下三角矩阵等
对称矩阵，下三角放入一位数组 B[n(n+1)/2]中，Aij对应i(i-1)/2+j-1或者代换aij=aji
上三角矩阵（含常量c），n(n+1)/2+1。aij=（n+n-i+2）(i-1)/2+(j-i)


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

3、树与二叉树

树的基本概念（选择题）

• 节点的度：节点的孩子个数。 树的度：树中节点的最大度数。

  树中节点数 = 总度数+1。（重要）

  总度数 = 边数的2倍。 （重要）

• 树的深度是从上往下的，高度是从下往上的，值都一样。

  度为m的树中，第i层上最多有m^i-1个节点。

  高度为h的m叉树中，最多有(m^h-1)/(m-1)个节点

• 有序树左右节点无法互换。

二叉树概念（选择题）：

• 父节点编号为i/2。

• 叶子节点个数 = 度为2的节点数+1，即n0=n2+1。

  证明， 因为n = n1+2*n2+1， 且n=n0+n1+n2。

• 第k层有2^k-1个节点。

• 存储方式

  顺序存储：构造成完全二叉树，用0填空，层次存入数组。

  链式存储：指向左右孩子指针。

• 遍历：先序，中序，后序，层次（大题）

• 树转二叉树：在兄弟节点间加跟线，根节点只保留第一个孩子的连线。

  森林转二叉树，每棵树都先转二叉树，然后兄弟节点连线，保留第一跟，顺时针转45度。

几种特殊的树（大题）

• 二叉排序树，左子树<根节点<右子树。

  中序遍历为从小到大排序。

• 哈夫曼树

  节点带权路径长度，为任意结点到根的总和。

  树的带权路径长度，为所有叶节点的带权路径长度之和。

4、图论

图的基本概念（选择题）

• 无向完全图边数 = n*(n-1)/2， 有向图不需要除2。有向带权图又称为网。

  度数总和 = 边数的两倍。

• 存储结构

  邻接矩阵， 邻接表，十字链表，邻接多重表。判断条件。

• 图的遍历

  DFS，BFS，求遍历序列。 一次dfs，连通图。

图的应用（大题）

• 最小生成树

  Prim：去掉所有的边，任选一个顶点。选点（与当前点集最近，不构成回路）。重复直到联通即可。

  Kruskal：去掉所有的边。 选边（边权最小，不构成回路）。重复直到图联通。

• 最短路

  Dijkstra：将点集分为在最短路中的和不在的。每次去不在的中找距离最近的加入最短路加入最短路，并用其去松弛其余边。

• 拓扑排序

  AOV网，顶点表示活动，边表示活动顺序。

  每次从AOV网中选择一个没有前驱的顶点输出，并删除该顶点和所有以它为起点的有向边。

• 关键路径

  AOE网，顶点表示事件，有向边表示活动，边上权值表示活动开销。

  关键路径：从开始点到结束点的所有路径中，具有最大路径长度的路径。关键活动为关键路径上的活动，即有向边。

  事件vk的最早发生时间为最大前驱。 ve(k) = MAX{ve(j)+weight(vj,vk)};，vj为前驱。

  事件vk的最迟发生时间为最小前驱。vl(k) = MIN{vl(j)-weight(vj,vk)};，vj为前驱。

  活动的最早开始时间e(i) = 为起点的最早发生时间

  活动的最晚开始时间l(i) = 终点的最迟发生事件 — 活动所需时间。

  求关键路径：求出所有点的最早开始时间和最晚发生时间。再求出所有活动的最早和最晚发生时间。 额差d()=l()-e()。 d()=0的为关键路径。

5、查找与排序

查找的考点

• 查找

  查找表（查找结构）：用于查找的数据集合。

  关键字：数据元素中某个数据项的值，可以标识一个数据元素。主关键字可以唯一标识。

  平均查找长度：所有查找过程中进行关键字比较次数的平均值。$ASL={\sum }_{i=1}^n{P}_i{C}_i$

  Pi为查找第i个元素的概率（一般每个元素都相等，即1/n），Ci为找到第i个元素需要的比较次数。

• 顺序查找的平均查找长度为 ：成功 = ${\sum }_{i=1}^n\frac{1}{n}(n-i+1)=\frac{n+1}{2}$， 失败 = n+1。

  折半查找的平均查找长度为：成功 = $\frac{n+1}{n}lo{g}_2(n+1)-1$。

  折半查找比较次数，可以画出判定树，看路过几个节点。

• 散列表

  一种散列存储方法。

  散列函数Hash(key) = Addr。把两个不同关键词映射到同一地址称为同义词。

  （1）直接定址法： H(key) = a*key+b。（2）除留余数法： H(key) = key%p。

  散列冲突的处理方法 & 构造散列表：（大题）

  （1）开放定址法：线性探测法di=0,1,2。平方探测法di=0^2,。再散列法di=hash2(key)

  查找不成功的平均查找长度 = 查找次数（1+13+12+。。2） / 散列后的地址个数（13）=7

  （2）拉链法： 存放到线性链表中。 ^符号表示后继指针为空。

  散列表的查找长度取决于3个因素：散列函数，冲突处理方法，装填因子。

  装填因子a = 表中记录数n / 散列表长度m。 a越大，记录越满，冲突可能性越大。

排序的考点：

• 排序的概念

  稳定性， 相对位置保持不变。

  内部排序：元素全部在内存中。基于比较和移动。外部排序需要外存。

• 插入排序

  直接插入排序：假设已经排好序，插入即可。

  希尔排序：把相隔某个增量的记录组成一个子表，对各个子表进行直接插入排序。整体基本有序后，整体直接插入。

  空间O(1)，时间不确定，不稳定。一般初始是稳定的，优化后不稳定。

  e.g，取增量d=5，组成多个子表，各排一次。再取d=3，再排一次。最后取增量d=1，即整体插入排序。

• 交换排序

  冒泡排序。优化后快速排序。

• 选择排序：

  简单选择排序。优化后堆排序。

  堆指的是：根节点比左右节点小或大的二叉树。

  构造大根堆：默认序列是二叉树。

• 归并排序

• 基数排序（基于关键字的各位大小）

  先分配：先按照个位进行分类，构造链表。

  再收集：按照顺序写到一起。

  以此类推，操作十位和百位，最后就有序了。

  给生日排序，基数排序是比较快的。

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/122386955