✦
课程教学大纲
✦
01
课程基本信息
02
课程简介
03
课程目标
本课程的主要教学环节有理论教学和实验教学，课程的总体教学目标是：掌握数据结构的基本概念、基本原理和基本方法；掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C++语言设计与实现算法的能力。具体教学目标如下：
展开剩余95%1．描述基本数据模型的逻辑特征，分析和评价数据模型的不同存储方法，进行存储结构定义；针对计算机领域的工程问题，构建数据模型、设计存储结构、描述存储示意图。
2．描述数据结构的基本操作、经典算法、经典查找技术和排序技术的执行过程，对重要的算法进行复现；针对计算机领域的工程问题，进行算法设计并运用大O记号进行算法性能分析。
3．针对计算机领域具有时空性能约束的复杂工程问题，应用数据结构的基本原则和方法，通过比较、选择、优化等过程，设计合理的存储结构和解决方案，进行数据表示、算法描述和程序实现。
04
课程支撑的毕业要求指标点及权重
05
教学方法
1. 问题驱动的课堂讲授法。课程的总体教学目标是培养学生的计算思维能力和应用计算机解决问题的算法与程序设计能力，因此，将教学主线确定为计算机进行问题求解的一般过程“问题→想法→算法→程序”，在这个一般过程中通过设疑、解疑，采用互动的方式进行知识传递。
2. 基于图示的动画演示法。在深刻揭示知识内涵的基础上，并将教学意图融入多媒体课件，将教学内容中抽象的概念和不可见的过程，通过动画形象地动态演示出来。
3. 引导思维的启发式教学。注意引导思维，通过讲思路讲过程讲方法，展现问题的求解过程，通过设疑、问疑、解疑一步步启发学生的思维，并将启发式教学方法贯彻到每一个教学专题。
4. 项目驱动的讨论式教学。根据课程内容布置具有一定难度的算法问题（结合ACM程序设计竞赛），以小组方式进行讨论，以抽签方式进行展示，提高学生的主动学习意识。
5. 全程跟踪的混合式教学。采用互动式教学工具，课前向学生发送预习任务，课前或课中设计相关测验完成即时考核，提高课堂教学的学习效果，课后完成作业和学习检查。
06
教学环节与教学安排
1.理论环节教学安排
2.实践环节教学安排
07
教材、参考书目和教学资源
教材：
[1] 王红梅，王贵参.数据结构——从概念到C++实现[M].4版.北京：清华大学出版社，2025.
[2] 王红梅，张丽杰，盖世蕊.数据结构学习辅导和实验指导——从概念到实现[M].北京：清华大学出版社，2024.
参考书目：
[1] Thomas H C，等.算法导论[M]. 3版.殷建平，等译.北京：机械工业出版社，2013.
[2] Mark A W.数据结构与算法分析：C++语言描述[M]. 4版.北京：机械工业出版社，2016.
[3] Bentley.编程珠玑[M].2版. 黄倩，译.北京：人民邮电出版社，2015.
[4] 严蔚敏，吴伟民.数据结构(C语言版) [M].北京：清华大学出版社，2007.
[5] 邓俊辉.数据结构(C++语言版)[M]3版.北京：清华大学出版社，2013.
教学资源：
MOOC 课程
08
考核方案
1.课程目标达成途径
2.考核环节与成绩比例
09
考核标准依据
作业考核与评价标准
作业考核与评价标准
平时测验考核与评价标准
平时测验考核与评价标准
3．实验考核与评价标准
4．期末考试成绩考核与评价标准
✦
参考书籍
✦
《数据结构——从概念到C++实现（第4版）》
作者：王红梅、王贵参
定价：56元
内容简介
本书按照《全国硕士研究生招生考试计算机学科专业基础综合考试大纲》(以下简称《考试大纲》)组织教材结构，涵盖《考试大纲》全部考查内容。本书主要介绍数据结构、算法以及抽象数据类型的概念，线性表、栈和队列、多维数组、树和二叉树、图等基本数据结构及实现方法，讨论常用查找技术和排序技术。本书兼顾概念层和实现层，既强调数据结构的基本概念和原理方法，又注重数据结构的程序实现和实际运用，在提炼基础知识的同时，进行了适当的扩展和提高。 本书内容丰富，层次清晰，深入浅出，结合实例，可作为计算机及相关专业数据结构课程的教材，也可供从事计算机软件开发和应用的工程技术人员参考和阅读。
目录
第1章绪论1
1.1引言2
1.2问题求解与程序设计3
1.2.1程序设计的一般过程3
1.2.2数据结构在程序设计中的作用6
1.2.3算法在程序设计中的作用7
1.2.4本书讨论的主要内容8
1.3数据结构的基本概念10
1.3.1数据结构10
1.3.2抽象数据类型12
1.4算法的基本概念14
1.4.1算法及算法的特性14
1.4.2算法的描述方法15
1.5算法分析16
1.5.1算法的时间复杂度16
1.5.2算法的空间复杂度17
1.5.3算法分析实例18
1.6扩展与提高20
1.6.1概率算法20
1.6.2算法分析的其他渐进符号21
思想火花——好算法是反复努力和重新修正的结果21
习题122
考研真题125第2章线性表27
2.1引言28
2.2线性表的逻辑结构29
2.2.1线性表的定义29
2.2.2线性表的抽象数据类型定义29
2.3线性表的顺序存储结构及实现31
2.3.1顺序表的存储结构31
2.3.2顺序表的实现31
2.4线性表的链式存储结构及实现36
2.4.1单链表的存储结构36
2.4.2单链表的实现38
2.4.3双链表46
数据结构——从概念到C++实现（第4版）
目录
2.4.4循环链表47
2.5扩展与提高48
2.5.1线性表的静态链表存储48
2.5.2顺序表的动态分配方式50
2.5.3顺序表和链表的比较52
2.6上机实验53
2.6.1顺序表的上机实现53
2.6.2单链表的上机实现53
2.6.3提纯线性表54
2.6.4约瑟夫环问题55
习题257
考研真题261第3章栈、队列和数组63
3.1引言64
3.2栈65
3.2.1栈的逻辑结构65
3.2.2栈的顺序存储结构及实现66
3.2.3栈的链式存储结构及实现68
3.2.4顺序栈和链栈的比较70
3.2.5栈的应用70
3.3队列72
3.3.1队列的逻辑结构72
3.3.2队列的顺序存储结构及实现73
3.3.3队列的链式存储结构及实现76
3.3.4循环队列和链队列的比较79
3.3.5队列的应用79
3.4多维数组79
3.4.1数组的逻辑结构79
3.4.2数组的存储结构与寻址80
3.5矩阵的压缩存储81
3.5.1特殊矩阵的压缩存储82
3.5.2稀疏矩阵的压缩存储84
3.6扩展与提高86
3.6.1两栈共享空间86
3.6.2双端队列87
3.6.3广义表88
3.7上机实验92
3.7.1顺序栈的上机实现92
3.7.2链队列的上机实现92
3.7.3括号匹配问题93
3.7.4机器翻译94
思想火花——用常识性的思维去思考问题96
习题396
考研真题399第4章树和二叉树102
4.1引言103
4.2树的逻辑结构104
4.2.1树的定义和基本术语104
4.2.2树的抽象数据类型定义105
4.2.3树的遍历操作106
4.3树的存储结构107
4.3.1双亲表示法107
4.3.2孩子表示法107
4.3.3孩子兄弟表示法108
4.4二叉树的逻辑结构109
4.4.1二叉树的定义109
4.4.2二叉树的基本性质110
4.4.3二叉树的抽象数据类型定义112
4.4.4二叉树的遍历操作113
4.4.5二叉树的构造114
4.5二叉树的存储结构115
4.5.1顺序存储结构116
4.5.2二叉链表116
4.5.3三叉链表121
4.6森林122
4.6.1森林的逻辑结构122
4.6.2树、森林与二叉树的转换122
4.7最优二叉树124
4.7.1哈夫曼算法124
4.7.2哈夫曼编码127
4.8扩展与提高128
4.8.1二叉树遍历的非递归算法128
4.8.2线索链表131
4.8.3堆与优先队列135
4.8.4并查集138
4.9上机实验140
4.9.1二叉链表的上机实现140
4.9.2孩子兄弟链表的上机实现140
4.9.3最近共同祖先141
4.9.4镜像对称二叉树142
思想火花——调试程序与魔术表演144
习题4145
考研真题4148第5章图151
5.1引言152
5.2图的逻辑结构153
5.2.1图的定义和基本术语153
5.2.2图的抽象数据类型定义155
5.2.3图的遍历操作156
5.3图的存储结构及实现158
5.3.1邻接矩阵158
5.3.2邻接表161
5.3.3邻接矩阵和邻接表的比较165
5.4最小生成树166
5.4.1Prim算法167
5.4.2Kruskal算法169
5.5最短路径173
5.5.1Dijkstra算法174
5.5.2Floyd算法176
5.6有向无环图及其应用178
5.6.1AOV网与拓扑排序178
5.6.2AOE网与关键路径181
5.7扩展与提高183
5.7.1图的其他存储方法183
5.7.2图的连通性185
5.8上机实验186
5.8.1邻接矩阵的上机实现186
5.8.2邻接表的上机实现187
5.8.3农夫抓牛187
5.8.4研发卡车189
思想火花——直觉可能是错误的190
习题5191
考研真题5195第6章查找技术198
6.1概述199
6.1.1查找的基本概念199
6.1.2查找算法的性能199
6.2线性表的查找技术200
6.2.1线性表查找结构的类定义200
6.2.2顺序查找201
6.2.3折半查找201
6.3树表的查找技术204
6.3.1二叉搜索树204
6.3.2平衡二叉树209
6.3.3B树213
6.4散列表的查找技术217
6.4.1散列查找的基本思想217
6.4.2散列函数的设计218
6.4.3处理冲突的方法220
6.4.4散列查找的性能分析224
6.4.5开散列表与闭散列表的比较225
6.5模式匹配225
6.5.1BF算法225
6.5.2KMP算法227
6.6扩展与提高229
6.6.1顺序查找的改进——分块查找229
6.6.2折半查找的改进——插值查找229
6.6.3平衡二叉树的改进——红黑树230
6.6.4B树的改进——B+树235
6.6.5各种查找方法的比较236
6.7上机实验237
6.7.1折半查找算法的上机实现237
6.7.2散列查找算法的上机实现237
6.7.3团队合照238
6.7.4独一无二的雪花239
思想火花——把注意力集中于主要因素241
习题6242
考研真题6245第7章排序技术248
7.1概述249
7.1.1排序的基本概念249
7.1.2排序算法的性能250
7.1.3排序类的定义250
7.2插入排序251
7.2.1直接插入排序251
7.2.2希尔排序253
7.3交换排序255
7.3.1起泡排序255
7.3.2快速排序256
7.4选择排序259
7.4.1简单选择排序259
7.4.2堆排序261
7.5归并排序266
7.5.1二路归并排序的递归实现266
7.5.2二路归并排序的非递归实现267
7.6外部排序269
7.6.1外部排序的基本思想269
7.6.2置换选择排序270
7.6.3败者树272
7.7各种排序算法的比较273
7.7.1各种排序算法的使用范例273
7.7.2各种排序算法的综合比较273
7.8扩展与提高275
7.8.1排序问题的时间下界275
7.8.2基数排序277
7.9上机实验279
7.9.1插入排序的上机实现279
7.9.2交换排序的上机实现279
7.9.3车厢重排280
7.9.4topK问题281
思想火花——学会“盒子以外的思考”282
习题7283
考研真题7286
附录A考研真题参考答案288
附录B实验报告的一般格式293
参考文献294
发布于：北京市富明配资提示：文章来自网络，不代表本站观点。
