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

1、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

2、） 有向图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. 能够用一种程

3、序设计语言描述数据结构和算法。注：参考书主要以参考书目1为标准，带*号部分不在考试范围之内。二、考试内容1）数据结构与算法的概念及相互关系a:数据结构及其相关的基本概念b: 算法及其复杂性分析 2）线性表 各种线性结构及其操作算法 线性表的应用3）树与二元树 二元树的定义、性质、表示、遍历算法 树的表示、操作算法c: 森林与二元树关系d: 树与二元树的应用4）图及其相关算法 图的相关概念 图的存储结构与搜索算法 图的经典应用算法5）查找与分类 各种查找与分类算法的基本思想 典型算法的描述及复杂性分析 查找与分类算法的应用6）外部分类与文件外部分类及其基本方法文件的组织方式、特点及应用a） 题型

4、结构填空题（015分）选择题（015分）判断题（010分）简答题（020分）e:算法设计题（030分）b） 注意事项算法设计题，必须包含算法的基本思想、存储结构设计和算法的描述。四、参考书目1廖明宏，郭福顺等，数据结构与算法（第4版），高等教育出版社，2007.62严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，1997.4附件三操作系统 （25分）1、 要求考生全面系统地掌握操作系统原理中所涉及的基本原理、概念、方法、结构和技术，了解操作系统的特点、功能和分类，加强理解系统实现的过程和与其它课程知识的联系。掌握操作系统如何实现对处理机、内存、文件、设备和作业的管理。2、 特别注重操作系

5、统中基本的应知应会知识的掌握。1、 操作系统的目标、作用和特性2、 进程管理1） 进程的基本概念2） 进程的控制3） 进程的同步与通信4） 进程的调度与死锁3、 存贮器管理1） 存贮管理的概念、方法和算法2） 虚拟存贮器的概念4、 设备管理1）I/O控制方式 2）缓冲管理5、 文件管理1） 文件和文件系统2） 目录管理6、 操作系统接口系统调用的概念与实现三、 试题类型1、 判断题（05分）2、 选择题（015分）3、 简答题（05分）四、 参考书目1、 汤子瀛等编著，计算机操作系统，西安电子科技大学，2004年2、 美william Sdallings编著，魏迎梅等译，操作系统内核与设计原理

6、，电子工业，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）语言与文法 文法和语言的定义及文法的表示 文法和语言的分类 推导与归

7、约，短语、直接短语和句柄，分析树及文法的二义性3）词法分析 词法分析器的功能 词法分析器的设计与实现 正则文法、正则表达式、确定的有穷自动机与不确定的有穷自动机及其它们之间的转换4）语法分析 语法分析器的功能 自顶向下分析法存在的问题及解决办法，递归下降法与LL（1）分析法 自底向上分析法的基本原理，算符优先分析法和LR分析法5）语法制导翻译与中间代码生成 语法制导定义、S属性定义和L属性定义 自顶向下的语法制导翻译与自底向上的语法制导翻译 几种典型语句的翻译：说明语句、表达式与赋值语句、分支与循环语句、过程说明与调用语句6）类型检查与运行时环境类型表达式及其等价静态存储分配与动态存储分配、参

8、数传递 符号表管理7）代码生成与优化代码生成器设计中的问题基本块与流图 常用的代码优化方法四、 试卷结构填空题（010分）选择题（010分）简答题（010分）构造题（010分）构造题既可能是分析或者翻译方法的构造，也可能是文法与有穷自动机等的构造。1Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman著，李建中，姜守旭译，编译原理，机械工业出版社，2005.12陈火旺，刘春林等，程序设计语言编译原理（第三版），国防工业出版社，2000.1附件五计算机网络 （25分） 二、 考试要求：要求学生了解并掌握计算机网络的基本概念、基本原理、典型的网络技术以及典型网络

9、协议；掌握计算机网络体系结构和参考模型、计算机网络基本原理以及计算机网络的基本组网技术；了解网络应用编程技术。二、考试内容：1） 计算机网络基础计算机网络及相关基本概念协议概念网络体系结构与网络参考模型（OSI和TCP/IP）网络组成与分类2） 网络应用典型的网络应用及应用层协议Socket编程基础3） 传输层典型滑动窗口协议-GBN、SR协议典型传输层协议：UDP，TCP拥塞控制基本原理与方法TCP协议拥塞控制方法4） 网络层虚电路网络与数据报网络典型路由算法：链路状态算法与距离矢量算法IP协议与IP地址、ICMP协议Internet路由及典型路由协议5） 数据链路层与局域网差错编码多路访问

10、技术与协议局域网-以太网、IEEE802.11局域网编址与ARP协议网络互连设备：集线器、桥接器（网桥）和交换机f:PPP协议6） 物理层典型数据传输编码网络传输介质典型网络接口规范五、 试卷结构：填空题（10分）判断题（5分）选择题（10分）1James F. Kurose & Keith W. Ross著，计算机网络自顶向下方法与Internet特色 - 第三版（影印版），高等教育出版社,2005.1附件六数据库系统（25分） 三、 考试要求要求考生全面系统地掌握数据库系统的基本概念、关系模型与关系运算，能够熟练编写正确的SQL语句，领会数据库设计的方法与过程，并能进行数据库设计的正确性分

11、析，具备较强的数据库设计与数据库应用编程的能力。1）数据库系统基本概念 数据库与数据库管理系统的基本概念 数据库管理系统的标准结构：三级模式两层映像。2） 关系模型与关系运算 关系与关系模型 关系代数运算 关系元组演算3） SQL语言 SQL简单查询、多表连接查询、嵌套查询、模糊查询 SQL分组统计查询 视图4） 数据库设计 数据库设计的基本概念 实体联系图（E-R图）及数据库设计基本知识 函数依赖相关的基本概念d. 关系范式：关系的第1、第2、第3范式及Boyce-Codd范式5） 数据库管理与维护 数据库完整性、安全性、索引与主索引等概念六、 试卷结构 填空题（ 0-25分 ） 选择题（ 0-25分 ） 判断题（ 0-25分 ） 简答题（ 0-25分 ）1Patrick ONeil，周傲英译，数据库原理、编程与性能, 机械工业出版社, 2002.12萨师煊, 王珊, 数据库系统概论第三版, 高等教育出版社, 2000.2