一、 适应范围及要求

（一）课程类型

《数据结构》课程是大类平台课程，不仅支撑着数据科学与大数据技术专业和计算机科学与技术专业的学科基础与专业核心课程，同时也是物联网工程、人工智能和电子信息类专业的重要专业基础课。

本大纲适应西京学院研究生入学用

（二）课程要求

通过《数据结构》课程的学习，学生将学会数据的基本逻辑结构、存储结构以及包括插入、删除、检索、排序等在内的相关操作，掌握对数据结构进行描述、实现和评价的方法。《数据结构》课程注重培养和训练学生的抽象能力和逻辑思维能力，引导学生学会运用所学知识，科学地分析和解决专业领域内的实际问题。

二、 课程教学内容

第一章概论

了解数据结构的基本概念和术语；深入理解并掌握基本的数据逻辑结构、存储结构，以及数据抽象类型的内涵，掌握并能运用算法时间复杂度分析算法。

重点难点：数据逻辑结构、存储结构；时间复杂度分析。

第二章线性表及其顺序存储

了解线性表的逻辑结构特性，以及线性表的顺序存储实现方式；熟练掌握顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算；熟练掌握栈和队列的定义与实现，以及栈的应用。掌握线性表的特点，掌握线性表顺序存储结构及顺序表的算法实现。

重点难点：线性表的特点以及存储实现，顺序表查找、插入和删除等基本操作实现，栈和队列特点，栈和队列基本操作实现，栈和队列的应用。

第三章线性表的链式存储

理解链表的概念、ADT描述、存储结构的实现及基本运算操作实现；掌握带头结点单链式存储结构及基本运算实现。了解双链表的基本概念及描述、链式栈和链式队列的实现，能够比较分析线性表顺序存储和链式存储优缺点。

重点难点：链表定义、ADT描述、存储实现，带头结点单链表查找、插入和删除等基本操作实现，线性表顺序存储和链式存储的优缺点比较。

第四章字符串、数组和特殊矩阵

了解并掌握字符串、数组和特殊矩阵的基本概念和基本操作；了解串的基本概念，理解串的逻辑结构特性，以及串的存储实现方式；了解数组的基本结构，掌握数组的寻址方式。

重点难点：数组寻址方式，特殊矩阵的压缩存储方法，稀疏矩阵的压缩存储方法。

第五章递归

了解递归程序设计思想和递归程序执行过程分析；能运用递归程序设计思想编程解决简单的实际应用问题。

重点难点：递归的概念、递归程序的执行过程分析，递归程序设计。

第六章树型结构

了解树的基本概念和术语；了解树的三种表示方法；掌握树的前序遍历、中序遍历、后序遍历算法。

重点难点：树的基本概念、树的存储结构，树的遍历。

第七章二叉树

掌握二叉树的基本运算和存储结构。掌握二叉树的链式存储结构和三种遍历的递归实现。掌握二叉树的三种遍历非递归算法和其他运算。了解穿线二叉树的基本概念。

重点难点：二叉树特点和性质，二叉树的ADT描述和存储实现，二叉树遍历的递归和非递归算法，基于二叉树的递归算法。

第八章图

理解图的基本概念、基本运算，掌握图的基本存储结构：邻接矩阵和邻接表；掌握图的深度优先遍历和广度优先遍历算法；重点掌握普里姆和克鲁斯卡尔最小生成树的普里姆和克鲁斯卡尔算法；掌握迪杰斯特拉最短路径算法；了解图的关键路径算法。

重点难点：图的邻接矩阵、邻接表存储结构及其构造方法，图的深度优先和广度优先遍历算法，最小生成树的及其算法，拓扑排序算法、最短路径算法。

第九章检索

掌握几种常用的检索方法。了解检索的基本概念，掌握顺序检索、二分法检索和分块检索算法；掌握Huffman树建立方法、Huffman编码和解码算法思想，掌握散列表检索算法及算法分析。

重点难点：线性表检索算法，Huffman树的构造方法和检索算法，哈希表的构造方法和检索算法，各种检索算法的优缺点和部分算法时间复杂性分析。

第十章内排序

掌握几种常用的内排序算法；了解排序的基本概念；掌握插入排序和选择排序的算法思想及算法程序实现，了解算法时间复杂度与稳定性。掌握交换排序、归并排序和基数排序的算法思想及算法程序实现，了解算法时间复杂度与稳定性。

重点难点：插入排序、选择排序、交换排序、归并排序和基数排序等排序算法的算法思想、程序实现。

三、 教学参考资料

1.参考教材

[1] 李云清，杨庆红，揭安全.《数据结构（C语言版）》（第3版）[M].北京:人民邮电出版社，2014年9月.