还剩1页未读，继续阅读
文本内容:
《数据结构》考试大纲（适用于沈阳师范大学计算机应用技术专业硕士研究生入学同等学力加试）
一、试卷满分及考试时间试卷满分为100分，考试时间为180分钟.
二、答题方式答题方式为闭卷、笔试.
三、试卷题型结构填空题10题，每空2分，共20分选择题10题，每题2分，共20分应用题4题，每题8分，共32分算法设计题2题，每题14分，共28分、考查目标及基本要求I《数据结构》是计算机应用专业硕士研究生入学考试复试科目，本考试主要考查考生以下知识与能力
1.掌握数据、数据结构和抽象数据类型等基本概念；
2.掌握线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用；
3.掌握动态存储管理的基本技术及算法；
4.掌握查找和排序的常用算法以及定性或定量的分析与比较；
5.掌握有关文件的基本概念和常用的文件结构及存取操作；、考试内容II本考试的主要考试内容包括
一、数据结构基本概念
1.数据结构的基本概念（识记）数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等
2.抽象数据类型的表示和实现（识记）
3.算法时间复杂度和空间复杂度的分析（识记）
二、线性表
1.线性表的类型定义（识记）
2.线性表的顺序存储方法和实现（识记），相关查找、插入和删除算法算法实现（识记）
3.线性表的链式存储方法和实现，相关查找、插入和删除算法算法实现（识记），链表中的头结点、头指针和首元结点的区别及循环链表（识记）、双向链表的特点（领会）
4.从时间和空间复杂度的角度比较两种存储结构的不同特点（识记）
三、栈和队列
1.栈的定义及特点，栈的顺序存储和链接存储的表示和实现，进栈和出栈算法（识记），栈的应用（表达式求值、数制转换等）（简单应用）
2.栈与递归的实现（领会）
3.队列的定义及特点，队列的顺序存储（循环队列）和链接存储的表示和实现（识记），循环队列和链队列的进队出队算法（简单应用）
四、串
1.串的定义（识记）
2.串的表示和实现，包括定长顺序存储表示，堆分配存储表示（识记）
3.串的模式匹配算法，包括古典的模式匹配算法和KMP算法（简单应用）
五、数组和广义表
1.数组的逻辑结构定义和存储方法（识记）
2.特殊矩阵和稀疏矩阵的压缩存储方法（识记）及其适用范围（简单应用）
3.广义表的结构特点及其存储方法（识记）
六、树和二叉树
1.二叉树的定义、性质和存储结构（识记）
2.二叉树的遍历及有关算法，利用遍历算法实现二叉树的其他操作（识记），如计算二叉树结点个数、叶子结点个数、二叉树的高度等（综合应用）
3.二叉树的线索化，线索化二叉树的特性（识记）及寻找某结点的前驱和后继的方法（综合应用）
4.树和森林的定义、存储结构（识记）与二叉树的转换（领会）
5.树的应用，哈夫曼树及哈夫曼编码、带权路径长度的计算（综合应用）
七、图
1.图的定义及相关术语和性质（识记）
2.图的存储结构四种存储结构数组表示法、邻接表、十字链表和邻接多重表（识记）
3.图的两种遍历策略深度优先搜索和广度优先搜索（综合应用），以及相关算法（简单应用）
4.图的连通性（识记），连通分量（领会），最小生成树（识记），构造最小生成树的两种算法普里姆算法和克鲁斯卡尔算法（简单应用）
5.拓扑排序（识记）和关键路径（简单应用）
6.两类求最短路径问题的算法，迪杰斯特拉算法和弗洛伊德算法（简单应用）
八、查找
1.静态查找顺序查找、折半查找、分块查找的查找方法（识记）及其实现方法（简单应用）
2.动态查找二叉排序树、平衡二叉树、B+树二叉排序树的插入和查找算法（识记）及其实现（简单应用）
3.哈希表哈希函数的构造方法、处理冲突的方法（识记）、哈希表的查找与分析（简单应用）
九、排序
1.排序的基本概念（识记）
2.插入排序（识记）直接插入排序、其他插入排序和希尔排序（简单应用）
3.交换排序（识记）冒泡排序和快速排序（简单应用）
4.选择排序（识记）简单选择排序和堆排序（简单应用）
5.归并排序（识记）2-路归并排序（简单应用）
6.基数排序（识记）多关键字的排序（简单应用）和链数基数排序（领会）
7.各种排序方法的时间复杂度的分析方法（简单应用）排序方法“稳定力或“不稳定”的含义（领会）
十、文件
1.顺序文件、索引文件、ISAM文件和VSAM文件等文件的基本概念（识记）
2.直接存取文件（散列文件）、多关键字文件、多重表文件和倒排文件等的相关内容及算法（识记）、参考书目III《数据结构》（C语言版）严蔚敏、吴伟民，2012,清华大学出版社。
个人认证
优秀文档
获得点赞 0
