重大计算机学014专业课考纲 15页

《计纂桃学科专业基磁综舍》奢试炭纲及参奢书B（2014年版）考试科目代码:917重庆大学考试形式和试卷结构3参考书「【3I.数据结构4【考查H标】4一、线性表4二、栈、队列和数组4三、树与二叉树4四、图5五、査找5六、排序5II.计算机组成原理6【考查目标】6一、计算机系统概述6二、数据的表示和运算6三、存储器层次结构7四、指令系统7五、中央处理器（CPU）7六、总线8\n七、输入输出（I/O）系统8I.操作系统9【考査H标】9一、操作系统概述9二、进程管理9三、内存管理10四、文件管理10五、输入输出（I/O）管理11II.计算机网络12【考查口标】12一、计算机网络概述12二、物理层12三、数据链路层13四、介质访问控制子层13五、网络层14六、传输层14七、应川层15考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。二、答题方式答题方式为闭港、笔试。三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分\n参考书目1.数据结构（C语言版本）.严蔚敏吴伟民.清华大学出版社.1997.4第一版2004.11第28次印刷.2.计算机组成和设计:硬件/软件接口.DavidA.Patterson.JohnL.Hennessy.机械工业出版社.2012年1M1日.3.操作系统：精髓与设计原理（原书第6版）•斯托林斯（WilliamStallings）著，陈向群，陈渝译.机械工业出版社,2010-09-01.4.计算机网络（第五版，简体中文）.AndrewS.Tanenbaum.DavidJ.Wethenill.清华大学出版社.2012年3月.\nI.数据结构【考查目标】1.掌握数据结构的基本概念、基本原理和基本方法。2.掌握数据的逻辑结构、存储结构及基木操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计为实现算法的能力。一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组（一）栈和队列的基木概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应丿U（五）特殊角阵的压缩存储三、树与二叉树（一）树的基本概念（二）二义树1.二义树的定义及其主要特性2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码\n%1.图（一）图的基本概念（二）图的存储及基木操作1.邻接矩阵法2.邻接表法3.邻接多重表、十字链表（三）图的遍历1.深度优先搜索2.广度优先搜索（四）图的基本应用1.最小（代价）牛成树2.最短路径3.拓扑排序4.关键路径五、查找（一）查找的棊木概念（二）顺序查找法（三）分块杳找法（四）折半査找法（五）B树及其基木操作、B+树的基木概念（六）散列（Hash）表（七）字符串模式匹配（八）查找算法的分析及应用六、排序（-）排序的基本概念（二）插入排序1.直接插入排序2.折半插入排序（三）起泡排序（BubbleSort）（四）简单选择排序（五）希尔排序（ShellSort）（六）快速排序（七）堆排序（八）二路归并排序（MergeSort）（九）基数排序（10各种内部排序算法的比较\n（十一）排序算法的应用II.计算机组成原理【考查目标】1.理解单处理器计算机系统中各部件的内部工作原理、纽成结构以及相互连接方式，具有完整的计算机系统的整机概念。2.理解计算机系统层次化结构概念，熟悉便件与软件Z间的界面，拿握指令集体系结构的基本知识和基本实现方法，掌握计算机性能评估的方法。3.能够运用计算机组成的棊木原理和基本方法，对有关计算机硕件系统中的理论和实际问题进行计算、分析，并能对一些基本部件进行简单设计。一、计算机系统概述（一）计算机发展历程（二）计算机系统层次结构1.计算机硕件的基本组成2.计算机软件的分类3.计算机的工作过程（三）计算机性能指标吞吐量、响应时间;CPU时钟周期、主频、CPkCPU执行时间;MIPS、MFLOPS；计算机性能的评估方法。数据的表示和运算（一•）数制与编码1.进位计数制及其相互转换2.真值和机器数3.BCD码4.字符与字符串5.校验码（二）定点数的表示利运算1.定点数的表示无符号数的表示；有符号数的表示。2.定点数的运算定点数的位移运算；原码肚点数的加/减运算；补码定点数的加/减运算，先行进位的概念；肚点数的乘/除运算，掌握补码的乘法和原码的除法；溢出概念和判别方法。（三）浮点数的表示和运算1.浮点数的表示1EEE754标准2.浮点数的加/减运算（四）算术逻辑单元ALU\n1.串行加法器和并行加法器2.算术逻辑单元ALU的功能和结构三、存储器层次结构（一）存储器的分类（二）存储器的层次化结构（三）半导体随机存取存储器1.SRAM储器的工作原理2.DRAM存储器的工作原理3.只读存储器（四）主存储器与CPU的连接（五）双端口RAM和多模块存储器（六）高速缓冲存储器（Cache）1.Cache的基本工作原理2.Cache和主存之间的映射方式3.Cache中主存块的替换算法4.Cache写策略（七）虚拟存储器1.虚拟存储辭的基本概念2.页式虚拟存储器3.段式虚拟存储器4.段页式虚拟存储器5.TLB（快表）四、指令系统（一）指令格式1.指令的基本格式2.定长操作码指令格式3.扩展操作码指令格式（二）指令的寻址方式1.有效地址的概念2.数据寻址和指令寻址3.常见寻址方式（三）CISC和RISC的基本概念和特点（四）指令系统设计的基木原则\n五、中央处理器（CPU）（一）CPU的功能和基本结构（二）指令执行过程（三）数据通路的功能和基本结构（四）控制器的功能和工作原理1.硬布线控制器2.微程序控制器微程序、微指令和微命令；微指令的编码方式；微地址的形式方式。（五）指令流水线1.指令流水线的基本概念2.指令流水线的基本实现3.超标量和动态流水线的基本概念（六）多核处理器的基本概念六.总线（一）总线概述1.总线的皋木概念2.总线的分类3.总线的组成及性能指标（二）总线仲裁1.集中仲裁方式2.分布仲裁方式（三）总线操作和定时1.同步定时方式2.异步定时方式（四）总线标准七、输入输出（I/O）系统（一）1/0系统基本概念（二）外部设备的工作原理1.输入设备：键盘、鼠标2.输出设备：显示器、打卬机3.外存储器：硬盘存储器、磁盘阵列、光盘存储器（三）I/O接口（I/O控制器）1.I/O接口的功能和基本结构2.I/O端口及其编址3.I/O地址空间及其编码（四）I/O方式1.程序查询方式\n1.程序中断方式中断的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念。2.DMA方式DMA控制器的组成；DMA传送过程。3.通道方式4.I/O处理机的概念III.操作系统【考查目标】1.掌握操作系统的基木概念、基木原理和基木功能，了解操作系统的整体结构。2.掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法。一、操作系统概述（-）操作系统的概念.功能.作用和提供的服务（二）操作系统的发展与分类，典型操作系统的特征（三）操作系统的接口（四）操作系统的运行坏境1.内核态与用户态2.屮断屏常3.系统调用（五）操作系统体系结构二、进程管理（一）进程与线程1.进程概念2.进程的状态与转换3.进程描述4.进程制约5.进程通信：共享存储系统，消息传递，管道通信6.线程的概念（二）处理机调度1.调度的基本概念2.调度时机.切换3.调度的基本准则4.调度方式5.调度算法：先来先服务调度算法，短作业（短进程.短线程）优先调度算法，时•间片轮转调\n度算法，优先级调度算法，响应比优先调度算法，多级反馈队列调度算法（三）同步与互斥1.进程同步与互斥的基本概念2.临界资源与临界区3.实现临界区互斥的基本方法：软件实现方法，硬件实现方法4.信号量的概念及应用5.管程的概念及应用6.经典同步问题：牛产者■消费者问题，读者■写者问题，哲学家进餐问题（四）死锁1.死锁的概念2.资源分配图3.死锁的条件4.死锁处理策略：死锁预防，死锁避免（系统安全状态.银行家算法），死锁检测与解除5.饥饿的概念三、内存管理（一）内存管理基础1.内存管理概念与功能2.交换与覆盖3.连续分配管理方式4.非连续分配管理方式：分页管理，分段管理，段页式管理（二）虚拟内存管理1.虚拟内存的概念2.局部性原理3.请求分页式管理4.页面置换算法：最佳置换算法（OPT）,先进先出置换算法（FIFO）,最近最少使用置换算法（LRU）,时钟置换算法（CLOCK）5.页面分配策略6.工作集7.抖动%1.文件管理（-）文件系统基础1.文件概念2.文件的逻辑结构：顺序文件，索引文件，索引顺序文件3.目录结构：文件控制块和索引节点，单级目录结构和多级目录结构，树形目录结构4.文件共享5.文件保护：访问类型，访问控制（二）文件系统实现1.文件系统层次结构\n1.目录实现2.文件实现（三）磁盘组织与管理1.磁盘结构2.磁盘调度算法3.磁盘管理五、输入输出（I/O）管理（一）1/0管理概述1.I/O控制方式2.I/O软件层次结构（二）1/O核心子系统1.I/O调度概念2.高速缓存与缓冲区3.设备分配与回收4.假脱机技术（SPOOLing）\nIV•计算机网络【考查目标】1.掌握计算机网络的基本概念.基本原理和基木方法。2.掌握计算机网络的体系结构和典型网络协议，了解典型网络的组成和特点，理解典型网络设备的工作原理。3.能够运用计算机网络的基本概念.基本原理和基本方法进行网络系统的分析.设计和应用。一、计算机网络概述（一）计算机网络基本概念1.计算机网络的概念.组成和功能2.计算机网络的分类（二）计算机网络体系结构1.计算机网络协议的三要素：语法.语义和同步2.计算机网络协议层次结构3.计算机网络协议服务为协议的关系（三）网络参考模型1.OSI/RM参考模型2.TCP/IP参考模型3.OSI/RM与TCP/IP比较二、物理层（一）数据通信的理论基础1.傅里叶分析2.带宽有限的信号3.信道的最人数据速率（二）传输介质1.双绞线2.同轴电缆3.光纤（三）无线传输1.无线电传输2.微波传输3.光通信4.通信卫星传输（四）数字调制与多路复用1.棊带传输\n1.通带传输2.频分复用3.时分复川4.码分复用三、数据链路层（一）数据链路层的功能设汁1.提供给网络层的服务2.成帧3.差错控制4.流量控制（二）差错控制1.纠错码2.检错码（三）数据链路层协议1.有错信道上的单工停■等式协议2.滑动窗口协议四、介质访问控制子层（一）多路访问协议1.ALOHA2.载波侦听多路访问协议3.无冲突协议4.有限竞争协议5.无线局域网协议（二）以太网1.经典以太网物理层2.经典以太网的MAC子层协议3.以太网的性能4.交换式以太网5.快速以太网（三）无线局域网802.111.1.802.11体系结构和协议栈2.2.802.11物理层3.3.802.11MAC子层协议（四）•数据链路层交换1.网桥的使用2.学习网桥3.牛成树网桥4.中继器/集线器/网桥/交换机/路市器和网关\n1.虚拟局域网五、网络层（一）网络层的设计1.存储转发数据报交换2.面向连接服务与无连接服务3.虚电路与数据报网络的比较（二）路rh算法1.最短路径算法2.泛洪算法3.距离欠量算法4.链路状态路由5.层次路由（三）Internet的网络层1.IPv4协议2.IP地址3.IPv6协议4.Internet控制I■办议5.OSPF■内部网关路山协议6.BGP■外部网关路由协议7.Internet组播8.移动IP六、传输层（一）传输服务1.Berkeley套接字2.套接字编程实例（二）传输协议的要素1.寻址2.连接建立3.连接释放4.差错控制和流量控制5.多路复川6.崩溃恢复（三）UDP协议1.UDP协议特点2.IP伪头部1.（四）TCP协议1.TCP服务模型2.TCP协议3.TCP段的头\n1.TCP连接建立2.TCP连接释放3.TCP滑动窗口4.TCP计时器管理5.TCP拥塞控制七、应用层（―）DNS域名系统1.DNS名字空间2.名字服务器3.域名解析（二）电子邮件1.体系结构和服务2.SMTP协议3.MIME协议4.POP协议5.IMAP协议（三）万维网1.万维网体系结构2.URL3.HTML超文本标记语言4.HTTP协议