2011年中科院上海微研所硕士研究生入学考试《计算机原理》考试大纲

　　二、考试要求
　　数据结构
　　1、掌握有关数据结构的基本概念，包括数据的逻辑结构、存储结构。
　　2、掌握算法的基本概念以及算法分析的基本方法。
　　3、掌握线性表的基本概念，在两种存储结构下的构造原理及相应的操作；
　　4、掌握堆栈和队列的基本概念与特征以及在两种存储结构下如何对堆栈和队列进行插入和删除等操作，具备使用堆栈与队列解决实际问题的能力。
　　5、掌握串的基本概念以及串的存储结构和相关的算法。
　　6、掌握数组、广义表和稀疏矩阵的基本概念以及基本操作。
　　7、掌握树型结构的逻辑特征以及各种存储结构的构造原理，能够熟练使用基于树的三种遍历方法。
　　8、掌握二叉排序树的逻辑特征、建立过程，具备使用其解决实际问题的能力。
　　9、了解图的逻辑结构的特点以及常用的两种存储方法，了解最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的具体求解过程。
　　10、掌握各种顺序文件的结构与相应的查找方法以及各种查找算法之间时空效率的差异；了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及基于散列的查找。
　　11、掌握各种排序方法的排序特点和排序过程，能够对每一种排序方法在时间、空间、排序的稳定性等方面进行简单分析。
　　计算机组成原理
　　1、掌握计算机的层次结构及软硬件组成等概念。
　　2、掌握计算机中数据的格式、机器数的表示方法和特点，掌握定点加减的运算方法和特点，掌握浮点运算方法和特点。
　　3、掌握存储系统的分类、分级结构与主存储器的技术指标；了解SRAM、DRAM、EPROM、闪速存储器、相联存储器的工作原理；掌握Cache存储器、虚拟存储器的功能和基本工作原理。
　　4、掌握指令格式、指令和数据的寻址方式，了解RISC和CISC的特点。
　　5、掌握CPU的功能、基本组成和各个部分的工作流程；了解微程序控制器的基本工作原理，了解微程序控制技术和硬布线控制技术；了解流水CPU的工作原理及特点。
　　6、掌握总线系统的基本概念和基本技术以及总线仲裁方式的基本工作原来和特点，了解PCI总线的特点。
　　7、掌握显示设备、打印设备、硬盘的工作原理和特点，能够计算一些常用的技术指标。
　　8、掌握外围设备的定时方式、信息交换方式的工作原理和特点，了解程序查询方式、中断方式和DMA方式原理，了解通道方式。