《计算机软件基础》考试大纲 返回

发布时间：2010-06-03 浏览次数：946

《盘算机软件底子》检验纲要

本《盘算机软件》检验纲要适用于中国迷信院研讨生院盘算机迷信与技艺等专业的硕士研讨生退学检验。盘算机软件是盘算机迷信与技艺和相关学科的紧张底子，重要内容包括数据布局、编译原理和操纵体系三大局部。要求考生对盘算机迷信与技艺和相关学科的基本见地有较深化、体系的明白，掌握种种数据布局的定义和完成算法，掌握操纵体系和编译原理所涉和的关键内容，并具有综合运用所学知识阐发标题和处置标题的身手。

一、检验内容

数据布局

   1、绪论

（1）数据布局的基本见地，数据的逻辑布局、存储布局。

（2）算法的定义、算法的基本特性以和算法阐发的基本见地。

2、线性表

（1）线性干系、线性表的定义，线性表的基本操纵。

（2）线性表的次第存储布局与链式存储布局(包括单链表、循环链表和双向链表)的布局原理。在以上两种存储布局上对线性表实行的最重要的操纵(包括三种链表的创立、拔出和删除、检索等)的算法方案。

3、堆栈与行列步队

（1）堆栈与行列步队的基本见地、基本操纵。

（2）堆栈与行列步队的次第存储布局与链式存储布局的布局原理。

（3）在差异存储布局的底子上对堆栈与行列步队实行拔出与删除等基本操纵对应的算法方案。

4、串

（1）串的基本见地、串的基本操纵和存储布局。

（2）串的形式立室算法和改造的KMP算法

5、数组和狭义表

（1）数组的见地、多维数组的完成

（2）对称矩阵和奇异矩阵的紧缩存储

（3）狭义表的基本见地

6、树与二叉树

（1）树的定义和性子

（2）二叉树的见地、性子和完成

（3）遍历二叉树和线索二叉树

（4）树和丛林

（5）赫夫曼树和其运用

（6）树的计数

7、图

（1）图的定义，基本见地，图的分类，常用名词术语。

（2）图的衔接矩阵存储要领、衔接表存储要领的布局原理。

（3）图的遍历操纵。

（4）最小天生树，最长途径，AOV网与拓扑排序。

8、文件和查找

（1）数据文件的基本见地和基本术语，数据文件的基本操纵。

（2）次第文件、索引文件、散列(Hash)文件。

（3）次第文件的次第查找要领、排序延续次第文件的半数查找要领以和其他文件的基本查找要领。

9、内排序

（1）排序的基本见地，排序要领的分类。

（2）拔出排序法(含半数拔出排序法)、选择排序法、泡排序法、快速排序法、聚集排序法、归并排序、基数排序。种种排序要领排序的原理、规律和特点，种种排序算法的时空庞大度大约阐发。

操纵体系

1、操纵体系概述
（1）盘算机基本构成、处置惩罚器的外部布局、高速缓冲存储器CACHE；
（2）操纵体系的见地、演化进程、特性、分类、运转环境、效果
（3）存储器的层次布局

2、、进程
进程、进程形貌和进程形状转换

3、线程、对称多处置惩罚SMP和微内核

（1）线程的见地，定义线程的需要性和大约性；

（2）线程的效果特性与完成方法；

（3）对称多处置惩罚SMP体系布局；

（4）操纵体系的体系布局（微内核与巨内核）和其功用阐发。

4、并发性

（1）并发性标题和相关见地，如临界区、互斥、信号量和管程等；

（2）进程互斥、同步和通讯的种种算法；

（3）逝世锁的见地、逝世锁的缘故原因和条件

（4）逝世锁的防范、抑制和检测算法。

5、存储器操持
（1）分区存储操持、解围与互换；
（2）页式操持和段式操持；
（3）段、页式存储操持要领和完成技艺；
（4）虚存的原理和相关的种种算法和数据布局。

6、单处置惩罚器调理
（1）处置惩罚器的三种调理范例；
（2）进程调理的种种算法和其特点。

7、多处置惩罚器调理和及时调理
（1）多处置惩罚器对进程调理的影响
（2）多处置惩罚器环境下的进程和线程调理算法；
（3）及时进程的特点；
（4）限期调理和速率单调调理要领。

8、配置操持和磁盘调理
（1）操纵体系中输入/输入效果的结构；
（2）中止处置惩罚；
（3）配置驱动步伐、配置有关的软件接口和spooling技艺；
（4）缓冲战略；
（5）磁盘调理算法；
（6）磁盘阵列。

9、文件体系
（1）文件体系特点与文件结构方法；
（2）文件体系的数据布局；
（3）目次的基天分子和着完成要领；
（4）磁盘空间的操持。

10、散布式体系
（1）散布式处置惩罚的特点、范例；
（2）多层体系布局、中心件技艺；
（3）机群体系；
（4）散布式进程操持相关的操纵体系方案标题。

编译原理

1、引论

（1）编译器的基本见地

（2）编译阶段和编译器伙伴

2、词法阐发

（1）词法阐发器

（2）正轨式

（3）有限自动机和扫描器天生器

3、语法阐发

（1）上下文有关文法

（2）种种语法阐发技艺，如自上而下阐发和自下而上阐发，LR阐发器

4、语法制导的翻译

（1）S属性和L属性

（2）自上而下翻译

（3）承袭属性的自上而下盘算

（4）递归盘算

5、范例查抄

（1）范例体制

（2）大约范例查抄器

（3）范例表达式的等价

（4）函数和算符的重载

6、运转环境

运转时存储空间和结构操持

7、中心代码天生

（1）常用的中心代码表现：后缀表现、图形表现和三地点表现

（2）声明、赋值和布尔表达式

8、代码天生

（1）代码天生涉和的重要标题

（2）目的呆板

（3）基本块和流图

9、代码优化

（1）优化的重要种类

（2）流图中的循环

（3）全局数据流阐发先容

（4）代码改造变卦

二、检验要求

数据布局

1、  创立有关数据布局最基本的见地，包括数据的逻辑布局、存储结会商算法，算法阐发的基本见地与基本要领

2、  掌握线性表的基本见地以和两种存储布局的布局原理，掌握在种种存储布局下对线性表举行的基本操纵的算法方案。

3、  掌握堆栈和行列步队的基本见地与特性，掌握在两种存储布局下怎样对堆栈和行列步队举行拔出和删除等操纵，以和应用堆栈与行列步队操持实践标题的基本要领。

4、  充沛相识串的基本见地、掌握串的存储结会商相关的操纵算法。

5、  掌握数组、狭义表和奇异矩阵的基本见地，物理结会商基本操纵的完成

6、  充沛相识树型布局的逻辑特性，掌握种种存储布局的布局原理，可以或许熟练地应用常用的三种遍历要领，掌握应用二叉树的遍历操纵操持实践标题的要领，掌握二叉排序树的创立以和在二叉排序树中查找一个结点存在与否的进程。

7、  充沛相识图的逻辑布局的特点，掌握常用的两种存储要领，掌握最小天生树(Prim算法和Kruskal算法)、最长途径、拓扑排序的详细求解进程。

8、  充沛相识种种次第文件的布局与相应的查找要领；相识种种查找算法之间时空遵从的差异；从布局与操纵上了驱逐列文件的创立、散列函数的选择(布局)准绳、处置惩罚散列争辩的要领以和在散列文件中查找一个记载存在与否的进程。

9、  充沛相识种种排序要领的排序特点和排序进程，对付恣意给出的数据元素序列，可以或许熟练地采取指定排序要领举行排序，并且可以或许对每一种排序要领排序进程中所举行的元素之间的比拟次数、相应排序算法的时间、空间、排序的动摇性等功用举行大约阐发。

操纵体系

1、         解操纵体系所统领的软、硬件资源；相识操纵体系的关键见地，从集团上驾驭操纵体系的特性与效果等见地；创立操纵体系的资源操持和运用接口的职能见地。

2、              掌握进程的实质特性，明白进程的静态特性，熟习进程形状间转换的缘故原因，创立进程是资源分派单位和一种运转实体的基本理念。

3、         明白引入线程作为基本运转实体的需要性和大约性；掌握线程种种完成方法和其特点；熟习SMP体系布局、操纵体系的体系布局（微内核与巨内核）。

4、         可以或许应用信号量、管程等技艺操持互斥条约步标题；明白逝世锁的见地和孕育产存亡锁的充沛需要条件；熟练掌握逝世锁的防范、抑制和检测算法；相识处置惩罚逝世锁标题时抑制饥饿的要领。

5、              相识存储操持的效果和存储操持对多道步伐方案的支持；掌握段、页式存储操持要领和完成技艺； 重点掌握虚存的原理和相关的种种算法和数据布局。

6、              相识长程、中程和短程三种调理范例；重点掌握进程调理的种种算法和其适用环境。

7、              相识调理粒度的见地，熟习多处置惩罚器环境下进程和线程调理算法，相识及时进程的实质，掌握限期调理和速率单调调理要领。

8、              相识输入输入配置和操纵体系中输入/输入效果的结构、掌握中止处置惩罚、配置驱动步伐、配置有关的软件接口和spooling等技艺，重点掌握种种用于提高功用的缓冲战略和磁盘调理算法；相识可提高功用和牢靠性的种种磁盘阵列配置方法。

9、              相识文件体系特点与文件结构，掌握文件体系的基本数据布局，相识文件、目次的基天分子和着完成要领；重点掌握磁盘空间的操持、文件体系的功用和牢靠性、文件体系的寂静性和掩护机制等。

10、          相识散布式处置惩罚的特点、范例；掌握多层体系布局、中心件技艺和机群体系的基本见地和特点；重点掌握进程迁移、散布式全局形状的认定、散布式互斥与逝世锁防范等技艺。

编译原理

1、              相识编译器的基本见地和基本布局

2、              相识词法阐发器的作用，掌握暗号的形貌和识别要领，掌握识别有限自动机的基本定义和从正轨式创立识别器的要领

3、              相识语法阐发器的作用，掌握上下文有关言语和文法的相关见地和性子，掌握种种语法阐发技艺，如自上而下阐发，自下而上阐发，以和LR阐发器。

4、              掌握上下文有关文法制导下的言语翻译，

5、              相识范例体制的基本见地，相识大约范例查抄器和范例表达式的等价

6、              相识步伐的运转时存储空间和结构操持

7、              相识中心代码的表现，相识步伐方案言语的布局怎样翻译成中心境势

8、              相识代码天生中涉和的基本标题，包括存储操持、指令选择、寄存器分派和盘算序次选择等基本标题

9、              掌握代码优化的重要种类和代码改造变卦。

三、重要参考书目

1、《数据布局》严蔚敏，清华大学出版社；2002

2、《编译原理和技艺》，陈意云，中国迷信技艺大学出版社；2003

3、William Stallings。。 Operating Systems: Internals and Design Principles。。 Fourth Edition, Prentice Hall。。 2001

4、《盘算机操纵体系》，汤子瀛，西安电子科技大学出版社。2002

方式单位：中国迷信院研讨生院

方式日期：2006年6月6日

中科院乌鲁木齐天文站分数线 中科院乌鲁木齐天文站招生简章

• 上一篇：中科院乌鲁木齐天文站高等数学（乙）考试大纲
• 下一篇：中科院乌鲁木齐天文站《量子力学》考试大纲