《数据结构》考试大纲

《数据结构》考试大纲

适用专业：计算机科学与技术、计算机软件工程
数据结构课程是一门实践性强的课程，需要进行大量的练习，数据结构课程的习题类型一般分为三类：一类是概念题，常见的形式包括是非判断题、简答题、选择题（单选或多选）与填空题几种；另一类是算法题，包括算法设计与算法填空两种形式；还有一类介于这两类题型之间，称为综合题或者问题求解题，这类题概念性一般不强，也不是写算法，可能是一种方法的具体应用，希望在复习中，多做一些相关的习题。

一、考试内容
1．数据结构的基本概念和术语
2．线性表
应掌握有关线性表基本概念，了解线性表基本操作有哪些；还要掌握线性表顺序存储结构与链式存储结构的构造原理和特点，在这两种存储结构上对线性表实施的一系列操作所对应的算法设计原理和方法，如线性链表、循环链表与双向链表的插入、删除算法的设计等。
3．数组与广义表
在程序设计语言中，通常将数组定义为具有相同类型的数组元素的集合，数组的基本操作有存、取、修改、查找和排序等。掌握常用操作的算法设计。本章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求熟悉这些内容。本章重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其表头表尾的运算，难点是稀疏矩阵的压缩存储表示下转置运算。
4．堆栈与队列
堆栈与队列是计算机领域非常重要的数据结构，从逻辑上看，堆栈与队列都是线性结构，掌握堆栈与队列的基本概念、常用操作的算法设计等。

5．串
本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算。本章重点是掌握串的基本概念和三种表示方法，这也是难点。

6．树与二叉树
了解树型结构的基本概念，掌握其名词术语，如：结点的度、树的度、叶结点、分支结点、树的层次、树的深度、树林、树的有序性等。掌握二叉树的定义、类型、性质；二叉树的存储结构、二叉树的遍历；二叉排序树的定义、建立、删除、查找等。了解Huffman树的概念。
7．图
图是非线性结构中比树结构还要复杂的结构，掌握图的定义、名词术语，如：顶点的度、路径、子图、图的连通、生成树与最小生成树、拓扑排序等；掌握图的存储结构、基本操作并了解图的其一些算法的设计。
8．查找
查找是顺序表和链表的基本应用，应理解查找的基本概念，熟练掌握顺序表查找的基本方法（顺序查找、二分查找），掌握静态索引结构以及查找、构造的基本算法。，理解散列的概念，了解散列函数的构造、解决冲突的方法。重点是熟练掌握顺序表查找的算法并理解静态/动态索引结构的特点。
9．内排序
排序是一种十分基本和重要的操作，了解排序的基本概念，掌握各种内排序方法，会设计内排序的算法。重点掌握插入排序（直接插入排序）、选择排序（直接选择排序、堆排序）、交换排序（气泡排序、快速排序）、归并排序等典型的排序算法及性能分析。

二、考试题型（分值，按100分计）
1、 选择题（单选）（8分）
2、 填空题（30分）
3、 运算题（30分）
3、 程序分析题（8分）
4、 算法设计题（24分）

三、参考书
[1] 《 数据结构（C语言版）》， 严蔚敏主编， 清华大学出版社
[2] 《数据结构题集（C语言版）》， 严蔚敏，吴伟民编著，清华大学出版社
四、考试时间：120分钟


==========

清华计算机专业课考研复习高效攻略

清华计算机专业课暑期复习高效攻略每年都有很多超自信的同学雄赳赳气昂昂的冲刺清华的计算机专业，同样每年也都有很多同学挥泪洒别清华计算机专业的考场。清华计算机专业排名全国第一，又是中国数一数二的名校，其角逐的激烈程度可想而知，专业课的考察的难度也是众所周知。如何在如此激烈的竞争中杀出一条血路金榜题名于2011，优化专业课备考的各个环节事半功倍的复习是关键。专业课教研室对同学们如何在暑期高效备考提供以下建议，供大家参考。复习总体指导思想谈到暑期的复习计划，由于各人的基础和学习背景不同，无法做一个统一的安排，但会有一个总体的指导思想。大家在暑期阶段要看完《数据结构(面向对象方法与C＋＋描述)》、《计算机组成与设计》、《计算机系统结构》、《操作系统概念》这四本书。这一遍不用太细，但要知道大体内容的位置，翻书的时候知道到何处去查找。另外看这四本书的时候可以结合《数据结构习题解析》做一些题目。这里面的题目质量都很好，而且老师喜欢在里面出题，毕竟这是清华老师自己写的书。专业参考书目解析

01 《数据结构(面向对象方法与C＋＋描述)》(第二版) 殷人昆等 清华大学出版社

02 《数据结构习题解析》 殷人昆等 清华大学出版社

03 《计算机组成与设计》(第二版) 王诚、刘卫东、宋佳兴 清华大学出版社

04 《计算机系统结构》(第二版) 郑纬民，汤志忠 清华大学出版社

05 《操作系统-精髓与设计原理》(第五版) William Stallings，陈渝译 电子工业出版

社(2006年2月)

06 《操作系统概念》(第六版) 郑扣根 译 高等教育出版社

这几本书都要买，都要看，没有轻重主次之分。除了这些书之外，还要给大家强烈推荐一本书。《计算机专业研究生入学考试全真题解》，共分5册，分别是：数据结构与程序设计分册。离散数学分册。操作系统分册。编译原理分册。硬件分册(包括数字逻辑、计算机组成原理、计算机系统结构)。这5册内容基本覆盖了计算机专业研究生入学考试涉及的7大部分。书中对知识点和考点之间的关系进行了深入挖掘，对典型例题进行了深入剖析，以求达到举一反三的目的。本书为硬件分册，包括如下几部分内容：试题分析和解题方法。这部分体现了全书的指导思想。主要内容概述。常考知识点及复习方法建议。真题详细解析。这部分是本书重点，汇集了近年来全国20余所著名院校计算机专业研究生入学考试的试题，对其进行了细致、深入的分析、解答和扩展。本书适合报考计算机专业研究生的考生有针对性地进行专业课的复习，也适合希望深入学习计算机专业知识的高校学生作为辅导书参考。同时，本书还可以作为习题集使用。