《数据结构》课程教学大纲

数据结构（DataStructure）课程基本信息课程编号：04021523课程总学时：32实验学时：8学时课程性质：选修课程属性:专业类开设学期：第4学期适用专业：电子信息工程对先修的要求：高等数学、C语言程序设计对后续的支撑：人工智能导论一、课程的教学理念、性质、目标和任务《数据结构》是电子信息专业的一门专业选修课。“数据结构”是设计与实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础，是介于数学，计算机硬件，软件之间的一门重要课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并对进行性能分析和比较。数据结构是程序设计（特别是非数值计算的程序设计）的基础，也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。数据结构课程要求掌握数据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，能够分析算法的时间、空间复杂度，培养良好的程序设计风格，掌握进行复杂程序设计的技能。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。二、课程目标及对毕业要求指标点的支撑序号课程目标支撑毕业要求指标点毕业要求1掌握数据结构的相关概念，理解计算机处理非数值数据问题的基本原理和处理方法，掌握实际问题到不同数据类型数据的抽象过程和处理方法；指标点1.222理解计算机处理数据的基本方法，能够运用数据分析以及数据处理算法，对实际问题进行分析和处理，并能得到有效结果。指标点2.44三、教学内容及进度安排（一）理论教学序号教学内容学生学习预期成果课内学时教学方式支撑课程目标1第1章绪论数据结构、算法描述和算法分析、算法作性能评价的方法；理解抽象数据类型的表示与实现；掌握数据结构的内容。熟悉与数据结构相关的基本概念和基本方法。2课堂PPT讲解目标12第2章线性表线性表的抽象数据类型定义；线性表的顺序存储和链式存储方法；线性表的各种运算、一元多项式的表示及相加。掌握线性表的各种运算、一元多项式的表示及相加。2课堂PPT讲解+代码演示；典型应用案例分析。目标13第3章限定性线性表——栈和队列栈和队列的抽象数据类型定义；栈与递归的实现；栈和队列的典型应用；用顺序结构和单链表结构实现栈和队列掌握栈和队列两种限定性线性表的定义、概念、性质和操作方法。4课堂PPT讲解+代码演示；典型应用案例分析。目标14第4章树和二叉树树的概念与定义；二叉树的性质；二叉树、树、森林与二叉树的相互转换。掌握二叉树的遍历，二叉树、树、森林与二叉树的相互转换，哈夫曼树及其应用。6课堂PPT讲解+代码演示；典型应用案例分析。目标15第5章图图的定义与基本术语；有向无环图的应用和最短路径；图的存储结构、图的遍历、图的连通性问题；图的存储结构、图的遍历。掌握各种图的结构、遍历等知识，并能应用图的知识解决实际问题。4课堂PPT讲解+代码演示；典型应用案例分析。目标16第6章查找查找算法的性能评价方法；基于线性表的查找法、基于树的查找法、计算式查找法——哈希法；基于线性表的查找法、基于树的查找法、计算式查找法——哈希法。掌握常用的查找方法。2课堂PPT讲解+代码演示；典型应用案例分析。目标17第7章内部排序排序的基本概念；直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、归并排序。掌握常用的排序方法。2课堂PPT讲解+代码演示；典型应用案例分析。目标1（二）实验教学序号实验名称学时实验教学内容学习要求支撑课程目标1实验一线性表的基本操作2在不同的存储结构（顺序结构和链式结构），实现线性表的基本操作。掌握线性表的特点；掌握线性表的顺序存储结构和链式存储结构的基本运算；掌握线性表的基本操作；能独立编写程序并通过调试。目标22实验二栈及其应用2编写一个程序listack.cpp，实现链栈（假设栈中元素类型ElemType为char）的各种基本运算，并在此基础上设计一个程序完成如下功能：初始化栈s；判断栈s是否非空；依次进栈元素a、b、c、d、e；判断栈s是否非空；输出出栈序列；判断栈s是否非空；释放栈。掌握栈的特点；掌握栈的顺序存储结构和链式存储结构的基本运算；掌握栈的基本操作；能独立编写程序并通过调试。目标23实验三队列的基本操作2编写一个程序，实现队列（假设队列中元素类型ElemType为char）的各种基本运算，并在此基础上设计一个程序，完成如下功能：初始化队列q；判断队列q是否非空；依次进队元素a、b、c；出队一个元素，输出该元素；依次进队元素d、e、f；输出出队序列；释放队列。掌握队列的特点；掌握队列的顺序存储结构和链式存储结构的基本运算；掌握队列的基本操作；能独立编写程序并通过调试。目标24实验四二叉树的基本操作2编写程序实现二叉树的基本运算，并在此基础上设计一个程序完成如下功能：由如图所示的二叉树创建对应的二叉链存储结构b，该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”；输出二叉树b；输出’H’结点的左右孩子结点值；输出二叉树b的高度；释放二叉树b。掌握二叉树的基本概念和其基本操作；掌握二叉树的生成、遍历等算法；能独立编写程序并通过调试。目标2四、课程思政本课程融合课程思政内容，将德育内容融入课程体系。教学过程中探讨学科前沿动态，引导学生探索新知识及培养创新思维和综合能力；将实践教学与理论教学相结合，用完美的实验结果验证理论知识，加深印象并提高学生对此课程的兴趣。主要从以下几个方面开展课程思政教学：（1）激发对算法设计的热爱之情，增强学好专业的使命感和责任感；强化工科思想素养和行为习惯，提高缘事析理、明辨是非的能力和工程伦理意识；培养精益求精的大国工匠精神，激发科技报国的家国情怀和使命担当，成为德才兼备、全面发展的技能型人才.（2）帮助学生树立正确的科学观，提高美学素养，学会欣赏“代码之美”和“算法之美”。（3）哈夫曼树：引导学生要打破常规，从逆向思维的角度分析问题、解决问题。同时引导学生解决问题要寻求最佳方案，以最小大代价达到最大的效益。（4）队列：日常生活排队现象，引导学生要尊重社会公德，遵守公共秩序，要守规矩但是不要墨守陈规。（5）实验数据的客观记录与分析，培养学生的实事求是科学态度。五、教材及参考资料1.选用教材：（1）理论课教材：数据结构——C语言描述（第二版），耿国华，西安电子科技大学出版社，2016（2）实验课教材：自编2.参考书：（1）数据结构与算法分析C语言描述（原书第2版），[美]马克·艾伦·维斯（Mark，Allen，Weiss）著，冯舜玺译译，机械工业出版社，2019（2）数据结构（第5版）（C语言版），邓文华著，电子工业出版社，2019（3）数据结构（C语言版），严蔚敏，清华大学出版社，20183.推荐网站（线上资源）：（1）西北大学:数据结构教学网，/datastr/（2）吉林大学数据结构，/z/i/230.ds（3）南京邮电大学数据结构，/course/NJUPT-1206361803六、教学条件计算机、C语言开发工具。七、课程考核、考核方式及成绩评定序号课程目标（支撑毕业要求指标点）考核内容评价依据及成绩比例(%)成绩比例(%)课堂表现作业实验期末考试1目标1：（支撑毕业要求指标点1.2）数据结构的基本概念、基本原理和处理方法。1020020502目标2：（支撑毕业要求指标点2.4）应用数据结构知识，对实际问题进行分析和处理，并能得到有效结果。00104050合计10201060100（1）课堂表现考核内容及评分标准课程目标考核内容评分标准90-100分80-89分70-79分60-69分<60分课程目标1（10%）考核学生预习、复习、课堂参与情况。遵守课堂纪律，积极参与教学活动，踊跃回答问题，准确率大于90%；或能回答老师提出的问题，准确率大于90%遵守课堂纪律，认真参与教学活动，踊跃回答问题，准确率大于80%；或能回答老师提出的问题，准确率大于80%。遵守课堂纪律，上课状态一般，能回答老师提出的问题，准确率大于70%。遵守课堂纪律，上课状态一般，能回答老师提出的问题，准确率大于60%。遵守课堂纪律，但不能正常参与课堂教学活动，不能回答老师提出的问题。（2）作业评分标准成绩课程目标优秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（<60分）课程目标1（20%）按时上交，书写规范工整；运用所学理论知识和公式正确，计算步骤完整，计算结果正确。按时上交，书写工整；运用所学理论知识和公式正确，计算步骤较完整，计算结果正确。按时上交，书写较工整；运用所学理论知识和公式正确，计算步骤较完整，计算结果基本正确。按时上交，书写潦草；运用所学理论知识和公式基本正确，计算步骤简单，计算结果基本正确。不按时上交书写潦草；运用所学理论知识和公式不正确，计算步骤较少，计算结果不正确。每次作业按百分制评分，以所有作业的平均成绩计入总成绩。（3）实验环节评分标准成绩课程目标优秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（<60分）课程目标2（10%）实验态度端正；实验操作规范、实验结果正确；考核中能准确地回答全部问题；实验报告撰写规范、整洁、全面。实验态度端正；实验操作规范、实验结果正确；考核中能基本准确地回答全部问题；实验报告撰写规范整洁。实验态度端正；实验操作基本规范，实验结果正确；考核中能准确地回答主要问题；实验报告撰写基本规范。实验态度较端正；实验操作基本规范，实验结果基本正确；考核中能准确地回答部分问题；实验报告撰写基本规范。实验态度不端正；无法独立完成实验操作，实验结果不正确；考核中不能准确地回答主要问题；实验报告书写不规范。（4）期末考核内容及评分标准课程目标考核内容评分标准90-100分80-89分70-79分60-69分<60分课程目标1（20%）数据结构的基本概念、基本原理和处理方法。熟练掌握数据结构的基本概念、基本原理和处理方法。掌握数据结构的基本概念、基本原理和处理方法。基本掌握数据结构的基本概念、基本原理和处理方法。了解数据结构的基本概念、基本原理和处理方法。不了解数据结构的基本概念、基本原理和处理方法。课程目标2（40%）应用数据结构知识，对实际问题进行分析和处理，并能得到有效结果。具有很强的应用数据结构知识，对实际问题进行分析和处理，并能得到有效结果。具有较强的应用数据结构知识，对实际问题进行分析和处理，并能得到有效结果。具有一定的应用数据结构知识，对实际问题进行分析和处理，并能得到有