《数据结构与算法》教学大纲.doc

数据结构与算法设计双语教学大纲课程编号：12000042英文名称：Data Structures and Algorithms Design学分：4 学时：64（其中理论学时：52 上机辅导：12）适用专业：计算机科学与技术专业；软件工程专业。一、 目的与任务数据结构是计算机专业的一门综合性基础课程，主要使学生了解数据抽象的目的和意义，学会分析研究计算机加工的数据对象的特征，选择合适的数据结构和存储结构以及相应的算法。初步学会各种算法时间和空间开销的分析方法同时学习本课程也是进行复杂程序设计的训练过程。因此，要求学生能用算法语言书写结构清晰正确的算法。并通过上机实验，使学生受到严格的基本技术训练，以便为今后的工作实践打好坚实基础。该课程是在离散数学、程序设计之后，在集合论、图论等理论基础上，以算法语言为工具，通过数据抽象的方法，研究数据的逻辑结构、存储结构及相应的算法。它是编译原理、操作系统、数据库、和面向对象程序设计等课程的重要基础。本课程通过双语教学的方式，使学生在学习数据结构的同时，加强英语的听、读、写、说的能力。二、 教学内容及学时分配（理论教学52学时+上机辅导12学时）第一章 绪论（理论教学1学时+0上机辅导学时）Chapter 1 Preface什么是数据结构，基本概念和术语，数据抽象和面向对象程序设计。 Definitions of data structure, Basic concepts and terminology, Data abstraction and OOP.第二章 算法分析（理论教学1学时+0上机辅导学时）Chapter 2 Algorithm Analysis程序、算法的定义，算法的时间特性，算法分析的方法和目的。Definition of program and algorithm, Time complexities, Methods and goals of algorithm analysis第三章 线性表、堆栈和队列（理论教学7学时+4上机辅导学时）Chapter 3 Lists, Stacks, and Queues抽象数据类型；线性表的ADT， 线性表的顺序存储结构，线性表的链式存储结构；数据结构与库函数；线性表的应用；静态链表；堆栈的顺序存储结构，堆栈的链式存储结构；栈的应用；栈在后缀、中缀表达式的应用；循环队列，队列应用。Definition of ADT, List ADT，Array implementation of lists, Linked Lists, Data structure and library of function, Applictions of lists, Cursor implementation of linked lists, Stack ADT, Array implementation of lists, Linked lists implementation of stack, Applictions of stacks, Postfix and infix evaluation, Circular queue, Applictions of queue实验：一元多项式程序，股票交易撮合，表达式中缀向后缀的转换，飞机场调度。LAB: 1.Polynomial evaluation, 2. Stock trading, 3. Infix to Postfix Conversion, 4. Schedule of airport第四章： 矩阵和广义表（理论教学3学时+2上机辅导学时）Chapter 4 Matrix And Generic List矩阵的压缩存储，矩阵运算实现。广义表的链式存储结构，广义表的递归算法，广义表的应用。Compression of matrix, Operations on compressed matrix, Linked implementation of generic lists, Recursive functions of generic lists, Applications of generic list.实验：矩阵乘法实现；广义表的建立及基本操作。LAB: 1. Multiplication of compressed matrix, 2. Basic operation of generic list第五章 树（理论教学8学时+2上机辅导学时）Chapter 5 Trees树的定义，树的兄弟表示法，树的遍历，树的应用；二叉树的定义和基本特性，遍历二叉树，二叉树的递归操作，线索二叉树；二叉排序树，平衡二叉树，Splay树，B-树，二叉树应用。Definition of tree ADT, FirstChild-NextSibling Representation, Tree traversals, Applications of trees, Definitions and properties of binary trees, Traversal of trees, Recursive functions of trees, Threaded binary trees, Binary search trees, AVL trees, Splay trees, B-trees, Application of binary trees.实验：树的建立及运算，平衡二叉排序树，博弈。LAB: Basic operation of trees, AVL tress, Game trees.第六章 优先级队列（理论教学2学时+0上机辅导学时）Chapter 6 Priority Queues堆的定义和特性，堆的运算，堆的应用, d-Heaps。Definitions and properties of heaps, Operations of heaps, Applications of heaps, d-Heaps.第七章 排序（理论教学6学时+2上机辅导学时）Chapter 7 Sorting插入排序，排序效率分析，希尔排序，堆排序，合并排序，快速排序，大型数据的排序，桶排序和基数排序。Insertion sort, A lower bound for simple sorting algorithms, Shellsort, Heapsort, Mergesort, Quicksort, Sorting large structures, Bucket sort and radix sort, 实验：快速排序，堆排序。LAB：Quicksort, Heapsort.第八章 哈希表（理论教学3学时+0上机辅导学时）Chapter 8 Hashing哈希表的基本概念，哈希函数设计，冲突解决方法, 哈希表的查找、插入、删除、重建运算。Basic concepts of hash tables, Hash functions designing, Collision solving methods, Basic operations of hash tables, Rehashing. 第九章 等价类（理论教学3学时+0上机辅导学时）Chapter 9 The Disjoint Set ADT等价关系的基本概念，动态等价问题，等价关系基本操作的实现，提高效率的方法。Basic concepts of Equivalence Relations, Dynamic equivalence problem, Basic operations of equivalence class, smart algorithm.第十章 图（理论教学12学时+2上机辅导学时）Chapter 10 Graph Algorithms图的定义和术语，图的存储结构，拓扑排序，AOV网，最短路径，AOE网，关键路径，网络流量分配，最小生成树，深度优先搜索，广度优先搜索，欧拉图，图的连通性，人工智能中的问题求解。Definintions and terminology of graph, Representation of Graphs, AOV network, Topological sort, Shortest path algorithms, AOE network, Critical Path, Network flow problems, Minimum spanning tree, Applications of Depth-First Search, Biconnectivity, Breadth-first search, Euler Circuits, Problem solving in AI.实验：最短路径，关键路径LAB: Shortest path problem, Critical Path Problem*第十一章 算法设计（理论教学6学时+0上机辅导学时）Chapter 11 Algorthm Design Techniques贪婪算法，分治法，动态法，回溯法Greedy Algorithms, Divide and Conquer, Dynamic Programming, Backtracking Algorithms说明：其中的*部分的章节和内容为可选内容。如果不讲授可选部分的内容，6学时可以如下分配：五一假期4学时，期末复习2学时。三、 考核与成绩评定采用日常性考核（作业、实验）和期末终结性考核相结合的方式。作业、实验成绩占40%，期末为闭卷笔试考试，成绩占60%。四、 大纲说明本课程是计算机科学与技术专业、软件工程专业本科生的核心课程。本课程的先修课程包括：离散数学、高级程序设计语言（C/C+）。本课程的后继课程主要包括：软件基础实习、操