HOME ] UP ] DSACPP ] LectureMate ] DSAJ ] Demo ] Tsinghua ] [ MOOC ]


数据结构MOOC


欢迎选修本人主讲的慕课数据结构[基础]数据结构[高级]计算几何

教材


在线编程训练


微信公众号



  • [Q0-00] English Please?



    [A0-00]?

    Sorry, the course is taught in Mandarin.

    本课程用中文教授。



  • [Q0-01]我想学习数据结构,请问一下这门课程有哪些知识储备\先修要求?对编程能力作何要求?



    [A0-01]?

    虽然我们常说这门课对于数学基础和编程基础有一定的要求,但这并不意味着你需要精通所有相关课程。实际上,你只需掌握若干重要的数学概念及方法,以及C/C++语言编程的基本技巧。为确认自己是否适宜选修这门课程,不妨对照以下清单做一清点:

    • C++语言程序设计基础:类、继承、重载、重写、虚方法、模板

    • 离散数学基础: 集合、偏序集、良序、数学归纳法、级数、递归、递推

    • 概率基础: 随机分布、概率、伯努利实验、数学期望、期望值的线性律



  • [Q0-02]我并没有良好的C\C++编程基础——我平时比较习惯使用Java\Python\C#\Matlab\Lisp……我能学好这门课吗?



    [A0-02]

    正如课程简介页面上所指出的,DSA需要兑现为具体的语言,但并不唯一地依赖于某一特定语言。正因为此,课程内容中也会涉及很多其它的语言(Java/Python/Perl/Ruby/...),它们之间的相互比较,对于我们理解DSA很有帮助。这也属于我们在课堂上,着重强调的拓展内容之一。因而对于这个问题,答案是肯定的。

    但是非常遗憾地,因为我们的资源限制,我们在编程作业上也只能忍痛割爱,在OJ上以统一的编译、运行环境进行测试,因而对于C\C++的编程基础,我们还是有一定的要求:事实上在数据结构中也只是会用到部分的特性(比如C++里的类模板)。主要是能够使用就行了,只要学一些过基本的内容问题应该不大。



  • [Q0-03]那么数学呢?数学呢数学呢?



    [A0-03]

    如大家所知,数据结构必然需要用到一些数学,但与程序语言一样,未必需要(也不可能)各方面都精通。事实上,本课程不涉及高深的数学知识,如果你的高中数学学得还行,那就应该能在小修小补的基础上应付。在课程简介信息中,我们尽可能罗列出了本课程所涉及的相关知识,尽管覆盖了不少学科,但若从仅是掌握其中所列知识点的话,即便从零基础开始,也花不了多少时间的。比如,建议你可以借助所给的关键词,在Wikipedia中逐条自学。



  • [Q0-04]这门课会如何给成绩?



    [A0-04]

    最终成绩由以下部分组成:

    • 课后测验(Problem Set),共6次,每次10道题目,每题占1%,合计60%

    • 编程习题(Programming Assignment),共4次,每次3道题目,每题分别占4%,4%,2%,合计40%



  • [Q0-05]能详细解释一下什么是课后测验,什么是编程习题吗?



    [A0-05]

    • 课后测验是我们对于学生对课程掌握程度的一种过程性评价,平均会在每章左右的时候放出一次,每次10道客观题,需要在规定的截止日期前作答。
    • 编程习题则是由我们课程特色所决定的的一种习题形式,会与OJ http://dsa.cs.tsinghua.edu.cn/oj/ 绑定,请以自己注册edx的邮箱注册到该平台,我们会自动把OJ上的成绩同步到edx上。


  • [Q0-06]那么对于这门课的学习,老师您是怎样定位的?从这门课中,我们能够对数据结构掌握到怎样的程度?如果我的基本功比较薄弱的话,我是否适合学习这门课?



    [A0-06]

    数据结构与算法(依然简称DSA)是个非常开放的专题,学习过程没有终点,任何一门课程都不可能穷尽。然而有意思的是,反过来,它的学习过程也是分阶段逐层递进的。一门好的此类课程,应该可以让不同背景、不同基础、不同目标的学习者有一定的选择余地,这也是我们设计这门课的重要标准之一。

    我喜欢将DSA比作汽车。
    熟悉基本的数据结构的基本功能与使用方法,犹如拿驾照会开车能上道。
    懂得不同DSA之间的差异及其适用场合,懂得针对问题需要选取适当的DSA,犹如懂得如何选购适宜于自己的汽车。
    懂得对DSA做适当的裁剪、扩充和改造,并优化组合,犹如玩车的行家里手,有DIY的能力和乐趣。
    探索DSA的优化极限,能够完成从内部优化到外部封装的整个过程,则是设计师与工程师的任务与要求。

    因此只要定位清楚,心态平和,一些基本功相对薄弱的学生学习DSA是完全可行的。我讲授的另一门课程《计算几何》是面向本专业研究生的,但我对自己的要求却是,(在以上第一、二个层面上)要让高中生能听懂。如果实在遇到不能很快弄懂的,不妨直接跳过。好在,我会尽力使用初等的方法,并将相关的结论简明扼要地概括出来,如不愿推敲,先记下就是了,并不影响你继续前行。

    最后,数据结构是典型的大学学习模式,不像中学,所有知识点都须面面俱到。学习的过程中,应更加关注自己“学到了什么”,而不是“什么还没学”。尽早地接触这种学习模式,相信对你日后的大学学习必有裨益。



  • [Q0-07]这门课的课程大纲及会上多少课可在哪里看?



    [A0-07]

    课程大纲可以参见页面顶部的“Progress”



  • [Q0-08]这门课对应的教材应该在哪里获取?有没有对应的源代码?



    [A0-08]

    教材和配套习题解析可以在页面上方导航栏中的对应版块在线阅读

    本课程所涉及的几乎所有代码,均以Visual Studio解决方案的形式汇编打包,共含50多个示例工程。读者可通过以下页面上的“示例代码”链接直接下载: http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/
    解压缩后,可在VS2008中打开dsacpp.sln,然后选择对应的工程、编译、运行。



  • [Q0-09]有没有什么便捷的渠道能够获取课程的最新信息?



    [A0-09]

    微信用户请关注微信公众平台“THU数据结构MOOC”,课程的最新信息会通过此平台发布。

    在微信中通过名称查找或者直接扫描以下二维码即可关注“THU数据结构MOOC”:

    如果你不使用微信也没关系,重要的课程信息都会在课程公告中发布。



  • [Q1-00]OJ到底是啥玩意?



    [A1-00]?

    OJ是Online Judge(在线评测)的缩写,本课程的编程作业(占总成绩的30%)需要在该系统(http://dsa.cs.tsinghua.edu.cn/oj/)上自动评测。也就是你需要用同样的邮箱在OJ系统上注册并根据课程进度要求提交作业源代码。



  • [Q1-01]那么这个OJ支持什么编程语言?



    [A1-01]

    非常遗憾地,目前只支持C/C++,正在探索支持其他语言的可能性(比如很多OJ都可以提交Java……看看别人家孩子)。



  • [Q1-02]好吧,既然只支持C/C++,那具体来说支持什么版本、什么函数库?



    [A1-02]

    OJ系统使用的编译器是gcc 4.4.5,不支持C++11。且编程作业中只允许使用最基本的函数库,而不能使用STL、Boost等函数库。比如说map、vector等是属于STL,无法使用。事实上也很容易理解,数据结构要教会你怎么实现数据结构,如果都直接用别人写好的那怎么行呢?



  • [Q1-03]那么OJ上提交文件的格式是什么?



    [A1-03]

    将所有源代码(.cpp文件和.h文件等)直接打包成rar文件后提交即可,无需提交可执行程序。具体可以尝试一下Tutorial课堂,Tutorial课堂是帮助大家熟悉OJ平台和热身的课堂,在Tutorial课堂中提交的编程题不计入成绩,Tutorial课堂中目前有两个作业,其中第一个作业的若干道题纯粹是为了帮助大家熟悉作业提交过程,第二次作业中的习题有一定挑战性,欢迎大家尝试。



  • [Q1-04]提交界面的Honor Code和Report都是嘛玩意?



    [A1-04]

    Honor Code是一个对自己作业的君子声明,你可以理解成安装软件的时候的那个"我同意此协议"。你不"同意此协议"就无法安装软件,你不提交HonorCode该次作业就不会被计分。顺便说句,故意抄袭他人代码并声称是自己的被视为可耻的行为。Report是作业报告,这是清华大学面授课堂的要求,大家可以不必提交Report。



  • [Q1-05]为什么我的程序总是不通过?我觉得没有问题呀。



    [A1-05]

    对于"Wrong Answer": 请首先检查自己的程序是否符合题面的输入、输出格式要求,不要在输出里加多余的东西。因为系统会用给定的输入运行你的程序并将输出与正确答案比对,多余的输出会导致比对失败。


    对于"Runtime Error": 该问题是由于程序执行过程中产生了未处理的异常。比如整数除以零(1/0)、assert失败、访问到了非法的内存等等。请进一步调试自己的程序。
    需要注意的是,main函数必须以“return 0;”结束,如果返回值非0,也会被认为是Runtime Error。如果保证返回值为0并且希望知道OJ返回错误代码的含义,可以参考 http://unixhelp.ed.ac.uk/CGI/man-cgi?signal+7。常见的是8除0错和11内存访问错误。

    对于"Exceed Time Limit"和"Exceed Memory Limit": 程序运行超时和程序使用的内存超过限制,请从算法和编码两个角度进一步优化自己的程序。




  • [Q1-06]那么可以给一些调试建议吗?对于OJ我还有更多的问题。



    [A1-06]

    事实上,“程序在我的机器上跑通过了”是个很不严格的说法,更严谨的说法是“程序在我的机器上用我的测例跑没出错”

    而把程序放在OJ上跑的时候,OJ的测例则必然会与你的测例有不同之处——它可能有更庞(bao)大(li)的测例,也可能会是一些边(e)界(xin)测例。吾日三省吾身:边界情况未考虑乎?(Wrong Answer/Runtime Error)内存装不下乎?(Exceed Memory Limit)跑太慢乎?(Exceed Time Limit)

    对应于后两种情况,优化是程序进步的阶梯,可能你需要一个更好的算法,也可能你的算法已经不错,只是差一个漂亮的实现。而对应于第一种情况,建议你测试更多测例以找出错误,事实上测试数据的构造也是课程训练的环节之一。我们也鼓励同学们互相交换测例以防微杜渐。



  • [Q2-00]我的浏览器播不了视频,求破……



    [A2-00]?

    请先尝试换一个浏览器,若不是浏览器的问题,可向edx平台反映。



  • [Q2-01] 视频是否能够打包下载?我想下载到本地后慢慢看。



    [A2-01]?

    我们提供了百度网盘的打包下载:http://pan.baidu.com/s/1qWM0CFy课程团队保留所有版权,未经授权不得用于与个人学习无关的活动



  • [Q3-00]在讨论区进行讨论,我们应当遵循怎样的规范?



    [A3-00]?
    • 由不当言论引起的法律纠纷和其他相关责任自负。
    • 不应出现与本课程无关的内容。
    • 不得出现与本课程编程题目相关的代码。

    特地补充一下,虽然我们禁止讨论区中出现与本课程题目相关的代码,但交流解题思路与测例则是被鼓励的。



  • [Q3-01]看见讨论区很多人能够打出漂亮的代码和公式,他们是怎么做到的?



    [A3-01]

    在讨论区的讨论,我们使用的是Markdown语法,详情可以参见Markdown语法说明。特殊地,对于公式的输入,我们使用类似于如下的方式进行书写:

    		\begin{equation}\
    		\left( \sum_{k=1}^n a_k b_k \right)^2 \leq \left( \sum_{k=1}^n a_k^2 \right) \left( \sum_{k=1}^n b_k^2 \right)
    		\end{equation}
    	
    ,效果如下:


TOP

HOME ] UP ] DSACPP ] LectureMate ] DSAJ ] Demo ] Tsinghua ] [ MOOC ]

Copyleft (c) 2003-3002, Junhui Deng
Last updated on 08/04/2023