856-数据结构与程序设计.pdf

"数据结构与程序设计" 数据结构与程序设计是计算机科学学院的核心课程，也是其他理工专业的热门选修课。它的主要内容包括线性、树型、图型这些基本数据结构及其相关算法，以及查找和排序的典型算法和算法的时间复杂度和空间复杂度分析。 数据结构的基本概念包括数据结构的抽象数据类型表示与实现、算法的基本概念及设计要求、算法的时间复杂度和空间复杂度分析等。线性表是数据结构的基本类型，包括线性表的类型定义、基本算法，以及集合运算等应用问题的解决方案。栈和队列是另外两种基本数据结构，包括栈的类型定义、栈的顺序存储表示和实现、栈的链式存储表示和实现、队列的类型定义、队列的链式存储表示和实现等。 串是数据结构的另一种基本类型，包括串的类型定义、串的表示和实现、串的模式匹配算法等。数组和广义表是数据结构的其他两种基本类型，包括数组的定义、数组的顺序表示和实现、矩阵的压缩存储、广义表的定义、广义表的存储结构、m 元多项式的表示等。 树和二叉树是数据结构的基本类型，包括树的定义和基本术语、二叉树的定义及性质、二叉树的二叉链表存储结构、遍历二叉树和线索二叉树、树的各种存储结构、树、森林与二叉树的转换、树和森林的遍历、哈夫曼树及其应用、回溯法与树的遍历、树的计数等。 图是数据结构的基本类型，包括图的类型定义、图的存储结构、图的遍历、图的连通性问题、拓扑排序及关键路径、最短路径等。查找是数据结构的基本操作，包括查找表的相关概念、顺序表的查找、有序表的查找、索引顺序表的查找、动态查找表的类型定义、哈希表的构造与查找等。 内部排序是数据结构的基本操作，包括排序的定义、排序方法的分类、插入排序、快速排序、选择排序、归并排序、基数排序等。程序设计是数据结构的基本应用，包括顺序结构程序设计、选择结构程序设计、循环控制、指针、动态内存分配、数组、结构体、函数、类型定义等基本预编译命令。 这个考试大纲要求考生掌握基本的数据结构和经典算法，具备对实际问题进行分析、抽象出表达实际问题的数学模型、设计出解决问题的算法、能灵活运用程序设计技术实现相应算法，具有分析问题、解决问题的能力。