2014年哈工大计算机硕士研究生复试考试大纲

考试科目名称：计算机科学与技术     考试科目代码：[    ]

复试科目除C 语言外均为选择题，每题2分。

（1）集合论与图论，占30分。

   （2）计算机体系结构，占30分。

（3）编译原理，占30分

（4）数据库系统，占30分

       （5）C语言程序设计，占50分

       （6）软件工程，占30分

注1：生物信息技术专业学生不考计算机体系结构、编译原理，考生物信息学引论（30分）、生物统计与基因组信息学（30分）。

集合论与图论部分（30分）

一、 考试要求

    1. 要求考生系统地掌握集合论、图论的基本概念、基本原理等基本知识，学会运用基本知识进行推理并应用到计算机科学领域解决实际问题。

二、考试内容

1） 集合及其运算

集合、子集、集合的相等关系、幂集；集合并、交、差、对称差、补集、

迪卡尔乘积运算，各运算的性质及相互联系；有穷集合的基数、基本计数法则、容斥原理及应用。

2） 映射

基本定义、鸽巢原理、映射的一般性质、映射的合成、逆映射、置换、二元运算、映射的应用。

3）关系

教学内容 二（n）元关系、几个特殊二元关系、二元关系的表示、关系的合

成运算、传递闭包、等价关系与集合的划分、偏序关系。

4）无穷集合的基数

可数集及其性质、存在不可数集—对角线法，基数及其比较、连续统。

5） 图的基本概念  

图、路、圈、连通图、偶图、补图、欧拉图、哈密顿图、图的邻接矩阵、最短路径问题。

6） 树和割集

树及其性质、生成树、割点和桥及其特征性质，最小生成树问题。

7）平面图和图的着色

平面图及其欧拉公式、库拉托斯基定理、图的着色、

8）有向图

有向图、可达（互达）、有向图连通（强、单向、弱连通）、有根树、有序树、二元树。

三、 试卷结构

选择题（四选一）

四、参考书目

    1．王义和编著，离散数学引论（第3版），哈工大出版社，2007。

    2．耿素云、屈婉玲、张立昂著，离散数学（第1版），高教出版社，2008.3。

计算机体系结构部分（30分）

一、 考试要求

要求考生系统地掌握计算机体系结构的基本概念、基本原理和基本方法等方面的基础知识，并能够运用基础知识解决计算机体系结构设计中的基本问题。

二、考试内容

1）计算机系统结构的基本概念

a）计算机系统结构的基本概念，计算机系统层次结构，计算机系统的设计技术，软硬件取舍原则；

b）软件可移植性的途径、方法、适用场合、存在的问题和对策；

c）计算机系统性能评价的基本方法；

d）并行性的概念，系统结构中开发并行性的途径和类型，计算机系统的分类。

2）指令系统设计

a）指令系统的分类、寻址技术、功能设计、格式设计；

b）指令系统的发展和改进

c）操作数的类型及大小

3）流水线技术

a）流水线的分类、性能指标和性能分析； 

b）非线性流水线的调度；

c）流水线中的相关和冲突问题及其解决方法； 

4）指令级并行及其开发（硬件方法）

a）指令级并行的概念，相关与指令级并行，指令的动态调度；

b）动态分支预测技术；

c）多指令流出技术。

5）存储系统

a）存储层次；

b）降低Cache不命中率的方法，减少Cache不命中开销的方法，减少命中时间的方法

6）输入输出系统

a）I/O系统的性能、可信性、廉价磁盘冗余阵列；

b）总线的设计、总线标准、与CPU的连接；

c）通道的作用和功能、工作过程、种类、流量分析。

三、试卷结构

a) 题型结构

选择题(30分)

四、参考书目

1．计算机系统结构教程，作者张晨曦,清华大学出版社

编译原理部分（30分）

一、考试要求

1. 要求考生能够理解和掌握编译过程各个阶段的工作原理，理解标准编译器各个组成部分的任务，熟悉编译过程各阶段所要解决的问题及其采用的方法和技术。

2. 能够应用一些标准的技术解决编译器构造过程中所产生的相关问题，理解编译器在生成代码时如何充分利用特定处理器的特征。

注：参考书主要以参考书目1为标准。

二、考试内容

1）编译的总体结构

a:编译的总体结构

b: 编译的各阶段及其任务

  2）语言与文法

a: 文法和语言的定义及文法的表示

b: 文法和语言的分类

c: 推导与归约，短语、直接短语和句柄，分析树及文法的二义性

3）词法分析

a: 词法分析器的功能

b: 词法分析器的设计与实现

c: 正则文法、正则表达式、确定的有穷自动机与不确定的有穷自动机及其它们之间的转换

4）语法分析

a: 语法分析器的功能

b: 自顶向下分析法存在的问题及解决办法，递归下降法与LL(1)分析法

c: 自底向上分析法的基本原理，算符优先分析法和LR分析法

5)语法制导翻译与中间代码生成

a: 语法制导定义、S属性定义和L属性定义

b: 自顶向下的语法制导翻译与自底向上的语法制导翻译

c:  几种典型语句的翻译：说明语句、表达式与赋值语句、分支与循环语句、过程说明与调用语句

6)类型检查与运行时环境

a:类型表达式及其等价

b:静态存储分配与动态存储分配、参数传递

c: 符号表管理

7)代码生成与优化

a:代码生成器设计中的问题

b:基本块与流图

c: 常用的代码优化方法、

三、试卷结构

1） 题型结构

选择题。

2） 注意事项

无。

四、参考书目

1．蒋宗礼，姜守旭，编译原理，高等教育出版社，2010.02.

2．Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman著，李建中，姜守旭译，编译原理，机械工业出版社，2005.01.

数据库系统部分（30分）

一、 考试要求

要求考生系统地掌握数据库系统的基本概念、关系模型与关系数据库，数据库语言SQL，数据库设计，数据库管理与维护等方面的知识。

二、考试内容

1）引论

a:数据库系统的构成

b:三级模式与两层映像；数据物理独立性与数据逻辑独立性

c:数据、模式与数据模型

d:数据库管理系统的功能；数据库语言DDL、DML、DCL.

  2)关系模型与关系运算

a: 关系相关的概念

b: 关系模型相关的概念

b: 关系代数及其应用

c: 元组演算及其应用

3)数据库语言SQL

a: 基本查询

b: 多表连接查询

c: 嵌套查询(IN, qSome/qall, Exists)

d: 聚集函数与分组查询/分组过滤

e: 空值相关的查询

f: 视图的定义与使用

4)嵌入式SQL语言与数据库应用程序设计

a: 游标的定义与使用

b: 事务的概念及其ACID特性

c: 并发控制

5)数据库设计

a: Crow’s foot形式的E-R图及其应用

b: IDEF1X形式的E-R图及其应用

c: 数据依赖，包括函数依赖、完全函数依赖、传递依赖；候选键；外键；函数依赖的公理系统；多值依赖；

d: 函数依赖集的闭包与属性闭包

e: 最小覆盖

f: 关系的1NF, 2NF, 3NF, BCNF

g: 模式分解，无损联结分解与保持依赖分解

h: 数据库设计过程

6)数据库管理与维护

a:数据库的文件组织方法

b:数据库重组

c: 索引，稠密索引与稀疏索引，主索引

d: 数据库查询优化(语法优化和执行优化)的基本思想

e: 数据库完整性，完整性约束规则，触发器

f: 数据库安全性，安全性访问规则，自主安全控制机制与强制安全控制机制

g:数据库故障及其恢复方法，日志及检查点

三、试卷结构

a) 题型结构

a: 选择题(30分)

四、参考书目

1．杨冬青等译，数据库系统概念(本科教学版)，机械工业出版社，2008 [ISBN:978-7-111-23422-7]

2．李建中等，数据库系统原理（第二版），电子工业出版社

C语言程序设计（50分）

一、 考试要求

要求考生全面系统地掌握C语言程序设计的基本方法，熟悉C语言的集成开发环境（Visual C++6.0或Code::Blocks+gcc+gdb），熟悉计算机求解问题的常用算法，能够根据实际问题选择合适的数据结构和算法，熟练运用结构化程序设计方法解决实际问题，熟练掌握程序分析、设计、编码和调试的基本技能。

二、考试内容

1)基本控制结构

a: 数据的键盘输入和屏幕输出 

b: 顺序、分支和循环三种基本控制结构

c: 循环的三种控制方法（计数控制的循环，条件控制的循环，标记控制的循环），嵌套循环

d: 流程的转移控制

2)函数 

a: 函数的定义 

b: 函数的调用

c: 向函数传递变量的值

d: 从函数返回一个值

e: 函数的递归调用，递归函数

3)数组

a:一维数组和二维数组的定义、初始化和引用

b: 向函数传递一维数组和二维数组

c: 向函数传递字符串

d: 常用的字符串处理操作（输入、输出、复制、连接、比较、计算长度、插入字符、删除字符等）

e: 常用的排序算法（选择排序、交换排序、冒泡排序、插入排序）和查找算法（顺序查找、折半查找）

4)指针 

a:指针变量的定义和初始化

b: 直接寻址和间接寻址

c: 指针变量做函数参数

d: 函数指针

e: 指针数组

5) 结构体

a:结构体变量、结构体数组和结构体指针的定义和初始化

b: 结构体变量、结构体数组或结构体指针做函数参数向函数传递结构体

c: 结构体指针变量做函数参数

三、试卷题型结构

a:编程题（40分）

b:附加改错题（10分）

四、参考书目

1．苏小红，王宇颖，孙志岗等，C语言程序设计（第2版），高等教育出版社，2013.07

2．苏小红，车万翔，王甜甜，C语言程序设计学习指导（第2版），高等教育出版社，2013.08

3. 苏小红，孙志岗，陈惠鹏，C语言大学实用教程（第3版），电子工业出版社，2012.06

4. 苏小红，孙志岗等，C语言大学实用教程学习指导（第3版），电子工业出版社，2012.07

软件工程（30分）

一、 考试要求

要求考生全面系统地掌握软件工程的基本概念、软件工程的常用过程模型、软件的生命周期、面向对象的软件分析、设计、开发和测试方法，并能灵活运用；能够利用软件工程的基本知识，为应用需求构造有效的需求方案、设计方案、测试方案；能够初步分析软件方案的合理性。

二、考试内容

1）软件工程的基本概念

a:软件工程概念、组成部分

b: 软件的生命周期、各阶段的作用、各阶段输入输出之间的关系

  2)软件生命周期模型与软件项目管理

a: 瀑布模型、增量模型、演化模型、敏捷模型的特征、过程和应用场景

b: 针对特定软件产品/项目的特征，选择恰当的过程模型

d: 软件风险管理的基本概念与方法

3)软件需求工程

a: 需求工程的阶段划分及各自之间的关系

b: 需求的分类、需求好坏的评判标准

c: 面向对象的需求分析方法

d: 需求规格说明的基本构成

4)软件设计

a: 软件设计的阶段划分及各自之间的关系

b: 软件体系结构的基本概念、常见的软件体系结构样式

c: 面向对象设计的基本方法

d: 用户界面设计、数据设计、算法设计的基本方法

5)软件测试

a: 软件测试的阶段划分、软件测试的类型

b: 软件测试的基本方法（黑盒测试、白盒测试等）及其应用

c: 测试用例的设计

6) 软件工程的其他阶段

a: 软件实施的基本方法与过程

b:软件维护的基本类型、基本过程

c:软件演化的基本思想

三、试卷结构

a) 题型结构

选择题(30分)

b) 注意事项

四、参考书目

1．刘强，孙家广。《软件工程-理论、方法与实践》，高等教育出版社，2006年5月

2．Rogers S. Pressman. Software Engineering: A Practitioner’s Approach (Seventh Edition). (郑人杰等译，《软件工程：实践者的研究方法》，机械工业出版社，2011年8月)

生物信息学引论（30分）

一、 考试要求

1. 要求考生系统地掌握生物信息学的基本概念、处理生物学数据的基本方法，掌握最新的生物信息研究所涉及的数据库、数据的基本结构等方面的知识。

2. 能够用基础理论知识对数据分析结果进行合理的解释。

二、考试内容

1）引论

a:生物信息学概念、及研究的目的与任务

b:生物大分子所包含的数据类型

c:生物信息学数据库类型及数据结构

  2)序列比较

a: 序列比较的概念与目的

b: 动态规划算法与应用

b: SP模型及其应用

c: DNA片段的组装

3)基因组信息分析

a: 真、原核基因组信息特点

b: 核苷酸关联分析

c: 基因识别

4)基因表达数据分析

a: 基因表达数据采集方法

b: 基因表达差异的显著性分析的统计学指标

c: 基因表达数据的数据库资源

5)分子进化分析

a: 分子进化分析的概念及基础理论；

b: 基于生物大分子的系统发育分析模型，包括蛋白质分析模型和核苷酸分析模型；

c: 基于生物大分子的系统发育树构建方法，包括距离法、最大似然法、最大简约法；

d: 系统发育树的可靠性检验。

三、 试卷结构

选择题(30分)

四、参考书目

1．许忠能，生物信息学，清华大学出版社，2008 [ISBN:9787302177937]

2．孙啸等，生物信息学基础，清华大学出版社，【ISBN:9787302102700】

生物统计与基因组信息学部分（30分）

一、 考试要求

1. 要求考生系统地掌握生物统计方法的基本原理、基本概念，以及具体统计分析方法等方面的知识。

2. 掌握基因组基本结构与信息，基因组信息分析的基本原理和方法，处理高通量基因组信息的方法。

二、考试内容

1）基因组信息学中生物学基础

a) DNA的结构、分子生物学中心法则

b) 基因组结构与基因表达调控

2）人类基因组及基因组数据库

a) 人类基因组计划及测序策略

b) 人类基因组特征

c) 基因组数据库NCBI、Ensembl与UCSC人类基因组浏览器

3）基因组信息分析

a) 原核生物基因组特点

b) 真核生物基因组特点

c) 基因组序列分析

d) 基因识别方法

e) 非编码区域分析与调控元件识别

4）基因芯片数据分析

a) 基因芯片分类与数据表示

b) 基因芯片数据预处理

c) 基因表达差异的显著性分析

d) 基因表达谱聚类分析

e) 基因表达数据的分类分析

5）概率与概率分布

a) 概率基础知识

b) 几种常见的理论分布

c) 统计量及统计量的分布：包括均值，方差的分布、t分布、分布、F分布

6）统计推断

a) 假设检验的原理与方法

b) 几种常用假设检验方法

c) 参数的区间估计与点估计

7）非参数检验

a) Wilcoxon秩和检验及Smirnov检验；

b) 符号检验及Wilcoxon符号秩检验

8）方差分析

a) 方差分析的基本原理

b) 单因素方差分析

c) 二因素方差分析

三、试卷结构

选择题(30分)

四、参考书目

1．杜荣骞，生物统计学（第3版），高等教育出版社，2009 [ISBN: 9787040257458]

2．孙啸、陆祖宏、谢建明，《生物信息学基础》，清华大学出版社。