（北大计算机）考研经验贴(zz)

kuddy

05年硕士学位研究生专业目录
计算机系统结构 (081201) 人数:48
01.指令级并行处理与线程级并行处理
02.系统芯片设计方法学
03.微处理器设计技术
04.软硬件协同设计
05.网络信息体系结构
06.网络计算与服务
07.计算机网络与分布式系统
08.分布式海量信息存储
09.计算机网络新技术
报考方向为０１－０４的考生，考试科目为计算机软件基础、计算机硬件基础任选一门；复试笔试科目包括数字逻辑、微机原理、汇编语言程序设计，复试参考书目：《微型计算机基本原理与应用》，王克义等，北京大学出版社，１９９７年。报考方向为０５－０９的考生，考试科目限计算机软件基础；复试笔试科目为计算机网络，复试参考书目为：《计算机网络》 A.S.T（译版、影印版）， Andrew S. Tanunbaum，熊桂喜译，清华出版社，１９９８年。
计算机软件与理论 (081202) 人数:75
01.软件工业化生产技术与系统
02.软件复用与软件构件技术
03.操作系统
04.嵌入式软件
05.面向对象方法与技术
06.软件项目管理
07.计算机语言与编译系统
08.网络与信息安全
09.Web信息共享与集成技术
10.并行计算与网格构件技术
11.知识工程
12.商务智能
13.面向移动设备的空间信息技术
14.Web环境中的信息提取
15.人工智能
16.生物特征识别
17.模式识别
18.图形图像与多媒体
19.人机交互与虚拟现实
20.典型应用领域的数据库与信息系统
21.Ｗｅｂ环境下的数据库与信息集成
22.数据库，数据仓库，数据挖掘
23.自然语言处理
24.机器翻译的理论与技术
25.信息提取
26.算法分析与计算复杂性
27.并行计算与Petri网
28.程序的形式语义与正确性验证
复试阶段笔试科目：报考０１－０７方向：软件工程；报考０８方向、２３－２５方向：计算机网络；报考０９－１７方向、２０－２２方向：数据库；报考１８－１９方向：计算机图形学；报考２６－２８方向：数理逻辑与组合数学。其参考书目为：《计算机网络》 A.S.T（译版、影印版）， Andrew S. Tanunbaum，熊桂喜译，清华出版社，１９９８年；《软件工程》第二版，王立福、麻志毅、张世琨，北京大学出版社，２００２年；《数据库系统概念》（第１至９章，第１５章，第１８章），Abraham Silberschatz等著，杨冬青、唐世渭等译，机械工业出版社，２００３年。
计算机应用技术 (081203) 人数:41
01.文字与图形信息处理
02.知识工程与智能教育
03.电子出版新技术
04.网络与数据库技术的应用
05.内容管理与知识管理
06.彩色图像处理
07.信息安全保障技术
08.嵌入式Linux技术
09.网络攻防技术
10.数字版权保护技术
11.电子政务技术
12.数字视频信息处理与多媒体技术
13.数据仓库与数据挖掘
14.多媒体与智能信息检索
15.人工智能与机器学习
16.时空数据库与时空信息分析技术
17.数字图书馆与数字博物馆
18.数据库与知识库
19.智能商务与Web智能
20.信息系统智能化
21.数据网格与知识网格
22.智能数据分析
复试阶段笔试科目：报考方向０１－０３的考生：软件工程；报考方向０４、１３－２２的考生：数据库；报考方向０５－１２的考生：计算机网络。其参考书目为：《计算机网络》 A.S.T（译版、影印版）， Adrew S. Tanunbaum，熊桂喜译，清华出版社，１９９８年；《软件工程》第二版，王立福、麻志毅、张世琨，北京大学出版社，２００２年；《数据库系统概念》（第１至９章，第１５章，第１８章），Abraham Silberschatz等著，杨冬青、唐世渭等译，机械工业出版社，２００３年。
初试科目：
101政治
201英
701计算机数学基础 (高等数学、离散数学)
01 高等数学（上、下册）  同济大学  高等教育出版社 Jul 1 2002 12:00:00:000AM 5 范围：一元微积分、无穷级数上册：除了第七章和加*号的部分外的所有章节下册：第11章的第一到第五节
02 离散数学教程  耿素云 屈婉玲 北京大学出版社(作者三:王捍贫) Jan 1 2002 12:00:00:000AM  范围：集合论与图论，代数结构第一到第五章，第七到第十九章
890计算机软件基础 (数据结构、操作系统)
01 数据结构  许卓群 杨冬青 高等教育出版社 Jul 1 2004 12:00:00:000AM   
02 数据结构与算法分析--C++第二版  张铭 刘晓丹 电子工业出版社 Jan 1 2002 12:00:00:000AM   
03 操作系统教程  陈向群 杨芙清 北京大学出版社 Jan 1 2001 12:00:00:000AM  第一章至第九章

kuddy

专业：我觉得要重视课后题目和本科生作业，多听课做笔记，重视理解，到后期的时候
os的一些重要的知识点要能背出来，ds的重点算法自己要能独自写出来
数学：离散书上的定理要自己能证出来，书后题最起码要全部独自做两遍以上（个人不十

分推荐做配套习题集的题目，题量太大，还有很多陈题），最重要要多理解，理解透彻。

不过按照今年的试卷来看，大家往往会重视离散过头，而忽视高数的学习（比如我）。如

果明年还是高数70分，离散80分的话建议大家要多花时间在高数上（离散和高数的所花时

间比不能太离谱）
英语：要早开始，作文要早点练，这个视个人基础所花时间，所采用方法而不同
政治：最好不要在10。1号前开始，不要迷信任何考研班，事实上最近几年没有任何考研
班能猜到题。要重视两本书:大纲分析和红宝书，尤其要参照红宝书把大纲分析看透，理
解透。马哲马政经注重理解，毛概邓论注重背诵。答题的时候要注意技巧，分段多写，忌

早交卷。
复试：一般来说在初试考完之前不要想任何复试的事情（什么考试，找导师之类的），初

试考完（甚至初试成绩出来之后）准备复试联系老师都是绰绰有余的。从今年的试卷来看

，今后几年的初试试卷可能也会难度不高（相对02，03，04），上线的人可能会比较多，

因此大家应该重视复试笔试，考得高会比只是刚好及格要有说服力。面试的时候要自信大

方，强调自己的优势，想去哪个实验室要早点联系老师。还有如果不是能保证一定能录取

你报的实验室的话最好多去别的实验室面试一下，省得在一棵树上吊死。
总的来说我觉得最重要的两点是：
1，要听课（实在对不住本科的ddmm，和张老师，陈老师了，不过这是个实话）
2，要几个人一起交流，查漏补缺

kuddy

说一下我觉得帮助最大的几类信息。

1.考研科目和教材。（说起来应该很容易得到，但历年都有一半人根本不知道
  要考些什么，sigh。）

2.历年试卷。数学和软件yeying扫描了11年的试卷，非常有用！其中数学，操作
  系统，数据结构，其考试题目绝大多数都没有越出前11年的范围，做过一遍试
  卷，及格应该是没问题。
  体系的试卷不卖，Admin 和偶各回忆了一些96,97期末的题目，凑齐了一份考卷，
  事后看来，80% 的题目都在其中。不过奉劝各位的是，体系太难，软工数据库
  虽然是两门，但力气花得少，考分也比体系高得多。

3.历年的瓶颈科目。比如99的软件，00的数学，是录取的瓶颈，一般是一年数学
  一年软件，今年果然又是软件，sigh。

4.软件的考研班。必上。其实我觉得这个重要性应该排第一的，但所有人都去上，
  那不过就是像**一样，构造一个囚徒困境的赚钱陷阱罢了。

5.跟班听课。能增强自信。考试时不会自卑和紧张。因为在那里，你会发现其实
  北大软件也颇有些弱弱的学生。

kuddy

专门谈谈外专业考生如何应对北大计软的考试

    考研不是拼比实力的考试，而是拼比耐心和毅力的。就我个人来说，主要吃
亏在目标定得太晚，理论上来说，如果要考外系的研究生，最好从3 月份开始准
备。我是从8 月份开始的，自己系里的期末考和实验设计和考研时间离得很近，
北大对学生又要求得过于严厉，令我疲于奔命。所以大三的外系考生请务必注意，
一定要在大三下学期，把所有限选和任选学分全部选满。大四上，多和本专业的
老师通气，让他们尽量放你一马，所有本系课程尽量在开学时一个月自学完！

    不要追求高分，因为一个人一学期能够拿到的总分是有限的。请尽量，把自
己专业的期末考分，压在70分以下！放心，没有人会笑话你的。改换专业是一件
非常体现勇气和冒险精神的行为。

    多认识北大计软的学生，如果有可能，找到一个能善始善终的复习伙伴。
外系的学生不能孤军奋战，这样十个会有九个失败的。如果你是外校学生，请
尽可能地一定要来北大听课。千万不要只和自己学校的考生讨论问题，因为你
们很可能会犯同样的错误，因此一定要多交流。

    在最后关头不要松懈。最后一周是最重要的，也许你会在复习自己系里的
期末考试，但千万注意不要放下数学和软件书。期末考一般会在考研前一周结
束，这一周如果做一下历年试卷，对成败有决定性的影响。

    在体力允许的条件下坚持。一般而言，理科考计软，从8 月份复习，每天用
来自习的时间不应少于10个小时，如果是文科考计软，那么请务必3 月份开始复
习，每天不应少于10个小时。在最后一个月，不应少于12个小时。而且要找到
专门自习教室，日光灯照明，不能有电脑。千万不要在床上用昏暗的应急灯，
这样会很疲劳。另外注意夜里一定要加餐。
    会很累，但要相信，当你摇摇欲坠的时候，别人已经倒下了。

    务必要注意数学，离散是北大计软的特色科目。如果不认真复习，那一定
会死得很难看。

kuddy

考研为什么难？就因为时
间脱的比较长，长时间经受精神上的“折磨“，复习各科时间参差不
齐，偏向概念性的一些东西往往容易遗忘，需要经常练习的内容因为
复习循环长轮到他上场的时候往往也忘了大半，几乎类似从头开始.
而令一个重要的原因是还有两座大山：英语和政治的压迫，有时候不
由自主的因为觉得那两门问题大影响复习专业课的心情或是脑子里由
于塞里很多政治概念，英语语法。。而一时间有点排斥别的东西.毕竟
人脑的记忆容量是有限的(短期）这个有科学为证的，特别是在压力比
较大的情况下记忆力更会打折扣，估计没几个考研人的平均复习效率
能比那些在轻松愉快的氛围下学习的人高.再有就是如何把时间合理
安排在如此多的课程上的问题了。最后就是缺乏在规定时间内按考试
标准完成相当内容的练习。所有这一切就导致了大多数考研的同学觉
得很累，很努力。但考试的结果却或多或少有点差强人意。可以理解！
人的智力水平应该是比较平均的，特别突出的只占极少一部分，我一
向对自己的IQ很有信心的。但发挥的不好。我想很多考研人都有如上
的一些感受吧,以此共勉.

kuddy

01.软件工业化生产技术与系统             ────        软件工程
02.软件复用与软件构件技术               ────        软件工程
03.操作系统                             ────        软件工程
04.嵌入式软件                           ────        软件工程
05.面向对象方法与技术                   ────        软件工程
06.软件项目管理                         ————        软件工程
07.计算机语言与编译系统                 ————        软件工程
08.网络与信息安全                       ————        信息安全
09.Web信息共享与集成技术                ————        人工智能
10.并行计算与网格构件技术               ————        人工智能
11.知识工程                             ————        人工智能
12.商务智能                             ————        人工智能
13.面向移动设备的空间信息技术           ————        人工智能
14.Web环境中的信息提取                  ————        人工智能
15.人工智能                             ————        人工智能
16.生物特征识别                         ————        人工智能
17.模式识别                             ————        人工智能
18.图形图像与多媒体                     ————        图形图像
19.人机交互与虚拟现实                   ————        图形图像
20.典型应用领域的数据库与信息系统       ————        数据库
21.Ｗｅｂ环境下的数据库与信息集成       ————        数据库
22.数据库，数据仓库，数据挖掘           ————        数据库
23.自然语言处理                         ————        语言所
24.机器翻译的理论与技术                 ————        语言所
25.信息提取                             ————        语言所
26.算法分析与计算复杂性                 ————        理论
27.并行计算与Petri网                    ————        理论
28.程序的形式语义与正确性验证           ————        理论

kuddy

网络的是如下：

体系中的方向
05.网络信息体系结构
06.网络计算与服务
07.计算机网络与分布式系统
08.分布式海量信息存储
09.计算机网络新技术
在计算机应用方向上所列出来的22个研究方向中，属于计算机科学与技术研究所
的有：01、03、04、05、06、07、08、09、10、11、12，
  注意：其中04是也属于计算中心，他们也用此方向（可能我们所和计算中心都有这
个研究方向吧），填报04时，请注明计算机研究所即可。
  不过为了保险起见，如果你不打算去计算中心，还是不要填04，因为我不知道今
年的报名表在研究方向一栏是否有备注一项可以填，去年就有这个例子，有个mm打
算报我们所，填的04方向，结果档案被送到计算中心去了。
   02是属于电教的。
   13－22我也不太清楚是哪个地方的（难道是信息中心？），若有考生想了解的话
，可以打电话去研究生教务老师那里问一下。

   下面简单就我得了解的计算机科学与技术研究所（简称计算机所）的情况说一说
吧。
   这边研究生大致有4个流向：
   方正电子：实验室在上地信息产业基地，主要作文字与图形信息处理、 数字版
权保护技术，电子出版新技术 ，导师有汤帜，贾文华等。
   方正数码：主要有信息安全工程研究中心，导师是王选（只带博士），邹维（我
们所的副所长）等；图形图像实验室，导师周秉锋（图形图像实验室主要做理论研
究，周老师在学术上造诣很深，喜欢图形图像研究的同学可以来这里）；电子金融
实验室，导师是梁循（梁老师是清华的博士，斯坦福的MBA).
   方正研究院：主要的研究方向是内容管理与知识管理 、彩色图像处理，导师有
陈晓鸥（方正研究院的院长）等。
   方正国际：主要研究文字与图形信息处理，导师是李平立。

   后三者的实验室在北大东门对面的方正大厦里。(我对方正电子，方正研究院，
方正国际的情况了解也不是很多，也是听师兄说的一些).

   我自己现在所在是信息安全工程研究中心，是研究所目前重点开拓的方向，中心
内设置了基础研究部、工程部、成果推广部、技术服务部等部门，研究生一般在基
础研究部了，做基础研究工作；其他部门是做成果转化的。基础研究部现在有（1）
微结构分析与验证（MICRO），研究网络攻击，（2）入侵检测系统（IDS），就是网
络防御了，（3）高性能安全计算平台（SEP），（4）SIP，（5）安全存储系统（S
-FS），（6）组播；

   报07和09方向的估计就是我们信息安全工程研究中心了。

   如果复试的时候大家报的方向比较集中的话，所里的老师会对大家的方向作些调
整（都是在被录取为计算机所的研究生后，所里内部的研究方向调节了）。

  大家想多了解一下计算机所的话，可以访问主页（www.icst.pku.edu.cn);那里有
更详细的信息。

kuddy

专业课千万不要只是看书，更要做题，建议你经常翻看一下数理逻辑的例题，一定要对书上的证明思路和格式非常熟悉，不然的话，就算是很简单的题也可能做不出来。考试时，书上的公理和例题的结论可以直接使用（课后练习题的结论不行），最好把例题的结论背下来（辅导班时老师也这样建议）。
集合论和图论都不难，适当做一些题就行了。代数结构和组合数学挺难的，要多花些功夫。英语最好多花些功夫，最好能形成优势。朱泰奇的书并没有想象的那么好，不要把宝押在他身上，听力可要多练练，记入总分的。
   ds光看没用，要多做题，可以做教材后边的习题和严蔚敏的那本习题集，所用语言并不是很重要。建议也看一下许卓群的那本教材（高教版），那是经典，张铭出题时也会参考的。

kuddy

操作系统考研考试范围和重点
基本要求：
1、考研题目大致分为两种类型，一类是基本概念、技术和方法（即问答题），一类是基本原理的综合应用（即应用题）。P、V操作题肯定考。
2、一般说来，具体操作系统如Windows、Linux/Unix不考，但讲解原理时引用的UNIX实现方法还要考（主要集中在4-6章）。
3、内容：1-9章，重点4-6章。
4、考试的思路两方面兼顾：灵活运用 与 知识点的全面掌握

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

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

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

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

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

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

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

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

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

第9章 操作系统结构
l        操作系统设计目标（正确性，高效性，易维护性，移植性）
l        操作系统结构设计方法
l        操作系统层次结构
上面的提纲是陈老师去年给的，大家可以看看，去年考试的题目97%都在里面了，可惜不能显示颜色，想要看看重点的同学发email给我：katyush@163.com

kuddy

北京大学计算机系

2005级硕士研究生入学考试

数据结构复习提要

（本课程考研总分为80分）


--------------------------------------------------------------------------------

1. 主要参考书：许卓群、杨冬青、唐世渭、张铭，《数据结构与算法》，高等教育出版社， 2004年 7月。ISBN 7-04-014616-9。

教材第1、2、3章由许卓群主笔，第4、5、6章由杨冬青主笔，第8、10章由唐世渭主笔，第7、9、11、12章由张铭主笔。
　

2. 关于算法：

  （1）算法语言无所谓，只要能看懂。考试用C++出题，但答题随意(可以用C/C++、Java、Pascal、自然语言等等，看得懂就可以)。

  （2）如果要求自己独立地写算法（而不是填空），请注意写算法思想，并加上足够的注释

    （3）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写ADT，并说明函数功能、入口参数、出口参数

3. 关于答疑

   张铭不回答关于考研的mail。

　

4.  考试范围和重点

不考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章 二叉树（教材中本章作者为杨冬青）

一. 概念

      1. 二叉树 2.二叉树的前序、中序、后序周游 3. 二叉排序树 4. 穿线树(中序、前序、后序) 5. Huffman树、Huffman编码 6. 堆、堆排序

二. 方法

        1．二叉树的链式存储

         （1）二叉链表

         （2）带父指针的三重链表

        2. 二叉树的顺序存储

           完全二叉树的顺序存储

    ★3. 使用栈(前、中、后序)周游二叉树(注意，不要使用带GOTO语句的机械消除递归的方法)、使用队列层次地周游二叉树，在周游过程中寻找某个结点或进行某种操作 (结合应用，例如穿线树，或把快速排序转换成非递归形式)

        4. 二叉检索树的插入与删除

         5. 构造Huffman树，利用Huffman树进行编码、解码

         6. 堆排序的建堆过程

　

第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章 内排序（教材中本章作者为张铭）

二. 方法

     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. 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四种旋转，不考删除)，严格按照算法来完成

   3. 伸展树（半伸展树）的插入操作