考研散列通(北航计算机类研究生专业考试科目)

你需要到人家的网站看招生简章、招生专业目录、参考书目录三个文件，都在招生信息里，或者在招生就业里！网站在百度输入学校名就有了. 或者直接某大学2008研究生招生专业目录，参考08年的，09年的每年7月后出！对应相应编号找 ，总之你只要会电脑，就在他的网站找到招生专业目录及参考书！一定要去他的网站

http://yzb.buaa.edu.cn/

院系名称:计算机学院

专业名称:计算机科学与技术

专业拟招收人数：220人

研究方向名称:计算机系统结构 计算机应用技术 计算机软件与理论

专业备注:基本学习年限为2.5年

考试科目单元 考试科目代码 考试科目名称

第一门考试科目 101 政治

第二门考试科目 201 英语

第三门考试科目 301 数学一

第四门考试科目 961 计算机专业综合

其中数学英语政治全国都一样，是统考！到考研书店问问就知道了！

专业课参考书：961 计算机专业综合

《数据结构教程》（第二版，第三次印刷〕

北航出版社

唐发根著

《计算机组成原理》

高等教育出版社

唐朔飞编著

《操作系统实用教程》

清华大学出版社

任爱华主编

《离散数学》（数理逻辑部分〕

高等教育出版社

尹宝林等编

大纲：961计算机专业综合考试大纲（2008版）

一、考试组成

961计算机专业综合共包括四门课程的内容：计算机组成原理、数据结构、操作系统、数理逻辑，分别占40分、40分、40分、30分。

二、计算机组成原理部分的考试大纲

(一) 参考书

《计算机组成原理》，高等教育出版社，唐朔飞编著

(二) 复习内容

1．存储系统

（1）主存储器：存储单元电路及其工作原理、存储芯片结构及其工作原理、DRAM的刷新原理和刷新方式、存储器的扩展方法。

（2）高速缓冲存储器：Cache的基本结构和工作原理、Cache的地址映射方式、Cache的替换策略。

（3）辅助存储器：磁盘存储器的结构、访问特征和性能参数计算。

2．指令系统

（1）指令格式：机器指令的一般格式以及指令字中各字段的作用和特点。

（2）寻址方式：常见寻址方式的有效地址计算方法、寻址范围、作用和特点。

（3）指令系统的设计：指令格式设计的相关因素及基本方法、扩展操作码技术。

3．CPU

（1）CPU的功能和结构: CPU的基本功能、内部结构、数据通路、控制信号。

（2）控制单元的功能：指令周期、多级时序系统、控制方式、指令执行过程的微操作流程分析。

（3）控制单元的设计：微程序控制器的结构和工作原理、微指令的格式和编码方式、微程序设计。

4．输入输出技术

（1）总线：总线的分类、总线的判优（仲裁）控制方式、总线的通信控制方式。

（2）I/O控制方式：中断响应与中断处理、DMA方式的工作原理。

三、操作系统部分的考试大纲

（一）指定参考书

《操作系统实用教程（第二版）》，任爱华，清华大学出版社。

（二）复习内容

1．进程

进程、进程同步和通信、进程调度和死锁等基本概念和相关算法。要求清楚理解进程，线程等基本概念，熟练掌握各种基本算法。

2．存储管理

存储器管理，包括重定位和虚拟存储器等基本概念，分区、分页、分段以及段页式存 储管理。要求清楚理解基本概念，熟练掌握各种分配算法。

3．设备管理

I/O设备管理、调度、分配机制, RAID 等。要求掌握I/O管理的基本概念。

4．文件系统

文件系统，包括文件的组织方式、目录结构、存取控制等。要求清楚理解文件系统的基本概念。

四、数据结构部分的考试大纲

（一）、指定参考书

《数据结构教程（第二版）》 唐发根编著 北京航空航天大学出版社，（建议选用第3次印刷的书）

（二）、复习内容

1．线性表

（1）线性关系，线性表的定义，线性表的基本操作；

（2）线性表的顺序存储结构与链式存储结构(单链表、循环链表和双向链表)的构造原理；

（3）在以上两种存储结构的基础上对线性表实施的基本操作对应的算法设计。

2．堆栈与队列

（1）堆栈与队列的基本概念，基本操作；

（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理；

（3）在以上两种储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计。

3．二叉树

（1）二叉树的基本概念与基本名词术语；

（2）完全二叉树与满二叉树，二叉树的基本性质；

（3）二叉树的顺序存储结构与二叉链表存储结构的基本构造原理，二叉树的前序遍历、中序遍历、后序遍历以及对应算法的设计(非递归算法)；

（4）二叉排序树的基本概念，二叉排序树的建立(插入)和查找。

4．图

（1）图的定义，基本名词术语；

（2）图的邻接矩阵存储方法、邻接表存储方法的基本构造原理；

（3）图的深度优先遍历与广度优先遍历；

（4）最小生成树与最短路径的基本概念和构造过程。

5．文件及查找

（1）顺序查找法与折半查找法，折半查找法对应的“判定树”的构造；

（2）B-树的基本概念，B-树的插入与查找；

（3）散列(Hash)表的构造、散列函数、散列冲突以及处理散列冲突的方法。

6．内排序

（1）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、(大顶)堆积排序法；

（2）各种内排序方法排序的基本原理和特点。

五、数理逻辑部分的考试大纲

（一）参考书

《离散数学》（第一篇 数理逻辑），高等教育出版社，尹宝林等编著

（二）复习内容

1. 命题逻辑

命题逻辑的基本概念及方法：联结词、赋值、等值演算、对偶定理、联结词的完全集、范式、逻辑推论。

2. 谓词逻辑

谓词逻辑的基本概念及方法：谓词和量词、项和公式、解释和赋值、永真式、等值演算、逻辑推论。

3. 公理系统

公理系统：命题逻辑及谓词逻辑的公理系统、可靠性和完全性。

4. 归结法原理

归结法原理：前束范式、斯科伦范式、命题逻辑及谓词逻辑的归结法。

还一个：

院系名称:软件学院

专业名称:软件工程

专业拟招收人数：80人

研究方向名称:集成电路设计 日文应用软件开发 嵌入式软件

专业备注:基本学习年限2.5年,培养费共4万元人民币,本专业只招收"自筹经费"和"委托培养"两种类别

第一门考试科目 101 政治

第二门考试科目 201 英语

或 203 日语

第三门考试科目 301 数学一

第四门考试科目 991 数据结构与C语言程序设计

专业课参考书：991 数据结构与C语言程序设计

《数据结构教程第二版》

北京航空航天大学出版社

唐发根著

《C程序设计》

清华大学出版社

谭浩强著

大纲：991数据结构与C语言程序设计考试大纲(2008版)

一、考试组成

数据结构与C语言程序设计包括“数据结构”与“C语言程序设计”两门课程的内容，各占75分，总分150分。

二、数据结构部分的考试大纲

（一）指定参考书

《数据结构教程（第二版）》 唐发根编著， 北京航空航天大学出版社

（建议选择2006年6月第3次印刷的书）

（二）复习内容及基本要求

1、概述

（1）数据的逻辑结构与存储结构的基本概念；

（2）算法的定义、基本性质以及算法分析的基本概念，包括采用大?形式表示时间或空间复杂度。

2、线性表

（1）线性关系、线性表的定义，线性表的基本操作；

（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理；

(3)在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的算法设计(含递归算法的设计)。

3、堆栈与队列

(1)堆栈与队列(含循环队列)的基本概念、基本操作；

(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理；

(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。

4、树与二叉树

(1)树与二叉树的基本概念，基本特征、名词术语；

(2)完全二叉树、满二叉树的概念、二叉树的基本性质；

(3)二叉树的顺序存储结构与二叉链表存储结构的构造原理、二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(重点为非递归算法)以及利用遍历解决有关二叉树的其它操作；

(4)线索二叉树的基本概念以及构造原理；

(5)二叉排序树的基本概念、建立(插入)和查找，在二叉排序树中查找结点的平均查找长度ASL。

5、图

(1)图的基本概念、名词术语；

(2)邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点；

(3)图的深度优先搜索和广度优先搜索的过程，图的遍历的基本作用；

(4)最小生成树及最短路径的特点、求解过程，拓扑排序及其目的。

6、文件及查找

(1)顺序查找法、折半查找法以及查找过程对应的“判定树”的构造；

(2)索引文件的基本概念；

(3)B-树与B+树的构造以及构造上异同，B-树的插入和查找；

(4)散列文件的特点，散列函数和散列冲突的概念，处理散列冲突的方法以及散列文件的查找。

7、内排序

插入排序、选择排序、泡排序、快速排序、堆积排序(大顶堆积)和二路归并排序法等排序方法的排序原理、规律和特点。

三、C语言程序设计部分的考试大纲

（一）指定参考书

《C程序设计》 谭浩强编著，清华大学出版社

（二）复习内容及基本要求

1、C语言基本知识

（1）C语言的特点以及C语言程序的组成；

（2）数据类型，包括整型、实型、字符型等常量与变量和变量的赋值；用typedef定义类型；

（3）各种类型数据之间的混合运算；

（4）各类运算符的运算规则和优先级；条件运算符；

（5）算术表达式、关系表达式和逻辑表达式，逗号运算符和逗号表达式，表达式sizeof的含义。

2、语句

（1）赋值语句(含条件赋值语句)、条件语句(含if、if-else、switch)、循环语句(含while、do-while、for语句，包括循环嵌套和break语句)；

（2）输入/输出语句，包括整型、实型、字符型(含字符串)等类型数据的格式输入函数scanf和格式输出函数printf。

3、数组

（1）一维数组与二维数组的定义，数组元素的引用，数组的初始化；

（2）字符数组的定义，字符数组的初始化，字符数组的引用，字符数组的输入与输出，字符串和字符串处理函数。

4、函数

（1）函数的定义，函数参数(形参和实参)与函数的返回值；

（2）函数的调用，包括函数的嵌套调用和递归函数的递归调用；

（3）命令行参数的概念（带参数的主函数）。

5、宏定义

（1）带参数的宏定义；

（2）包含文件的处理。

6、指针

（1）指针的概念，变量的指针与指向变量的指针变量，包括定义、引用以及指针变量作为函数参数；

（2）数组的指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数；

（3）字符串的指针与指向字符串的指针变量。

7、结构体

（1）结构体的基本概念和特点，结构体的初始化与引用；

（2）结构体数组。

8、文件

（1）文本文件的基本概念，文本文件的类型指针FILE以及文本文件的使用方式；

（2）文本文件的打开(fopen函数)、文本文件的关闭(fclose函数)；

（3）文本文件的状态，包括feof函数和ferror函数；

（4）文本文件的读写，包括fputc函数和fgetc函数、fgets函数和fputs函数等；

（5）文本文件的输入函数fscanf和输出函数fprintf。

复式：北京航空航天大学计算机学院

2008年硕士研究生复试规定与安排

北航计算机学院硕士研究生招生复试工作基本安排如下：

一、 统考生源复试安排（仅适合统考生源）

1. 复试分数线：计算机科学与技术（081200）和地图制图学与地理信息工程（081603）两个专业的复试分数线均为：总分350分，政治和外语单科50分，数学和专业单科80分。另外，计算机学院2008年继续在统考生源中招收部分软件工程硕士（双证），有关软件工程硕士的分数线和复试办法参见《北京航空航天大学计算机学院2008年软件工程硕士复试规定与安排》。

2. 复试办法：复试采取差额复试的办法，复试分为C语言上机考试和综合面试两部分，每部分各150分，复试总成绩300分，没有笔试。每部分成绩及格（90分以上（含）），方具有录取资格。

C语言上机考试只测试考生的C语言编程能力，直接在计算机上进行，系统环境为Microsoft Visual Studio 6.0，建议使用标准C编程。

综合面试内容包括英语口语、听力、数理基础和专业综合素质等方面的内容。专业综合素质方面将涉及计算机基础与专业知识，考生在相关领域内曾经进行的开发、研究工作，考生本科的专业背景、曾获得的各种荣誉，参加的各种科技、社会活动等。复试注重实际能力和可培养潜力。

3. 资格审查：所有参加复试的考生须按本规定附件1的要求准备好复试资格审查材料，复试报到时提交以便学院进行资格审查。

4. 复试报到：3月23日上午8:30，参加复试的考生到新主楼G849报到，递交复试资格审查材料，进行考生复试资格审核（复试资格审核办法见附件1），同时领取导师情况简介和导师志愿表。

5. C上机考试：3月23日下午2:00，参加复试的考生到计算机学院教学实验中心参加C语言上机测试，测试时间2小时。

6. 地图制图学与地理信息工程专业综合面试：3月24日上午8:30报考地图制图学与地理信息工程专业的学生统一参加导师组面试。面试结束后公布复试结果。

7. 计算机科学与技术专业综合面试流程

参加计算机科学与技术专业复试的考生根据导师介绍、导师招生人数等情况填报两个导师志愿，3月24日中午12:00前将志愿表返回G849（过时无故不交，视为自动放弃复试）。3月24日下午6:00公布第一批面试分组名单。

第一批面试（3月25日上午8:30）的考生是第一志愿填报教授导师的考生，第一志愿填报副教授导师的考生不参加第一批面试。每个导师的面试人数一般不超过招生人数的150％，排名在150％以后的考生，如第一志愿服从调剂，学院将根据具体情况将考生调剂到报名人数不足150％的教授所在的面试小组参加面试。3月25日下午5:30左右公布第一批拟录取名单和3月26日上午（第二批）面试分组名单。

第二批面试3月26日上午8:30进行，第一志愿填报副教授的考生按其第一志愿和第一志愿填报教授导师但没被录取的考生的第二志愿一起排队参加面试。每个导师的面试人数一般不超过招生人数的150％。排名在150％以后的考生，学院将根据具体情况进行调剂，以确保每人至少有一次面试机会。

两轮面试仍然没有录取满的导师，学院将从剩余考生中根据考生统考成绩和考生是否服从分配等因素调剂录取。

3月26日下午5:30左右公布全部拟录取名单。最终录取与否，以收到研究生院发出的正式录取通知书为准。

3月26日下午5:30左右，所有被拟录取的考生到学院办公室领取政审表，录取类别为自筹的考生领取并签署自筹协议，录取类别为委托培养的考生领取定向委托培养协议。

8. 同等学历加试：按同等学力身份参加复试的考生（国家承认学历的成人应届本科毕业生或获得国家承认的大专毕业证书后连续工作两年或两年以上的）需要单独加试《C语言程序设计》和《编译原理》课程（《C语言程序设计》用上机考试成绩代替），《编译原理》成绩不低于60分，方有资格录取。

二、 推免、单考和强军计划类别生源复试安排

推免生不再进行复试。

单考和强军计划考生的复试采取等额复试的办法，且不参加C语言上机考试。

3月23日下午2:30，单考和强军计划类别参加复试的考生到院会议室（如心楼407）报到，同时领取综合面试记录表、政审表。

3月24日单考和强军计划类别考生与志愿导师联系，取得导师认可后，参加导师所在组的综合面试。

北京航空航天大学计算机学院

2008年3月18日

计算机学院硕士研究生招生咨询电话：

010－82317630

附件1：

北京航空航天大学计算机学院

2008硕士研究生招生复试资格审核及材料提交办法

参加复试的考生在报到时应提交如下材料以进行资格审核后，方可参加复试：

1. 考生参加研究生入学考试的准考证原件和一份复印件；

2. 本人有效身份证件（身份证、现役军官证、文职干部证）原件和一份复印件，应届本科毕业生还需同时提交本人学生证原件和一份复印件，原件审核后当场退回考生；

3. 非应届本科毕业生需提交：（1）学历证书原件和一份复印件；（2）由档案所在单位人事部门提供的在校历年学习成绩表复印件一份（原件上应有毕业学校公章），并由档案所在单位人事部门加盖公章。

4. 应届本科毕业生需提交所在学校教务部门提供的加盖公章的在校历年学习成绩表一份。

5. 英语六级或四级证书复印件。

国家承认学历的成人应届本科生可按同等学力资格参与复试，但必须同时符合如下条件方有资格录取：

加试专业成绩合格（加试科目：《C语言程序设计》和《编译原理》）；

2008年8月底以前获得本科毕业证书；

在计算机相关领域核心期刊以第一作者发表一篇以上（含）论文；

2008年8月底以前通过国家英语四级。

获得国家承认的大专毕业证书后到2008年9月1日连续工作两年以上（含）可按同等学力参加复试，但必须同时符合如下条件方有资格录取：

加试专业成绩合格（加试科目：《C语言程序设计》和《编译原理》）；

在全日制普通高校辅修完所报专业本科的全部主干课程且成绩合格（提交加盖学校教务处公章的成绩表）；

在计算机相关领域核心期刊以第一作者发表一篇以上（含）论文；

2008年8月底以前通过国家英语四级。

以下材料不属于复试资格审核必须的，但希望考生提供：

考生自述；

考生获得的校级以上的奖励证书复印件（如果有）

凡提交信息与本人实际情况不符，一经发现，立即取消复试或拟录取资格。无论录取与否，考生复试报到时所提交资料恕不退回。

所有提交的材料均以A4纸大小按如下顺序统一左侧装订（成绩单超过A4的，装订后折叠成A4大小）：

1） 封面（见附件2）

2） 准考证复印件；

3） 有效身份证复印件，应届毕业生将身份证与学生证复印在同一A4纸上；

4） 考生自述；

5） 往届生的学历证复印件和成绩证明，应届生成绩证明；

6） 英语六级或四级证书复印件（有六级证书的不要再提供四级证书）

7） 同等学力考生应提交的其他证明材料；

8） 各类校级以上获奖证书复印件。

北京航空航天大学计算机学院

2008年3月18日

附件2：

北京航空航天大学计算机学院

2008硕士研究生招生复试审核材料

准考证号：

考生姓名：

毕业学校：

所学专业：

初试成绩（总分）：

本人郑重声明：

在此提交的所有材料均与实际情况一致，如有不实之处，本人愿承担由此引起的相关责任。

签名：

时间： 年 月 日

设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树

你可以照大纲看看阿。算法那时必须会的，不要存在侥幸心理，算法是数据结构课的灵魂，09年没有考并不意味着以后也不考。并且09年还是有算法题的。应用题第二题要写算法的。

另附09大纲：

Ⅰ考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络

等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，

能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟

二、答题方式

答题方式为闭卷、笔试

三、试卷内容结构

数据结构45分

计算机组成原理45分

操作系统35分

计算机网络25分

四、试卷题型结构

单项选择题80分（40小题，每小题2分）

综合应用题70分

Ⅲ考查范围

数据结构

考查目标

1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作

的实现。

2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

3.能够选择合适的数据结构和方法进行问题求解。

一、线性表

（一）线性表的定义和基本操作

（二）线性表的实现

1.顺序存储结构

2.链式存储结构

3.线性表的应用

二、栈、队列和数组

（一）栈和队列的基本概念

（二）栈和队列的顺序存储结构

（三）栈和队列的链式存储结构

（四）栈和队列的应用

（五）特殊矩阵的压缩存储

三、树与二叉树

（一）树的概念

（二）二叉树

1.二叉树的定义及其主要特征

2.二叉树的顺序存储结构和链式存储结构

3.二叉树的遍历

4.线索二叉树的基本概念和构造

5.二叉排序树

6.平衡二叉树

（三）树、森林

1.书的存储结构

2.森林与二叉树的转换

3.树和森林的遍历

（四）树的应用

1.等价类问题

2.哈夫曼（Huffman）树和哈夫曼编码

四、图

（一）图的概念

（二）图的存储及基本操作

1.邻接矩阵法

2.邻接表法

（三）图的遍历

1.深度优先搜索

2.广度优先搜索

（四）图的基本应用及其复杂度分析

1.最小（代价）生成树

2.最短路径

3.拓扑排序

4.关键路径

五、查找

（一）查找的基本概念

（二）顺序查找法

（三）折半查找法

（四）B-树

（五）散列（Hash）表及其查找

（六）查找算法的分析及应用

第2页共？页六、内部排序

（一）排序的基本概念

（二）插入排序

1.直接插入排序

2.折半插入排序

（三）气泡排序（bubble sort）

（四）简单选择排序

（五）希尔排序（shell sort）

（六）快速排序

（七）堆排序

（八）二路归并排序（merge sort）

（九）基数排序

（十）各种内部排序算法的比较

（十一）内部排序算法的应用计算机组成原理

考查目标

1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有

完整的计算机系统的整机概念。

2.理解计算机系统层次化结构概念，熟悉硬件与软件之间的界面，掌握指令集体系结构的

基本知识和基本实现方法。

3.能够运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问

题进行计算、分析，并能对一些基本部件进行简单设计。

一、计算机系统概述

（一）计算机发展历程

（二）计算机系统层次结构

1.计算机硬件的基本组成

2.计算机软件的分类

3.计算机的工作过程

（三）计算机性能指标

吞吐量、响应时间；CPU时钟周期、主频、CPI、CPU执行时间；MIPS、MFLOPS。

二、数据的表示和运算

（一）数制与编码

1.进位计数制及其相互转换

2.真值和机器数

3.BCD码

4.字符与字符串

5.校验码

第3页共？页（二）定点数的表示和运算

1.定点数的表示

无符号数的表示；有符号数的表示。

2.定点数的运算

定点数的位移运算；原码定点数的加/减运算；补码定点数的加/减运算；定点数

的乘/除运算；溢出概念和判别方法。

（三）浮点数的表示和运算

1.浮点数的表示

浮点数的表示范围；IEEE754标准

2.浮点数的加/减运算

（四）算术逻辑单元ALU

1.串行加法器和并行加法器

2.算术逻辑单元ALU的功能和机构

三、存储器层次机构

（一）存储器的分类

（二）存储器的层次化结构

（三）半导体随机存取存储器

1.SRAM存储器的工作原理

2.DRAM存储器的工作原理

（四）只读存储器

（五）主存储器与CPU的连接

（六）双口RAM和多模块存储器

（七）高速缓冲存储器（Cache）

1.程序访问的局部

2.Cache的基本工作原理

3.Cache和主存之间的映射方式

4.Cache中主存块的替换算法

5.Cache写策略

（八）虚拟存储器

1.虚拟存储器的基本概念

2.页式虚拟存储器

3.段式虚拟存储器

4.段页式虚拟存储器

5.TLB（快表）

四、指令系统

（一）指令格式

1.指令的基本格式

2.定长操作码指令格式

3.扩展操作码指令格式

（二）指令的寻址方式

1.有效地址的概念

2.数据寻址和指令寻址

第4页共？页3.常见寻址方式

（三）CISC和RISC的基本概念

五、中央处理器（CPU）

（一）CPU的功能和基本结构

（二）指令执行过程

（三）数据通路的功能和基本结构

（四）控制器的功能和工作原理

1.硬布线控制器

2.微程序控制器

微程序、微指令和微命令；微指令的编码方式；微地址的形式方式。

（五）指令流水线

1.指令流水线的基本概念

2.超标量和动态流水线的基本概念

六、总线

（一）总线概述

1.总线的基本概念

2.总线的分类

3.总线的组成及性能指标（二）总线仲裁

1.集中仲裁方式

2.分布仲裁方式

（三）总线操作和定时

1.同步定时方式

2.异步定时方式

（四）总线标准

七、输入输出（I/O）系统

（一）I/O系统基本概念

（二）外部设备

1.输入设备：键盘、鼠标

2.输出设备：显示器、打印机

3.外存储器：硬盘存储器、磁盘阵列、光盘存储器

（三）I/O接口（I/O控制器）

1.I/O接口的功能和基本结构

2.I/O端口及其编址

（四）I/O方式

1.程序查询方式

2.程序中断方式

中断的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的

概念。

3.DMA方式

DMA控制器的组成；DMA传送过程。

4.通道方式

第5页共？页操作系统

考查目标

1.了解操作系统在计算机系统中的作用、地位、发展和特点。

2.理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术。

3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题。

一、操作系统概述

（一）操作系统的概念、特征、功能和提供的服务

（二）操作系统的发展与分类

（三）操作系统的运行环境

二、进程管理

（一）进程与线程

1.进程概念

2.进程的状态与转换

3.进程控制

4.进程组织

5.进程通信

共享存储系统；消息传递系统；管道通信。

6.线程概念与多线程模型

（二）处理机调度

1.调度的基本概念

2.调度时机、切换与过程

3.调度的基本准则

4.调度方式

5.典型调度算法

先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度

算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。

（三）进程同步

1.进程同步的基本概念

2.实现临界区互斥的基本方法

软件实现方法；硬件实现方法。

3.信号量

4.管程

5.经典同步问题

生产者-消费者问题；读者-写者问题；哲学家进餐问题。（四）死锁

1.死锁的概念

2.死锁处理策略

3.死锁预防

4.死锁避免

第6页共？页系统安全状态：银行家算法。

5.死锁检测和解除

三、内存管理

（一）内存管理基础

1.内存管理概念

程序装入与链接；逻辑地址与物理地址空间；内存保护。

2.交换与覆盖

3.连续分配管理方式

单一连续分配；分区分配。

4.非连续分配管理方式

分页管理方式；分段管理方式；段页式管理方式。

（二）虚拟内存管理

1.虚拟内存基本概念

2.请求分页管理方式

3.页面置换算法

最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近

法（LRU）；时钟置换算法（CLOCK）。

4.页面分配策略

5.抖动

抖动现象；工作集。

6.请求分段管理方式

7.请求段页式管理方式

四、文件管理

（一）文件系统基础

1.文件概念

2.文件结构

顺序文件；索引文件；索引顺序文件。

3.目录结构

文件控制块和索引节点；单级目录结构和两级目录结构；树形

目录结构。

4.文件共享

共享动机；共享方式；共享语义。

5.文件保护

访问类型；访问控制。

（二）文件系统实现

1.文件系统层次结构

2.目录实现

3.文件实现

（三）磁盘组织与管理

1.磁盘的结构

2.磁盘调度算法

3.磁盘的管理

五、输入输出（I/O）管理

第7页共？页（一）I/O管理概述

1.I/O设备

2.I/O管理目标

3.I/O管理功能

4.I/O应用接口

5.I/O控制方式

（二）I/O核心子系统

1.I/O调度概念

2.高速缓存与缓冲区

3.设备分配与回收

4.假脱机技术（SPOOLing）

5.出错处理计算机网络

考查目标

1.掌握计算机网络的基本概念、基本原理和基本方法。

2.掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组

型网络设备的工作原理

3.能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统

用

一、计算机网络体系结构

（一）计算机网络概述

1.计算机网络的概念、组成与功能

2.计算机网络的分类

3.计算机网络与互联网的发展历史

4.计算机网络的标准化工作及相关组织

（二）计算机网络体系结构与参考模型

1.计算机网络分层结构

2.计算机网络协议、接口、服务等概念

3.ISO/OSI参考模型和TCP/IP模型

二、物理层

（一）通信基础

1.信道、信号、宽带、码元、波特、速率等基本概念

2.奈奎斯特定理与香农定理

3.信源与信宿

4.编码与调制

5.电路交换、报文交换与分组交换

6.数据报与虚电路

（二）传输介质

1.双绞线、同轴电缆、光纤与无线传输介质

第8页共？页2.物理层接口的特性

（三）物理层设备

1.中继器

2.集线器

三、数据链路层

（一）数据链路层的功能

（二）组帧

（三）差错控制

1.检错编码

2.纠错编码

（四）流量控制与可靠传输机制

1.流量控制、可靠传输与滑轮窗口机制

2.单帧滑动窗口与停止-等待协议

3.多帧滑动窗口与后退N帧协议（GBN）

4.多帧滑动窗口与选择重传协议（SR）

（五）介质访问控制

1.信道划分介质访问控制

频分多路复用、时分多路复用、波分多路复用、码分多

本原理。

2.随即访问介质访问控制

ALOHA协议；CSMA协议；CSMA/CD协议；CSMA

3.轮询访问介质访问控制：令牌传递协议

（六）局域网

1.局域网的基本概念与体系结构

2.以太网与IEEE 802.3

3.IEEE 802.11

4.令牌环网的基本原理

（七）广域网

1.广域网的基本概念

2.PPP协议

3.HDLC协议

4.ATM网络基本原理

（八）数据链路层设备

1.网桥

网桥的概念；透明网桥与生成树算饭；源选径网桥与源选

2.局域网交换机及其工作原理。

四、网络层

（一）网络层的功能

1.异构网络互联

2.路由与转发

3.拥塞控制

（二）路由算法1.静态路由与动态路由

2.距离-向量路由算法

3.链路状态路由算法

4.层次路由

三）IPv4

1.IPv4分组

2.IPv4地址与NAT

3.子网划分与子网掩码、CIDR

4.ARP协议、DHCP协议与ICMP协议

四）IPv6

1.IPv6的主要特点

2.IPv6地址

五）路由协议

1.自治系统

2.域内路由与域间路由

3.RIP路由协议

4.OSPF路由协议

5.BGP路由协议

六）IP组播

1.组播的概念

2.IP组播地址

3.组播路由算法

七）移动IP

1.移动IP的概念

2.移动IP的通信过程

八）网络层设备

1.路由器的组成和功能

2.路由表与路由转发

传输层

传输层提供的服务

1.传输层的功能

2.传输层寻址与端口

3.无连接服务与面向连接服务

UDP协议

1.UDP数据报

2.UDP校验

TCP协议

1.TCP段

2.TCP连接管理

3.TCP可靠传输

4.TCP流量控制与拥塞控制

应用层

第10页共？页网络应用模型

1.客户/服务器模型

2.P2P模型

DNS系统

1.层次域名空间

2.域名服务器

3.域名解析过程

FTP

1.FTP协议的工作原理

2.控制连接与数据连接

电子邮件

1.电子邮件系统的组成结构

2.电子邮件格式与MIME

3.SMTP协议与POP3协议

WWW

1.WWW的概念与组成结构

2.HTTP协议Ⅳ．

试题示例

一、单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项中，

请选出一项最符合题目要求的。

试题示例：

1、下列排序算法中，时间复杂度为O（nlog2n）且占用额外空间最少的是

A．堆排序

B．起泡排序

C．快速排序

D．希尔排序

2、下列序列中，满足堆定义的是

A．（100，86，48，73，35，39，42，57，66，21）

B．（12，70，33，65，24，56，48，92，86，33）

C．（103，97，56，38，66，23，42，12，30，52，6，26）

D．（5，56，20，23，40，38，29，61，35，76，28，100）

3、程序计数器PC用来存放指令地址，其位数和下列哪个寄存器相同？

A．指令寄存器IR

B．主存数据寄存器MDR

C．程序状态字寄存器PSWR

D．主存地址寄存器MAR

4、假定一个十进制数为-66，按补码形式存放在一个8位寄存器中，该寄存器的内容用十六

进制表示为

A．C2H

B．BEH

C．BDH

D．42H

5、下列进程状态转换中，不可能发生的转换是

A．运行→就绪

B．运行→等待

C．等待→运行

D．等待→就绪

6、高某系统中有3个并发过程都需要4个同类资源，该系统不会发生死锁的最少资源是

A．9

B．10

C．11

D．12

7、根据CSMA/CD协议的工作原理，下列情形中需要提高最短帧长度的是

A．网络传输速率不变，冲突域的最大距离变短

第12页共？页B．冲突域的最大距离不变，网络传输速率提高

C．上层协议使用TCP的概率增加

D．在冲突域不变的情况下减少线路中的中继器数量

8、在选择重传协议（SR）中，当帧的序号字段为3比特，且接收窗口与发送窗口尺寸相同

时，发送窗口的最大尺寸为

A．2

B．4

C．6

D．8

二、综合应用题：41~47小题，共70分。

试题示例：

41．（10分）设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），

（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表

示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从

顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度.

42.(15分)已知一棵二叉树采用二叉链表存储,结点构造为:

LeftChild Data RightChild,root指向根结点。现定义二叉树中结点X0的根

路径为从根结点到X0结点的一条路径，请编写算法输出该二叉树中最长的根路径（多条

最长根路径中只输出一条即可。算法可使用C或C++或JAVA语言实现）。

43．（11分）某计算机的主存地址位数为32位，按字节编址。假定数据Cache中最多存放

128个主存块，采用4路组相联方式，块大小为64Byte,每块设置了1位有效位“脏（Dirty）”

位。

要求：

（1）分别支出主存地址中标记（Tag）、组号（Index）和块内地址（Offset）三部分的

位置和位数

（2）计算该数据Cache的总位数（请给出详细计算过程）

44（.10分）下图是一个简化的CPU与主存连接结构示意图（图中省略了所有多路选择器）。

其中有一个累加寄存器AC、一个状态数据寄存器和其他四个寄存器：主存地址寄存器

MAR、主存数据寄存器MDR、程序计数器PC和指令寄存器IR，各部件及其之间的连线表

示数据通路，箭头表示信息传递方向。

计算机考研常见问题解答

地址：http://www.jsj8.com/post/49.html

2010年计算机考研大纲

地址：http://www.jsj8.com/post/70.html

2009年计算机专业统考试题及解析

地址：http://www.jsj8.com/post/70.html

计算机专业考研视频汇总

地址：http://www.jsj8.com/post/19.html

计算机考研全国统考复习指导及备战建议

地址：http://www.jsj8.com/post/390.html

09年全国计算机专业排名公布

地址：http://www.jsj8.com/post/70.html

计算机考研统考行之有效的备考方案

地址：http://www.jsj8.com/post/335.html

计算机考研最好考的10所学校

地址：http://www.jsj8.com/post/70.html

设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树

夫曼树的构造：

（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；

（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。

（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；

（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。

哈夫曼.bmp (134.99 KB)

2008-8-5 17:55

以上是过程

最后的树是这样：

35

20 15

9 11 7 8

3 5

wpl=3*3 5*3 7*2 9*2 11*2=78

本文来自: 冠威计算机网(