832计算机综合考试大纲.docx

《832计算机综合考试大纲.docx》由会员分享，可在线阅读，更多相关《832计算机综合考试大纲.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、832计算机综合考试大纲计算机综合包括数据结构、计算机组成原理两部分内容，每部分 内容各占1/2。I数据结构一、考试基本要求要求考生系统地理解线性结构（线性表、数组和矩阵、栈、队列、 跳表和散歹I表）、树型结构（森林（树）、二叉树、优先队列、搜索树）、 图结构等各种主要数据结构的基本概念，掌握各种数据结构的定义、 实现算法和应用；掌握基本算法设计方法（递归、贪婪算法、分而治 之、动态规划）及应用；掌握程序性能分析方法。要求考生具有抽象 思维能力，逻辑推理能力，和综合运用所学的知识分析问题和解决问 题的能力。二、考试范围（一）预备知识1 . C+基本语法结构和应用2 .递归思想和方法（二）程序性

2、能分析1 .复杂性（时间复杂性和空间复杂性）的表示和计算方法2 .插入排序、选择排序、冒泡排序、按名次排序方法3 .顺序搜索、折半搜索方法（三）线性表2. I/O接口(I/O控制器)(1) I/O接口的功能和基本结构(2) I/O端口及其编址2.1 /0方式(1)程序查询方式(2)程序中断方式中断的基本概念；中断响应过程；中断处理过程；多重中断 和中断屏蔽的概念；中断处理顺序。(3) DMA方式DMA控制器的组成；DMA传送过程。(4)通道方式四、参考书目(一)唐朔飞，计算机组成原理(第3版)，高等教育出版社，2020.10,十二五”普通高等教育本科国家级规划教材。(二)白中英 戴志涛，计算机

3、组成原理(第6版)，科学出版社，2019.8,十二五”普通高等教育本科国家级规划教材。1 .线性表的数组描述、链表描述等存储方法2 .线性表的插入、删除、合并等基本操作实现方法3 .遍历器的作用、实现方法和应用4 .线性表结构应用：箱子排序、基数排序、并查集（在线等价 类）等（四）数组和矩阵1 . 一般矩阵存储方法和基本运算实现2 .特殊矩阵的特征、存储方法和基本运算实现3 .稀疏矩阵的存储方法和基本运算实现（五）栈1 .栈的基本概念、基本操作和实现方法2 .栈结构应用：括号匹配、列车车厢I重排、迷宫老鼠、离线等 价类等（六）队列1 .队列的基本概念、基本操作和实现方法2 .队列结构应用：列车

4、车厢重排、电路布线、图元识别等（七）跳表和散列1 .字典结构基本概念和表示结构2 .跳表的基本概念、基本操作和实现方法3 .散列表的基本概念、基本操作和实现方法4 . LZW压缩思想（八）二叉树和其他树1 .树（以及森林）和二叉树的基本概念、存储方法、常用操作 和特性2 .二叉树的前序、中序、后序、层次遍历方法及应用3 .树（以及森林）的存储方法4 .树和二叉树结构的应用：基于树存储的并查集（在线等价类） 等（九）优先队列1 .优先队列基本概念和表示结构2 .堆结构基本概念，堆的插入、删除和初始化等操作实现方法3 .堆结构应用：堆排序、霍夫曼树、霍夫曼编码4 .左高树基本概念和插入、删除、合并

5、、初始化等操作的实现 思想（十）搜索树1 .二叉搜索树（排序树）基本概念和插入、删除、搜索等操作的实 现方法2 .二叉平衡树（AVL树）基本概念和插入、删除、搜索等操作 的实现方法3 . m叉搜索树和B-树基本概念以及插入、删除、搜索等操作的 实现方法（十一）图1 .图基本概念和特性2 .图的邻接矩阵和邻接链表存储方法及各种基本操作和实现方法3 .图的深度优先搜索（DFS）和广度优先搜索（BFS）算法4 . DFS/BFS应用：寻找路径、连通图及连通构件、生成树等（十二）贪婪算法1 .贪婪算法基本思想2 . AOV网的拓扑排序算法3 .单源最短路径Dijkstra算法4 .最小成本生成树的概念

6、、Prim算法和Kruskal算法5 . AOE网的关键路径算法（十三）分而治之1 .分而治之思想2 .归并排序、快速排序方法3 .选择问题实现方法（十四）动态规划1 .动态规划思想2 .所有顶点对之间的最短路径算法三、参考文献（一）数据结构，算法与应用-C+语言描述（原书第2版），SartajSahni著 王立柱，刘志红译，机械工业出版社2015年出版（二）数据结构（用面向对象方法与C+语言描述 第二版）殷 人昆著清华大学出版社II计算机组成原理一、课程基本要求(一)理解单处理器计算机系统中各部件的内部工作原理、组成结构 以及相互连接方式，具有完整的计算机系统的整机概,念；(二)理解计算机系

7、统层次化结构概念，熟悉硬件与软件之间的界 面，掌握指令集体系结构的基本知识和基本实现方法；(三)能够综合运用计算机组成的基本原理和基本方法，对有关计算 机硬件系统中的理论和实际问题进行计算、分析，对一些基本部件进 行简单设计，并能对高级程序设计语言(如C语言)中的相关问题进行 分析。二、考试范围(一)计算机系统概述1 .计算机发展历程2 .计算机系统层次结构(1)计算机系统的基本组成(2)计算机硬件的基本组成(3)计算机软件的分类(4)计算机的工作过程3 .计算机性能指标CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS (2)字长 (3)容量(4)总线宽度(二)数据的表示和

8、运算1 .数制与编码(1)进位计数制及其相互转换(2)真值和机器数(3) BCD 码(4)字符与字符串(5)校验码2 .定点数的表示和运算(1)定点数的表示无符号数的表示及范围；有符号数的表示及其相互转换。(2)定点数的运算定点数的移位运算；补码定点数的加/减运算；定点数的乘/除运算；溢出概念和判别方法。3 .浮点数的表示和运算(1)浮点数的表示浮点数的表示范围；浮点机器数与真值间的相互转换。(2)浮点数的加/减运算4 .算术逻辑单元ALU(1)并行加法器(2)算术逻辑单元ALU的功能和结构(3)快速进位链设计原理(三)存储器层次机构1 .存储器的分类2 .存储器的层次化结构3 .半导体随机存

9、取存储器(1) SRAM存储器的工作原理(2) DRAM存储器的工作原理；刷新方式。(3)只读存储器、Flash存储器(4)主存储器的基本组成、存储单元的属性、数据的存放模式(5)存储器的技术指标4 .存储器的扩展方式及存储器与CPU的连接5 .多体并行存储器系统6 .高速缓冲存储器(Cache)(1) Cache的基本工作原理(2) Cache和主存之间的映射方式及其地址转换(3) Cache中主存块的替换算法(4) Cache读、写策略(四)指令系统1 .指令格式(1)指令的基本格式(2)定长操作码指令格式(3)扩展操作码指令格式2 .指令的寻址方式(1)有效地址的概念(2)数据寻址和指令

10、寻址(3)常见寻址方式3 . CISC和RISC的基本概念(五)中央处理器(CPU)1 .CPU的功能和基本结构2 .指令执行过程3 .数据通路的功能和基本结构基于数据通路，指令周期流程及取指、间址、执行和中断周期 的数据流。4 .控制器的功能和工作原理(1)微操作命令的分析取指周期、间址周期、执行周期和中断周期的微操作命令及 其节拍安排。(2)组合逻辑(硬布线)控制器组合逻辑控制器的组成结构、设计步骤。(3)微程序控制器微程序、微指令、微命令、微操作、控制存储器的基本概念;微程序控制器的设计思想、组成结构、工作原理；微指令的编码方式；微地址的形式方式。5 .指令流水线(1)指令流水线的基本概念(2)指令流水线的基本实现影响指令流水线性能的因素：结构相关、数据相关、控制相关；流水线的主要性能：吞吐率、加速比、效率。(3)流水线的多发技术超标量处理机、超流水线处理机、超长指令字处理机的基本 概念。(六)总线1 .总线概述(1)总线的基本概念(2)总线的分类(3)总线的组成及性能指标2 .总线仲裁(1)集中仲裁方式(2)分布仲裁方式3 .总线操作和定时(1)同步定时方式(2)异步定时方式4 .总线标准(七)输入输出(I/O)系统1.1/0系统基本概念