北京邮电大学2014年硕士研究生入学考试自命题科目考试大纲（一）(14)

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

北京邮电大学 /2013-11-01

算法的定义，算法的基本特征及算法分析的基本概念。

（二）线性表

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

线性表的顺序存储结构的构造原理；

对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。

（三）链表

单链表、双向链表和循环链表三种链表形式的存储结构和特点以及基本操作；

稀疏矩阵的存储结构和特点以及基本操作。

（四）栈和队列

栈的定义、结构特点及其存储方式(顺序存储与链接存储)和基本操作的实现算法；

队列的结构、特点及其存储方式(顺序存储与链接存储)和基本操作的实现算法。

（五）数组和串

串的基本概念、串的存储结构和相关的操作算法；

数组的存储结构，在顺序存储的情况下，数组元素与存储单元的对应关系；

字符串比较的基本算法(包括KMP算法)。

（六）递归

递归的基本概念和实现原理以及用递归的思想描述问题和书写算法的方法；

用栈实现递归问题的非递归解法。

（七）树和森林

树的结构和主要概念，各种二叉树的结构及其特点；

二叉树的三种遍历方法的实现原理和性质，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数、二叉树计数等问题，遍历的非递归实现方法；

线索化二叉树的结构和基本操作；

堆的原理和基本操作的实现方法；

森林的定义和存储结构，森林的遍历等方法的实现；

基于霍夫曼树生成霍夫曼编码的方法；

AVL树的定义和特点以及AVL树调整操作的实现原理；

最优二叉树的构造原理和相关算法。

（八）图

图的各种基本概念和各种存储方式；

图的两种搜索方法和连通分量的生成方法；

两种最小生成树的生成方法；

各种求最短路径的方法；

用顶点表示活动和用边表示活动的两种网络结构特点和相关操作的实现算法。

（九）排序

插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序等排序方法排序的原理、规律和特点；

各种排序算法的时空复杂度简单分析。

（十）索引结构与散列

线性索引结构、倒排表、静态搜索树的结构和特点；

B树的结构和各种操作的实现算法；

散列的实现原理和各种操作的实现算法。

三、试卷结构：

考试题型：填空题、选择题、简答题、编程题

第二部分操作系统（50/150）

一、考试要求

要求考生比较系统地理解和掌握操作系统的基本概念、主要功能、主要组成部分、各个主要组成部分的不同实现方法；从资源管理和应用程序与硬件系统接口的观点掌握操作系统设计的基本思想，掌握现代计算机系统对其各种软硬资源的管理技术。要求考生具备综合运用所学知识分析问题和解决问题的能力。

二、考试内容

（一）基本概念

计算机基本构成、处理器的内部结构、高速缓冲存储器CACHE；

操作系统的概念、演变历程、特性、分类、运行环境、功能；

存储器的层次结构。

（二）进程

进程的概念和特点；

进程状态转换。

（三）线程、对称多处理SMP和微内核

线程的概念，定义线程的必要性和可能性；

线程的功能特性与实现方式；

对称多处理SMP体系结构；

操作系统的体系结构（微内核与单内核）及其性能分析。

（四）并发

并发性问题及相关概念，如临界区、互斥、信号量和管程等；

进程互斥、同步和通信的各种算法；

死锁的概念、死锁的原因和条件；

死锁的预防、避免和检测算法。

（五）存储器管理

分区存储管理、覆盖与交换；

页式管理及段式管理；

段、页式存储管理方法及实现技术；

虚存的原理及相关的各种算法和数据结构。

（六）单处理器调度

处理器的三种调度类型；

14/16 首页上一页 12 13 14 下一页尾页

北京邮电大学2014年硕士研究生入学考试自命题科目考试大纲（一）(14)

北京邮电大学 /2013-11-01

相关话题/大纲

领限时大额优惠券,享本站正版考研考试资料!

北京邮电大学2014年硕士研究生入学考试自命题科目考试大纲（二）

2011年警务硕士专业学位专业基础课考试大纲

2011年警务硕士专业学位专业综合课考试大纲

北京理工大学2014年单独考试思想政治理论大纲

北京理工大学2014年单独考试数学大纲

北京理工大学2014年单独考试英语大纲

2014年经济类专业学位联考综合能力测试考试大纲