909数据结构考试大纲 - 山东大学研究生招生信息网

《909数据结构考试大纲 - 山东大学研究生招生信息网》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、909-数据结构一、考试基本要求要求考生系统地理解数据结构的基本概念，掌握各种数据结构的定义和实现算法。要求考生具有抽象思维能力，逻辑推理能力，和综合运用所学的知识分析问题和解决问题的能力。二、考试范围和主要内容1．预备知识了解C++和Java基本语法结构；掌握递归思想。2．程序性能了解复杂性的表示和计算方法。掌握插入排序、选择排序、冒泡排序、名词排序基本思想。3．数据描述掌握线性表的公式化描述、链表描述、间接寻址等存储方法，了解遍历器的作用和实现方法，掌握插入、删除、合并等运算方法。掌握箱子排

2、序、基数排序4．数组和矩阵掌握对角矩阵、三对角矩阵、三角矩阵、对称矩阵等特殊矩阵的特征，掌握存储方法和基本运算实现。了解稀疏矩阵的存储方法和基本运算实现。5．堆栈掌握堆栈的基本概念、基本操作和实现方法。掌握括号匹配、离线等价类的实现思想。6．队列掌握队列的基本概念、基本操作和实现方法。7．跳表和散列了解跳表的基本概念、基本操作和实现方法。掌握散列的基本概念、基本操作和实现方法。8．二叉树掌握二叉树的基本概念、存储方法、常用操作和特征；掌握二叉树的前序、中序、后序、按层遍历方法。掌握基于树存储的在

3、线等价类实现。了解树的存储方法。9．优先队列掌握堆的基本概念和插入、删除和初始化方法。掌握堆排序思想。掌握霍夫曼树、霍夫曼编码实现方法。了解左高树基本概念和插入、删除、合并、初始化的实现方法。10．搜索树掌握二叉搜索树(排序树)基本概念和插入、删除、搜索的实现方法。掌握二叉平衡树（AVL树）基本概念和插入、删除、搜索的实现方法。掌握m叉搜索树和B树基本概念以及插入、删除、搜索的实现方法。11．图掌握图基本概念。掌握图的邻接矩阵和临界链表存储方法；掌握图的深度优先和广度优先遍历算法。掌握图的寻找路

4、径和寻找连通构件方法。掌握生成树的寻找方法。12．贪婪算法了解贪婪算法基本理念。掌握AOV网的拓扑排序算法。掌握单源最短路径Dijkstra算法。掌握最小耗费生成树的概念、Prim算法和Kruskal算法。了解AOE网的关键路径算法。13．分而治之算法了解分而治之思想；掌握归并排序、快速排序实现方法。了解选择问题基本思想。14．动态规划掌握所有顶点对时间的最短路径算法。三、参考教材《数据结构，算法与应用——C++语言描述》DataStructures,Algorithms,andApplicat

5、ionsinC++SartajSahni著汪诗林，孙晓东译机械工业出版社2000年出版