《数据结构和数据库》课程回顾


2.26 | 3.5 | 3.12 | 3.19 | 3.26 | 4.2 | 4.9 | 4.16 | 4.23 | 4.28 | 4.30 | 5.14 | 5.21 | 5.28 | 5.31 | 6.4 | 6.11

6月11日课程要点

  • 元组关系演算(不在考试范围之内):ALPHA语言,侧重在检索
  • 关系数据库标准语言SQL
    • SQL的特点:综合统一,高度非过程化,面向集合的操作方式,以同一种语法结构提供两种使用方法,语言简洁,易学易用
    • 基本表的定义、删除与修改
    • 查询:单表查询、连接查询、嵌套查询(in,比较运算符)
    • 视图的定义、删除与查询(不在考试范围之内)
[
顶层]

6月4日课程要点

[顶层]

5月31日课程要点

  • 数据库绪论
    • 数据/数据库/数据库管理系统/数据库系统
    • 数据管理及其发展阶段
    • 数据模型:概念、构成要素
      概念模型:实体、联系、E-R模型
      层次数据模型(自学)、网状数据模型(自学)、关系数据模型
    • 数据库系统的模式结构:三级模式结构和二级映像功能
    • 数据库管理系统(自学):功能、组成
  • 关系数据库
    • 关系数据结构:关系、关系的性质、关系模式、关系数据库
    • 关系的完整性:实体完整性、参照完整性(自学,下次课讲例子)、用户自定义的完整性
    • 关系代数(自学,下次课讲例子):、交、广义笛卡儿积选择投影、连接、除
[
顶层]

5月28日课程要点

  • 排序
    • 插入排序:直接插入排序、折半插入排序
    • 交换排序: 冒泡排序、快速排序
      主要掌握:各种排序算法的思想、稳定性、时空性能分析
    • 快速排序:partition算法及其应用
    • 选择排序:简单选择排序、堆排序(堆的概念、筛选和建堆的算法思想)
    • 归并排序: 2-路归并排序
      主要掌握:各种排序算法的思想、稳定性、时空性能分析
  • 数据库绪论:数据
[
顶层]

5月21日课程要点

  • 查找
    • 静态查找表:分块查找(块间有序、块内无序)
    • 动态查找表:二叉排序树(二叉查找树)
      主要掌握:二叉排序树的定义与性质、查找算法、插入和删除的算法思想、查找的时空性能分析
    • 散列表
      主要掌握:冲突的解决办法、查找算法、查找的时空性能分析
  • 排序
    • 概念:排序、稳定性
    • 插入排序:直接插入排序、折半插入排序
[
顶层]

5月14日课程要点

    • 最小生成树: 普里姆算法、克鲁斯卡尔算法
    • 拓扑排序: 算法思想
      利用拓扑排序,可以判断有向图是否存在环
      对于有向无环图,利用DFS算法可以得到逆拓扑有序序列
    • 最短路径: Dijkstra算法思想(有向网中从某个源点到其余各顶点的最短路径)
  • 查找
    • 概念:静态查找表、动态查找表;查找成功、查找不成功、(平均)查找长度
    • 静态查找表:顺序查找、折半查找(二分查找, 判定树的形态与关键字的数目有关)
      主要掌握:算法思想、数据结构、算法、时间性能分析(平均查找长度)
[
顶层]

4月30日课程要点

    • 图的定义和术语:子图、连通分量、生成树
    • 图的存储结构: 邻接矩阵、邻接表
      总体(图的种类、顶点数、边/弧数);顶点信息;边/弧信息
    • 图的遍历
      • 深度优先搜索(DFS)、广度优先搜索(BFS)---会写算法
        --设置并维护访问标志数组
        --算法:基于ADT Graph;基于MGraph;基于ALGraph
      • 遍历序列和生成树(森林)
    • 图的连通性:利用DFS(BFS)可以求得图的各连通分量
    • 最小生成树: MST性质
[
顶层]

4月28日课程要点

  • 树和森林
    • 树的存储结构:孩子兄弟表示法
    • 森林与二叉树的转换: 二叉链(孩子兄弟链~左右孩子链)
    • 树和森林的遍历: 先根遍历(对应二叉树的先序遍历),后根遍历(对应二叉树的中序遍历)
  • 赫夫曼树及其应用
    • 赫夫曼树的定义,性质和构造算法
    • 赫夫曼编码
    • 图的定义和术语:连通性
[
顶层]

4月23日课程要点

  • 二叉树
    • 先序/中序/后序遍历的应用: 如何带回多个值?如何传递中间结果?
      求二叉树先序遍历的第k个结点的值。
      求二叉树中值为x的结点的直接前驱。
    • 层次遍历: 辅助数据结构-队列
    • 层次遍历的应用: 判断一棵树是否是完全二叉树?
  • 树和森林
    • 树的存储结构: 双亲表示法,孩子表示法
[
顶层]

4月16日课程要点

[顶层]

4月9日课程要点

  • 数组
    • 数组的定义与表示:特殊的线性表(元素类型都为原子或者都是定长线性表)
    • 特殊矩阵的压缩存储:按规律确定压缩存储方法,重点是地址变换公式
    • 稀疏矩阵的压缩存储:三元组顺序表,十字链表
  • 树和二叉树
    • 树的定义和基本术语
      • 结点:叶子(终端结点)、分支结点(非终端结点)、内部结点、结点的度和深度
      • 结点间的关系:孩子-双亲、祖先-子孙、兄弟、堂兄弟
      • :树的度和深(高)度、无序树和有序树
    • 二叉树的定义: 二叉树 vs. 度小于等于2的有序树
[
顶层]

4月2日课程要点

  • 栈与递归的实现
    • 例子N皇后问题
    • 递归及函数调用的实现:系统工作栈
  • 队列
    • 队列的定义:特殊的线性表,运算受限FIFO,队头/队尾
    • 队列的表示与实现
      • 类型定义以及约定,如rear指向什么?
      • 队空、队满; 初始化空队、入队、出队
      • 难点:循环队列

      • 删除时前移n-1个元素-->出队时不前移-->假上溢-->循环队列-->队空和队满的条件一样-->如何区分队空和队满?
        循环队列中存放元素的连续空间的下标下界不为0时,该如何实现基本操作?
  • 应用举例:离散事件模拟
[
顶层]

3月26日课程要点

  • 栈的定义:特殊的线性表——运算受限(插入/删除)FILO,栈顶/栈底
  • 栈的表示与实现
    • 类型定义:顺序栈、链栈
      注意约定:如top指向什么?
    • 基本操作:栈空、栈满; 初始化空栈、入栈、出栈
  • 应用举例:表达式求值
    • 表达式的表示:前缀式(波兰式)、中缀式、后缀式(逆波兰式)
    • 各种表达式的计算:括号?操作数栈?操作符栈?计算的时机?
  • 栈与递归的实现
    • 显式的递归定义(数据结构、递归过程)
    • 问题求解的方法:大问题分解成若干小问题来求解
    • 例子:阶乘、表的元素查找、Hanoi
[
顶层]

3月19日课程要点

  • 基于线性表的算法设计(以例2-2为例)
    注意理解不同存储结构的线性表在解决同一实际问题时的差异
    顺序表L 链表L
    位置指示器 绝对地址p = L.elem; 或相对地址(即下标)pos = 0; 绝对地址:无头结点p = L; 或有头结点 p= L->next;
    当前元素的值 *p 或 L.elem[pos] p->data
    位置指示器的后移 p++ 或 pos++ p=p->next
    位置指示器的边界判断 p < L.elem+L.length 或 pos < L.length 非循环链表p!=NULL 或 循环链表p!=L
    其他 顺序表初始化时,用于存放元素的连续空间的分配 重新分配结点空间?重用已有的结点空间?
  • 双向链表:插入、删除
  • 其他链表表示:增加length、尾指针
  • 有序表---是数据结构,不是存储结构
  • 一元多项式的表示及相加
[
顶层]

3月12日课程要点

  • 线性表的顺序存储(映像)——顺序表
    • 基本操作的实现
      • 插入操作(上溢,插入位置的合法性)
      • 删除操作(下溢,删除位置的合法性)
    • 基于顺序表的算法设计:例2-1
  • 单链表
    • 概念:结点、指针域(链域)、链、头指针、头结点
    • 类型定义LNode, LinkList
    • 基本操作的实现:取第i个元素(GetElem), 插入(ListInsert), 删除(ListDelete)
    • 链表的创建:头插法, 尾插法
      注意
      1. 本书所陈述的抽象数据类型及其实现在实际的程序设计语言中并未直接提供;
      2. 一些语言的支持库提供了部分数据结构的实现,如C++ Standard Template Library 中的list
      3. 一个基本操作的接口定义是可以根据实际需要而略微变化的,如取第i个元素可以定义为
                                    Status GetElem(LinkList L,int i, ElemType &e )
        也可以定义为: LNode *GetElem(LinkList L,int i)
      4. 通过画图指导链表中的算法设计
  • 循环链表
[
顶层]

3月5日课程要点

  • 算法的的评估(时间复杂度、空间复杂度):事前评估
  • 线性表
    • 线性表的逻辑特征
    • ADT List的定义
    • 基于ADT List的算法设计 :例2-1,例2-2
    • 线性表的顺序存储(映像)——顺序表
      • 特点: 逻辑上相邻,物理上必然相邻;随机存取
      • 类型定义:方案1—定长顺序存储;方案2—增量式顺序存储
      • 基本操作的实现
        • 理解malloc, free和realloc的含义,理解Status和一些宏(如INFEASIBLE等)的含义
        • 初始化操作
        • 求表长、取第i个元素、按值查找
        • 插入操作(上溢,插入位置的合法性)
[
顶层]

2月26日课程要点

  • 程序 = 数据结构 + 算法
  • 数据、数据元素、数据项
  • 数据结构、逻辑结构、存储结构
  • 数据类型与抽象数据类型
    • 伪C语言与C语言的区别
    • C语言中的值传递
    • C++中的引用参数->==>用于表达算法中的变参
    • 辨别C程序中标识符的规则:算符的优先级和结合性
  • 算法的定义、特点,算法的评估(时间复杂度)
[
顶层]