71计算机集成一考试大纲一、考试性质和范围本次考试是计算机科学与技术专业研究生的专业基础课考试。旨在考察考生对计算机组成与数据结构基本原理和方法的掌握程度，以及运用基本原理和方法分析和解决问题的能力。考试范围包括计算机组成原理和数据结构。二、考试的基本要求计算机组成原理要求考生掌握:1。掌握计算机硬件系统的基本组成和工作机理，包括运算器的组成和工作原理；控制器的设计与实现方法，以及内存分级存储系统的概念和工作原理；I/O系统和工作模式。并建立整机概念，如何协调基本部件完成分配的任务；2.了解计算机系统层次结构的概念，熟悉硬件和软件的接口，掌握指令集体系结构的基础知识和实现方法；3.能够运用计算机组成的基本原理和方法，计算和分析与计算机硬件系统有关的理论和实际问题，并能简单设计一些基本部件。数据结构要求考生掌握:1。数据结构的基本概念、基本原理和基本方法；2.数据的逻辑结构和存储结构以及基本运算的实现，可以分析算法的基本时间复杂度和空之间的复杂度；能运用数据结构的基本原理和方法分析和解决问题，具备用C或C++语言设计和实现算法的能力。三、考试形式及评分答题方式闭卷、笔试。考试时间180分钟，试卷满分150分，其中:计算机组成原理75分数据结构75分4、考试内容一计算机组成原理1。计算机系统概述1)电子计算机和存储程序控制。了解计算机发展史，掌握数字化的概念，存储程序的工作模式和冯诺依曼系统。2)计算机系统的层次结构:计算机硬件的基本组成，计算机软件的分类，计算机的工作过程(1)计算机系统。熟悉计算机硬件系统的组织，硬件和软件的关系，计算机系统硬件和软件的逻辑等价。(2)掌握计算机系统的层次结构概念，了解串行计算机与软件的兼容性。3)计算机性能指标的吞吐量和响应时间；时钟周期、主频、CPI、CPU执行时间；MIPS，MFLOPS .2.数据的机器级表示1)数字数据的表示。熟悉进位计数制的基本概念，掌握原码和补码的表示及其相互转换。2)机器号的定点表示和浮点表示。掌握定点整数和定点小数表示。掌握浮点数的表示方法和范围，归一化和隐藏位等技术，序列码的码移位表示和IEEE754标准。了解定点和浮点记数法，定点和浮点计算机的区别。3)非数值数据的表示。了解字符和字符串的表示，汉字和Unicode的编码。4)十进制数和数字串的表示。掌握十进制数的常用编码方法和十进制数串的存储方法。了解现代微机系统中各种数据的表示方法。5)数据校验码。掌握数据校验码的概念和实现原理，了解奇偶校验、汉明校验的验证原理和实现方法。3.指令系统1)指令格式:掌握设计扩展操作码指令集的基本方法。基本指令格式、固定长度操作码指令格式和扩展操作码指令格式。2)指令的寻址方法:有效地址的概念、数据寻址和指令寻址、常用寻址方法、堆栈结构和堆栈操作3)CISC和RISC的基本概念4 .数值的机器运算1)定点运算1。定点的移位运算和舍入运算。2.定点的加减运算；溢出的概念和判别方法。3.定点的乘法/除运算；掌握一位乘法及其实现逻辑。2)规格化浮点运算1。浮点运算方法和流程2。浮点运算单元的组成与实现3)算术逻辑单元ALU1。串行加法器、并行加法器和快速进位链2。算术逻辑单元ALU 5的基本组成和实现。存储器系统和结构1)存储器的分类2)存储器的层次结构3)半导体随机存取存储器1。1的工作原理。SRAM 2。2的工作原理。DRAM 3。只读存储器4。闪存4)主存储器和CPU之间的连接5)双端口RAM和多模块存储器6)高速缓冲存储器(Cache)1。本地程序访问2。cache 3的基本工作原理。高速缓存和主存储器之间的映射方法。cache 5中主存块的替换算法。缓存写入策略6。中央处理器(CPU)1)CPU的功能和基本结构2)数据通道的功能和基本结构3)时序系统和控制方法4)指令执行过程5)控制器1的功能和工作原理。组合逻辑控制器2。微指令的微控制器编码方式；微地址的形式。6)控制单元的设计。掌握设计样机的过程，组合逻辑控制器的组成原理和设计方法；掌握微程序控制器的设计方法和步骤。7.输入/输出(I/O)系统1)I/O系统的基本概念2)I/O接口(I/O控制器)1。I/O接口的功能和基本结构2。I/O端口及其寻址3)I/O模式1。程序查询模式2。程序中断模式的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念。3.DMA模式下DMA控制器的组成；DMA传输过程。4.通道模式4)总线技术1。总线2的基本概念、分类和性能指标。同步时序模式，异步模式II数据结构1。数据结构介绍1)数据结构的基本概念，数据的逻辑结构和物理结构2)算法和算法分析2。线性表1)线性表的定义和基本操作2)线性表的顺序存储结构3)线性表的链式存储结构4)线性表的应用3。堆栈和队列1)堆栈和队列的定义和操作2)堆栈和队列的顺序存储结构3)堆栈和队列
1)数组的定义和操作2)数组的存储结构3)矩阵的压缩存储。
5.树
1)树的基本概念2)二叉树的定义及其基本运算，二叉树的性质和存储结构3)二叉树的遍历4)线索二叉树5)树和森林6)哈夫曼树和哈夫曼编码7)二叉树的应用5。图1)图的定义和操作2)图的存储结构3)图的遍历4)最小生成树5)最短路径问题6)拓扑排序和关键路径7)图的应用6。搜索1)搜索的基本概念2)序列表的搜索。树)和平衡二叉排序树4)哈希表及其搜索5)搜索算法的应用7。排序1)排序的基本概念2)插入排序:直接插入排序、半插入排序、链表插入排序、外壳排序3)交换排序:冒泡排序、快速排序4)选择排序:直接选择排序、堆排序5)双向归并排序6)基数排序7)各种内部排序方法的比较8)内部排序算法参考书目[1]蒋本山。计算机组成原理(第3版)。清华大学出版社，2013[2]唐硕飞。计算机组成原理(第二版)。[3]齐岳，夏克俭，高等教育出版社，2008
