Data Structures 2021

时间与地点

时间：2-8周，周四 18:30起；9-16周，周一18:30起
地点：软件学院一楼5-104机房（在一楼）

评分

--- ACM ---

期末考试 50%
大作业0 – Bookstore/Python解释器 5%
大作业1 – STL 15%
- vector / priority queue 4%
- deque 5%
- map 6%
大作业2 – 火车票管理系统 10%
机考 10%
小作业 10%

--- 工科 ---

期末考试 40%
大作业 - STL 30%
- vector 8%
- deque 10%
- map/B+树 12%
机考 15%
小作业 15%

小作业

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

大作业0 - Bookstore （B班）

https://github.com/IvyCharon/Bookstore-2021
ddl：第0周周末

大作业1 - STL

小作业与机考题目难度	作业要求对象	题目分类（按照洛谷难度）	题目数量
1级	工科	入门、普及-	2
2级	工科&B班	普及/提高-	4
3级	B班&A班	普及+/提高	2
4级	A班	提高+/省选/NOI/IOI	3

ACM班	发布	ddl
vector（B班）/priority_queue（A班）	第1周	第3周周三23:00
deque	第1周	第6周周日23:00
map	第1周	第10周周日23:00
工科
vector	第2周	第5周周三23:00
deque	第5周	第9周周日23:00
map与b+树二选一	第8周	第14周周日23:00

在 OJ 上通过测试数据可获得 80% 的分数，code review 占 20% 的分数。
sjtu::priority_queue要求以最高O(log n)的时间复杂度实现合并操作。
sjtu::deque要求支持以不超过O(sqrt n)时间完成任意位置的插入和删除，但随机访问的时间复杂度要求降低为O(sqrt n)。
sjtu::deque的迭代器在首尾操作后也会失效。
sjtu::map的实现B班要求平衡化（可使用AVL树、红黑树、AA树等），A班要求使用红黑树完成。
对于工科的第三个STL大作业：
- 在 OJ 上通过 map (easy)，只能获得 10 分；
- 在 OJ 上通过 map (hard)，获得 12 分；
- 在 OJ 上视 B+ Tree 的通过情况，最高获得 15 分.

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

https://github.com/IvyCharon/TicketSystem-2021
发布: 第8周
ddl: 第15周周日23:00
火车票管理系统为组队作业，共15组，每组由两人组成。
要求实现一个类似于12306的火车票订票系统，该系统能将用户数据、购票数据、车次数据进行本地存储，并对其进行高效操作。
基础分 - 85%
- 性能 - 75%
  - 正确性测试 - 50%
  - 压力测试 - 25%
- 文档 - 10%
bonus - 15%
- 后端：添加缓存，B+树的空间回收实现，并发，数据库的导出/备份/增量备份/回滚
- 前端，用户友好的图形操作页面

机考

共五次机考，分别在第4、6、8、12、14周
第0次机考不计入成绩
共5题，考试时间18:30~20:30。工科做123题，B班做234题，A班做345题。

时间表

第2周

助教介绍，课程安排/作业安排介绍
- 文件:数据结构第一次上机课 3.4.pptx

第3周

用栈模拟递归
单调队列、单调栈
- 文件:第2次上机课3.11.zip

第4周

第0次机考

第5周

线段树
- 文件:线段树入门.pptx

第6周

第1次机考

第7周

前向星
- 文件:链式前向星及图的搜索.pptx
字符串选讲
- 文件:String.pdf

第8周

第2次机考

第9周

第10周

哈希
- 文件:哈希.pptx
LCA
- 文件:Lca.pdf

第12周

第3次机考

第13周

并查集
- 文件:并查集.pdf

第14周

第4次机考

第15周

拓扑排序
tarjan算法（强连通分量）

第17周

期末试卷讲解与答疑

Contact

Name	Email
周聪	cong258258@sjtu.edu.cn
史涵雯	shihanwen@sjtu.edu.cn
张洪鑫	icefox@sjtu.edu.cn
许振宇	battlin@sjtu.edu.cn
杨新宇	yang_xinyu@sjtu.edu.cn
黄臻	xmhuangzhen@sjtu.edu.cn
王天乐	wtl666wtl@sjtu.edu.cn
衡阳	wnmMrrd@sjtu.edu.cn
任一凡	ivan-ren@sjtu.edu.cn
陈雪阳	anoxiacxy@sjtu.edu.cn