2009年计算机考研大纲:数据结构与基础知识

需积分: 9 2 下载量 187 浏览量 更新于2024-12-02 收藏 210KB PDF 举报
"2009年研究生入学考试计算机统考大纲涵盖了数据结构、计算机组成原理、操作系统和计算机网络这四门学科的基础课程。大纲强调考生需系统掌握这些课程的概念、基本原理和方法,并能应用到理论问题和实际问题的解决中。试卷满分为150分,考试时间为180分钟,答题方式为闭卷笔试。内容结构包括数据结构45分,计算机组成原理45分,操作系统35分,计算机网络25分。题型包括单项选择题和综合应用题。数据结构部分要求理解基本概念,设计与分析算法,以及根据问题选择合适的数据结构。具体包括线性表、栈、队列、数组、树与二叉树、图、查找和内部排序等子话题。" 在数据结构部分,大纲详细规定了以下知识点: 1. 线性表:包括线性表的定义、基本操作,以及顺序存储结构和链式存储结构的实现,还有线性表的应用场景。 2. 栈和队列:讲解了栈和队列的基本概念,如进栈、出栈、入队、出队,以及它们的顺序存储结构和链式存储结构,同时探讨了栈和队列在实际问题中的应用。 3. 树与二叉树:涵盖了树的基本概念,二叉树的定义、特征、存储结构(顺序和链式)、遍历方法(前序、中序、后序),线索二叉树、二叉排序树和平衡二叉树。 4. 图:介绍了图的基本概念,图的存储结构(邻接矩阵和邻接表),图的遍历方法(深度优先搜索和广度优先搜索),以及图的应用,如最小生成树、最短路径、拓扑排序和关键路径。 5. 查找:包含查找的基本概念,如顺序查找、折半查找,B-树的介绍,散列(Hash)表及其查找操作,以及查找算法的分析和应用。 6. 内部排序:讲解了排序的基本概念,具体排序算法如直接插入排序、折半插入排序、气泡排序、简单选择排序和希尔排序。 这个大纲为准备研究生入学考试的考生提供了全面的复习指导,要求考生不仅要理解理论知识,还要具备将知识应用于实际问题的能力。考生需要对每个主题进行深入学习,掌握各种数据结构的操作和应用,以及各种算法的设计与分析技巧。