2011年计算机考研大纲：数据结构与计算机组成原理

"2011年计算机考研大纲涵盖了数据结构和计算机组成原理的主要知识点，旨在帮助考生掌握计算机科学的基础概念、原理和技能。" 在数据结构部分，大纲强调了以下几个核心概念： 1. **线性表**：考生应了解线性表的定义，包括其顺序存储和链式存储两种实现方式，以及线性表在实际问题中的应用。 2. **栈和队列**：要求考生理解栈和队列的基本操作，如入栈、出栈、入队、出队，并能运用这两种数据结构解决实际问题，如递归和回溯算法等。同时，特殊矩阵的压缩存储也是这部分的一个重点。 3. **树与二叉树**：这部分要求考生掌握树的基本概念，深入理解二叉树的性质，包括遍历算法（前序、中序、后序）和线索二叉树。此外，还需要了解树、森林的存储结构和转换，以及树和二叉树在排序和编码（如哈夫曼树和哈夫曼编码）中的应用。 4. **图**：考生应熟悉图的基本概念，掌握图的存储方法（邻接矩阵和邻接表），并能执行图的遍历（深度优先和广度优先）。此外，图的应用如最小生成树、最短路径、拓扑排序和关键路径的计算也是考核的重点。 5. **查找**：这部分包括查找的基本概念，如顺序查找、折半查找，以及更高级的数据结构如B-树和B+树的基本操作，还有哈希表的查找技术。考生需要能分析和应用这些查找算法。 6. **内部排序**：考生需要理解排序的基本概念，熟悉多种内部排序算法，如直接插入排序、折半插入排序、起泡排序、选择排序、希尔排序、快速排序、堆排序、二路归并排序和基数排序。这部分还包括对各种排序算法的性能比较和实际应用。 在计算机组成原理部分，大纲重点关注： 1. **计算机系统组件**：考生需要理解单处理器计算机中各部件（如CPU、内存、I/O设备等）的工作原理、结构以及它们如何相互连接。 2. **层次化系统结构**：掌握计算机系统从底层硬件到高层软件的层次化结构，理解硬件与软件之间的接口。 3. **指令集架构**：理解指令集的基本概念，熟悉其设计和实现方法，包括指令的编码、寻址模式等。 4. **计算机系统性能分析**：考生需要能运用所学知识分析计算机性能，如指令执行时间、数据传输速率等。 通过以上知识点的学习和掌握，考生应能设计和实现简单的算法，具备基本的程序设计能力，为后续的研究生学习打下坚实的基础。