请点击右上角按钮，选择“在Safari中打开”
再点击页面中的下载或打开
“数据结构”是计算机科学与技术专业、物联网工程专业、大数据专业、信息科学专业、智慧农业专业，甚至于其它电气信息类专业的重要专业基础课程。它所讨论的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其它课程，还是对从事数据分析、信息工程的开发等，都是重要而必备的基础。
程序设计解决问题往往有多种方法，且不同方法之间的效率可能相差甚远。程序的时间和空间效率，不仅跟数据的组织方式有关，也跟处理流程的巧妙程度有关。本课程将介绍并探讨有关数据组织、算法设计、时间和空间效率的概念和通用分析方法，帮助学员学会数据的组织方法和一些典型算法的实现，能够针对问题的应用背景分析，选择合适的数据结构，设计高效率的算法，从而培养高级程序设计技能。学习了数据结构，会让你知道怎样设计出高质量的程序。
注意：本课程只涉及最基础的数据结构和与之关联的最基本的算法，更多更复杂的数据结构和经典的解决优化问题的算法，将在后续课程中介绍。
本课程的特点是，对每一种重要的经典数据结构，我们都会从实际应用问题出发，导出其定义、实现（存储）方法以及操作实现，并以更丰富的综合应用案例和练习题帮助学员增强对理论的感性认识，从而明白这些数据结构为什么存在以及在什么情况下可以最好地解决什么样的问题。为了兼顾起点不同的学员，课程中特意设计了“小白专场”系列，手把手教授如何将解决问题的抽象算法用具体的代码实现，从而引导初学者更好地入门。
坚持完成本课程学习、并按慕课网中的要求完成所有练习的学员，应该具备了PAT（Programming Ability Test）甲级需要的所有基础知识，辅以充分的英语阅读能力和熟练的编程能力，应可以取得优良成绩。
一、课程信息
课程中文名称：数据结构
课程英文名称： Data Structures
课程编号：10241
先修课程：高级语言程序设计（C语言）、离散数学
课程类别：专业课
总学时：64学时（理论40学时，实验24学时）
总学分：4
适用专业：计算机科学与技术、信息与计算科学、物联网工程、数据科学与大数据、信息科学、智慧农业。
二、课程的性质、地位与任务
《数据结构》是信息类专业的课程。
课程教学任务：使学生较全面地掌握各种常用的基本数据结构和算法的基础知识和基础理论，为学习后续软件课程提供必要的基础，提高运用数据结构表示实际问题并设计有效算法解决实际问题的能力。该课程的特点是既需要良好的思维能力，又要求有较强的实践能力。既要注意培养和训练学生的软件开发的基本技术和方法，同时更不能忽视软件开发过程的系统思想和观点。
三、课程的基本要求
《数据结构》主要内容包括基本数据结构和算法的基础知识和基础理论。课程的内容重点应立足于基础知识和基础理论的掌握和应用能力的培养。
基本要求：
(1) 从数据结构的逻辑结构、存储结构和数据的操作三个方面掌握线性表、树、二叉树、图和文件等常用的数据结构。
(2) 掌握在各种常用数据结构上实现的查找和排序等算法。
(3) 对算法的时间和空间复杂性有一定的分析能力。
(4) 针对简单的应用问题，能够选择合适的数据结构设计有效的算法。
《数据结构》主要内容包括基本数据结构和算法的基础知识和基础理论。课程的内容重点应立足于基础知识和基础理论的掌握和应用能力的培养。
知识目标：
（1）了解数据结构及其分类、数据结构与算法的密切关系。
（2）熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。
（3）掌握设计算法的步骤和算法分析方法。
（4）掌握数据结构在排序和查找等常用算法中的应用。
（5）初步掌握文件组织方法和索引技术。
能力目标：
培养基本的、良好的程序设计技能，编制高效可靠的程序。
(1) 从数据结构的逻辑结构、存储结构和数据的操作三个方面掌握线性表、树、二叉树、图和文件等常用的数据结构。
(2) 掌握在各种常用数据结构上实现的查找和排序等算法。
(3) 对算法的时间和空间复杂性有一定的分析能力。
(4) 针对简单的应用问题，能够选择合适的数据结构设计有效的算法。
素质目标：
（1）注重培养学生独立思考能力，学会科学地分析和解决问题。
（2）培养学生的团结协作能力。
（3）培养学生求真务实、讲求时效和一丝不苟的学习态度。
（4）为学生形成良好的职业道德打下基础。
作为一个合格的大学生，应该具备自学能力、动手能力、团队协作能力。因而，我们也把培养具有这些能力的学生作为我们的课程目标，把对这些能力的培养融入到平常的授课过程中。对学生主要注重问题分析的全面性，程序流程设计的合理性，以及编程技巧和方法的培养，为进一步培养软件项目综合开发和应用能力作准备。 使得学生无论以后在学习、工作中使用什么语言编程，都能灵活应用这些思想和方法。这些能力的培养不但有效的支撑这学生后续专业课程的学习，更重要的是增强了学生毕业后面向社会的适应能力。
这门课的一个重要目的是，帮助大家明白一些经典的数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。要做到这一点，非自己动手解决问题不可。
与程序设计课程类似，每一周的课后，我们都留有两类练习，一类是在线完成的选择、是非或填空题，以下称作“小测验”，用以辅导同学们巩固本节所学理论知识；一类是实验练习，包含四川农业大学学习平台、头歌实验平台、PAT（Programming Ability Test）的配套练习等。目的是将课堂所学知识转化为解决问题的实际动手能力。同学们按照实验要求完成算法设计，并上机通过运行。从而达到理论知识向实际运用能力的转化的目标。
其中，网站 拼题A 上的 编程练习题，以下称作“编程练习”。你可以自己注册帐户，随时进行练习，并不限于发布练习的时段。
注意：
课程过半时，会有一次期中考试，是在线完成的选择、是非或填空题，不包括编程题。期中考试在两周内用连续的60分钟完成均有效。
最后，在期末考试的前一周，会有一次在线期末考试，需要在某一天内用连续的120分钟完成。
本课程还可以获得MOOC平台颁发的证书，是否能获得由以下因素决定：
此外，若你的期末考试成绩高于期中考试或者无期中成绩，则期末占100%；若你的期末考试成绩低于期中考试，则期中考试占40%，期末考试占60%。
满足条件1并且总评成绩达到60分及以上者，可以获得本课程的合格证书。总评达到90分及以上，可以获得优秀证书。
另加福利：最后获得合格或优秀证书的同学，总评分在[80, 100]区间内者，可以申领50元PAT代金券；在[60, 80)区间内者，可以申领20元PAT代金券。全国考点通用，一年有效。申领者用本课程注册邮箱将拼题A用户名和总评成绩发邮件到chenyue@zju.edu.cn 领取。
第一讲 基本概念（1:15:26）[陈越]
1.1 什么是数据结构（4节共32:43）
1.2 什么是算法（3节共22:41）
1.3 应用实例：最大子列和问题（3节共20:02）
第一章作业
第二讲 线性结构1（2:19:00）[何钦铭]
2.1 线性表及其实现(6小节共45:04)
2.2 应用实例：多项式加法运算(1小节10:37)
小白专场：多项式乘法与加法运算- C实现（3小节共27:43）
线性表
第三讲 栈和队列
3.1 堆栈(4小节共39:51)
3.2 队列(2小节共15:45)
栈和队列
第四讲 树(上) （1:50:08）[何钦铭]
3.1 树与树的表示(5小节共38:54)
3.2 二叉树及存储结构(2小节共16:43)
3.3 二叉树的遍历(4小节共37:02)
小白专场：树的同构 - C语言实现（2小节共17:29）
树（上）
第五讲 树（下）（1:53:28）[何钦铭]
5.1 堆（4小节共30:05）
5.2 哈夫曼树与哈夫曼编码（3小节共19:52）
5.3 集合及运算（2小节共12:57）
小白专场：堆中的路径 - C语言实现（1小节共7:51）
小白专场[陈越]：File Transfer - C语言实现（4小节共42:43）
树（下）
第六讲 散列查找（1:43:39）[何钦铭]
11.1 散列表(2小节共13:43)
11.2 散列函数的构造方法(2小节共13:05)
11.3 冲突处理方法(6小节共36:26)
11.4 散列表的性能分析(1小节10:26)
11.5 应用实例:词频统计(1小节6:01)
小白专场[陈越]：电话聊天狂人- C语言实现（4小节共23:58）
查找小测验
第七讲 排序（上）（1:11:44）[陈越]
9.1 简单排序（冒泡、插入）（4小节共23:26）
9.2 希尔排序（1小节共9:29）
9.3 堆排序（2小节共10:27）
9.4 归并排序（3小节共28:22）
排序上（测验）
第八讲 排序（下）（54:20）[陈越]
10.1 快速排序（4小节共25:25）
10.2 表排序（2小节共12:41）
10.3 基数排序（3小节共12:13）
10.4 排序算法的比较（1小节共4:01）
第九讲 图（上）（1:29:32）[陈越]
6.1 什么是图（3小节共24:02）
6.2 图的遍历（4小节共22:22）
6.3 应用实例：拯救007（1小节共14:40）
6.4 应用实例：六度空间（1小节共8:06）
小白专场：如何建立图- C语言实现（6小节共20:22）
第十讲 图（下）（57:02）[陈越]
8.1 最小生成树问题（2小节共20:16）
8.2 拓扑排序（2小节共27:57）
图之习题选讲-旅游规划（2小节共8:49）
学过一门编程语言，具有一定编程基础，即可理解主要内容，因为数据结构本质上是不依赖于编程语言的，且编程练习平台可以接受二十余种语言代码的提交。但由于算法描述多用类似C语言的伪码，且“小白系列”仅讲解C语言的算法实现，所以如果学过C语言会更容易接受。
如果还对计算机处理离散结构的基本理论和方法有较为系统的理解（即预修“离散数学”），则对更扎实地掌握本课程内容有很大帮助，但并不是必须的。
推荐教辅和资料：
1.教材：《数据结构教程》第六版，李春葆主编，清华大学出版社。
2．参考资料《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
3．参考资料《数据结构学习与实验指导（第2版）》，陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2019年7月
4． 课程练习网站：
0。我应该怎么设置账号开始学习呀？
答：同时在两个窗口登录拼题A和中国大学MOOC，进入拼题A用户名下的“个人中心”找“我的绑定”，点击“绑定中国大学MOOC”，妈妈再也不用担心你学完了没成绩啦！然后继续在“个人信息”中输入本学期的“邀请码”，就可以“应邀做题”啦~
1。我不是计算机专业的，能学这门课吗？
答：只要会写程序就能学。
2。我数学不好，能学这门课吗？
答：会算术就可以了…… 有个别例子涉及基础数学概念（比如什么是多项式），花一分钟上网搜索一下定义就可以搞定。
3。我不会写程序，能学这门课吗？
答：不能…… 还是先学会写程序再说吧~ 隔壁翁恺老师的C语言讲得很好懂，推荐~
4。学这门课每周要花多少时间？
答：平均4-8小时，开始可能轻松一点，后面的课业会越来越重 —— 这样你才能长进嘛~ 建议开课前先去拼题A做一下自测：如果1小时内能做到满分，这门课你是可以轻松搞定的；如果需要2小时，那么你学这门课每周估计要花5小时以上；如果3小时还拿不到满分，那你这门课可能要花8小时以上（说不好是每周还是每天……）
5。为什么我的程序在自己机器上跑得好好的，提交到拼题A网站就各种错误？
答：因为你自己用于测试自己程序的数据太弱了同学…… 另外一定注意严格按照题目要求输出结果，不要输出如“Please input ...”之类的多余信息。要用标准输入输出，不要从文件读写。不要急，想想ACM竞赛的世界冠军们也是这样哭着走过来的，心理就平衡了~
6。拼题A的测试数据能不能公布呀？
答：不能。公布数据后一定会有人直接打印结果的…… 不过，如果在某组数据上卡了比较长的时间，可以到论坛上哭诉，老师会在一段时间后打开那组数据的提示信息。
7。什么是PAT甲级，能吃？
答：PAT是Programming Ability Test的缩写，是一个考试，分顶级、甲级、乙级三个级别。证书真的能吃 —— 就如托福考试在留学申请中的作用一样，百余家联盟企业划定了PAT分数线，对达到分数线的考生给予免除与编程能力测试相关的笔试，直接邀请进入面试的机会。数十家企业的HR排队打电话请你去面试，想想也是醉了……
8。什么时候考PAT最合适？
答：一般大三下半学期春季考试，凭成绩在企业春招中找份实习工作，暑假先去实践一下，对找工作非常有帮助。
或者大四开学参加秋季考试，正对上企业大规模秋招的时间。
万一秋季没考好、并且秋招时没找到理想的工作，还可以参加冬季考试、同时选择春季才把成绩推送给企业。
万一冬季也没考好，还有最后一次春季考试，这样大四阶段还可以抓住最后春招的机会。
拼题A常见问题及解答
评分
试题的解答提交后由评分系统评出即时得分，每一次提交会判决结果会及时通知；系统可能的反馈信息包括：
| 结 果 | 说 明 |
|---|---|
| 等待评测 | 评测系统还没有评测到这个提交，请稍候 |
| 正在评测 | 评测系统正在评测，稍候会有结果 |
| 编译错误 | 您提交的代码无法完成编译，点击“编译错误”可以看到编译器输出的错误信息 |
| 答案正确 | 恭喜！您通过了这道题 |
| 部分正确 | 您的代码只通过了部分测试点，继续努力！ |
| 格式错误 | 您的程序输出的格式不符合要求（比如空格和换行与要求不一致） |
| 答案错误 | 您的程序未能对评测系统的数据返回正确的结果 |
| 运行超时 | 您的程序未能在规定时间内运行结束 |
| 内存超限 | 您的程序使用了超过限制的内存 |
| 非零返回 | 您的程序结束时返回值非 0，如果使用 C 或 C++ 语言要保证 int main 函数最终 return 0 |
| 段错误 | 您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起 |
| 浮点错误 | 您的程序运行时发生浮点错误，比如遇到了除以 0 的情况 |
| 内部错误 | 评测系统发生内部错误，无法评测。工作人员会努力排查此种错误 |
常见问题
*我应该从哪里读输入，另外应该输出到哪里？
如果没有特别说明，你的程序应该从标准输入（stdin，传统意义上的“键盘”）读入，并输出到标准输出（stdout，传统意义上的“屏幕”），不要使用文件做输入输出。由于系统是在你的程序运行结束后开始检查输出是否是正确的，对于有多组测试数据的输入，可以全部读入之后再输出，也可以处理一组测试数据就输出一组。
*为什么我的程序交在这里得到编译错误，而我在自己的机器上已经编译通过了？
本系统所使用的编译器和你在自己机器上使用的可能有区别，请留意几个常见的地方：
*为什么我的程序得到了“返回非零”？
*程序的时间和内存占用是如何计算的？
程序的运行时间为程序在所有 CPU 核占用的时间之和，内存占用取程序运行开始到结束占用内存的最大值。
*为什么同样的程序运行时间和所用内存会不同？
程序运行时间会受到许多因素的影响，尤其是在现代多任务操作系统以及在使用动态库的情况下，多次使用同一输入运行同一程序所需时间和内存有一些不同是正常 现象。我们的题目给出的运行限制一般为标准程序的若干倍，也就是说，选用正确的算法和合适的语言，那么运行限制是富余的。
*不同语言的时间限制和内存限制是相同的吗？
是相同的，我们认为选择合适的编程语言也是一项必备技能，所以没有为不同语言设置不同的限制条件。
*我提交的代码可以做什么，有什么限制吗？
没有。这里没有系统调用白名单，也没有针对语言限制可使用的包或库。虽然我们比较宽容大度，但还是请不要做不符合道义的事情。如果你需要使用我们系统没有提供的某个语言的某个库，或者需要更改编译参数，可以联系我们。
其他问题
在考试或比赛中遇到其他问题请咨询现场工作人员。
教授
副教授
副教授
由高教社联手网易推出，让每一个有提升愿望的用户能够学到中国知名高校的课程，并获得认证。
网上有害信息举报（涉未成年人）：网站 https://www.12377.cn 邮箱（涉未成年人） youdao_jubao@rd.netease.com
粤B2-20090191-26
| 京ICP备12020869号-2 |
京公网安备44010602000207
©2014-2025
浙公网安备 33010802012594号
