作者 名校之梦北京大学计算机系咨询员 ylwxm

　　声明：05年考研的考试范围只有在04年10月份辅导班的时候才能知道。那么我们现在复习的范围是什么？显然是04年的范围。每年范围有变化，但是不大。下面是04年考试的范围，详情可购买辅导班笔记。

　　操作系统：陈向群 杨芙清 的前6章，也就是分布式系统以前的部分，前六章关于unix的要看一下，信号量只考pv操作。

　　数据结构：

　　chp1~3 概念： 数据类型 抽象数据结构 数据结构 存储结构 算法 算法度量（时间空间代价）

　　方法： 根据二元组画出逻辑结构 算法度量的大O表示法的简化法则

　　chp4 概念： 线性表 单链表 双链表 循环表 栈 队列 循环队列

　　方法： 线性表的运算（指针操作的正确性） 表达式求值（表达式二叉树、后缀表达式） 栈的性质，用栈来生成序列

　　chp5 概念： 二叉树 二叉树的前中后序周游 而叉排序树 传线树（前中后） huffman树及编码 堆及堆最排序

　　方法： 二叉树的链式存储：1、二叉链表2、带父指针的三重链表

　　完全二叉树的顺序存储 使用栈周游二叉树 队列层次周游

　　二叉检索书的插入删除 堆排序的建堆过程

　　chp6 概念：书、森林 树的先根后根和层次周游

　　方法： 树林与二叉树相互转换 森林的链式存储 转换为相应的二叉树，用二叉链表表示 父指针的表示法 子节点表示法

　　森林的顺序存储 二叉书和森林的层次周游 树的计数

　　chp7概念：图的深度周游 图的宽度周游 图的生成树、生成树林。最小生成树

　　方法：图的存储－相邻矩阵、邻接表 图的周游－深度优先。宽度优先

　　图的生成树和最小生成树 prim kruskal算法

　　拓扑排序 最短路径

　　chp8： 直接、shell快速、基数、归并

　　算法分析－基于比较次数额移位次数分析的最好、最坏时间和空间 记住各种排序方法的平均时间 各种排序方法的局部修改和混合使用

　　chp9： 顺序文件、散列文件 倒排文件 方法： 多路归并

　　chp10： 概念：平均检索长度 二分法检索 散列表。同义词、碰撞、堆积

　　方法：二分发检索判定树、查找某个节点的比较次数 散列函数的选择 冲突处理的方法

　　chp11：概念：动态索引技术 方法：b b＋的插入和删除

　　chp12：概念：多维数组 稀疏矩阵 广义表 方法：数组的行优先、列优先存储地址的判定 稀疏矩阵的三元组及十字链表存储 广义表带表头的单链存储 广义表的表头、表尾、长度和深度

　　chp13：概念avl树 字符树trie树 方法：avl书的插入 字符树的画法

　　离散（大本）：

　　第一编

　　第一章1.1 1.2 1.3 1.4

　　第二章 1－8节

　　第三章 1－4

　　第四章 1

　　第五章 1－3

　　第二编

　　7.1－7.5 8.1－8.2 9.1－9.2 10.2 11.1－11.4 12.1 12.3－12.4 13.1－13.3 14.4 14.5

　　第三编

　　15.1－15.4 16.1 17.1－17.7 18.1－18.3 19.1－19.4

　　第四编

　　20.1 21.1－21.4 22.1－22.6 23.1－23.4

　　第五编

　　26.1－26.10 27.1－27.7