哈工大软件学院硕士生招生复试大纲Word格式.docx

哈工大软件学院硕士生招生复试大纲Word格式.docx

《哈工大软件学院硕士生招生复试大纲Word格式.docx》由会员分享，可在线阅读，更多相关《哈工大软件学院硕士生招生复试大纲Word格式.docx（12页珍藏版）》请在冰点文库上搜索。

b）集合的运算及其性质

c）计数法则

2）映射

a）映射、单射、满射、双射

b）映射的合成运算、逆映射

c）映射的应用：

二元运算、置换、特征函数

3）二元关系

a）二元关系及特殊的二元关系

b）二元关系的合成运算、传递闭包

c）等价关系、等价类、集合的划分

d）偏序关系及有关概念

4）无穷集合

a）可数集及其性质

b）连续统、对角线法

5）无向图

a）无向图的相关概念

b）偶图、欧拉图、哈密顿图

c）无向图的邻接矩阵

6）树、割点和桥

a）树及其性质

b）割点和桥及其性质

c）生成树

7）平面图、图的顶点着色

a）平面图和欧拉公式

b）Grinberg定理

c）图的顶点着色、色数、五色定理

8）有向图

a）有向图及相关概念

b）强连通、单向连通、弱连通

c）可达、互达性，可达矩阵、邻接矩阵

d）有根树、有序树及相关概念

e）比赛图

三、试卷结构

题型

a．计算题（0-25）

b．选择题（0-25）

c．简单的推理（0-10）

d．判断题（0-10）

四、参考书

1．王义和，离散数学引论，哈尔滨工业大学出版社，2002年，第1，2，3，4，6，7，9，10章

附加二

数据结构部分（25分）

1.要求考生全面系统地掌握数据结构与算法的基本概念、数据的逻辑结构和存储结构及操作算法，并能灵活运用；

能够利用数据结构和算法的基本知识，为应用问题设计有效的数据结构和算法；

能够分析算法的复杂性。

2.能够用一种程序设计语言描述数据结构和算法。

注：

参考书主要以参考书目1为标准，带*号部分不在考试范围之内。

二、考试内容

1）数据结构与算法的概念及相互关系

a:

数据结构及其相关的基本概念

b:

算法及其复杂性分析

2）线性表

各种线性结构及其操作算法

线性表的应用

3）树与二元树

二元树的定义、性质、表示、遍历算法

树的表示、操作算法

c:

森林与二元树关系

d:

树与二元树的应用

4）图及其相关算法

图的相关概念

图的存储结构与搜索算法

图的经典应用算法

5）查找与分类

各种查找与分类算法的基本思想

典型算法的描述及复杂性分析

查找与分类算法的应用

6）外部分类与文件

外部分类及其基本方法

文件的组织方式、特点及应用

a）题型结构

填空题（0—15分）

选择题（0—15分）

判断题（0—10分）

简答题（0—20分）

e:

算法设计题（0—30分）

b）注意事项

算法设计题，必须包含算法的基本思想、存储结构设计和算法的描述。

四、参考书目

1．廖明宏，郭福顺等，数据结构与算法（第4版），高等教育出版社，2007.6

2．严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，1997.4

附件三

操作系统（25分）

1、要求考生全面系统地掌握操作系统原理中所涉及的基本原理、概念、方法、结构和技术，了解操作系统的特点、功能和分类，加强理解系统实现的过程和与其它课程知识的联系。

掌握操作系统如何实现对处理机、内存、文件、设备和作业的管理。

2、特别注重操作系统中基本的应知应会知识的掌握。

1、操作系统的目标、作用和特性

2、进程管理

1）进程的基本概念

2）进程的控制

3）进程的同步与通信

4）进程的调度与死锁

3、存贮器管理

1）存贮管理的概念、方法和算法

2）虚拟存贮器的概念

4、设备管理

1）I/O控制方式2）缓冲管理

5、文件管理

1）文件和文件系统

2）目录管理

6、操作系统接口

系统调用的概念与实现

三、试题类型

1、判断题（0—5分）

2、选择题（0—15分）

3、简答题（0—5分）

四、参考书目

1、汤子瀛等编著，计算机操作系统，西安电子科技大学，2004年

2、[美]williamSdallings编著，魏迎梅等译，操作系统—内核与设计原理，电子工业，2005年

附件四

编译原理（25分）

一、考试要求

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

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

参考书主要以参考书目1为标准，5.7-5.10，6.5-6.7，7.7-7.9，9.7-9.12，10.4-10.13和第12章不在考试范围之内。

1）编译的总体结构

编译的总体结构

编译的各阶段及其任务

2）语言与文法

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

文法和语言的分类

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

3）词法分析

词法分析器的功能

词法分析器的设计与实现

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

4）语法分析

语法分析器的功能

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

（1）分析法

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

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

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

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

几种典型语句的翻译：

说明语句、表达式与赋值语句、分支与循环语句、过程说明与调用语句

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

类型表达式及其等价

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

符号表管理

7）代码生成与优化

代码生成器设计中的问题

基本块与流图

常用的代码优化方法

四、试卷结构

填空题（0—10分）

选择题（0—10分）

简答题（0—10分）

构造题（0—10分）

构造题既可能是分析或者翻译方法的构造，也可能是文法与有穷自动机等的构造。

1．AlfredV.Aho,RaviSethi,JeffreyD.Ullman著，李建中，姜守旭译，编译原理，机械工业出版社，2005.1

2．陈火旺，刘春林等，程序设计语言编译原理（第三版），国防工业出版社，2000.1

附件五

计算机网络（25分）

二、考试要求：

要求学生了解并掌握计算机网络的基本概念、基本原理、典型的网络技术以及典型网络协议；

掌握计算机网络体系结构和参考模型、计算机网络基本原理以及计算机网络的基本组网技术；

了解网络应用编程技术。

二、考试内容：

1）计算机网络基础

计算机网络及相关基本概念

协议概念

网络体系结构与网络参考模型（OSI和TCP/IP）

网络组成与分类

2）网络应用

典型的网络应用及应用层协议

Socket编程基础

3）传输层

典型滑动窗口协议-GBN、SR协议

典型传输层协议：

UDP，TCP

拥塞控制基本原理与方法

TCP协议拥塞控制方法

4）网络层

虚电路网络与数据报网络

典型路由算法：

链路状态算法与距离矢量算法

IP协议与IP地址、ICMP协议

Internet路由及典型路由协议

5）数据链路层与局域网

差错编码

多路访问技术与协议

局域网-以太网、IEEE802.11

局域网编址与ARP协议

网络互连设备：

集线器、桥接器（网桥）和交换机

f:

PPP协议

6）物理层

典型数据传输编码

网络传输介质

典型网络接口规范

五、试卷结构：

填空题（10分）

判断题（5分）

选择题（10分）

1．JamesF.Kurose&

KeithW.Ross著，计算机网络—自顶向下方法与Internet特色-第三版（影印版），高等教育出版社,2005.1

附件六

数据库系统（25分）

三、考试要求

要求考生全面系统地掌握数据库系统的基本概念、关系模型与关系运算，能够熟练编写正确的SQL语句，领会数据库设计的方法与过程，并能进行数据库设计的正确性分析，具备较强的数据库设计与数据库应用编程的能力。

1）数据库系统基本概念

数据库与数据库管理系统的基本概念

数据库管理系统的标准结构：

三级模式两层映像。

2）关系模型与关系运算

关系与关系模型

关系代数运算

关系元组演算

3）SQL语言

SQL简单查询、多表连接查询、嵌套查询、模糊查询

SQL分组统计查询

视图

4）数据库设计

数据库设计的基本概念

实体联系图（E-R图）及数据库设计基本知识

函数依赖相关的基本概念

d.关系范式：

关系的第1、第2、第3范式及Boyce-Codd范式

5）数据库管理与维护

数据库完整性、安全性、索引与主索引等概念

六、试卷结构

填空题（0-25分）

选择题（0-25分）

判断题（0-25分）

简答题（0-25分）

1．PatrickO’Neil，周傲英译，数据库原理、编程与性能,机械工业出版社,2002.1

2．萨师煊,王珊,《数据库系统概论》第三版,高等教育出版社,2000.2