2015年宜春学院专升本数据结构课程考试大纲

《2015年宜春学院专升本数据结构课程考试大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程考试大纲（一）适用专业：计算机科学与技术（专升本）（二）考试的基本要求：要求考生比较系统地理解数据结构的基本概念和基本理论，掌握数据结构的基本算法。要求考生具有抽象思维能力，逻辑推理能力和综合运用所学的知识分析和解决问题的能力。（三）教材及主要参考书清华大学严蔚敏数据结构(C语言版)（四）课程主要内容一绪论考试内容数据结构抽象数据结构数据类型抽象数据类型算法算法的特性算法设计的要求时间复杂度空间复杂度考试要求1、了解数据结构在计算机科学中的地位和在程序设计中的重要作用。2、了解数据结构的基本概念术语。3、掌握算法的描述和分析算法。二线性表考试内容线性表线性表的逻辑结构

2、和存储结构线性结构的特点线性表的基本操作（初始化，插入，删除等）考试要求1、了解线性表的基本特点和逻辑结构。2、掌握线性表的顺序存储结构和链式存储结构。3、掌握线性表的基本操作。三栈和队列考试内容栈栈的特点栈的表示和实现栈的基本应用队列队列的特点队列的表示和实现队列的应用考试要求1、了解栈和队列的特点。2、了解栈和队列的应用。3、掌握栈和队列的各种表示和实现方式。4、掌握栈和队列的基本操作。四串考试内容串的定义串的存储结构串的基本操作串的模式匹配算法串的应用考试要求1、了解串的特点和各种存储结构。2、掌握串的模式匹配算法。3、了解串的基本应用。五数组和广义表考试内容数组的定义数组的顺

3、序存储结构特殊矩阵稀疏矩阵三元组表十字链表矩阵的转置矩阵的乘法广义表的定义广义表的存储结构广义表的递归算法考试要求1、了解数组和广义表的定义。2、掌握数组和广义表的存储结构。3、掌握特殊矩阵和稀疏矩阵的存储特点。4、掌握矩阵运算和广义表递归算法。六树和二叉树考试内容树的结构定义和存储结构树的基本术语二叉树的定义和基本操作二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树森林的定义森林与二叉树的转换森林和树的遍历哈夫曼树及应用考试要求星原专升本扣：8000-89910、22487015511、了解树和森林的定义和基本概念。2、掌握二叉树的各种存储结构及基本操作。3、掌握二叉树的线索化。

4、4、掌握哈夫曼树的构造方法和应用。七图考试内容图的定义图的基本概念图的存储结构图的遍历图的最小生成树拓扑排序关键路径最短路径考试要求1、了解图的特点和图的基本概念。2、了解图的基本应用。3、掌握图的各种存储结构。4、掌握图的深度优先和广度优先搜索遍历算法。5、掌握图的最小生成树算法。6、学会利用拓扑排序解决问题。7、掌握关键路径和最短路径算法及应用。八动态存储管理考试内容动态存储管理的基本描述可利用空间表首次拟合法最佳拟合法最差拟合法边界标志法的分配与回收算法伙伴系统的分配与回收算法无用单元的收集存储紧缩技术星原专升本：15979868189考试要求1、了解动态存储管理的基本过程。2

5、、掌握动态存储管理的结构和分配算法。3、了解无用单元的收集和存储紧缩技术。九查找考试内容查找表关键字查找顺序表的查找有序表的查找静态树表的查找静态最优查找树次优查找树索引顺序表的查找二叉排序树和平衡二叉树的操作B树的操作键树的操作哈希表哈希函数的构造方法处理冲突的方法查找性能的分析考试要求1、了解各种查找表和查找树的特点和查找性能。2、掌握查找表和查找树的查找方法。3、掌握哈希表的构造方法、查找过程、处理冲突的方法。4、能熟练分析各种查找算法的特点。十内部排序考试内容排序直接插入排序折半插入排序2-路插入排序表插入排序希尔排序快速排序简单选择排序树形选择排序堆排序归并排序基数排序考试

6、要求1、掌握各种插入排序算法及性能。2、掌握快速排序算法及性能。3、了解选择排序算法过程及性能。4、了解基数排序算法过程及性能。5、掌握归并排序算法及性能。6、能够熟练比较各种算法的性能。十一外部排序考试内容外部排序外存信息的存取败者树置换-选择排序最佳归并树磁带归并排序星原专升本扣：8000-89910、2248701551考试要求1、了解外部排序的特点。2、了解外存信息的存取过程。3、学会利用败者树进行归并排序。4、熟悉置换-选择排序的过程。5、了解最佳归并树的构造。6、了解磁带归并排序算法。十二文件考试内容文件顺序文件连续文件串联文件索引文件索引顺序存取方法虚拟存储存取方法散列

7、文件多关键字文件多重表文件倒排文件考试要求1、了解文件的各种逻辑结构和存储结构。2、掌握文件的各种存取方法。3、了解散列文件和多关键字文件的特点和存取方法。