2016年山东大学909数据结构考研大纲
909-数据结构一、考试基本要求要求考生系统地理解数据结构的基本概念,掌握各种数据结构的定义和实现算法。要求考生具有抽象思维能力,逻辑推理
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年出版
(实习编辑:史若阳)
- 2022-07-06个人考研笔记及资料分享(文学语言学笔记+各科历年真题)
- 2022-03-222019年 山东大学 哲学专业 真题回忆
- 2022-03-22山大文学院拟录取,经验和教训分享
- 2022-02-10免费下载山东大学文学与新闻考研资料
- 2021-11-1908-17年山大文学史包括综合考试真题 笔记 试题分析
- 2021-08-172017山东大学法学院考研经验分享
- 2021-07-212013山大英语语言文学初试复试指南+个人经验(二外日语)
- 2021-05-13山大英语语言文学
- 2021-03-22山东大学管理学考研资料
- 2021-02-26山东大学基础医学之免疫学2020届经验贴