中国科学院研究生入学考试
本《计算机原理》考试大纲适用于中国科学院非计算机科学与技术一级学科下各专业研究生入学考试。计算机原理是计算机科学与技术及相关学科的重要基础，包括数据结构、计算机组成原理和计算机网络。要求考生对计算机科学与技术及相关学科的基本概念有深入系统的了解，掌握各种数据结构的定义和实现算法，掌握计算机组成原理涉及的关键内容，掌握计算机网络的基本原理和技术，具备综合运用所学知识分析和解决问题的能力。
一、检查表格
闭卷，笔试，考试时间180分钟，总分150分。
二、试卷结构
常见的数据结构、计算机组成原理和计算机网络题，如：概念题(填空、选择、简单回答)、应用题(计算、绘图、分析)等。
三、考试内容
(一)数据结构(50分)
:31020简介
(1)数据结构的基本概念，数据的逻辑结构和存储结构。
(2)算法分析的定义、基本特征和基本概念。
2、线性表格
(1)线性关系，线性表的定义，线性表的基本操作。
(2)线性表的顺序存储结构和链式存储结构(包括单链表、循环链表和双向链表)的构造原理。以上两种存储结构上最重要操作(包括三个链表的建立、插入、删除和检索)的算法设计。
3、堆栈和队列
(1)堆栈和队列的基本概念和操作。
(2)堆栈和队列的顺序存储结构和链式存储结构的构造原理。
(3)在不同存储结构的基础上，实现了插入、删除栈和队列等基本操作对应的算法设计。
4、字符串
(1)字符串的基本概念，字符串的基本操作和存储结构。
(2)字符串模式匹配算法和改进的KMP算法。
5、数组和通用表
(1)数组的概念和多维数组的实现。
(2)对称矩阵和稀疏矩阵的压缩存储。
(3)广义表的基本概念。
6、树和二叉树
(1)树木的定义和性质。
(2)二叉树的概念、性质和实现。
(3)遍历二叉树和线索二叉树。
(4)树木和森林。
(5)赫夫曼树及其应用。
(6)数树。
:图7、
(1)图的定义、基本概念、分类和常用术语。
(2)图的邻接矩阵存储法和邻接表存储法的构造原理。
(3)图的遍历操作。
(4)最小生成树、最短路径、AOV网和拓扑排序。
8、文件和搜索
(1)数据文件的基本概念和术语以及数据文件的基本操作。
(2)顺序文件、索引文件和散列文件。
(3)顺序文件的顺序查找法、排序顺序文件的半查找法和其他文件的基本查找法。
:在9、范围内排序
(1)排序的基本概念和排序方法的分类。
(2)插入排序法(包括半插入排序法)、选择排序法、冒泡排序法、快速排序法、堆排序法、归并排序法和基数排序法。各种排序方法的原理、规律和特点，以及各种排序算法的时空复杂度的简单分析。
(二)计算机组成原理(50分)
1、计算机系统介绍
(1)计算机的分类。
(2)计算机硬件。
(3)计算机软件。
(4)计算机系统的层次结构。
2、操作方法和操作员
(1)数据和文字的表示方法。
(2)定点加减运算。
(3)定点乘法。
(4)定点除法。
(5)定点运算单元的组成。
(6)浮点运算方法和浮点运算符。
3、存储系统
(1)记忆概述。
(2)随机读写存储器。
(3)只读存储器和闪存。
(4)高sp
5、 CPU
(1)1)CPU的功能和组成。
(2)指令周期。
(3)时序发生器和控制方式。
(4)微程序控制器。
(5)微程序设计技术。
(6)硬连线控制器。
(7)流水线CPU。
(8)RISC中央处理器.
6、总线系统
(1)总线的概念和结构。
(2)总线接口。
(3)总线的仲裁时序和数据传输方式。
(4)主机总线和PCI总线。
(5)InfiniBand标准。
7、外围设备
(1)外围设备概述。
(2)磁盘存储设备及其技术发展。
(3)磁带存储设备。
(四)光盘和磁光盘存储设备。
(5)显示设备。
(6)输入设备和打印设备。
8、输入和输出系统
(1)外围设备的速度分类和信息交换方式。
(2)程序查询模式。
(3)程序中断方式。
(4)DMA模式。
(5)渠道模式。
(三)计算机网络(50分)
:31020简介
(1)计算机网络的概念、分类、标准、组成和功能。
(2)计算机网络的层次结构，协议、接口和服务等概念，ISO/OSI模型和TCP/IP模型。
2、物理层
(1)通信信道、信号、宽带、符号、波特、速率、源和目的地、奈奎斯特定理和香农理论、编码和调制、电路交换、报文交换和分组交换、数据报和虚电路等基本概念。
(2)双绞线、同轴电缆、光纤和无线传输介质，物理层接口、中继器和集线器的特性。
:数据链路层
(1)数据链路层的功能、成帧和差错控制(检错和纠错编码)。
(2)流量控制、可靠传输和滑轮窗口机制、停止等待协议、退避N帧协议(GBN)和选择性重传协议(SR)。
(3)频分复用、时分复用、波分复用、码分复用的概念和基本原理：ALOHA协议、CSMA协议、CSMA/CD协议、CSMA/CA协议、令牌传递协议。
(4)局域网的概念和体系结构，以太网和IEEE 802.3标准协议，IEEE802.11标准协议，令牌环网。
(5)广域网、PPP协议和HDLC协议的概念。
(6)电桥的概念和原理，开关及其工作原理。
4、网络层
(1)网络层、异构网络互连、路由和转发以及拥塞控制的功能。
(2)路由算法，静态路由和动态路由，距离矢量路由算法，链路状态路由算法，分层路由。
(3)IPv4分组、IPv4地址和NAT、子网划分和子网掩码、CIDR、ARP协议、DHCP协议和ICMP协议。
(4)IPv6的主要特点，IPv6地址。
(5)路由协议，自治系统，域内路由和域间路由，RIP路由协议，OSPF路由协议和BGP路由协议。
(6)组播的概念，IP组播地址。
(7)移动IP的概念和移动IP的通信过程。
(8)路由器、路由表和路由转发的组成和功能。
5、传输层
(1)传输层的功能，传输层寻址和端口，无连接服务和面向连接的服务。
(2)UDP协议、UDP数据报和UDP校验。
(3)TCP协议、TCP段、TCP连接管理、TCP可靠传输、TCP流量控制和拥塞控制。
6、应用层
(1)客户机/服务器模式，P2P模式。
(2)DNS概念，分级域名空间，域名服务器，域名解析流程。
(3)3)FTP协议的工作原理，控制连接和数据连接。
(4)电子邮件系统的结构，电子邮件格式和MIME，SMTP协议和POP3协议。
(WWW、HTTP协议的概念和结构。
四、检查要求
数据结构
1、掌握关于数据结构的基本概念，包括数据的逻辑结构和存储结构。
2、掌握算法的基本概念和算法分析的基本方法。
3、熟悉线性表的基本概念，两种存储结构下的构造原理和相应操作。
4、熟悉堆栈和队列的基本概念和特征，以及如何在两种存储结构下插入和删除堆栈和队列，具备运用堆栈和队列解决实际问题的能力。
5、掌握字符串的基本概念，字符串的存储结构和相关算法。
6、掌握数组、广义表、稀疏矩阵的基本概念和运算。
7、掌握树结构的逻辑特征和各种存储结构的构造原理，能够灵活运用基于树的三种遍历方法。
8、掌握二叉排序树的逻辑特征和建立过程，具有灵活运用二叉树解决实际问题的能力。
9、了解图的逻辑结构的特点和两种常用的存储方式，了解最小生成树(Prim算法和Kruskal算法)、最短路径和拓扑排序的具体求解过程。
10、掌握各种顺序文件的结构、对应的搜索方法以及各种搜索算法在时间和空间效率上的差异。介绍了溶解列文件的建立、哈希函数的选择(构造)原则、哈希冲突的处理方法和基于哈希的搜索。
11、精通各种排序方法的排序特点和排序流程，能够从时间、空间、排序稳定性等方面对每种排序方法进行简单分析。
(二)计算机组成原理
1、掌握计算机层次结构和软硬件组成的概念。
2、掌握计算机中机器数的数据格式、表示方法和特点，掌握定点加减法的运算方法和特点，掌握浮点运算方法和特点。
3、掌握存储系统主存的分类、层次结构和技术指标，了解SRAM、DRAM、EPROM、flash存储器和联想存储器的工作原理，掌握缓存和虚拟存储器的功能和基本工作原理。
4、精通指令格式、指令和数据寻址，了解RISC和CISC的特点。
5、掌握CPU各部分的功能、基本组成和工作流程，了解微程序控制器的基本工作原理，了解微程序控制技术和硬接线控制技术，了解流水线CPU的工作原理和特点。
6、掌握总线系统的基本概念和技术，总线仲裁方式的基本工作原理和特点，了解PCI总线的特点。
7、了解显示设备、打印设备、硬盘的工作原理和特点，能够计算一些常用的技术指标。
8、了解外围设备的定时模式和信息交换模式的工作原理和特点，了解程序查询模式、中断模式和DMA模式的原理，了解通道模式。
(3)计算机网络
1、掌握计算机网络的基本概念、原理和方法。
2、掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，了解典型网络设备的工作原理。
3、能运用计算机网络的基本概念、原理和方法分析、设计和应用网络系统。
主要参考书目
1、数据结构(C语言版)，严为民，吴伟民主编，清华大学出版社，2007。
2、计算机组成原理(第4版)，白中英主编，科学出版社，2007年。
3、《计算机网络》(第5版)，特南鲍姆、韦瑟罗尔著，魏延、潘爱民译，清华大学出版社，2012年。
