《计算机学科专业基础综合》考试大纲与参照书目.docx

计算机学科专业根基综合考试大纲及参考书目2014年版重庆大学考试科目代码：91745分45分35分25分80分40小题，每题2分70分试卷内容构造数据构造计算机组成原理操作系统计算机网络四、试卷题型构造单项选择题综合应用题 参考书目数据构造C语言版本.严蔚敏 吴伟民.清华大学出版社.1997.4第一版2004. 11第28 次印刷.计算机组成和设计：硬件/软件接口. David A. Patterson. John L. Hennessy.机械工业 出版社.2012年1月1日.操作系统：精华与设计原理原书第6版.斯托林斯(Wi I I iamStal I ings)著，陈向群, 陈渝 译.机械工业出版社,2010-09-01.计算机网络第五版，简体中文.Andrew S. Tanenbaum. David J. Wethera I I.清华大学 出版社.2012年3月.数据构造【考察目标】掌握数据构造的基本概念、基本原理和基本方法。掌握数据的逻辑构造、存储构造及 基本操作的实现，能够对算法进展 基本的时间复 杂度与空间复杂度的分析。能够运用数据构造的 基本原理和方法进展问题的分析与求解，具备采用C或C+语言 设计与实现算法的能力。一、线性表一线性表的定义和基本操作二线性表的实现顺序存储链式存储线性表的应用二、栈、队列和数组一栈和队列的基本概念二栈和队列的顺序存储构造三栈和队列的链式存储构造四栈和队列的应用五特殊矩阵的压缩存储三、树与二叉树TCP连接建设TCP连接释放TCP滑动窗口TCP计时器管理TCP拥塞控制七、应用层一DNS域名系统DNS名字空间 名字服务器 域名解析二电子邮件 体系构造和服务SMTP协议MIME协议POP协议IMAP协议三万维网 万维网体系构造URLHTML超文本标记语言HTTP协议一树的基本概念二二叉树二叉树的定义及其主要特性二叉树的顺序存储构造和链式存储构造二叉树的遍历线索二叉树的基本概念和构造三树、森林树的存储构造森林与二叉树的转换树和森林的遍历四树与二叉树的应用二叉排序树平衡二叉树哈夫曼Huffman树和哈夫曼编码四、图一图的基本概念二图的存储及基本操作邻接矩阵法邻接表法邻接多重表、十字链表三图的遍历深度优先搜索广度优先搜索四图的基本应用最小代价生成树最短路径拓扑排序关键路径五、查找一查找的基本概念二顺序查找法三分块查找法四折半查找法五B树及其 基本操作、B+树的 基本概念六散歹”Hash表七字符串模式匹配八查找算法的分析及应用六、排序一排序的基本概念二插入排序直接插入排序折半插入排序三起泡排序（BubbleSort四简单项选择择排序五希尔排序（Shel ISort六快速排序七堆排序八二路归并排序MergeSort J九基数排序十各种内部排序算法的对比十一排序算法的应用计算机组成原理【考察目标】理解单处理器计算机系统中各部件的内部工作原理、组成构造以及相互连接方式，具有 完整的计算机系统的整机概念。理解计算机系统层次化构造概念，熟悉硬件与软件之间的界面，掌握指令集体系构造的 基本知识和基本实现方法，掌握计算机性能评估的方法。能够运用计算机组成的 基本原理和 基本方法，对有关计算机硬件系统中的理论和实际问题进展计算、分析，并能对一些 基本部件进展简单设计。一、计算机系统概述一计算机开展历程二计算机系统层次构造计算机硬件的基本组成计算机软件的分类计算机的工作过程三计算机性能指标吞吐量、响应时间；CPU时钟周期、主频、CPL CPU执行时间；MIPS、MFL0PS;计算机 性能的评估方法。二、数据的表示和运算一J数制与编码进位计数制及其相互转换真值和机器数BCD码字符与字符串校验码二定点数的表示和运算定点数的表示无符号数的表示；有符号数的表示。定点数的运算定点数的位移运算；原码定点数的加/减运算；补码定点数的加/减运算，先行进位的概 念；定点数的乘/除运算，掌握补码的乘法和原码的除法；溢出概念和判别方法。三浮点数的表示和运算浮点数的表示IEEE754 标准浮点数的加/减运算四算术逻辑单元ALU串行加法器和并行加法器算术逻辑单元ALU的功能和构造三、存储器层次构造一存储器的分类二存储器的层次化构造三半导体随机存取存储器SRAM储器的工作原理DRAM存储器的工作原理只读存储器四主存储器与CPU的连接五双端口 RAM和多模块存储器六高速缓冲存储器CacheCache的基本工作原理Cache和主存之间的映射方式Cache中主存块的替换算法Cache写策略七虚拟存储器虚拟存储器的基本概念页式虚拟存储器段式虚拟存储器段页式虚拟存储器TLB快表四、指令系统一指令格式指令的基本格式定长操作码指令格式扩展操作码指令格式二指令的寻址方式有效地址的概念数据寻址和指令寻址常见寻址方式三CISC和RISC的基本概念和特点四指令系统设计的基本原则五、中央处理器CPU一CPU的功能和基本构造二指令执行过程三数据通路的功能和基本构造四控制器的功能和工作原理硬布线控制器微程序控制器微程序、微指令和微命令；微指令的编码方式；微地址的形式方式。五指令流水线指令流水线的基本概念指令流水线的基本实现超标量和动态流水线的 基本概念六多核处理器的基本概念六、总线一总线概述总线的基本概念总线的分类总线的组成及性能指标二总线仲裁集中仲裁方式分布仲裁方式三总线操作和定时同步定时方式异步定时方式四总线标准七、输入输出I/O系统一I/O系统基本概念二外部设备的工作原理输入设备：键盘、鼠标输出设备：显示器、打印机外存储器：硬盘存储器、磁盘阵列、光盘存储器三I/O接口I/O控制器I/O接口的功能和基本构造I/O端口及其编址I/O地址空间及其编码四I/O方式程序查询方式程序中断方式中断的 基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念。DMA方式DMA控制器的组成；DMA传送过程。通道方式I/O处理机的概念操作系统【考察目标】掌握操作系统的 基本概念、 基本原理和 基本功能，了解操作系统的整体构造。掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述 相关算法。一、操作系统概述一操作系统的概念.功能.作用和提供的服务二操作系统的开展与分类，典型操作系统的特征三操作系统的接口四操作系统的运行环境内核态与用户态中断.异常系统调用五操作系统体系构造二、进程管理一进程与线程进程概念进程的状态与转换进程描述进程制约进程通信：共享存储系统，消息传递，管道通信线程的概念二处理机调度调度的基本概念调度时机.切换调度的基本准则调度方式调度算法：先来先服务调度算法，短作业短进程.短线程优先调度算法，时间片轮转调度算法，优先级调度算法，响应比优先调度算法，多级反响队列调度算法三同步与互斥进程同步与互斥的基本概念临界资源与临界区实现临界区互斥的 基本方法：软件实现方法，硬件实现方法信号量的概念及应用管程的概念及应用经典同步问题：生产者-消费者问题，读者-写者问题，哲学家进餐问题四死锁死锁的概念资源分配图死锁的条件死锁处理策略：死锁预防，死锁防止系统安全状态.银行家算法，死锁检测与解除饥饿的概念三、内存管理一内存管理根基内存管理概念与功能交换与覆盖连续分配管理方式非连续分配管理方式：分页管理，分段管理，段页式管理二虚拟内存管理虚拟内存的概念局部性原理请求分页式管理页面置换算法：最正确置换算法OPT，先进先出置换算法FIFO，最近最少使用置 换算法LRU，时钟置换算法CLOCK页面分配策略工作集抖动四、文件管理一文件系统根基文件概念文件的逻辑构造：顺序文件，索引文件，索引顺序文件目录构造：文件控制块和索引节点，单级目录构造和多级目录构造，树形目录构造文件共享文件保护：访问类型，访问控制二文件系统实现文件系统层次构造目录实现文件实现三磁盘组织与管理磁盘构造磁盘调度算法磁盘管理五、输入输出I/O管理一I/O管理概述I/O控制方式I/O软件层次构造二I/O核心子系统I/O调度概念高速缓存与缓冲区设备分配与回收假脱机技术c SPOOL i ng J计算机网络【考察目标】掌握计算机网络的基本概念.基本原理和基本方法。掌握计算机网络的体系构造和典型网络协议，了解典型网络的组成和特点，理解典型网 络设备的工作原理。能够运用计算机网络的 基本概念. 基本原理和 基本方法进展网络系统的分析.设 计和应用。一、计算机网络概述一计算机网络基本概念计算机网络的概念.组成和功能计算机网络的分类二计算机网络体系构造计算机网络协议的三要素：语法.语义和同步计算机网络协议层次构造计算机网络协议服务与协议的关系三网络参考模型OS I /RM参考模型TCP/1P参考模型OS I /RM 与 TCP/IP 对比二、物理层一数据通信的理论根基傅里叶分析带宽有限的信号信道的最大数据速率二传输介质双绞线同轴电缆光纤三无线传输无线电传输微波传输光通信通信卫星传输四数字调制与多路复用基带传输通带传输频分复用时分复用码分复用三、数据链路层一数据链路层的功能设计提供应网络层的服务成帧过失控制流量控制二过失控制纠错码检错码三数据链路层协议有错信道上的单工停-等式协议滑动窗口协议四、介质访问控制子层一多路访问协议ALOHA载波侦听多路访问协议无冲突协议有限竞争协议无线局域网协议二以太网经典以太网物理层经典以太网的MAC子层协议以太网的性能交换式以太网快速以太网三无线局域网802. 111.802. 11体系构造和协议栈2. 802. 11物理层3.802. 11MAC子层协议四.数据链路层交换网桥的使用学习网桥生成树网桥中继器/集线器/网桥/交换机/路由器和网关虚拟局域网五、网络层一网络层的设计存储转发数据报交换面向连接服务与无连接服务虚电路与数据报网络的对比二路由算法最短路径算法泛洪算法距离矢量算法链路状态路由层次路由三I nternet的网络层IPv4协议IP地址IPv6协议I nternet控制协议OSPF-内部网关路由协议BGP-外部网关路由协议I nternet 组播移动IP六、传输层一传输服务Berke I ey套接字套接字编程实例二传输协议的要素寻址连接建设连接释放过失控制和流量控制多路复用崩溃恢复三UDP协议UDP协议特点IP伪头部四TCP协议TCP服务模型TCP协议TCP段的头