|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
909-数据结构
一、考试基本要求
要求考生系统地理解数据结构的基本概念，掌握各种数据结构的定义和实现算法。要求
考生具有抽象思维能力，逻辑推理能力，和综合运用所学的知识分析问题和解决问题的能力。
二、考试范围和主要内容
1．预备知识
了解 C++和 Java 基本语法结构；掌握递归思想。
2．程序性能
了解复杂性的表示和计算方法。
掌握插入排序、选择排序、冒泡排序、名词排序基本思想。
3．数据描述
掌握线性表的公式化描述、链表描述、间接寻址等存储方法，了解遍历器的作用和实现
方法，掌握插入、删除、合并等运算方法。
掌握箱子排序、基数排序
4．数组和矩阵
掌握对角矩阵、三对角矩阵、三角矩阵、对称矩阵等特殊矩阵的特征，掌握存储方法和
基本运算实现。
了解稀疏矩阵的存储方法和基本运算实现。
5．堆栈
掌握堆栈的基本概念、基本操作和实现方法。
掌握括号匹配、离线等价类的实现思想。
6．队列
掌握队列的基本概念、基本操作和实现方法。
7．跳表和散列
了解跳表的基本概念、基本操作和实现方法。
掌握散列的基本概念、基本操作和实现方法。
8．二叉树
掌握二叉树的基本概念、存储方法、常用操作和特征；掌握二叉树的前序、中序、后序、
按层遍历方法。
掌握基于树存储的在线等价类实现。
了解树的存储方法。
9．优先队列
掌握堆的基本概念和插入、删除和初始化方法。
掌握堆排序思想。
掌握霍夫曼树、霍夫曼编码实现方法。
了解左高树基本概念和插入、删除、合并、初始化的实现方法。
10．搜索树
掌握二叉搜索树(排序树)基本概念和插入、删除、搜索的实现方法。
掌握二叉平衡树（AVL 树）基本概念和插入、删除、搜索的实现方法。
掌握 m 叉搜索树和 B 树基本概念以及插入、删除、搜索的实现方法。
11．图
掌握图基本概念。
掌握图的邻接矩阵和临界链表存储方法；掌握图的深度优先和广度优先遍历算法。
掌握图的寻找路径和寻找连通构件方法。
掌握生成树的寻找方法。
12．贪婪算法
了解贪婪算法基本理念。
掌握 AOV 网的拓扑排序算法。
掌握单源最短路径 Dijkstra 算法。
掌握最小耗费生成树的概念、Prim 算法和 Kruskal 算法。
了解 AOE 网的关键路径算法。
13．分而治之算法
了解分而治之思想；掌握归并排序、快速排序实现方法。
了解选择问题基本思想。
14．动态规划
掌握所有顶点对时间的最短路径算法。
三、参考教材
《数据结构，算法与应用—— C++语言描述》Data Structures,Algorithms,and
Applications in C++ Sartaj Sahni 著 汪诗林，孙晓东 译 机械工业出版社 2000 年出
版
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
