跳转到内容

Data Structures 2022

来自ACM Class Wiki

时间与地点

  • 时间：1-16周，周日 18:30起
  • 地点：软件学院一楼5-104机房 （在一楼）

评分

ACM

  • 期末考试 50%
  • 机考 10%
  • 小作业 10%
  • 大作业1 – STLite 20%
    • vector 4%
    • priority queue 5%
    • linked_hashmap 6%
    • map 5%
  • 大作业2 – 火车票管理系统 10%

工科

  • 期末考试 40%
  • 机考 15%
  • 小作业 15%
  • 大作业 - STLite 30%
    • vector 5%
    • list 5%
    • priority_queue 7%(9%)
    • linked_hashmap 8%
    • map/bpt 12%(15%)

小作业

  • 每两周发布一次，每次作业考察上机课的内容
  • 成绩只取决于AC与否，不考虑时间（penalty），做完即满分
  • OJ: https://acm.sjtu.edu.cn/OnlineJudge/
  • 若无声明，本课程中所有大小作业不能用STL
  • 可用的头文件：cstdio, cstring, cmath, iostream

大作业1 - STL

ACM班 发布 ddl
vector 第1周 第3周周六23:00
priority_queue 第3周 第5周周六23:00
map 第5周 第8周周六23:00
linked_hashmap 第8周 第10周周六23:00
工科
oop练习 第1周 第3周周六23:00
vector+list 第3周 第6周周六23:00
priority_queue 第6周 第9周周六23:00
linked_hashmap 第9周 第11周周六23:00
map与bpt二选一 第11周 第16周周六23:00
  • 在 OJ 上通过测试数据可获得 80% 的分数，code review 占 20% 的分数。
  • sjtu::priority_queue要求以最高O(log n)的时间复杂度实现合并操作。
  • sjtu::map的实现B班要求平衡化（可从AVL树、红黑树、AA树中选择），A班要求使用红黑树完成。
  • sjtu::linked_hashmap要求以均摊O(1)的复杂度实现插入、查找和删除，并支持按照插入顺序进行迭代器遍历。
  • 对于工科的第三个STL大作业：
    • 在 OJ 上通过 map (easy)，可以获得 10 分；
    • 在 OJ 上通过 map (hard)，可以获得 12 分；
    • 在 OJ 上视 B+ Tree 的通过情况，最高获得 15 分。

大作业2 - 火车票管理系统

  • https://github.com/ACMClassCourse-2021/TicketSystem
  • 发布: 第10周
  • ddl: 第18周周日23:00
  • 火车票管理系统为组队作业，共16组+1人，每组由一名A班同学与一名B班同学组成。分组方式为自行组队。
  • 本次作业要求实现一个类似于 12306 的火车票订票系统，该系统向用户提供购票业务相关功能，包括车票查询、购票、订单操作等，以及向管理员提供后台管理功能（包括一个特殊的回滚数据库功能）。系统需将用户数据、购票数据、车次数据进行本地存储，并对其进行高效操作。
  • 基础分 - 85%
    • 性能 - 75%
      • 正确性测试 - 35%
      • 压力测试 - 30%
      • 回滚测试 - 10%
    • 文档 - 10%
  • bonus - 15%
    • 后端: 缓存/空间回收/命令行交互拓展/并发/增量备份
    • 前端: 提供一个用户友好的图形操作页面，推荐实现跨平台的前端，如网页，Qt 等。

机考

  • 共七次机考，在第3周开始的奇数周
  • 第0次机考不计入成绩
  • 共6题，考试时间18:30~20:30。工科做123题，B班做234题，A班做456题。

时间表

第1周

  • 助教介绍，课程安排/作业安排介绍

文件:2022数据结构上机课介绍.pptx

第2周

  • A班
    • 树链剖分
    • 主席树

文件:数据结构A班第一次上机课.zip

  • B班
    • KMP
    • ST表

文件:数据结构B班第一次上机课.zip

第3周

  • 第零次机考（不计入成绩）

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=268

第4周

  • A班
    • dp优化

文件:数据结构A班第二次上机课.zip

  • B班
    • 单调栈
    • 单调队列
    • 用栈模拟递归

文件:数据结构B班第二次上机课.zip

第5周

  • 第一次机考

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=284

第6周

  • A班
    • 网络流

文件:数据结构A班第三次上机课.zip

  • B班
    • lca
    • 字典树

文件:数据结构B班第三次上机课.zip

第7周

  • 第二次机考

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=289

第8周

  • A班
    • 点分治
    • 虚树

文件:数据结构A班第四次上机课.zip

  • B班
    • 线段树
    • 树状数组

文件:数据结构B班第四次上机课.zip

第9周

  • 第三次机考

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=305

第10周

  • A班
    • LCT

文件:数据结构A班第五次上机课.zip

  • B班
    • 哈希
    • 并查集

文件:数据结构B班第五次上机课.zip

第11周

  • 第四次机考

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=317

第12周

  • A&B班
    • 图算法选讲

文件:数据结构第六次上机课.zip

第13周

  • 第五次机考

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=329

第14周

  • A班
    • AC自动机

文件:数据结构A班第七次上机课.zip

  • B班
    • 基础dp

文件:数据结构B班第七次上机课.zip

第15周

  • 第六次机考

https://acm.sjtu.edu.cn/OnlineJudge/contest?contest_id=341

第16周

  • 期末笔试复习

文件:数据结构第八次上机课.zip

Contact

ACM班助教

Name Email
夏天 xia_tian@sjtu.edu.cn
倪文韬 wennitao@sjtu.edu.cn
吴叶鑫 wuyexin_libro_i131@sjtu.edu.cn
洪熠佳 hyj542682306@sjtu.edu.cn
韦中敬 wzj2001@sjtu.edu.cn
林杨楠 fourest_lyn@sjtu.edu.cn
潘开森 pks0813@sjtu.edu.cn
何夏麟 hexialin1129@sjtu.edu.cn
王硕 Shuo_Wang@sjtu.edu.cn

工科助教

Name Email
刘泓轶 liu.hong.yi@sjtu.edu.cn
廖伟鑫 liaoweixin@sjtu.edu.cn
郭锦沛 mike0728@sjtu.edu.cn
检索自“https://acm.sjtu.edu.cn/w/index.php?title=Data_Structures_2022&oldid=4609”