2019年中国科学院大学899计算机专业综合考研初试大纲

2018/12/25 9:31:50 来源: 网络
分享:

  2019年中国科学院大学硕士研究生入学考试《计算机专业综合》考试大纲

  一、考试方法和考试时间

  闭卷,笔试,考试时间180分钟,总分150分。

  试卷共16道大题,每题15分,共240分,考生可以任意选择其中10道大题回答,并在答题纸的该题答案前标明“选做本题”。

  如果选做的题目多于10道,则判卷将按照所选做试题的题号顺序选择前10道大题计分,后续所做视为无效考试内容。

  二、试卷结构

  题型:概念题(填空、选择、判断、简答),应用题(计算、画图、分析、设计)等。

  三、考试科目

  数据结构、计算机体?#21040;?#26500;、操作系统、编译原理四门课程,每门课程各占25%左右。

  四、考试内容

  I、计算机体?#21040;峁共?#20998;

  (一)考试大纲

  1、计算机体?#21040;?#26500;概论

  (1)计算机体?#21040;?#26500;的发展

  (2)计算机系统层次结构

  计算机系统的基本组成,计算机硬件的基本组成,计算机软件和硬件的关系,计算机的工作过程

  (3)衡量计算机的指标

  (4)计算机体?#21040;?#26500;的设计原则

  2、指令系统结构

  (1)指令系统设计原则

  (2)指令系统的演变

  指令集分类,存储管理,运行级别

  (3)指令集结构

  指令集的分类,指令操作数的存储,指令操作数的特征,指令操作和编码,C语言的机器表示

  (4)异常与中断

  异常分类,异常处理,中断机制

  (5)存储管理

  MIPS处理器对虚存系统的支持,LINUX操作系统的存储管理

  3、计算机硬件结构

  (1)计算机组成原理和结构

  冯诺依曼结构,计算机硬件结构的演进,处理器与IO间的通信,计算机系统主要组成?#32771;?/p>

  (2)计算机总线接口技术

  片上总线,内存总线,IO总线

  (3)计算机系统启动过程

  处理器核初始化,总线接口初始化,设备探测及驱动加载

  4、CPU微结构

  (1)二进制与逻辑电路

  计算机中数的表示,CMOS逻辑电路

  (2)简单运算器设计

  定点补码加法,减法,比较,移位

  (3)定点补码乘法器

  (4)指令流水线

  处理器数据通路,五级流水处理器,解决指令相关

  (二)计算机体?#21040;峁共?#20998;考试要求

  1、掌握从外部I/O与上层应用交互的整体软硬件过程

  2、掌握基于MIPS处理器的Linux操作系统TLB例外过程

  3、掌握C语言与指令系统的关系

  4、掌握系统初始化时PCI设备的探测过程

  5、掌握I/O通信中DMA传输过程

  6、能读懂CMOS电路,根据晶体管电路给出逻辑表达式

  7、掌握先行进位加法器结构及其verilog实现

  8、掌握Booth编码和华莱士树

  9、掌握指令流水线原理,了解解决相关的方法,能够用时空图表达流水线的运行

  (三)主要参考书目

  1、计算机体?#21040;?#26500;基础、胡伟武等著;机械工业出版社,2017年。

  II、 数据结构

  (一)考试大纲

  1、绪论

  (1)数据结构的基本概念,数据的逻辑结构、存储结构。

  (2)算法的定义、算法的基本特性以及算法分析的基本概念。

  2、线性表

  (1)线性表的定义、基本操作。

  (2)线性表的实现及应用,包括顺序存储结构、链式存储结构(单链表、循环链表和双向链表)的构造原理,在两种存储结构上对线性表实施的主要的操作(三种链表的建立、插入和删除、检索等)的算法设计与实现。

  3、堆栈与队列

  (1)堆栈与队列的基本概念、基本操作。

  (2)堆栈与队列的顺序存储结构、链式存储结构的构造原理。

  (3)在不同存储结构的基础上对堆栈、队列实施基本操作(插入与删除等)对应的算法设计与实现。

  4、数组和广义表

  (1)数组的基本概念、多维数组的实现。

  (2)对称矩阵和稀疏矩阵的压缩存储。

  (3)广义表的基本概念。

  5、树与二叉树

  (1)树的基本概念和性质。

  (2)二叉树的基本概念、性质。

  (3)二叉树的存储,包括顺序存储、链式存储结构。

  (4)二叉树的遍历。

  (5)线索二叉树的基本概念和构造。

  (6)树和森林的存储结构、遍历。

  (7)哈夫曼(Huffman)树和哈夫曼编码。

  6、图

  (1)图的基本概念和性质。

  (2)图的存储,包括邻接矩阵法、邻接表法。

  (3)图的遍历操作,包括深度优先搜索、广度优先搜索。

  (4)最小生成树、最短路径、关键路径、拓扑?#21028;?#31639;法的原理、实现和应用。

  7、查找

  (1)顺序查找法、分块查找法、折半查找方法的原理、实现和应用。

  (2)二叉?#21028;?#26641;、平衡二叉树、键树的原理、实现和应用。

  (3)B树及其基本操作、B+树的基本概念。

  (4)哈希(Hash)表的原理、实现和应用。

  (5)字符串模式匹配算法的原理和实现。

  8、?#21028;?/p>

  (1)?#21028;?#30340;基本概念。

  (2)直?#30828;?#20837;?#21028;頡?#25240;半插入?#21028;頡?#27668;泡?#21028;頡?#31616;单选择?#21028;頡?#24555;速?#21028;頡?#22534;?#21028;頡?#20108;路归并?#21028;頡?#22522;数?#21028;頡?#22806;部?#21028;?#31639;法的原理、实现和复杂度。

  (3)?#21028;?#31639;法的应用。

  (二)考试要求

  1、掌握数据结构的基本概念、基本原理和基本方法。

  2、掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。

  3、能够运用数据结构基本原理和方法进行问题的分析与求解,具备采用C或C++语言设计与实现算法的能力。

  (三)主要参考书目

  1、数据结构(C语言版)、 严蔚敏,吴伟民 编著,?#26412;?#28165;华大学出版社,2007年。

  III、 编译原理

  (一) 考试大纲

  1、编译系统的概念和架构

  (1)编译的概念、分类、编译系统的组成

  (2)程序设计语言的基础知识、作用域、参数传递等

  (3)四类形式文法的相关概念

  (4)构建编译系统的相关科学以及编译技术的应用等

  2、词法分析

  (1)词法分析器的作用

  (2)词法符号的描述(包括正则式、正则定义等内容)

  (3)基于状态转换的词法分析实现

  (4)有限状态自动机概念,正则表达式、NFA、DFA间的转换,DFA的化简

  3、语法分析

  (1)语法分析基础,上下文无关文法、二义性文法

  (2)文法的设计:二义性的消除、消除左递归、提取左因子等

  (3)自上而下的分析方法、递归下降分析和非递归的预测分析器等

  (4)自下而上的分析方法、LR分析

  4、语法制导的翻译

  (1)属性文法、继承属?#38498;?#32508;合属性

  (2)语法制?#32423;?#20041;、求值顺序

  (3)语法制导翻译的应用

  (4)语法制导的翻译方案

  (5)实现L属性的SDD

  5、中间代码生成

  (1)语法树的变体、DAG

  (2)三地址代码

  (3)类型和声明的处理

  (4)表达式的翻译

  (5)静态类?#22270;?#26597;

  (6)控制流的处理等

  6、运行时环境

  (1)存储组织、静态分配、栈式分配的基本概念等

  (2)作用域的运行时实现、非局部名字的?#26790;?#31561;

  7、目标代码生成简介

  (1)代码生成器设计中的问题

  (2)目标代码中的地址处理

  (3)基?#31350;?#21644;流图

  (4)基?#31350;?#30340;优化

  (5)代码生成器的简单实现

  (6)窥孔优化

  (7)寄存器分配和?#27010;?/p>

  (8)指令调度等

  (二)考试要求

  1、掌握编译系统构成的基本概念和相关原理

  2、熟悉词法分析的基础理论,明晰正则式、正则定义、有限状态自动机等基本概念以及相关转换的方法,能够按照要求构造简单的有限状态自动机,并实施必要的变换

  3、熟悉语法分析的基本理论,掌握上下文无关文法的基本概念、推导等,明晰文法、句子、语言之间的关系;能够根据需要对文法进行必要的改写(如消除二义性、消除左递归、提取左因子等);对自上而下和自下而上的典型分析方法能够熟悉其流程、构建相关的分析表等

  4、熟悉语法制导翻译的典型方法(如语法制?#32423;?#20041;、翻译方案)及其基本概念(如继承属性、综合属性等),掌握S属?#38498;蚅属性定义,并理解在语法分析框架中实现翻译的方法和过程

  5、能够利用语法制导翻译的理论指导中间代码生成,对三地址代码有基本了解,熟悉对典型语句的翻译处理、理解类?#22270;?#26597;的原则和典型的静态类?#22270;?#26597;的方法

  6、熟悉运行时环境、存储组织等的基本概念、熟悉对非局部名字?#26790;?#30340;处理方法

  7、熟悉代码生成的基本概念,对基?#31350;欏?#27969;图等有充分认识,对简单的优化方法(如DAG的优化、窥孔优化、寄存器分配、指令调度等)有初步了解

  (三)主要参考书目

  1、英文原版:《Compilers Principles, Techniques and Tools》Alfred V、 Aho, Monica S、 Lam, Ravi Sethi, Jeffrey D. Ullman, second edtion,机械工业出版社有影印版

  2、英文原版的中译本《编译原理》;赵建华、郑?#31232;?#25140;新宇译,机械工业出版社2009年1月,2015年10月第二次印刷

  IV.操作系统

  (一) 考试大纲

  1、操作系统概述

  (1)计算机基本构成、处理器的内部结构、高速缓冲存储器CACHE

  (2)操作系统的概念、演变历程、特性、分类、运行环境、功能

  (3)系统调用的功能和过程。

  2、进程

  进程、进程描述、进程地址空间分?#25216;?#36827;程状态转换

  3、线程、对称多处理SMP和微内核

  (1)线程的概念,定义线程的必要?#38498;?#21487;能性;

  (2)线程的功能特性与实现方式;

  (3)操作系统的体?#21040;?#26500;(微内核与巨内核)及其性能分析。

  4、处理器调度

  (1)处理器的三种调度类型;

  (2)进程调度的各种算法及其特点。

  (3)多处理器对进程调度的影响

  (4)实时进程的特点,限期调度和速率单调调度方法。

  5、并发性

  (1)并发性问题及相关概念,如临界区、互斥、信号量和管程等;

  (2)进程互斥、同步和通信的各种算法;

  (3)?#28010;?#30340;概念、?#28010;?#30340;原因和条件

  (4)?#28010;?#30340;预防、避免和检测算法。

  6、存储器管理

  (1)分区存储管理、覆盖与交换;

  (2)页式管理及段式管理;

  (3)段、页式存储管理方法及实现技术;

  (4)虚存的原理及相关的各种算法和数据结构。

  7、设备管理和?#25490;?#35843;度

  (1)操作系统中输入/输出功能的组织;

  (2)中断处理;

  (3)设备驱动程序、设备无关的软件接口和spooling技术;

  (4)缓冲策略;

  (5)?#25490;?#35843;度算法;

  (6)?#25490;?#38453;列。

  8、文件系统

  (1)文件系统特点与文件组织方式;

  (2)文件系统的数据结构;

  (3)目录的基本性?#22987;?#20854;实现方法;

  (4)?#25490;?#31354;间的管理。

  (5)分布式文件系统

  9、分布式系统

  (1)分布式处理的特点、类型;

  (2)机?#21512;?#32479;。

  10、操作系统安全

  (1)操作系统安全保护目标及相关技术

  (2)常见操作系统攻击方法的原理和防护

  (二)考试要求

  1、了解操作系统所管辖的软、硬件?#35797;?了解操作系统的关键概念,从整体上把握操作系统的特性与功能等概念;建立操作系统的?#35797;?#31649;理和应用接口的职能概念。理解系统调用的执行过程。

  2、掌握进程的本质特征,明?#26041;?#31243;的动态特性,理解进程的地址空间分布,熟悉进程状态间转换的原因,建立进程是?#35797;?#20998;配单元和一种运行实体的基本理念。

  3、理解引入线程作为基本运行实体的必要?#38498;?#21487;能性;掌握线程各种实现方式及其特点;熟悉SMP体?#21040;?#26500;、操作系统的体?#21040;?#26500;。

  4、了解批处理、交互式、实时三种调度类型;重点掌握进程调度的各种算法及其?#35270;?#29615;了解实时进程的本质,掌握限期调度和速率单调调度方法。

  5、灵活运用信号量、管程等技术解决互斥合同步问题;理解?#28010;?#30340;概念和产生?#28010;?#30340;充分必要条件;熟练掌握?#28010;?#30340;预防、避免和检测算法;了解处理?#28010;?#38382;题时避免饥饿的方法。

  6、理解存储管理的功能?#25353;?#20648;管理对多道程序设计的支持;掌握段、页式存储管理方法及实现技术;掌?#25307;?#23384;的原理及相关的各种替换算法和数据结构。

  7、理解输入输出设备及操作系统中输入/输出功能的组织、掌握中断处理、设备驱动程序、设备无关的软件接口和spooling等技术,重点掌握各?#38047;?#20110;提高性能的缓冲策?#38498;痛排?#35843;度算法;了解可提高性能和可靠性的各种?#25490;?#38453;?#20449;?#32622;方式。

  8、理解文件系统特点与文件组织,掌握文件系统的基本数据结构,了解文件、目录的基本性?#22987;?#20854;实现方法;重点掌握?#25490;?#31354;间的管理、文件系统的性能及可靠性、文件系统的安全性及保护机制,分布式文件系统的问题和特点等。

  9、了解分布式处理的特点、类型;掌握多层体?#21040;?#26500;和机?#21512;?#32479;的基本概念和特点。

  10、了解操作系统安全保密性、完整?#38498;?#21487;用性的基本概念及保护方法。了解常用的攻击和防御技术的原理。

  (三)主要参考书目

  1、?#26029;?#20195;操作系统(第三版)》 Andrew S、 Tanenbaum , 2008

追梦之旅,选择比努力更重要!海天考研,为成功考研指引方向!

中间广告图.jpg

活动专题