1计算机专业技术基础考研复习大纲.doc

461计算机专业技术基础考研复习大纲计算机专业技术基础共包括三门课程的内容：计算机组成原理、数据结构、操作系统、数理逻辑和计算机网络技术，分别占40分，30分、30分、25分和25分，总分150分。计算机组成原理部分参考书：计算机组长原理，高等教育出版社，唐朔飞编著一、存储系统1. 主存储器组成与工作原理，包括：存储单元电路及其工作原理、存储芯片结构及其工作原理、存储器的扩展方式、动态存储器的刷新。2. 高速缓冲存储器的组成、结构和工作原理，包括：高速缓冲存储器的功能和工作原理、高速缓冲存储器的结构、地址映射方式。3. 磁盘存储器的结构、访问特征和性能参数计算。二、指令系统1. 指令格式与寻址方式；2. 指令系统的设计；三、CPU1. CPU的功能与结构；2. 控制方式、指令周期；3. 指令执行过程、指令执行微操作流程分析；4. 微程序原理、微指令格式、微程序控制器设计；四、输入输出技术1. 总线分类、总线的控制方式；2. 中断响应与中断处理；3. DMA输入输出方式的工作原理。数据结构部分参考书：数据结构（第二版），科学出版社，唐发根编著一、绪论1. 数据结构的基本概念，数据的逻辑结构、存储结构。2. 算法的定义、算法的基本特性以及算法分析的基本概念。要求：通过本章的学习，能够建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的的基本概念与基本方法。二、线性表1. 线性关系、线性表的定义，线性表的基本操作。2. 线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。3. 在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。要求：学生通过本章的学习，能够掌握线性表的基本概念以及两种存储结构的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。三、堆栈与队列1. 堆栈与队列的基本概念、基本操作。2. 堆栈与队列的顺序存储结构与链式存储结构的构造原理。3. 在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。要求：学生通过本章的学习，掌握堆栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。四、树与二叉树1. 树与二叉树的基本概念，包括基本特征、基本操作。2. 二叉树的基本性质、二叉树的二叉链表存储结构的构造原理、二叉树的三种基本遍历方法(前序、中序和后序)；由二叉树的遍历序列恢复二叉树。3. 二叉排序树的基本概念、建立和查找(含算法)。要求：学生通过本章的学习，充分了解树型结构的逻辑特征，掌握各种存储结构的构造原理，能够熟练地利用常用的三种遍历方法，掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉排序树的建立以及在二叉排序树中查找一个结点存在与否的过程。五、图1. 图的定义，基本概念，图的分类，常用名词术语。2. 图的邻接矩阵存储方法、邻接表存储方法的构造原理。3. 图的遍历操作。4. 最小生成树，最短路径，AOV网与拓扑排序。要求：学生通过本章的学习，充分了解图的逻辑结构的特点，掌握常用的两种存储方法，掌握最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的具体求解过程。六、文件及查找1. 数据文件的基本概念和基本术语，数据文件的基本操作。2. 顺序文件、索引文件、散列(Hash)文件。3. 顺序文件的顺序查找方法、排序连续顺序文件的折半查找方法以及其他文件的基本查找方法。要求：学生通过本章的学习，充分了解各种顺序文件的结构与相应的查找方法；了解各种查找算法之间时空效率的差异；从结构与操作上了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。七、内排序1. 排序的基本概念，排序方法的分类。2. 插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法。3. 各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。要求：学生通过本章的学习，充分了解各种排序方法的排序特点和排序过程，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。操作系统部分参考书：操作系统实用教程（第二版），任爱华，清华大学出版社。第三章 进程讲述了进程、进程同步和通信、进程调度和死锁等基本概念和相关算法。这是操作系统的核心，要求清楚理解进程等基本概念，熟练掌握各种算法，不包括与Linux相关的部分。第四章 存储管理介绍存储器管理，包括重定位和虚拟存储器等基本概念，分区、分页、分段以及段页式存储管理。这是操作系统的重点，要求清楚理解基本概念，熟练掌握各种分配算法，不包括与Linux相关的部分。第五章 设备管理介绍I/O设备管理、调度、分配机制等。要求掌握I/O管理的基本概念，不包括与Linux相关的部分。第六章 文件系统讲述了文件系统，包括文件的组织方式、目录结构、存取控制等。要求清楚理解文件系统的基本概念，不包括与Linux相关的部分。数理逻辑部分参考书：离散数学（第一篇 数理逻辑），高等教育出版社，尹宝林等编著第一章 命题逻辑命题逻辑的基本概念及方法：联结词、赋值、等值演算、对偶定理、联结词的完全集、范式、逻辑推论。第二章 谓词逻辑谓词逻辑的基本概念及方法：谓词和量词、项和公式、解释和赋值、永真式、等值演算、逻辑推论。第三章 公理系统公理系统：命题逻辑及谓词逻辑的公理系统、可靠性和完全性。第四章 归结法原理归结法原理：前束范式、斯科论范式、命题逻辑及谓词逻辑的归结法。计算机网络部分参考书：计算机网络教程，人民邮电出版社，谢希仁编著第一部分：计算机网络的理论基础一、计算机网络的体系结构1. 计算机网络基本常识2. 计算机网络的层次结构、虚实通信要求：掌握以上各种概念和相关知识。二、数据通信的基础知识1. 数据通信系统模型，点-点，端-端。2. 信号的富氏分析，带宽，信道的最大数据传输率3. 模拟传输，数字传输，基带，宽带4. 传输与交换5. 传输媒介要求：了解以上概念和相关知识，掌握信道数据传输率和最大数据传输率的计算方法。三、物理层1. 物理层协议包含的内容：机械、电气、功能、过程等特性的定义2. 物理层接口实例：EIA/TIA 568A/B要求：理解物理层协议所包括的范围，掌握实例。四、数据链路层1. 停等协议，滑动窗口协议2. 链路协议的效率计算3. 实例分析：HDLC，PPP要求：了解数据链路层的功能，熟悉基本链路层协议中的停等协议、滑动窗口协议和协议实例的工作原理，掌握链路协议效率的计算方法。五、网络层1. 虚电路与数据报2. 路由选择算法和路由表3. 拥塞控制算法要求：掌握虚电路和数据报子网工作原理，了解几种常见的路径选择算法，如最短路径优先、向量距离算法等，熟悉拥塞控制算法中的分组丢弃法和源抑制算法。六、传送层1. 连接建立、数据发送、连接释放2. 流量控制，可靠传输控制要求：了解传送层的地址模式，建立连接的三次握手方式，数据发送的禁区，释放连接的算法。第二部分：局域网实例（IEEE 802系列）1. 广播网络的介质访问算法2. 局域网互连技术和设备要求：理解广播网络、冲突域、广播域的概念和介质访问算法中的CSMA/CD、Token Ring，掌握IEEE 803