简单摘抄的概念

基础

  1. 数据、数据元素、数据项、数据结构
  2. 数据的逻辑结构和存储结构
    • 逻辑：集合、线性结构、树形结构、图状结构（网状结构）
    • 存储：顺序存储、链式存储、索引存储、散列存储
  3. 算法特性和算法设计要求
    • 有穷性、确定性、输入、输出、可行性
    • 正确性、可读性、健壮性、高效率与低存储量需求
  4. 时间复杂度和空间复杂度
  • 常见排序算法的时间复杂度
  1. 队列假溢出：存储区未满但溢出
    • 循环队列：空一个位置，区分队空队满；逻辑环，顺序存储
      • 队空：front = rear
      • 队满：front = (rear+1)%maxsize
      • 插入删除：（front/rear+1)maxsize
    • 设标记tag记录最后一次操作是插入还是删除，判断front = rear 属于那种情况，后再平移操作
    • 增设记录队列长度的变量，再平移操作
  2. 静态链表
    • 用数组来描述线性表的链式结构，指针是结点的相对下标（数组下标）
    • 预先分配连续的内存空间
  3. 头指针、首元结点与头结点的区别
    • 存储的第一个元素之前是否附设一个结点
    • 头结点优点：使对首元结点的操作与其他结点操作一致；头指针非空，使空表和非空表的操作一致
  4. 顺序表和链表的比较
    • 存取（读写）方式：是否随机存取
    • 逻辑结构与存储结构：逻辑上相邻，存储上是否相邻
    • 查找、插入与删除操作：
      • 按值查找，区分是否有序，O(n)与O(logn),可用折半查找；按序号查找，O(1)与O(n)
      • 插入删除，平均移动半个表长的元素与修改指针域
    • 空间分配：静态动态分配
  5. 快速排序优点
  6. prim（普利姆）算法和kruskal（克鲁斯卡尔）算法的区别
  7. KMP算法:
  8. 实现单链表的就地逆置
    就地指算法的辅助空间为O(1)
    对于有头结点L的链表：另设两个指针p、q分别指向第一个元素与第二个元素，首先L指向NULL，遍历链表中执行：p->next = L, L= p, p = q, q = q->next
  9. 二叉排序树的概念与算法
  • 左子树上所有结点的值均小于根结点的值
  • 右子树上所有结点的值均大于根结点的值
  • 左右子树也是二叉排序树
  • 递归查找
  1. 平衡二叉树：任意结点的不超过1
    • 平衡因子：左右子树高度差
    • 对二叉树二改进，可减少查找次数
    • 旋转调整
  2. 哈夫曼树：带权路径长度最小的二叉树（n个权值就有n个叶结点）
    构造规则：
  • 将w1、w2、... 、wn看成是有n棵树的森林，每棵树只有一个结点
  • 在森林中选出两个根结点的权值最小的树合并为一棵新树的左右子树，新树的根结点权值为其左右子树根结点结点权值之和
  • 从森林中删除这两棵树，并将新树加入森林
  • 重复上述两步，直至森林中只剩一棵树为止，该树即为所求的哈夫曼树

特点：权值越大的结点，离根结点越近；树中没有度为1的结点；
哈夫曼编码：最短前缀编码
带权路径长度：Σ（叶结点权值*路径长度）
16. 深度优先搜索遍历和广度优先搜索遍历的过程
深度：一条路走到头，撞墙回头，贪。栈。类似树的先序遍历
广度：稳扎稳打，逐步扩散。队列。类似树的层次遍历

  • 深度、广度遍历不一定唯一（可从不同顶点开始）
    贪吃蛇游戏思考：每次吃奖励，是通过一条路直冲，直达奖励，还是通过盘曲身体，慢慢靠近奖励
  1. 最小生成树的理解
    • 连通图的最小连通子图，在添加一条边就成一个环
    • 普里姆算法
    • 库鲁斯卡尔算法
    • n个结点的最小生成树有n个结点，n-1条边
  2. 二叉树的存储方式
    • 顺序结构：用数组来存储二叉树，按编号依次填入数组；占用完全二叉树的存储空间，可能浪费空间
    • 链式存储：双亲、兄弟等
  3. 大根堆与小根堆
    • 堆，一种数据结构，可看作完全二叉树
    • 任何一个非叶结点的值都不大于(或不小于)其左右结点的值
    • 堆排序
  4. 非连通图如何访问每一个结点
    • 从每一个连通分量中选择初始点，分别进行遍历
    • DFS或者BFS
  5. M阶B树和M阶B+ 树的区别
  6. 二叉树的遍历
    • 先序、中序、后序、层次遍历
  7. 装填因子 = 填入表中的元素个数/ 散列表的长度
    • 散列表长度不是求余值
  8. 栈和队列的应用
    • 受限的线性表
    • 队列，先进先出，图的BFS、二叉树的层次遍历、缓存区
    • 栈，后进后出，括号匹配、递归调用、表达式后缀中缀计算
  9. 排序方法
    - 插入类：直接插入排序、希尔排序
    - 交换类：冒泡排序、快速排序
    - 选择类：简单选择排序、堆排序
    - 归并类：二路归并排序
    - 基数排序
    不稳定排序：简希快堆；简单选择、希尔、快速、堆
  10. 内部排序与外部排序
    区别：排序期间元素是否全部放入内存中进行排序；
    内外存之间进行移动需要缓冲区
  11. AOE网：带权有向图中，以顶点表示事件，边表示活动，边上的权值表示完成该活动的开销
    - 关键路径及关键活动，总开销受关键路径（活动）的影响，开销改变是不是关键活动，有多少条关键活动，是否有部分重合