课程名称：算法与数据结构（AlgorithmsandDataStructure）撰写人：李睿审核人：张永一、课程编号：205329二、学时学分：56学时，其中授课48学时，上机8学时，3.5学分三、先修课程：程序设计,离散数学四、适合专业：计算机科学与技术五、课程性质和任务算法与数据结构是计算机科学与技术的一门核心专业基础课程。通过本课程的学习，可以培养学生分析问题、解决问题的能力，使学生学会怎样对处理的数据建立抽象数据类型，利用抽象数据类型进行程序设计。掌握对典型的数据结构的各种基本操作，并使学生对算法的复杂度有一定的分析能力，对各种抽象数据类型的应用背景有进一步的了解，从而拓宽学生的视野。六、主要教学内容1、绪论：什么是数据结构；基本概念和术语；数据结构的发展简史及在计算机科学中所处的地位；算法和算法分析2、线性表：线性表的逻辑结构；线性表的顺序存储结构；线性表的链式存储结构；一元多项式的表示及相加3、栈和队列：栈；栈的应用；栈与递归的实现；队列4、串：串类型的定义；串的表示和实现；串的模式匹配算法；串操作应用举例5、数组和广义表：数组的定义；数组的顺序表示和实现；矩阵的压缩存储；广义表的定义；广义表的存储结构6、树：树的定义和基本术语；二叉树；遍历二叉树和线索二叉树；树和森林；树与等价问题；哈夫曼树及其应用；回溯法与树的遍历；树的计数7、图：图的定义和术语；图的存储结构；图的遍历；图的连通性问题；有向无环图及其应用；最短路径8、查找：静态查找表；动态查找表；哈希表9、内部排序：概述；插入排序；快速排序；选择排序；归并排序；基数排序；各种内部排序方法的比较讨论10、文件：数据在外存中的组织形式七、教学基本要求根据课程在知识结构中的作用，教学要求分为掌握、熟悉、了解、选学四个层次，具体要求如下。1．掌握部分：绪论：算法和数据结构的基本概念；算法和算法分析；线性表：线性表的逻辑结构；线性表的顺序存储结构和链式存储结构及相关算法；栈和队列：栈的顺序存储结构及相关算法；队列的顺序存储结构和链式存储结构及相关算法；树：树的定义和术语；二叉树的性质及存储结构；二叉树三种遍历的递归算法和中序遍历非递归算法；图：图的概念和术语；图的邻接矩阵和邻接表的存储结构；图的遍历；查找：顺序表的查找、有序表的查找算法；二叉排序树的插入；哈希表；内部排序：直接插入排序；希尔排序；快速排序；简单选择排序；堆排序2．熟悉部分：栈和队列：栈与递归的实现；串：串类型的定义；串的表示和实现；树：树的存储结构；二叉树、树和森林的转换；哈夫曼树及其应用；图：最小生成树、拓扑排序、关键路径和某个源点到其余各顶点的最短路径的算法思想3．了解部分：线性表：一元多项式的表示及相加；串操作应用；数组和广义表：数组的顺序表示和实现及矩阵的压缩存储；广义表的定义及存储结构；二叉树的线索化；图：图的十字链表和邻接多重表的存储结构；每一对顶点之间的最短路径；查找：平衡二叉树、B-树和B+树的概念；内部排序：归并排序；基数排序；文件：数据在外存中的组织形式4．选学部分：离散事件模拟；串的模式匹配算法；B-树的查找分析、插入和删除算法；树：树与等价问题；回溯法与树的遍历；树的计数；查找：键树八、参考学时分配：序号课程主要内容学时讲授实验上机1绪论22线性表613栈和队列614串35数组和广义表26树927图928查找59内部排序5210文件1合计488九、其他说明本大纲依据兰州理工大学2006年本科指导性培养计划编写。十、参考教材1．严蔚敏等编，数据结构，清华大学出版社，1998。2．王晓东等编，算法设计与分析，清华大学出版社，2003。3．ThomasH.Cormen等著，IntroductionToAlgorithms(SecondEdition)，TheMITPress原版，高等教育出版社影印版，2002。