2025.1.16 昨天早上考的昨天晚上就出卷面分，课程组效率高的。今天查卷查完心情不错(同时发现万老师班相比其他几个班评课数目不多)，遂评。

本人：大一觉得自己物理学得依托，C学的还可以，于是run了。（非信竞党）ds这门课是现学的，所以同非信竞党可以参考一下，对竞赛党参考价值不大。

• 课程前置内容：（如果你像我一样没有信竞基础一切靠现学的话，建议可以提前回顾一下）C语言，主要看看指针、链表和数组那块。
• 课堂体验：万老师讲课水平一流，如果好好听课可以节省一些理解算法的时间（yysy教材感觉不如dsa的教材）。我是不预习党，数据结构跟着万老师课上学感觉还可以。老师会把算法一点一点讲的很细，前几课有关顺序表（链表数组）会讲的慢一点（顺便帮大家温习C语言 万老师讲到函数参数调用的时候，有几个同学不解，万老师：“你们的C语言，哎（叹气），回去好好复习一下吧”）；但是后面会提速，课程节奏是越来越快的；最后会花一周左右的时间把排序讲了，但是排序不考（KMP和排序是dsa的重点考察内容，但是咱们更高阶的ds却不考QAQ,不过还是要好好学，这块内容保研和考研都要用的）。
• 课程重点内容：本课程重点是后面的树、图、查找三章，同时务必要打好顺序表、栈和队列等前几章的数据结构的基础。我感觉很多同学对于数据结构考试的恐惧源于考试范围的未知性，我参考了历年ds和dsa这两门课的试卷，写一下重点复习的内容，希望可以帮到一些：哈夫曼树的构造和编码算法，树和森林的遍历和衍生算法，图的BFS和DFS,最小生成树的生成算法（Prim和Kruscal）,拓扑排序算法，单源最短路径的Dijkstrra算法，（floyd今年不考，以后说不定），（AOE网的那个关键路径算法dsa常考，但是ds好像近几年没考）,二叉排序树（24秋dsa考了）,二叉平衡树（今年ds考了一个有关二叉平衡树LL型单旋转平衡化的代码填空题，比较简单的就填了一个修改BalanceFactor，我挺害怕那个旋转的代码书写，事实证明应该不会考太难的，知道这个思想就行了）,B-树和B+树（主要是那个结点分裂和合并的过程，这种就是不会让你直接写代码，但是你要掌握这个算法的，比如可以画出构造的过程），哈希表的构建。几个小点：ASL平均查找长度（主要是哈希表里面），WPL带权路径长度（huffman树里面讲了）（这种给一个树你要会算，类似的比如说直接给你一个顺序表让你二分查找也要会这个算法的具体过程，给出一个输入可以求出查找次数），前缀编码（去年ds考了），利用栈的逻辑结构进行前缀（波兰式）、中缀、后缀表达式的转换（今年没考但这个感觉要会），（有同学问键树考不考，键树不考；关节点和重连通那个小节不考；线索二叉树的相关算法不考，但是逻辑结构存储结构要掌握哈（比如问你先序/中序/后序线索二叉树有几个空指针域）。免责声明：以上仅仅为个人的想法，具体考试范围以当学期的老师表述为准，若有误差为正常情况，不保证能cover到所有考点，同时每年的范围也是动态的，请依具体情况而定。
• 实验：我都是现学的，每个实验都要debug好久，实验量算中规中矩，题目历年都是差不多（甚至一样的），每个实验会给一两周的时间，还是比较充足的（万老师：保研机考的时候很多科大的学生成绩和外校的比很差，所以上机的这个能力要有…你们会感谢现在的自己的），但是每个实验要写报告介个介个呃呃嗯嗯呃呃。。。发现其他班有的要用C++写，万老师班C和C++都可。
• 作业：不多，每次布置几个算法题，难度中偏上，事实证明考试的算法题也差不多是这个难度（写写类C代码，主要会这个思想）。
• 考试：选择题、填空题、算法流程（画图，也就是说要会这个思想），算法题（手写类C）。前三parts挺简单的，30-40min可以写完，然后我后面的两个算法写了1.5hour（我菜，我反思/(ㄒoㄒ)/）
• 助教和老师回答问题都挺耐心的，acceptable。
• 有点名，无小测，qq群里发一个定位打卡的东西，大概会点4-5次吧，所以我觉得本课堂更适合像我一样打算通过上课学习的初学者，辅修人或竞赛党可以出门右拐ljl什么的。
• 给分尚未出，但是这学期这个班依旧是ds置课班（ai他们上dsa），具体情况等给分出了再写。
• 我对课程的建议是，作业答案和实验的讲解能不能早点发，感觉等到习题课的时候，基本上自己做的啥都忘了，以至于本学期的作业对我来说总体上主要是练手的效果，而未起到查漏补缺的效果。

个人错题：（ds期末 24秋）完全二叉树有5000个结点，求其中的叶子结点个数____。

错解：一个高度为k的完全二叉树的结点总数n: 2^(k-1)-1<n≤2^(k)-1,所以这个二叉树有13层。前k-1层有2^(12)-1=4095个结点，叶子结点数=最后一层结点数=5000-4095=905.

然而这是不对的，倒数第二层也有叶子结点，叶子结点数！=最后一层结点数。倒数第二层结点数目为2^(12-1)=2048,叶子结点数=905+(2048-\math.ceil(905/2))=2500.

方法2在评论区。

最后两个算法题有点忘了，记得的友友们可以贴一下哈。

出分在意料之内，看不出给分好坏。总体上说你的总评主要取决于考试吧，实验和作业占比不会像ics那么高。

现在是深夜两点四十分……早上八点半考试，最后一场了

期末周破防的我想知道自己能否看完万老师的PPT……

旧事重提: 非常后悔当时听课不够认真，这倒与考试无关，主要是现在回想起老师上课带你一步步分析算法，而我在后排不时刷着手机，总有种怅然的悲伤。 虽然我上课状态一言难尽，但确实得承认这门课，或者说妮可很多课的确可以通过自学掌握大部分知识。这门课在这学期置给了ai和ds，所以到课的人也不是很多，老师经常点名。 还是那句话，选择大于努力，建议别选ds和ai的课。 这本教材是大概20年以前的，我不晓得ppt的情况，但内容非常详细。同时，也并非所有内容都有考察，带星号的几乎不会考试，但老师还是会带你过一遍算法。这些内容，应该会在读研的时候发挥作用。 实验一共五个，好像不是最多的，但也不少。每个实验满分十分但有附加两分。整体难度还好，有难有易。但话又说回来，这班几乎都是ds和ai，都在卷，不做附加会有点吃亏。此外，实验允许补交，但会扣除一定分数。 但是，这门课考试难度完全出乎我意料。我估计平均分能有八十几，在如此高的分数下，总评占比几乎都给了考试，实验和作业加起来估计也就10%-20%，可以说，考试决定你的成绩。 我的实验并没有做满全部的分，作业又不是满分，但是在出勤率慢的情况下，考试91分，最终总评93。 一些建议: 好好听课，好好听课，好好听课 你的水平取决于你自己，你的成绩取决于你的同行 选择大于努力，别来ds或者ai

非常好老师，使我的电脑旋转

作为一名高中竞赛生+ACM队员，记忆中只去上了屈指可数的几次课。。。。自从万老师说“觉得自学期末能考好的可以不来听课”我就没怎么来过（除了一个讲B-树的清晨，记得那天整个教室只有不到40人OTZ）（此处映射一波疯狂点名的马老师）

我是大一被马老师“图形化”+眼花缭乱的讲课方式吓到了隔壁数据结构班的。

总体感受上，万老师讲课的ppt和清晰程度实在是好（此处映射一波马老师），而且对实验报告啊内容啊各方面的细节要求也十分清楚（再次映射一波马老师），助教们也很用心的在判作业和验收实验（顺道映射一波马老师的助教们）

今年的期末卷子是万老师出的（因为我期中反馈的时候说马老师老喜欢出只有自己班留过的作业原题然后他就帅锅了OTZ）。不偏不怪，难易也很适合（前一晚上熬夜看B树和各种哈希各种排序结果考的都很基本OTZ），基本是选择填空+程序填空+简单的算法结果模拟+程序设计题（最后觉得试卷体量较大还延长了15分钟QAQ）

我是卡上了4.3，估计给分也都比较好。

真的，觉得马老师比较那啥的可以换过来，真的，我觉得很赚

老师会点名，提醒一下，尤其是辅修和叠课的

鉴定为若至期末😋，很好期末使我不挂科

讲课清晰，会帮我们回顾c语言知识，会带我们层层分析算法

半夜发现出分了，庆幸自己去查卷了，找回了两分，没被卡绩

老师非常好，助教只能说还OK。

哥们要更新一下，实验报告要写吐血了，话说为什么数据结构还要写实验报告，吐血了吐血了。

挺重要的课，怪我太摆烂了总评84，劝学弟学妹好好学。

前面的同学说的都很详细了，我就来说说实验吧。

实验的基本原则：做的越多分越高（助教会有具体的评分标准）

1. 稀疏一元多项式的运算和表示

输入一元多项式的每项系数和幂次以录入多项式，同时支持多项式的加减乘除、微分积分求值等功能。

2. 简单的栈与队列的实现

我做的是「行编辑器」，「括号配对检验」，「银行业务模拟」三个题目，一共（应该）有五个。

3. 二叉树的应用

利用 Huffman 树压缩 & 解压文件。

值得注意的是，这里可以用范式 Huffman 编码，降低存储 Huffman 树的开销；分割文件为一个一个的 Trunk，可以更好的利用局域的相似性。

更能肝的同学可以研究一下 deflate，实现一波（我本来想这样做的，但是发现时间确实不是很够...）

4. 图的应用

输入一个无向图，输出图的深度优先搜索遍历顺序与广度优先搜索遍历顺序。显然的，最后的答案会有多种可能，这里统一要求：当有多个节点可以搜索时，优先去节点编号最小的那个。

输入一个无向铁通讯网图，用Prim和Kruskal算法计算最小生成树并输出。

输入一个无向铁路交通图、始发站和终点站，用Dijkstra算法计算从始发站到终点站的最短路径。

5. 哈希表

(1).  输入关键字序列；

(2).  用除留余数法构建哈希函数，用线性探测法解决冲突，构建哈希表HT1；

(3).  用除留余数法构建哈希函数，用拉链法解决冲突，构建哈希表HT2；

(4).  分别对HT1和HT2计算在等概率情况下查找成功和查找失败的ASL；

(5).  分别在HT1和HT2中查找给定的关键字，给出比较次数

还有，万老师给分太好啦～4.3 路过（溜

  期末周靠着评课社区的前人留言才顺利速通，现在到我评论了。

  先说课程风格。万老师很负责任，两位助教也比较尽心，线下沟通很好说话，但线上消息回的很少。听老师讲课有点喂饭的感觉，很详细。仔细听应该能收获不少，可惜我耐不下性子。实验有五次，可能中间十一月其他课期中考试会比较紧张。其他时间认真对待问题不大。作业不多，但作为小白我每次写个算法的伪代码都磕磕绊绊的。（最终期末的算法题也需要伪代码，最好平时留意一下）。课堂会点名,次数也不少，喜欢翘课的同学需要注意。

  再说考试内容。这学期分为选择、填空、简答、算法设计四部分。

选填主要是对学过的数据存储结构的考察，可以留意一下二叉树的一些数字特征。复习的时候广义表、特殊数组存储等内容需要过一遍，容易忽略。刚刚查卷发现自己自己把广义表的长度当成深度了，线索二叉树好像也做错了。

简答题今年考察了B树的插入删除，Dijstra算法，和Prim算法，以及构建线性探测的哈希表并求ASL。

算法设计题第一题为给定1<K<M，求从1到M中取K个数和为N的所有解，第二题是Dijistra算法的变形。第一题当时在考场上递归函数老是写不好，最好助教给了一半分。

  给分的内容先空着，等总评出来再补

老师讲课超好，可以说是很少我能听下去的课之一，而且助教很帅(

给分也超好，作业和实验都可以补交，唯一美中不足的是实验报告要写吐了

老师讲课抑扬顿挫，很认真，很仔细，像是引导小学生一样。但说实话，从高中以来已经很久没有听过这样的课了，所以很不适应，经常是听着听着就不想听，宁愿自学了。课堂风格感觉和隔壁马老师（天花乱坠）是各有千秋，看哪个是你的菜了。

试卷出的挺好的，平时作业和实验涉及的多的基本就是重点了，没有考一些很偏很难的点。像B+树、旋转、KMP之类到了考前还觉得很偏很难不太会的都是没有考的。感觉考前把PPT完整过一遍就差不多了。