计算机专业课考研大纲-学术学位

计算机考研专业课大纲一一学术学位第一部分概述一、考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念，理论、技能和方法，能够运用所学的知识判断和解决相关的理论问题和实际问题。二、考试形式和试卷结构试卷满分及考试时间本试卷满分为150分，考试时间为180分钟答题方式：闭卷、笔试三、试卷内容结构数据结构45分计算机组成原理35分操作系统35分计算机网络35分四、试卷题型结构第二部分《数据结构》第三部分《计算机组成原理》第四部分《操作系统》第五部分《计算机网络》cache的基本原理cache访问cache缺失处理写操作处理一个cache的例子:内置FastMATH处理器.cache性能的评估和改进通过更天活地放置块来减少cache缺失在cache中查找一个块替换块的选择使用多级cache结构减少缺失代价通过分块进行软件优化可信存储器层次失效的定义虚拟存储器页的存放和查找缺页故障关于写加快地址转换:TLB.集成虚拟存储器、TLB.和cache虚拟存储器中的保护处理TLB缺失和缺页存储器层次结构的一般框架561问题1:一个块可以被放在何处问题2:如何找到一个块问题3:当cache缺失时替换哪一块问题4:写操作如何处理第四部分《操作系统》考查目标.掌握操作系统基本概念，认识操作系统的运行机理；深刻理解进程、线程、作业及其相互关系；理解程序并发与资源共享的控制方法，能灵活运用PV操作、管程等并发控制机制解决互相斥、同步、通信问题；理解并熟练掌握死锁与饥饿的概念及其处理方法；掌握处理机、存储器、文件、设备等各种资源的管理方法与技术。.掌握操作系统的各部分构成及计算机系统中各种硬件、软件资源管理的实现原理和方法，提高解决复杂应用问题的能力。.了解UNIX操作系统的数据结构与核心算法。题型结构：包括简答题与综合应用题具体内容：一操作系统概述操作系统的概念操作系统的特性操作系统的硬件环境操作系统的界面形式操作系统的运行机理研究操作系统的儿种观点二进程、线程与作业多道程序设计进程的引入线程与轻进程作业三中断与处理器调度中断与中断系统处理器调度调度级别与多级调度实时调度四互斥、同步与通信并发进程2进程互斥进程同步进程高级通讯五死锁与饥饿死锁的概念死锁的类型死锁的条件死锁的处理资源分配图死锁的预防死锁的避免死锁的发现死锁的恢复鸵鸟算法饥饿与饿死可复用资源死锁的静态分析同种组合资源死锁的必要条件六存储管理存储管理的功能内存资源管理单一连续区存储管理页式存储管理.段式存储管理段页式存储管理七虚拟存储管理外存储器管理技术虚拟页式存储管理虚拟段式存储管理虚拟段页式存储管理八文件系统文件与文件系统文件的访问方式文件的组织文件目录文件的共享文件的保护和保密文件存储空间的管理内存所需的表目文件系统的界面日志文件系统内存映射文件文件的安全九设备与输入输出管理设备管理的功能与目标设备的分类设备的物理特性数据传输方式I/O软件的层次同步I/O与异步I/O设备分配与去配设备驱动设备调度缓冲与缓存输入输出进程RAID技术虚拟设备十UNIX实例分析进程管理存储管理文件系统设备管理系统调用第五部分《计算机网络》考查目标.理解计算机网络的分层体系结构，特别是TCP/IP网络体系结构。理解数据通信基本原理.，包括信息的编码技术、传输模式、多路复用技术、以及差错检测和控制。.了解物理层接口的机械特性、电气特性、功能特性和规程特性及物理层网络互连。理解数据链路层的线路规程、差错和流量控制、停止等待协议和滑动窗口协议的工作过程，数据链路层通信协议，LLC和MAC、以太网、数据链路层网络互连设备及网桥路由算法。理解网络层功能和提供的服务、路由选择策略和路由算法、网络层网络互连、网络层的流量控制和拥塞控制，理解TCP/IP协议族中的IP协议、ICMP协议、IGMP协议等网络层协议及Internet路由问题及IPv6。理解传输层的功能和服务、传输层地址和传输层复用、传输层流量控制和拥塞控制、掌握TCP/IP协议族中的UDP协议和TCP协议。了解域名服务（DNS）、文件传输（FTP）、Email以及Web服务等具有代表性的Internet服务。3,掌握计算机网络的基本知识，具有协议分析能力。题型结构：简答题或基础知识题，综合分析题参考教材：《计算机网络》（第三版），胡亮、徐高潮、魏晓辉、车喜龙编著，高等教育出版社，2018年9月出版。具体内容一、概论计算机网络的发展计算机网络的功能、组成及拓扑结构计算机网络的功能计算机网络的组成计算机网络的拓扑结构计算机网络体系结构网络协议和分层ISOOSI参考模型层间通信与对等层间通信服务和数据单元面向连接和无连接的服务TCP/IP网络体系结构TCP/IP协议栈TCP/IP的物理层和数据链路层TCP/IP的网络层TCP/IP的传输层TCP/IP的应用层二、数据通信基础数据通信系统数据通信系统的组成数据通信系统应解决的主要问题数据通信的主要技术指标信号和数据编码模拟与数字信号数字—数字编码数字一模拟编码奈奎斯特准则香农定理线路配置和传输方式线路配置传输模式多路复用技术频分多路复用时分多路复用波分多路复用码分多路复用错误检测编码奇偶校验码循环冗余校验（CRC）码检查和三、物理层第二部分《数据结构》考查目标.熟悉数据结构的相关概念及其分类，数据结构与算法的关系。掌握线性表、堆栈和队列，数组和字符串等数据结构的存储、操作和应用，树与二叉树的性质与应用算法，图的存储结构和相关算法，排序与查找的典型算法。.掌握算法时空复杂性分析和正确性验证的基本方法。.能够综合运用数据结构、算法、数学等多种知识，对问题进行分析、建模，选择或构建合适的数据结构，设计较优算法。题型结构：包括问答题与算法设计题具体内容：一、绪论（1）数据、数据元素、数据逻辑结构和存储结构的定义及其关系；（2）数据逻辑结构及其分类；（3）算法的定义和特征；（4）算法的正确性证明方法；（5）算法的时间和空间复杂性分析方法及复杂性函数的渐进表示。二、线性表、堆栈和队列（1）线性结构的概念和特点；（2）顺序存储和链式存储线性表的基本操作；（3）堆栈的定义和两种存储结构下堆栈的基本操作；（4）堆栈在括号匹配和递归中的应用；物理层功能物理接口RJ45接口标准USB接口标准日A-232接口标准传输介质双绞线同轴电缆光缆无线传输介质物理层互连设备四、数据链路层线路规程询问/应答模式轮询/选择模式流量控制与差错控制停止等待协议滑动窗口协议HDLC通信协议HDLC支持的站点类型、链路配置和通信方式HDLC帧格式S-帧的使用方式U-帧的种类HDLC协议通信实例IEEE局域网通信协议IEEE局域网标准IEEE局域网参考模型逻辑链路控制LLC以太网以太网访问模式：CSMA/CD以太网MAC帧格式以太网种类无线局域网无线局域网标准802.11协议族MAC帧格式CSMA/CA协议802.11b标准数据链路层网络互连网桥网桥路由算法二层交换机帧中继五、网络层网络层的功能和服务网络层的功能面向连接的网络服务面向非连接的网络服务网络层互连路由器三层交换机网关路由选择原理距离向量路由算法链路状态路由算法拥塞控制和流量控制拥塞控制流量控制IP协,议IP地址IPv4报文格式子网编址与子网掩码IP路由选择ICMP：Internet控制报文协议ICMP报文格式和类型ICMP地址掩码请求与应答使用ICMP协议的实例IGMP：Internet组管理协议多播的基本概念IGMP报文格式IGMP协议功能Internet路由问题内部网关路由选择协议：OSPF外部网关路由选择协议：BGPv4新型网络协议一IPv6591IPv6基本报头IPv6扩展报头IPv6地址IPv6地址类型六、传输层传输层服务传输层功能与服务概述传输层寻址传输层复用可靠传输传输层流量控制传输连接用户数据报协议UDPUDP报文格式UDP检查和传输控制协议TCPTCP提供的服务TCP的报头格式TCP连接的建立和释放传输层拥塞控制七、应用层客户/服务器模型DNS月艮务DNS的历史DNS的工作原理DNS报文格式DNS与ARP的比较电子邮件服务电子邮件系统的组成简单邮件传送协议SMTP邮件读取协议通用因特网邮件扩充MIMEFTP服务FTP的工作原理FTP的主要命令简单文件传输协议Web服务超文本(Hypertext)超文本传送协议一HTTPWeb浏览器的结构WEB网站的软件构架HTTP报文格式（5）队列的定义和两种存储结构下队列的基本操作；（6）队列的应用。三、数组和字符串（1）二维及多维数组的存储原理及寻址方式；（2）矩阵的存储及基本操作；（3）三元组表和十字链表存储的稀疏矩阵的基本操作;（4）字符串的存储及基本操作；（5）模式匹配算法。四、树与二叉树（1）树的概念、相关术语和表示方法；（2）二叉树的定义和性质；（3）二叉树的顺序存储结构和链接存储结构；（4）二叉树遍历的递归与非递归算法；（5）线索二叉树的定义和操作；（6）树与二叉树的转换；（7）树的链接存储结构，树和森林的遍历算法；（8）树的顺序存储结构；（9）树在并查集实现中的应用。五、图（1）图的基本概念；（2）图的邻接矩阵和邻接表存储结构；（3）图的遍历算法；（4）拓扑排序和关键路径算法；（5）无权最短路径算法、正权最短路径算法、每对顶点之间的最短路径算法，满足约束的最短路径问题；（6）最小支撑树算法；（7）图的可及性及传递闭包算法、连通分量算法。六、排序（1）直接插入排序和Shell排序；（2）冒泡排序和快速排序；（3）直接选择排序;（4）堆的概念与性质，堆排序算法；（5）合并排序算法；（6）分治排序的一般方法，基于关键词比较的排序算法下界分析。七、查找（1）顺序查找算法；（2）对半查找、一致对半查找、斐波那契查找和插值查找算法；（3）对半查找算法的二叉判定树；（4）二叉查找树的概念和性质，二叉查找树的查找、插入和删除算法；（5）高度平衡树的概念和性质，高度平衡树的查找和插入过程；B树及B+树的概念和基本操作；（7）散列的基本概念，散列函数的构造方法；（8）散列函数的冲突调节方法，拉链法和线性探查法。第三部分《计算机组成原理》考查目标.了解计算机硬件的发展史，技术的发展对计算机组成与体系结构变迁的影响。理解计算机系统的基本架构、核心构成部分的功能与相互联系，围绕CPU建立起整机的概念。.理解计算机是软硬件的有机体，掌握指令集体系结构的基本知识和实现方法，掌握计算机系统结构的核心思想、CPU的组成与工作机制，指令的执行过程和存储器体系的层次结构。.能够深入研究各功能部件的相互连接与相互作用，运用计算机组成的基本原理和基本方法，进行一些基本功能部件的逻辑设计，解决所遇到的理论和实际问题。题型结构：包括简答题与综合应用题具体内容：一、计算机概要与技术计算应用的分类及其特性计算机系统结构中的8个伟大思想性能的定义和度量CPU性能及其因素指令的性能经典的CPU性能公式二、指令:计算机的语言计算机硬件的操作计算机硬件的操作数存储器操作数222常数或立即数操作数有符号数和无符号数计机中指令的表示逻辑操作决策指令循环.2case/switch语句计算机硬件对过程的支持使用更多的寄存器嵌套过程在栈中为新数据分配空间在堆中为新数据分配空间人机交互MIPS中32位立即数和寻址32位立即数分支和跳转中的寻址MIPS寻址模式总结机器语言解码并行与指令：同步翻译并执行程序编译器汇编器链接器加载器动态链接库2.13数组与指针用数组实现clear用指针实现dear比较两个版本的clear三、计算机的算术运算加和减法乘法顺序的乘法算法和硬件有符号乘法更快速的乘法.MIPS中的乘法除法除法算法及其硬件结,构有符号除法更快速的除法MIPS中的除法浮点运算浮点表不浮点加法浮点乘法MIPS中的浮点指令算术精确性四、处