课程名称 |
数据结构实验 |
Experiments of Data Structure |
开课单位 |
计算机科学与工程学院 |
课程性质 |
必修课 |
课程类别 |
实践环节 |
课程代码 |
210731103301 |
学分 |
1 |
学时 |
22 |
适用专业 |
计算机科学与技术、软件工程、物联网工程、信息安全、智能科学与技术 |
先修课程 |
程序设计基础 |
支撑课程 |
数据结构 |
授课语言 |
中文 |
一、课程简介
（一）课程中文简介
《数据结构》课程具有较强的编程实践性，内容丰富且抽象，《数据结构实验》的主要任务是将数据结构的理论知识应用于实践之中，以此提高学生编程解决复杂实际问题的能力。
通过该实验课程的学习，使学生能够掌握线性表、栈、队列、树、图以及查找表等各类常用数据结构的基本概念及其不同的实现方法，学会其中的编程技巧和规律，能根据具体问题的特点选择或者设计合理的数据结构，并掌握查找、排序算法及算法背后隐含的算法设计策略，培养学生良好的算法设计和编码技能等专业能力。学生最终能熟练使用C、C++及其相应的编译环境完成求解算法的设计、代码编写和程序调试，为后续算法设计与分析、软件工程和操作系统等课程奠定基础。
（二）课程英文简介
Data structure has strong programming practice property. It is rich in content and very abstract. The main task of experimental course is to apply the theoretical knowledge of data structure to practice, so as to improve students' ability to solve complex practical problems.
Through this course, the students shouldmaster the definition and realization of various data structures including linear tables, stacks, queues, trees, graphs and search tables.It enables students to master the programming skillsand select or design an appropriate data structure according to the specific problems. It also enables students to master search and sorting algorithms and some general algorithm design strategies behind concrete algorithms, and cultivate students' good algorithm design ability and programming skills and other professional abilities. Finally, the students can complete the algorithm design, coding and debugging using C or C++ language and its corresponding compiler environment. This course also helps the students to lay the foundation for the follow-up courses including algorithm design and analysis, software engineering, operating systems etc.
二、实验课程目标
本课程的目标包括：
CO1：掌握线性表、栈、队列、树、图和查找表等常见抽象数据类型的相关概念，实现各类数据结构的基本操作。
CO2：掌握线性表、栈、队列、树、图、查找表以及排序相关的各类算法原理及算法设计的一般步骤，运用递归、分治、贪心、动态规划等面向复杂问题的算法设计策略求解典型问题。
CO3：综合运用各种数据结构类型及算法策略的理论知识，设计计算机技术与应用领域复杂工程问题的求解方案，完成问题求解。
课程目标与所支撑的毕业要求指标点的对应关系如下表所示。
适用专业 |
毕业要求内涵观测点 |
课程目标 |
计算机科学与技术 |
GR3.1能够综合运用计算机科学与技术专业涉及的工程设计概念、原则和方法，针对复杂工程问题提出合理的解决方案。 |
CO1，CO2，CO3 |
软件工程 |
GR3.3能够针对特定软件需求，完成模块设计，并在设计中体现创新意识，特别是互联网应用、智能应用软件与游戏软件领域的算法设计。 |
CO1，CO2，CO3 |
物联网工程 |
GR3.4综合利用物联网应用领域的专业知识和新技术,在针对复杂工程问题的系统设计中体现创新意识。 |
CO1，CO2，CO3 |
信息安全 |
GR3.3能根据目标选取恰当的信息安全技术与设计流程。 |
CO1，CO2，CO3 |
智能科学与技术 |
GR3.2能够针对人工智能应用系统的功能模块，进行面向应用领域的算法设计，应用软硬件开发技术完成详细设计与实现。 |
CO1，CO2，CO3 |
三、实验内容与要求
（一）实验设计（实验类型及内容）
数据结构实验课程包含6个实验，实验内容主要是重现线性表、栈、队列、树、图和查找表等的基本操作，针对应用问题，综合运用各类数据结构以及递归与分治、贪心、动态规划等算法设计策略的相关知识，选择并设计合适的数据结构及算法，给出实验方案，获得实验结果。
实验课程目标 |
对应实验 |
CO1 |
实验1、实验5 |
CO2 |
实验2、实验6 |
CO3 |
实验3、实验4 |
（二）实验内容及要求
编号 |
实验项目 |
学时数 |
实验内容 |
实验类型 |
实验要求 |
1 |
线性表 |
2 |
（1）线性表抽象数据类型的实现：顺序表、链表及改进的单链表的基本操作； （2）线性表的应用：顺序表的合并、有序表的合并、多项式计算。 |
综合性 |
必做 |
2 |
栈和队列 |
4 |
（1）栈和队列抽象数据类型的实现：栈、队列的基本操作； （2）栈和队列的应用：如程序括号匹配检测、表达式求值、银行排队问题等。 |
综合性 |
必做 |
3 |
树与二叉树 |
4 |
（1）树与二叉树抽象数据类型实现：树与二叉树的基本操作； （2）递归与分治策略的程序设计：利用递归和分治策略实现树与二叉树相关问题的求解，如求二叉树的深度； （3）树与二叉树的应用：如Huffman树、文件目录管理等。 |
设计研究性 |
必做 |
4 |
图 |
4 |
（1）图抽象数据类型实现：图的创建和遍历等基本操作； （2）贪心和动态规划策略的程序设计：利用贪心和动态规划策略实现图相关问题的求解，如最短路； （3）图的应用：如拓扑排序、校园导航等。 |
设计研究性 |
必做 |
5 |
查找表 |
4 |
静态查找表与动态查找表的查找算法的实现：如折半查找、二叉排序树的操作，哈希查找的实现及应用。 |
综合性 |
必做 |
6 |
内部排序 |
4 |
快速排序、归并排序等排序算法的实现及其应用。 |
综合性 |
必做 |
注：任课教师可根据授课班级学生特点设计不同的具体实验内容，各项目学时可适当调整。
四、实验设备与环境配置
1. 计算机：Intel Core2 Duo E4300 1.8GHZ、内存4G以上、硬盘100GB以上，每个学生一台。
2.开发环境：CodeBlocks或者Visual C++6.0等C及C++编程环境。
五、课程思政、创新创业元素
教学章节 |
知识点 |
思政元素案例 |
培养目标 |
备注 |
实验2 |
队列的运算规则 |
排队对社会的影响 |
遵守社会秩序、规章制度、遵纪守法，学习并践行社会主义核心价值观。 |
|
实验3 |
树的结构特点 |
家族家谱的传承过程 |
鼓励学生辩证地学习传统文化，引导学生具有爱国情怀， 爱家、爱家族、爱家乡、爱祖国。 |
|
实验4 |
迪杰斯特拉算法 |
Dijkstra的生平事迹 |
引导培养学生严谨务实、坚持真理以及终生学习的科研精神。 |
|
实验5 |
搜索的应用 |
人工智能的发展 |
引导培养学生的科学精神与工匠精神 |
|
实验6 |
基数排序 |
基数排序的提出 |
培养学生的逆向思维，多角度分析问题、解决问题的能力 |
|
实验4 |
图的应用 |
社交网络的发展（如微博、微信等） |
鼓励学生学以致用，培养学生勤于思考、将所学知识应用于解决实际问题的能力 |
创新创业案例 |
实验5 |
查找算法 |
百度网站的创立 |
激发学生的创新创业动力及勇气，培养学生用于探索和敢于创新的精神 |
创新创业案例 |
六、主要参考资料
[1] 严蔚敏，吴伟民著.数据结构（C语言版）[M]. 北京：清华大学出版社，2007-03．
[2] 科曼（Cormen,T.H.）等著，潘金贵 等译.算法导论[M]. 北京：机械工业出版社，2006-09.
[3]https://pintia.cn/
七、考核方式、方法及实验成绩评定方法
课程成绩考核包括平时考核和期末考核，其中平时考核占比不低于50%。平时考核包括学习态度、实验项目完成情况、各次实验考核、表达与交流能力、实验报告或程序评价等方面。
（一） 评分标准
考核 环节 |
<60 （不及格） |
60-69 （及格） |
70-79 （中等） |
80-89 （良好） |
90-100 （优秀） |
平时 |
①不能够完成课内实验内容，程序调试及运行结果基本不正确，不能够解决报错问题； ②按时完成实验项目数低于50%； ③不能准确描述问题，不参与交流讨论。 ④报告或程序组织结构不合理，内容不规范或不完整性，逻辑性差。作品表述能力差，实验结果错误或没有。 |
①能够完成课内实验内容，程序调试及运行结果基本正确，基本能够解决报错问题； ②按时完成实验项目占比为60%-75% ③基本能够提出问题，较少参与交流讨论。 ④报告或程序组织结构合理性尚可，内容规范完整性尚可，逻辑性尚可。作品表述能力尚可，实验结果分析较少。 |
①能够完成课内实验内容，程序调试及运行结果正确，基本能够解决报错问题； ②按时完成实验项目占比为75%-90% ③能够提出问题，参与交流讨论。 ④报告或程序组织结构基本合理，内容基本规范完整，基本符合逻辑性。作品表述能力一般，实验结果分析一般。 |
①能够较好完成课内实验内容，程序调试及运行结果正确，方法较好，能够解决报错问题； ②按时完成实验项目占比为90%以上； ③能够较准确地提出问题，交流讨论较积极。 ④报告或程序组织结构较合理，内容比较规范完整，符合逻辑性。作品表述能力较好，实验结果较好。 |
①能够出色完成课内实验内容，程序调试及运行结果稳定，能够独立解决报错问题； ②所有实验项目均按时完成； ③能够准确提出问题，积极交流讨论。 ④报告或程序组织结构合理，内容规范完整，符合逻辑性。作品表述能力出色，实验结果分析准确，并有独到见解。 |
期末考核 |
以考核成绩（分数）为准。 |
（二）考核环节权重
考核环节 |
目标1 |
目标2 |
目标3 |
平时考核 |
Ö |
Ö |
Ö |
期末考核 |
|
Ö |
Ö |
总权重 |
100% |
100% |
100% |
撰稿人：栾文静
审核人：贾瑞生
批准人：罗汉江
