硕士入学考试大纲.docx

硕士入学考试大纲考试科目代码及名称：910数据结构一、考试要求1、掌握数据结构的基本概念、基本原理和基本方法。2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析Q3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C+语言设计与实现算法的能力。二、考试内容一、线性表（一）线性表的定义和基本操作（二）线性表的实现1、顺序存储2、链式存储3、线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树1、二叉树的定义及其主要特征2、二叉树的顺序存储结构和链式存储结构3、二叉树的遍历4、线索二叉树的基本概念和构造（三）树、森林1、树的存储结构2、森林与二叉树的转换3、树和森林的遍历（四）树与二叉树的应用1、二叉排序树2、平衡二叉树3、哈夫曼（HUffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作1、邻接矩阵法2、邻接表法3、邻接多重表、十字链表（三）图的遍历1、深度优先搜索2、广度优先搜索（四）图的基本应用1、最小（代价）生成树2、最短路径3、拓扑排序4、关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）分块查找法（四）折半查找法（五）B-树及其基本操作、B+树的基本概念（六）散列（HaSh）表（七）字符串模式匹配（A）查找算法的分析及应用六、排序（一）排序的基本概念（二）插入排序1直接插入排序2、折半插入排序（三）冒泡排序（BUbbIeSOrt）(四)简单选择排序(五)希尔排序(ShenSOrt)(六)快速排序(七)堆排序(A)二路归并排序(MergeSort)(九)基数排序(+)各种排序算法的比较(十一)排序算法的应用三、试卷结构(题型分值)1本科目满分为150分，考试时间为180分钟。2.题型结构(1)选择题：占总分的40/150。(2)简答题：占总分的20/150。(3)分析计算题：占总分的30/150。(4)算法分析阅读题：占总分的30/150。(5)算法设计题：占总分的30/150。四、参考书目数据结构(C语言版)，严蔚敏、吴伟民编著，清华大学出版社，2007年。