跳转至

1708789779

数据结构基础

CS 专业基础 AI 专业基础 IS 专业基础

课程学习内容

FDS 按专题授课，主要介绍栈、队列、树、堆、并查集、图等数据结构，以及最短路、搜索、网络流、排序、哈希等算法。求各专题之间联系不大，不存在前一节课不听后一节课就听不懂的情况。课程难度适中，课程要求主要是掌握简单算法的算法流程（会手算具体样例、会写代码实现），对于一些相对复杂的算法（比如网络流、Tarjan 算法）以及复杂度和定理的证明点到为止，一般只在作业中要求，不会出现在考试中。

以下有两个版本的课程内容大纲，自测版的部分条目以问题的形式出现，答案在完整版里。该大纲可以用于开课前的自测，明确自身定位，以便制定学习计划；也可以用于考前复习。在浏览大纲的同时，可以标记自己不明确的定义以及不清楚的算法，在上课期间重点关照；而如果你对整个专题都非常熟悉，则可以考虑只看 ppt 不听课，用这节课时间做点别的事情。

课程内容大纲（自测版）
  1. 第一节课介绍分数构成、作业形式等重要内容！
  2. 复杂度分析
    • 大 O、大 Ω、大 θ、小 o
  3. 栈和队列
    • 中缀表达式转后缀表达式
    • 中缀表达式转前缀表达式
    • 表达式树
  4. 树
    • 前、中、后序遍历
    • threaded binary tree 线索二叉树
    • 完全二叉树、满二叉树
  5. 二叉搜索树
    • 查找、插入
    • 删除根节点
    • 支持删除指定节点 ( 带 lazy tag 后的查找和删除 )
  6. 堆
    • 线性建堆及其复杂度证明
    • push & pop
    • d-heap（满足堆性质的 d 叉树）:
      • push & pop 复杂度
      • 父亲编号、最大的儿子编号、最小的儿子编号
  7. 并查集
    • union-by-size 及其复杂度证明
    • union-by-depth 及其复杂度证明
    • 路径压缩
  8. 图
  9. 最短路算法
    1. Floyd
    2. Dijkstra
      • 堆优化
      • 可以处理负权边吗？
    3. Bellman-Ford & SPFA
    4. 拓扑排序
  10. 其他图论算法
    1. 最小生成树
      • Kruskal
      • Prim
    2. 最大流
      • 最大流最小割定理，平面图最大流的对偶图方法，及其局限性（课程不涉及，但可以加快手算最大流的速度）
      • 增广路算法：
        1. 什么是反向边？
        2. Dinic & 当前弧优化
  11. DFS 的应用：
    1. 欧拉路径（回路）和哈密尔顿路径
    2. 无向图的双连通分量
      • 定义（一个关节点可以出现在多个双连通分量中吗？）
      • tarjan 算法
    3. 有向图的强联通分量
      • tarjan 算法
  12. 排序：
    • 插入排序
    • 希尔排序
    • 堆排序
    • 快速排序
    • 归并排序
    • table sort
    • bucket sort（桶排序） & radix sort（基数排序）
    • 其他
      • 稳定的排序
      • 基于交换的排序的复杂度下界证明
  13. Hash
    • 哈希函数：自变量是整数的情况，自变量是字符串的情况
    • 开放寻址法
      1. linear probing 循环找下一个位置直到找到空位
      2. quadratic probing: 往后找 1, 2, 4, ... 个位置
      3. double hashing: f(i)=i*hash2(x)探测的步长与 key 值有关
      4. rehashing
      5. seperate chaining: 对相同哈希值用链表存储
    • 删除（tag）

任课教师

双语教学，但是英语讲的一般，有时含混不清。上课基本是读 ppt，看 ppt 不听课的同学可以完全不用担心上课讲到了 ppt 上没有的内容。

上课不点名，但小测不会提前通知。如果是线下教学，小测是手写代码上交，也可以在下课前在钉钉拍照上交；如果是线上教学小测在 pta 上进行。

关于总评成绩，期末考试成绩不能覆盖期中，bonus 可以直接补在总分里。project 助教给分不错，分数基本与报告长度成正比，但方差较小（所以卷报告长度拿分效率不高）。

陈越老师是个比较有个性的老师，导致她查老师的评分比较低，但只要不触碰她的雷区，她其实是个非常好的老师。陈越的规则意识非常强，她提到的纪律就是铁律，要是违反的话她将会按照跟约定好的惩罚措施实行惩罚，所以一定要认真听她讲的规矩，按照规矩办事。下面是一些一定要注意的雷区：

  1. 作业的函数题和编程题一定不要网上复制代码！！！！一定不要抄别人的代码！！！！她每次作业都会使用 PTA 的查重功能，以第一次全部通过测试的代码作为查重的指标，一旦你被查重，她将让你去退课等重修，不退课只能挂科！！！非常严重！！！写她的作业一定要记住函数题和编程题一定要自己写！！不要想着拿网上的代码来测试 OJ 有没有错误！！！不要将自己的代码发出去给别人看，免得被抄！！！！
  2. 她规定 project 的互评不能泄露个人信息，否则本次 project 互评为 0 分，project 的注释要为代码的 30%，否则本次互评直接扣 50 分，这两条必须要严格执行，即使你觉得无意义，别的班或许会通融，但是在姥姥的班，一旦发现将按照这规定的惩罚措施执行。

最雷的点也就差不多以上这些，总体来说就是认真听她的规矩，按照规矩办事，一旦出了什么问题，一定要充分利用自己申诉的权利，特别是被误判或者被恶意扒个人信息的时候，这个时候姥姥会给你申诉的机会和空间的。除了这些雷点，陈越老师其实是个非常好的老师，讲课讲的非常好，上课像慈祥的老奶奶，英语非常标准，在较难的地方会用中文来解释，上她的课能学到很多东西。除此之外，她的期中、小测都是在 PTA 上进行，都是作业题，或者跟作业题难度差不多，难度适中，不会有变态的题目，好好做作业这两块的分数都不会差的，她的课有 bonus 能够补平时分，要是 project 选 hard 难度的话相当于你的总分比别人多 5 分，给分也是非常好的。由于评分的关系选上她的课难度不会太高，推荐规则意识比较强的同学选她的课。

中文讲课，ppt 英文，讲课内容完全参照 ppt。

不点名不小测（都不占分数），但是有可能会在课前在 pta 开一套题目作为签到（分数计入作业，但是 21 级只是口头说过，并没有这样搞过）。

总评成绩 bonus 不溢出，但 hard 多的 5 分总评可以溢出。期末分数占比是最重的（50%），需要认真对待。

中文讲课，上课节奏适中，知识点讲解也比较清楚，也会有适当的代码讲解。

上课不点名，但是需要注意的是 22 级有三次不提前通知的小测，占总评 10 分。每次小测都是一道作业原题，非常简单，并且只要求写答案，不需要过程，因此基本到课了本次小测就是满分。如果错过一次小测，相当于总评丢掉了 3.3 分，非常不值得。而且鉴于 yzq 老师讲课挺不错的，建议没有 fds 基础的同学不要翘课。

分数构成

  • 作业 10%：全部在 pta 上布置
  • quiz 10%：2 到 3 次，期中考和期末考前两三周小测概率较大，可能会线下要求手写代码
  • 期中考 15%
  • 期末考 40%
  • lab 25% 或 30%
    • lab 分数 = 助教打分 50% + 互评 50%
    • lab 有 normal 和 hard 两个可选分级，前者 25 分，后者有 30 分。选择 hard 的同学总分是 105 分，超过 100 的分数会被舍掉。
  • bonus 4%：一般可以直接补在总分里，也有可能只能补平时分，视不同老师而定。
  • 总体来看，平时分 60%，期末 40%，细则如下：
  • 作业：10%
  • 课前小测：10%
  • 期中：15%
  • 期末：40%，如果你的期末考的比期中要高，那么期中的分数将会调为期中的分数
  • project：25%(normal) / 30%(hard)，选 hard 的同学多出 25 分的部分将直接加在总分中，不算在平时分的 60% 中
  • bonus：4 分，这四分 Bonus 用于补平时分，平时分补满 60 分为止。
  • 其他细则：总评超过 100 分的同学除非你所有分数都是满的，否则一律为 99。要是全满，则总评为 100。
  • 期末 50%
  • 平时分 50%
    • 期中 15%
    • homework 10%
    • project 25%
    • bonus 4%

平均分四个部分加起来和 50 取 min（不溢出），期中 project 分数不论 normal 还是 hard 都是 100 分满。但是选了 hard 的可以在总评上额外多加 * 0.05 分。

  • 期末 40%
  • 平时分 60%
    • 期中 15%：期末成绩可覆盖期中成绩
    • 作业 10%：每周作业在 pta 上布置，题量不大
    • project
      • normal 25%，hard 30%, hard 多出来的五分可以溢出到总评
    • quiz 10%：22 级总共 3 次 quiz，每次一道题，并且是作业原题，详见任课教师中的评价
    • bonus 4%：bonus 为两道编程题，每道两分，在 pta 上完成，此部分 bonus 只加在平时分上，不能溢出到总评

课程教材

官方教材是《Data Structures and Algorithm Analysis in C》，可以在 zlibrary 上搜索书名进行下载。但教材上课并不会用到，老师一般会基于 ppt 进行讲解。对于不明白的算法，百度或者 google 搜索算法名字，用别人的博客进行学习是一个效率较高的选择。对于课上教授的经典算法和数据结构，网上有非常多全面且细致的博客，一般不需要买其他教材。

参考笔记

课程学习建议

在制定 FDS 的学习计划之前，可以先利用上面的大纲进行自测。如果你对大部分数据结构比较熟悉，对大部分算法能够大致说出流程或者知道核心思想（比如快排的哨兵、最大流的反向边），对小部分知识点听说过但是不甚了解，并且对自己的 C 语言功底比较有自信，那么你可以选择只在这门课上花费一周两课时甚至更少的时间。如果你对于每个专题都或多或少有些不了解的地方，并且有些专有名词是第一次看见，那么你需要在这门课上投入更多的时间。

对想要为 FDS 投入时间的同学

建议好好听课，或者去听你觉得讲的好的老师的课。

其次，作业非常重要，基本涵盖考试会考到的所有知识点。作业请认真完成并及时订正。另外 FDS 有不少杂乱的小知识点，有一个笔记本记录下自己容易忽视的部分，会大大减轻考前复习的压力，好记性不如烂笔头嘛。

所以每周花费的时间大概是 2 课时听课，2 到 3 课时作业以及 0 到 1 课时的订正整理和其他事项。

如果你觉得仅仅完成课内任务还不够，可以选择刷期中期末真题。

对不想为 FDS 花费很多时间的同学

课可以不听，在你预感要小测的时候去教室坐着就行了。但是有两个部分我觉得是有必要保证完成的——作业和整理。

首先是作业。作业基本涵盖考试会考到的所有知识点，甚至有原题或者非常相似的题。做作业和订正是基本盘，需要认真对待。即使你已经非常熟悉某个专题的知识点了，也需要通过作业接触一些毒瘤题，以及筛查一下有没有之前没注意到的知识点。并且对于熟练工而言，每周作业花不了很多时间。

其次是整理。整理的好处毋庸讳言，特别是像 FDS 这样考试分数占比较大的科目，整理能为你的期中期末考提分不少。并且 FDS 知识点较少，并且分专题，所以非常好整理。你可以在考前去看别人的整理，或者跟着课程进度做笔记，或者在期末自己从头梳理一遍。对于不想花太多时间的同学，在开学时就找到一份不错的知识点整理，在此基础上进行修改时效率最高的。

Project Report 避坑指南

FDS 是同学们第一次接触“互评”的课程。在互评中你的程序和报告会交给三位课友进行打分，而你也需要给三位同学打分。为了保证公平，你需要保证你的程序和报告不泄露个人信息。并且报告的评分标准非常繁杂，建议面向要求编写报告。详细的报告要求会在第一次互评时给出，但当你看到报告要求时报告的提交已经截止了。为了不被严格的互评人背刺，最好提前对互评要求有一定的概念，下面罗列了报告每一章节容易忽视的注意事项（并不全面，详细要求见老师给出的文档）。

  1. 删除个人信息（老师会发一个 ppt 专门教怎么删除个人信息）
  2. 封面
    • 标题 + 日期 ( 没写 -1，下面同理 )
  3. Chapter 1 Introduction
    • 自己描述题目，不能照搬照抄 (-3)
  4. Chapter 2 Algorithm Specification
    • 伪代码 + 自然语言描述
    • 不要直接贴项目代码
  5. Chapter 3 Testing Result
    • 每一组测试样例都要写 purpose (-3)
    • 至少一组综合测试样例 (comprehensive test case)，数据规模的上下边界各一组，极限情况 (extreme case) 必须测试到，再加 n 组随机数据 (-4，一般不会要求非常严格 )
    • 可以搞点图表来展示运行时间
  6. Chapter 4 Analysis and Comments
    • 分析复杂度需要写过程不能直接给出结果 (-4)
      • 例如循环的复杂度要这么写：The loop runs for N times and the complexity of each loop body is O(1), so the total time complexity is O(N).
    • 时间和空间都要写到
  7. 代码
    • 一定要多写注释，至少写到代码总长度的 30% 以上 (-50，某些老师如 cyll 管得比较严 )
  8. README
    • 怎么编译？怎么运行？怎么输入？期望的输出？最好能给一组样例输入输出