数据结构与算法教学大纲-辽宁普通高等学校本科专业信息平台.pdfVIP

《数据结构与算法》教学大纲 （学分 4 ，学时 120 ） 一、课程的性质与任务 本课程是工科软件工程专业大类课程之一，也是信息学科相关专业学生掌握计算机程序与现实世 界问题关联的入门课程。本课程的任务是使学生从应用角度出发，掌握基本数据结构的逻辑结构、物 理结构及常用算法，能够运用课程所讨论的结构和算法更好地进行数据处理，为进一步提高程序设计 的能力、进一步学习和掌握计算机专业基础知识奠定基础。 二、课程内容、基本要求与学时分配 （一）数据结构与算法概念 2 学时 1． 了解数据结构的基本概念，数据的逻辑结构与物理结构的相互关系。 2． 了解算法概念及计算复杂度的概念。掌握基本的算法分析技巧。 （二）线性表 10 学时 1．了解线性表的逻辑结构特性，以及线性表的两种存储实现方式。 2．掌握顺序表的定义与实现，包括有哪些信誉好的足球投注网站、插入、删除等基本算法的实现。会分析基本算法的最 坏情况和平均情况时间复杂度。 3．掌握单链表的定义与实现，包括有哪些信誉好的足球投注网站、插入、删除等基本算法的实现。会分析基本算法的最 坏情况和平均情况时间复杂度。了解带表头链表和不带表头链表的区别。 4．了解循环链表的特点，循环链表上的基本操作。 5 ．了解双向链表的特点，双向链表上的基本操作。 6 ．掌握栈的概念、特性，栈的顺序存储结构和链式存储结构及相应的基本操作。会用栈结构解 决基本问题。 7 ．了解递归的概念和递归的栈实现思想。会用递归技术解决基本问题。 8．掌握队列的概念、特性，队列的顺序存储结构和链式存储结构及相应的基本操作。会用队列 结构解决基本问题。 9 ．了解字符串作为一类特殊线性表的重要性。掌握字符串类的实现及基本算法实现。掌握简单 模式匹配算法。了解 KMP 算法思想，会分析 KMP 算法的时间复杂度。 （三）树与二叉树 12 学时 1．掌握二叉树的概念、性质及二叉树的表示。 2 ．掌握二叉树的遍历方法，包括非递归算法。 3 ．掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。 4 ．掌握堆的定义，堆的建立、堆的插入与删除、堆的向上和向下调整等算法以及用来实现优先 级队列的方法。 5 ．掌握二叉有哪些信誉好的足球投注网站树的插入、删除、有哪些信誉好的足球投注网站算法，掌握 AVL 树的平衡化旋转、构造、插入、删除时 的调整方法。 6 ．了解树与森林的概念及存储方法、树的遍历算法，掌握树与二叉树的相互转换。 7 ．掌握霍夫曼树的实现方法、构造霍夫曼编码的方法及带权路径长度的计算，会用霍夫曼树进 行编码和解码。 （四）图 10 学时 1．掌握图的概念、性质及基本存储方法：邻接矩阵和邻接表，了解多重邻接表和十字链表。 2 ．掌握图的两种遍历算法与求解连通性问题的方法，包括深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站算法、 求连通分量的方法。 3 ．掌握构造最小生成树的 Prim 算法和 Kruskal 算法，会在给定实例图上描述算法过程。 4 ．掌握单源最短路径的Dijkstra 算法，会在给定实例图上描述算法过程。了解所有点对之间的最 短路径算法。 5 ．了解活动网络的表示方法，掌握关键路径的算法。 （五）排序 8 学时 1．了解排序算法的概念、用途及基本分析方法。 2 ． 掌握插入排序、冒泡排序、选择排序等基本算法的思想及程序实现，会分析各类算法的时间 复杂度。 3 ．了解希尔排序的算法思想。 4 ．掌握快排序、归并排序、堆排序等高级算法思想及程序实现，了解分析这些算法时间复杂度 的技巧。了解各个算法的改进方法。 5 ．了解基数排序算法思想，会使用基数排序算法对4 位数以下的整数序列