山东专升本数据结构考试大纲

山东普通高等教育专升本考试《数据结构》数据结构考试大纲 一.考试要求： 能分析数据的内在逻辑关系 掌握常用数据结构在计算机中的表示方法 理解数据表示和数据处理之间的关系，理解算法效率的分析方法 能利用常见的数据结构，进行算法设计 二.考试内容： 引论 了解数据结构的基本概念 了解数据的逻辑结构、存储对象、算法的概念 理解数据类型、抽象数据类型的概念 理解时间复杂度、空间复杂度的概念 理解数据结构二元组的概念 S=〈D，R〉 线性表 1.理解ADT的概念机基本运算 Abstract Data Type 2.掌握线性表的顺序存储结构及其运算的实现 3.掌握线性表的链接存储技术及其运算的实现 4.理解单链表、循环链表、双向链表的特点 （三）栈 1.掌握栈的定义和基本运算 2.掌握栈的顺序实现及运算的实现 3.掌握栈和队列的链接实现及其运算的实现 4.掌握栈的应用 （共享栈）（后缀表达式）（寄生栈）（括号匹配）（前中后缀转换） 5.理解递归的概念 6.了解分支与递归的关系 7.了解用栈模拟递归技术 （四）队列 1.掌握队列的定义和基本运算 2.掌握队列的顺序实现（循环队列）及其运算的实现 3.掌握队列的链接实现及其运算的实现 4．掌握队列的应用 （五）广义表、串、数组 1.广义表的概念 2.数组的概念和应用 3.数组的压缩、稀疏矩阵、对称矩阵、对角矩阵 4.字符串的概念和相关操作 （六）树 1.掌握树的存储表示，包括双亲表示法、孩子表示法、孩子兄弟表示法、数和二叉树的转换 2.理解二叉树的定义和术语、性质 3.掌握二叉树的存储结构，包括顺序存储、二叉链表 4.掌握二叉树的遍历算法及应用 5.了解线索树、平衡二叉树、B+树、B-树的概念 6.掌握哈夫曼树及其应用 （七）图 1.理解图的概念、术语 2.掌握图的存储结构（邻接矩阵