计算机软件基础——中国科学院数学与系统科学研究院2006年硕士初试大纲-易考网-Easy考研网提供考研试卷专业清单-考研一站式_Easy考研网_考研资料、考研专业课试题、考研专业目录、考研参考书目、考研咨询、考研辅导报名、考研书籍、考研会员服务

计算机软件基础——中国科学院数学与系统科学研究院2006年硕士初试大纲

http://www.ezkaoyan.com 2006-4-18

硕士研究生入学考试
《计算机软件基础》考试大纲

本《计算机软件基础》考试大纲适用于中国科学院数学与系统科学研究院计算机软件与理论专业的硕士研究生入学考试。作为本专业的基础课程，《计算机软件基础》将主要包括编译原理、操作系统、数据结构和程序设计等四个方面的内容。要求考生对其基本概念有较深入的了解，能系统地运用相关的知识，并能够通过程序设计来解决相关问题。

一、考试内容

（一）数据结构部分
1. 数据结构和算法分析的基本概念和术语
2. 线性结构，包括线性表、栈和队列、串等，的类型定义和相关算法
3. 树形结构的类型定义和相关算法
4. 图状结构或网状结构的类型定义和相关算法
5. 查找和排序算法
（二）编译原理部分
1. 编译器的基本概念和基本结构
2. 词法分析器、正规式、有限自动机和扫描器生成器
3. 上下文无关文法，各种语法分析技术，如自上而下分析和自下而上分析，LR分析器和分析器的生成器
4. 上下文无关文法制导下的语言翻译
5. 类型检查
6. 与面向对象语言和函数式语言的编译相关的概念
（三）操作系统
1. 操作系统的基本概念
2. 并发控制原理及其实现，包括：程序和进程、互斥和同步、死锁与饥饿和进程调度等
3. OS资源管理及其实现的相关概念，包括：存储器管理、文件管理和I/O设备管理等
（四）程序设计
1. 要求能用C或C++编写正确的程序

二、考试要求

（一）数据结构部分
1. 理解并掌握数据结构和算法分析的基本概念和术语，了解数据类型和抽象数据类型的表示和实现，并了解算法设计的要求和算法效率的度量
2. 熟练掌握线性结构，包括线性表、栈和队列、串等的类型定义和抽象数据类型表示，熟练掌握与线性结构相关的典型算法，并能够使用这些结构和算法解决实际问题
3. 熟练掌握树形结构的类型定义和抽象数据类型表示，熟练掌握与树形结构相关的典型算法，如遍历算法等，并能够使用这些结构和算法解决实际问题
4. 熟练掌握图状结构或网状结构的类型定义和抽象数据类型表示，熟练掌握与图结构相关的遍历算法和相关性质，并能够使用这些结构和算法解决实际问题
5. 熟练掌握各种查找和排序算法的设计和实现
（二）编译原理部分
1. 了解编译器的基本概念和基本结构
2. 了解词法分析器的作用，掌握记号的描述和识别方法，掌握识别有限自动机的基本定义和从正规式建立识别器的方法，了解词法分析器Lex
3. 了解语法分析器的作用，掌握上下文无关语言和文法的相关概念和性质，掌握各种语法分析技术，如自上而下分析，自下而上分析，以及LR分析器，了解分析器的生成器Yacc
4. 掌握上下文无关文法制导下的语言翻译，
5. 了解类型体制的基本概念，了解简单类型检查器和类型表达式的等价
6. 了解与面向对象语言和函数式语言的编译相关的概念
（三）操作系统
1. 了解什么是操作系统，以及操作系统的发展历程
2. 掌握与并发控制相关的概念，包括：程序和进程、互斥和同步、死锁与饥饿和进程调度等，掌握其基本的实现方式
3. 掌握OS资源管理的相关概念，包括：存储器管理、文件管理和I/O设备管理等，了解其基本的实现方式
（四）程序设计
1. 要求能用C或C++编写正确的程序

三、主要参考书目
1. 《数据结构》，严蔚敏著，清华大学出版社。
2. 《编译原理和技术》陈意云著，中国科技大学出版社。
3. 《操作系统：原理、技术与编程》蒋静、徐志伟著，机械工业出版社。
4. 《程序设计C语言》谭浩强著，清华大学出版社。