北京大学计算机系
2008级硕士研究生入学考试
数据结构复习提要
2007年10月  张铭  编写
关于算法：
  （1）算法语言无所谓，只要能看懂。考试用 C++出题，但答题随意(可以用C/C++、Java、Pascal、自然语言等等，看得懂就可以) 。
  （2）如果要求自己独立地写算法（而不是填空），请注意写算法思想，并加上足够的注释
  （3）对于算法中直接使用的类和函数（例如栈、队列的函数），应该 先写ADT，并说明函数功能、入口参数、出口参数

考试范围和重点
不考11.3存储管理，不考12.3空间树结构，不考12.4.1决策树、12.4.2博弈树。
各章节以下面的内容为复习重点，尤其是绿颜色文字、红色文字或★标出部分为重中之重。其中红色部分为根据新教材本届考试增加的内容。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质。
________________________________________
第1章 概论 （教材中本章作者为许卓群）
一. 重要概念
    1. 数据类型 2. 抽象数据结构 3. 数据结构 4. 存储结构 5. 算法 6. 算法度量(时间代价、空间代价)
    7.  数据结构的选择和评价
二. 方法
     1. 根据二元组画出图示逻辑结构(注意边的方向)
     2. 根据要求设计数据结构
     3. 算法度量的大O表示法的简化法则（不要求掌握大Ω、大Θ表示法）
　
第2章线性表（教材中本章作者为许卓群）
一. 概念
     1. 线性表 2. 单链表 3. 双链表 4. 循环表 5. 栈 6. 队列 7. 循环队列
二. 方法
    1. 线性表的运算(指针操作的正确性)
    2. 循环队列队列的实现
   ★3. 表达式求值(前中后缀各种表达式互相转化、表达式树与各种表达式互相转换、前缀后缀表达式求值)
    4. 栈的性质，用栈来生成序列
　
第3章字符串（教材中本章作者为许卓群）
一. 概念
   1. 串   2. 模式匹配
二. 方法
   1. 串的基本操作
   2. 串的存储
★ 3. 串的KMP快速模式匹配算法(next数组)，特征next数组（N数组）和利用next数组完成匹配的方法
   4. 相关串运算和处理算法
　
第4章二叉树（教材中本章作者为杨冬青）
一. 概念
      1. 二叉树 2.二叉树的前序、中序、后序周游 3. 二叉排序树 4. 穿线树(中序、前序、后序) 5. Huffman树、Huffman编码 6. 堆、堆排序
二. 方法
      1．二叉树的链式存储
         （1）二叉链表
         （2）带父指针的三重链表
      2. 二叉树的顺序存储
           完全二叉树的顺序存储
★3. 使用栈(前、中、后序)周游二叉树(注意，不要使用带GOTO语句的机械消除递归的方法)、使用队列层次地周游二叉树，在周游过程中寻找某个结点或进行某种操作 (结合应用，例如穿线树，或把快速排序转换成非递归形式)
       4. 二叉树周游时，Visit的访问点问题（注意前、中、后序Visit访问点可以在应用中灵活地结合运用）
       5. 二叉检索树的插入与删除
       6. 构造Huffman树，利用Huffman树进行编码、解码
       7. 堆排序的建堆过程
　
第5章树（教材中本章作者为杨冬青）
一. 概念
       1. 树、森林  2. 树、森林的先根周游、后根周游、层次周游
二. 方法
      1. 树林与二叉树相互转换
      2．森林的链式存储
          (1) 转换为相应的二叉树，用二叉链表表示
          (2) 父指针表示法
          (3) 子结点表表示法
       3. 森林的顺序存储
      不必死记各种顺序存储方法，要了解原理。其本质是按照周游的性质，把顺序存储的森林信息反构造成森林（在内存中往往用二叉树来表示）
       4. 二叉树和森林的层次周游(用队列)，可能结合应用
　
第6章图（教材中本章作者为杨冬青）
一. 概念
     1. 图的深度周游 2. 图的宽度周游 3. 图的生成树、生成树林、最小生成树 （不要求掌握关键路径）
二. 方法
   ★1. 图的存储方法
       （1） 相邻矩阵 （2） 邻接表(结点表 -- 边表)
     2. 图的周游
       （1） 深度优先 （2） 宽度优先
     3. 图的生成树与最小生成树
       （1） 从某一点出发，按深度优先或宽度优先周游的生成树
       （2） 最小生成树 ① Prim算法 ② Kruskal算法(避圈法)
     4. 拓扑排序 : 对于给定图，找出若干个或所有拓扑序列
        任何无环的有向图，都可以拓扑排序。
     5. 最短路径
        Dijkstra算法、Floyd算法(这两个算法都属于贪心法，也属于动态规划法) ★ 两个算法的关键都在求Min的部分
     6. 贪心法
     7. 图的相关算法
　
★第7章内排序（教材中本章作者为张铭）
二. 方法
     1. 重点排序算法：直接插入法、Shell排序、★快速排序、基数排序、归并排序
     2. 算法分析
       （1）基于比较次数和移位次数（一个移位就是一次纪录赋值操作，例如一次 swap 交换是3次移位），分析最好、最坏的时间、空间
       （2） 记住各种排序方法的平均时间
      3. 各种排序方法的局部修改和混合应用
　
第8章文件管理和外排序（教材中本章作者为唐世渭）
一. 概念
     1. 顺序文件 2. 散列文件 3. 倒排文件
二. 方法
     1. 置换选择排序
     2. 赢者树、败者树
     3. 多路归并
　
第9章检索（教材中本章作者为张铭）
一. 概念
     1. 平均检索长度
     2. 二分法检索
   ★3. 散列表、同义词、碰撞、堆积 （聚积）、二次聚集
二. 方法
     1. 二分法检索的判定树、查找某个结点的比较次数
     2. 散列表: 1) 散列函数的选择(除余法、折叠法)
               2) 冲突处理方法(分离同义词子表、线性探测、双散列函数)
     3. 递归分治、回溯
　
第10章索引技术（教材中本章作者为唐世渭）
一. 概念
        动态索引结构(B树)
二. 方法
     1. 索引结构设计以及索引效率分析
    ★2. B树、B+树的插入与删除(注意保持性质，特别是等高；以及子女和关键码个数的上下限制)
         B树中关键码没有重复，父结点中的关键码是其子结点的分界；B+中最底层是关键码的一个全集，往根的方向一层层复写。
         B树插入 : 插入 -------- 分裂
         B树删除 : 交换 -------- 删除 -------- 借关键码 -------- 合并
         B+树插入 : 插入 -------- 分裂
         B+树删除 : 删除 -------- 借关键码 -------- 合并　
　
第11章数组与广义表（教材中本章作者为张铭）
一. 概念
     1. 多维数组 2. 稀疏矩阵 3. 广义表(递归表、再入表)
二. 方法
     1. 数组的行优先、列优先顺序存储地址计算
     2. 稀疏矩阵的三元组及十字链表存储
   ★3. 广义表的带表头的单链形式存储(递归表、再入表)
     4. 广义表的表头、表尾、长度、深度
　
第12章高级树结构（教材中本章作者为张铭）
一. 概念
     1. 字符树(trie树、PATRICIA树)   2. 最佳BST       3. 平衡二叉树(AVL树)      4. 伸展树（半伸展树）
二. 方法
    1. 字符树的画法
    2. 最佳BST以及动态规划方法
    ★3. AVL树的插入(LL，LR，RR，RL四种旋转，不考删除)，严格按照算法来完成
4. 伸展树（半伸展树）的插入操作
5. 红黑树结点的插入、删除（习题集扩展）
6．各种BST的变化和性质
　
操作系统考研考试范围和重点
基本要求：
1、考研题目大致分为两种类型，一类是基本概念、技术和方法（即问答题），一类是基本原理的综合应用（即应用题）。P、V操作题肯定考。
2、一般说来，具体操作系统如Windows、Linux/Unix不考，但讲解原理时引用的UNIX实现方法还要考（主要集中在4-6章）。
3、内容：1-9章，重点4-6章。
4、考试的思路两方面兼顾：灵活运用 与 知识点的全面掌握

说明：蓝色表示重要概念、技术和方法，绿色表示应用。

第1章 操作系统概述
 资源、资源管理的观点
 操作系统、操作系统的地位和作用、操作系统的特征、操作系统的设计目标
 历史上著名的操作系统
 研究操作系统的观点
 操作系统分类（工作方式，特点，追求目标，与其它类型的区别，吞吐量，时间片）

第2章 操作系统的硬件环境
 CPU状态，管态和目态，程序状态字
 存储体系
 缓冲技术
 中断系统
 中断、中断源、中断类型（强迫性中断[硬件故障中断、程序性中断、时钟中断、控制台中断、输入输出中断]，自愿性中断）
 中断响应（中断寄存器，程序状态字，中断响应过程）
 中断处理、各类中断事件的处理
中断优先级、中断屏蔽、中断嵌套处理
 时钟

第3章 作业管理
 用户与操作系统的接口（操作员级接口，程序员级接口）
 批处理系统作业管理（作业组成，作业控制语言，作业说明书，作业输入[预输入程序，数入井，作业表，预输入表，收容状态]，作业调度，作业调度的必要条件，设计作业调度算法的准则，作业调度算法[先来先服务，短作业优先，最高响应比优先，优先数，均衡调度]，作业调度与进程调度的关系，作业的控制执行过程，作业的完成[缓输出程序，输出井]）
 系统调用及其实现

第4章 进程管理
 多道程序设计、为什么引入多道程序设计、引入多道程序设计后带来的问题
 进程、进程与程序的联系和区别、可再入程序、进程的三种基本状态及状态转换
 进程控制块（作用，主要内容）、进程映像
 进程控制：进程的创建和撤消
 进程的特征
 线程、线程与进程的比较、线程的属性、线程的优点（为什么引入线程）
 处理机调度的三种类型
 进程调度、进程调度算法（先来先服务，优先数，时间片轮转，多级队列反馈）、选择进程调度算法的准则、进程调度的时机、进程的切换、调度过程
 系统核心、核心执行特点、核心的组成、中断和进程切换控制流程
 与时间有关的错误
 进程的互斥、临界区、相关临界区、相关临界区管理原则
 进程的同步
 信号量及P、V操作、原语
 用P、V操作解决进程间互斥同步问题
 进程通信、进程通信与P、V操作的比较
 通信机制（共享内存、消息传递[消息缓冲、信箱]、管道文件）

第5章 存储管理
 存储器分类、存储器特点、内存空间划分（系统区、用户区）
 存储管理的功能
 内存空间的分配和回收
 物理地址和逻辑地址（相对地址与绝对地址）、地址重定位（地址转换）、静态重定位、动态重定位
 存储共享、存储保护（防止地址越界、防止操作越权）
 可变分区存储管理（内存分配方法、内存分配表[已分配区表，空闲区表]、内存分配算法[最先适应，最优适应，最坏适应]、内存回收[归还区有下邻空闲区、有上邻空闲区、有上下邻空闲区、没有上下邻空闲区]、硬件提供的支持[基址寄存器，限长寄存器]、地址转换、存储保护、碎片、移动技术[移动增加了系统开销，移动是有条件的，应尽可能减少移动的作业数和信息量]）
 页式存储管理（用户程序划分、逻辑地址形式、内存空间划分、内存分配方式、内存分配表、页表、位示图、空闲块分配算法、空闲块回收算法、硬件提供的支持[页表始址寄存器、页表长度寄存器、高速缓冲存储器[TLB]]、快表、地址转换过程、优缺点）
 虚拟存储技术、虚拟存储器、MMU的作用
 虚拟页式存储管理（基本思想、页表增加内容、缺页中断处理、页面调度、页面调度算法[先进先出、理想、最近未使用、最近最少使用、最不经常使用、第二次机会]、性能考虑[颠簸或抖动，影响缺页中断次数的四个原因，工作集模型]）

第6章 文件管理
 文件、文件名、文件系统
 文件分类
 文件系统的功能
 存储介质、存储设备、块
 文件的存取方式（与文件的存储介质和文件的使用有关，顺序存取方式，随机存取方式）
 磁带结构
 磁盘结构、磁盘地址
 目录项、文件目录、目录文件、文件的按名存取
 树形目录结构（多级目录结构）及其优点
 路径名、绝对路径名、相对路径名
 目录检索、当前目录（值班目录）
 文件目录的改进：目录项分解
 文件逻辑结构：流式文件、记录式文件
 文件物理结构：顺序结构（连续结构）、链接结构（串联结构）、索引结构（UNIX的三级索引结构）
 记录的成组和分解
 磁盘空间管理（位示图、空闲块表、空闲块链[单块链接、成组链接]）
 文件系统的实现（系统打开文件表、用户打开文件表）
 文件操作，六种主要文件操作（何时使用、调用参数、工作过程）
 文件共享（实现方案：直接指向I节点、符号连接）
 文件系统的可靠性与安全性、文件系统的一致性
 文件保护、造成文件被破坏的原因（系统故障，用户使用不当）、文件保护措施（建立副本、定时转储、规定文件存取权限[存取控制表，文件使用权限]）、UNIX的文件使用权限
 文件保密、保密措施（隐藏目录、口令、加密）
 文件系统的性能（块高速缓存、合理分配磁盘空间、信息的优化分布、磁盘驱动）
 磁盘驱动调度、磁盘结构、磁盘地址、执行一次信息传输的时间（寻找时间 + 延迟时间 + 传送时间）、移臂调度、旋转调度、信息优化分布
 移臂调度算法（先来先服务，最短寻找时间优先，电梯调度，单向扫描）、旋转调度算法（同一磁道，不同扇区；不同磁道，不同扇区；不同磁道，同一扇区）

第7章 设备管理
 设备管理的功能、设备独立性
 输入输出操作、设备控制方式、缓冲机制
 设备分类：（从存储介质物理特性角度[存储型设备，输入输出型设备]，从使用角度[独占设备，共享设备，虚拟设备]）
 I/O软件的组成
 I/O硬件组成、I/O过程、I/O端口编址方式
 设备分配与回收、独占设备分配算法、共享设备分配问题
 通道、通道工作原理、为什么引入自成独立系统的通道、通道结构（连接）、通道命令、通道程序、通道地址字、通道状态字
 输入输出中断事件的处理（正常结束，异常结束）
 SPOOLING系统工作原理、联机同时外围设备操作SPOOLING斯普林系统、预输入程序、缓输出程序、脱机外围设备操作
 DMA技术
 缓冲技术

第8章 死锁
 死锁的定义、死锁产生的原因、有关死锁的结论
 产生死所得四个必要条件（互斥使用资源，占有并等待资源，不可抢夺资源，循环等待资源）
 资源分配图（资源类，资源实例，占有边，等待边）、死锁定理、资源分配图化简
 死锁的防止（破坏占有并等待条件[资源的静态分配、释放已占有资源]，破坏不可剥夺条件[允许抢夺资源，具体做法]，破坏循环等待条件[资源有序分配法]）
 死锁的避免（安全状态，银行家算法）
 死锁的检测（资源分配表、进程等待表）
 死锁的解除（重新启动、终止进程，抢夺资源[进程的饿死]，进程回退）

第9章 操作系统结构
 操作系统设计目标（正确性，高效性，易维护性，移植性）
 操作系统结构设计方法
 操作系统层次结构

哦对了 我传的OS大纲是06年的
谁有08年的？？

你没看看那个帖子是什么时候发的