北京林业大学 2011年《数据结构》考试大纲 考试内容 复习参考书 考研辅导

《北京林业大学 2011年《数据结构》考试大纲 考试内容 复习参考书 考研辅导》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》考试大纲一、考试大纲的性质数据结构是报考我校软件工程、计算机技术专业学位硕士的考试科目之一。为帮助考生明确考试复习范围和有关要求，特制定本考试大纲。二、考试范围和内容第一章数据结构基本概念(1)数据结构的一些基本概念：数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。(2)抽象数据类型的表示和实现。(3)算法时间复杂度和空间复杂度的分析。第二章线性表(1)线性表的类型定义。(2)线性表的顺序存储方法和实现，相关查找、插入和删除算法算法实现。(3)线性表的链式存储方法和实现，相关查找、插入和删除算法算法实现，同时要注意链表中的

2、头结点、头指针和首元结点的区别及循环链表、双向链表的特点。(4)从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。第三章栈和队列(1)栈的定义及特点，栈的顺序存储和链接存储的表示和实现，进栈出栈算法，注意栈满和栈空的条件。(2)栈的应用举例，如迷宫求解和表达式求值。(3)栈与递归的实现，Hanoi塔问题。(4)队列的定义及特点，队列的顺序存储(循环队)和链接存储的表示和实现，循环队列和链队列的进队出队算法。循环队列中队头与队尾指针的表示，队满及队空条件。第四章串(1)串类型的定义。11/5【育明教育】中国考研考博专业课辅导第一品牌官

3、方网站：http://www.yumingedu.com开设课程：【网络函授班】【精品小班】【高端一对一】【状元集训营】【定向保录】(2)串的表示和实现，包括定长顺序存储表示，堆分配存储表示和块链存储表示。(3)串的模式匹配算法，包括古典的模式匹配算法和KMP算法。第五章数组和广义表(1)数组的逻辑结构定义和存储方法。(2)特殊矩阵和稀疏矩阵的压缩存储方法及其适用范围。(3)广义表的结构特点及其存储方法。第六章树和二叉树(1)二叉树的定义、性质和存储结构。(2)二叉树的遍历及有关算法，利用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结

4、点个数、二叉树的高度等。(3)二叉树的线索化，线索化二叉树的特性及寻找某结点的前驱和后继的方法。(4)树和森林的定义、存储结构与二叉树的转换。(5)树的应用，哈夫曼树及哈夫曼编码、带权路径长度的计算。第七章图(1)图的定义及相关术语和性质。(2)图的存储结构四种存储结构：数组表示法、邻接表、十字链表和邻接多重表。(3)图的两种遍历策略：深度优先搜索和广度优先搜索，以及相关算法。(4)图的连通性，连通分量，最小生成树，构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。(5)拓扑排序和关键路径。(6)两类求最短路径问题的算法，迪杰斯特拉算法和弗洛

5、伊德算法。第八章查找(1)静态查找：顺序查找、折半查找、分块查找的查找方法及其实现方法。(2)动态查找：二叉排序树、平衡二叉树、B-树和B+树。二叉排序树的插入和查找算法及其实现。(3)哈希表：哈希函数的构造方法、处理冲突的方法、哈希表的查找与分析。第九章内部排序22/5【育明教育】中国考研考博专业课辅导第一品牌官方网站：http://www.yumingedu.com开设课程：【网络函授班】【精品小班】【高端一对一】【状元集训营】【定向保录】(1)排序的基本概念。(2)插入排序：直接插入排序、其他插入排序和希尔排序。(3)交换排序：冒泡排序和快

6、速排序。(4)选择排序：简单选择排序、树形选择排序和堆排序。(5)归并排序：2-路归并排序。(6)基数排序：多关键字的排序和链数基数排序。(7)以上各种排序的定义和各种排序方法的特点，并能加以灵活应用。各种排序方法的排序过程及其依据的原则。各种排序方法的算法实现。各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析算法的平均情况和最坏情况的时间性能。排序方法“稳定”或“不稳定”的含义。三、考试方式和时间考试时间：120分钟。考试方式：闭卷笔试。试卷满分：100分考试主要题型：选择题、填空题、判断题、简答题、算法实现及分析题（图示、编

7、程题的算法实现用C语言、C++均可）；四、主要参考书（1）数据结构（C语言版）.严蔚敏，吴伟民编著，清华大学出版社，1997（2）数据结构——用面向对象方法与C++描述.殷人昆等著，清华大学出版社，2002。（3）殷人昆主编．数据结构与习题解析（用面向对象方法与C++描述）．北京：清华大学出版社．33/5【育明教育】中国考研考博专业课辅导第一品牌官方网站：http://www.yumingedu.com开设课程：【网络函授班】【精品小班】【高端一对一】【状元集训营】【定向保录】2014年有甘XX等多名学员以优异成绩考上北京林业大学的风景园林,城市

8、规划，行政管理，翻译硕士等各个专业，可以说这些专业是我们育明教育的一个王牌专业，希望广大学子能够来育明实地查看，加入我们的辅导课程，你会