研究生操作系统与计算机网络.doc

1、212 博士研究生操作系统和计算机网络 入学测试大纲 第一部分 测试说明 一、测试性质 操作系统和计算机网络入学测试是华中科技大学计算机科学和技术相关专业所设置的一个测试科 目。它的评价标准是高等学校计算机学科优秀硕士毕业生能达到的及格或及格以上水平，以保证录取的博 士生具有一定的计算机专业理论及软件开发能力，以利于计算机学科相关专业各导师择优选拔。 测试对象为参加博士生入学测试的硕士毕业生，以及具有同等学历的在职人员。 二、测试的学科范围 操作系统的外特性，包括：操作系统的定义、功能、特性、类型以及现代操作系统的用户界面 和操作系统的逻辑结构。 操作系统资源管理的策略、功能和实现技术，包括：

2、处理机管理、存储管理、设备管理和文件 系统。了解操作系统的重要论题：死锁概念。 并发处理的概念及实现技术，包括：进程概念，进程状态及变迁、进程控制、进程同步互斥的基 本原理和实现技术，了解进程通信的概念。 实例操作系统，如 UNIX 系统和 Windows 系统的类型、结构、用户界面，进程管理、设备管理和 文件管理的有关问题。 计算机网络的基本概念、局域网、广域网、网络互连、网络使用及安全等。 三、评价目标 “现代操作系统”科目测试是要考核学生对操作系统、计算机网络基本概念、基本原理及实现技 术的掌握程度，考核学生融会贯通及综合运用所学知识的能力。 本科目的测试要求学生能正确理解操作系统、计算

3、机网络的基本概念、基本原理和实现技术， 能灵活地运用所学知识分析问题、解决问题。 四、测试形式和试卷结构 1. 答卷方式：闭卷，笔试。 2. 答题时间：180 分钟 3. 考查内容及考查比例 操作系统测试内容占 70 ，计算机网络内容占 30%。 考查内容分为较易、较难、难三个等级，每份试卷中不同难度试题的分配比例是 3 ：4 ：3 。 基本概念和基础知识约占 30 ，需要灵活地运用所学知识来解决问题的试题约占 40，需要综合 几个知识点来解决问题的试题约占 30。 题目的形式可以有多样，如：名词解释、填空题、选择题、判断改错题、问答题、计算题、图解 题、分析论述题、编程题。题型不是关键，最关

4、键的是对基本概念、基本原理和实现技术的真正理解， 对知识点的掌握程度。因为，针对任一个知识点都可以产生多个不同类型的试题。 五、参考书目 1 操作系统原理第三版庞丽萍编著 华中科技大学出版社。 2 计算机网络第三版 坦尼伯姆 电子工业出版社。 3 计算机网络第二版、第三版 谢希仁 电子工业出版社。 第二部分 考查要点 一、操作系统 1. 操作系统基本概念 (1) 计算机体系结构和操作系统的关系，操作系统的定义、功能、特性，操作系统的类型； (2) 多道程序设计技术和分时技术； (3) 操作系统虚拟机概念，操作系统的逻辑结构； (4) 基本硬件结构：处理机的状态和特权指令； (5) 中断和俘获。

5、 2. 操作系统的用户界面 了解运行一个用户程序的过程，理解用户界面的概念、掌握操作系统的用户界面的类型及实现技 术。 3. 进程及进程管理 (1) 进程的概念：进程的定义、进程的描述、进程的状态及变迁； (2) 进程控制：进程控制的概念、常用的进程控制原语及实现。 (3) 进程的互斥和同步：临界资源、临界区、进程互斥定义；进程同步的例、进程同步的定义； 信号灯及 P、V 操作的概念，用信号灯的 P、V 操作实现进程互斥和同步。 4. 操作系统资源管理 (1) 操作系统资源管理概述 资源分配机制、资源分配策略。 (2) 死锁 死锁的概念、产生死锁的原因、必要条件、死锁的预防、死锁的避免。 (3

6、) 处理机管理 处理机的多及调度、作业调度、进程调度算法、调度方式。 (4) 主存管理 存储管理功能；分区分配机构、方法及放置策略；分页存贮管理的基本概念、页地址变换；请求 分页概念和实现方法；段式系统的二维地址结构、段地址变换；段页式存贮管理概念和实现方法。 (5) 设备管理 设备管理功能、设备独立性概念；缓冲技术的概念和常用的缓冲技术；设备分配技术；输入输出 控制的基本功能。 (6) 文件系统 文件和文件系统的定义；文件的逻辑结构； 文件的物理结构(连续结构、串联结构、索引结构) ； 文件目录的定义、文件目录项内容、文件目录结构、文件路径名和当前目录； 常用的文件操作命令； 文件共享的概念

7、和方法；文件安全的概念和方法。 5. 实例操作系统(UNIX 操作系统和 Windows 操作系统) 实例操作系统类型、特点和结构；实例操作系统用户界面；UNIX 系统的进程结构、进程状态和 状态的变迁、进程调度功能和算法；UNIX 缓冲管理技术；理解 UNIX 文件系统中主要数据结构及功 能实现、文件的索引结构及文件目录结构。 二、计算机网络 1 计算机网络的基本概念 a 计算机网络的定义 b 互连网络 c 协议和体系结构 2 物理层和数据链路层 a 物理层的基本概念 b 模拟传输和数字传输 c 数据链路层的基本概念 d 停止等待协议 e 连续 ARQ 协议 f 面向比特的数据链路控制规程

8、HDLC g Internet 中的数据链路层 3 计算机局域网 a 局域网的体系结构 b IEEE802.3 标准：CSMA/CD c IEEE802.5 标准：令牌环 d 高速以太网 e 局域网络操作系统 4 广域网和网络互连 a 广域网的概念 b 广域网中的路由选择机制 c 路由选择的一般原理 d 互连网的概念 e Internet 的网际协议 IP f Internet 的路由选择协议 5 运输层协议概述 a TCP/IP 体系中的运输层 b 用户数据报协议：UDP c 传输控制协议：TCP 6 网络使用及安全 a 网络使用的概念 b 域名系统 DNS c 文件传输协议 FTP d 电

9、子邮件 EMAIL e 万维网 WWW f 远程登录 TELNET g. 计算机网络安全的概念 252 博士研究生计算机系统结构测试大纲 第一部分 测试说明 一、测试性质 本测试大纲用于计算机系统结构专业博士研究生“现代计算机系统结构”课程入学测试。 它的评价标准是高等学校本学科优秀毕业生能达到的及格或及格以上水平，以保证被录取者具有 基本的计算机专业理论基础，以利于计算机系统结构专业各导师择优选拔。 二、评价目标 在考察基本知识和基本理论的基础上，还要考察运用理论知识解决实际问题的能力。测试有一定 的深度，还要求考生有较宽的知识面。 三、测试形式和试卷结构 1答卷方式：闭卷，笔试。 2答题时

10、间：180 分钟。 3测试类型： 选择题、问答题、计算题、分析题等 四、参考书 1J. L. Hennessy, D.A. Patterson, Computer Architecture: A Quantitative Approach, Third Edition. 即：计算机体系结构量化研究方法第三版（英文版） ，机械工业出版社, 2003 2郑纬民，汤志忠，计算机系统结构（第二版） ，清华大学出版社 第二部分 测试要点 1. 计算机系统设计基础 1.1 计算机设计所面临的挑战 1.2 技术趋势 1.3 价格和成本对设计的影响 1.4 性能描述及其测量方法 1.5 计算机设计的量化理论

11、2. 指令集的设计原理 2.1 指令集结构的分类 2.2 寻址方式 2.3 信号处理的地址模式 2.4 操作类型和长度 2.5 控制流的指令 2.6 指令集的编码 3. 指令级并行及其使用 3.1 指令级并行概念和挑战 3.2 动态调度中避免数据冒险 3.3 使用硬件动态预测减小分支代价 3.4 使用多发射提高指令级并行 3.5 基于硬件的推断执行 3.6 指令级并行的限制 4. 使用软件方法实现指令级并行 4.1 实现指令级并行的编译方法 4.2 静态分支预测 4.3 静态多发射 4.4 实现指令级并行的高级编译方法 4.5 在编译时提高指令级并行的硬件设计 5. 层次型内存结构设计 5.1

12、 cache 概念 5.2cache 的性能 5.3 减少 cache 失效代价 5.4 减少失效率 5.5 减少命中时间 5.6 主内存结构 5.7 内存技术 5.8 虚拟内存 6. 多处理器和线程级并行 6.1 使用程序的特点 6.2 对称式共享内存多处理器结构 6.3 分布式共享内存多处理器结构 6.4 同步问题 6.5 内存一致性 7. 存储系统 7.1 存储设备类型 7.2 总线 7.3 可靠性、可用性和依赖性 7.4 磁盘阵列 7.5I/O 性能测量 7.6 排队论基础 7.7 存储性能和可用性的指标 8. 互连网络和集群 8.1 简单网络 8.2 互连网络媒介 8.3 网络拓朴

13、8.4 互连网络 8.5 集群技术 253 博士研究生现代操作系统入学测试大纲 第一部分 测试说明 一测试性质 现代操作系统入学测试是华中科技大学计算机科学和技术相关专业所设置的一个测试科目。 它的评价标准是高等学校计算机学科优秀硕士毕业生能达到的及格或及格以上水平，以保证录取的博 士生具有一定的计算机专业理论及软件开发能力，以利于计算机学科相关专业各导师择优选拔。 测试对象为参加博士生入学测试的应届或非应届硕士毕业生，以及具有同等学历的在职人员。 二测试的学科范围 操作系统的基本概念，包括：操作系统的定义、功能、特性、类型以及现代操作系统的用户界面 和操作系统的逻辑结构。 操作系统资源管理策

14、略、功能和实现技术，包括：处理机管理、存储管理、设备管理和文件系统。 了解操作系统的重要论题：死锁概念。 并发处理的概念及实现技术。包括：进程概念、进程状态及变迁、进程控制、进程同步互斥的概 念及实现技术。 实例操作系统，如：UNIX 系统和 Windows 系统的类型、结构、用户界面、进程管理、设备管理 和文件系统的有关问题。 三评价目标 现代操作系统科目测试是考核学生对操作系统的基本概念、基本原理及实现技术的掌握程度， 考核学生融会贯通及综合运用所学知识的能力。 本科目的测试要求学生能理解操作系统的基本原理及实现技术，不要死记硬背；要求学生能灵活 地运用所学知识分析问题、解决问题；要求学生

15、能理论联系实际，了解实例操作系统的主要的概念及 实现技术。 四测试形式和试卷结构 1答卷方式：闭卷，笔试。 2答题时间：180 分钟。 3考查内容及考查比例 考查内容的难度分为较易、较难、难三个等级。每份试卷中不同难度试题的分配比例是 3：4：3。基本概念和基本知识约占 30%，在理解的基础上，运用所学知识来解决问题的试题约占 40%， 需要综合几个知识点来解决问题的试题约占 30%。 题目的形式可以有多样。如：填空题、选择题、判断改错题、简答题、计算题、图解题、实现同 步互斥的编程题等。题型不是关键，最关键的是对操作系统这门课程的知识点掌握的程度，知识就是 每章必须掌握的基本内容。针对任一个

16、知识点都可以产生多个不同类型的试题，只有真正的理解、掌 握了知识点，才能自如的运用所学知识。 五参考书目 操作系统原理第三版，庞丽萍编著，华中科技大学出版社。 第二部分 考查要点 一操作系统基本概念 1计算机体系结构和操作系统的关系，操作系统定义、功能、特性和操作系统的基本类型。 2多道程序设计技术和分时技术。 3操作系统虚拟机概念。 4操作系统的结构。 5基本硬件结构：处理机的态和特权指令。 6中断和俘获。 二操作系统的用户界面 1运行一个用户程序的过程。 2操作系统的用户界面：用户界面的定义、操作系统提供的用户界面的类型及使用场合、不同 类型操作系统提供的用户界面；系统调用的定义及实现方法

17、。 三进程及进程管理 1进程的概念：进程的定义、进程的描述、进程的状态及变迁。 2进程控制：进程控制的概念、常用的进程控制原语的功能及实现。 3进程互斥和同步：临界资源、临界区、进程互斥的定义；进程同步的例、进程同步的定义； 信号灯及 P、V 操作的概念，用信号灯的 P、V 操作实现进程互斥，用信号灯的 P、V 操作实现进程同 步。 四操作系统的资源管理 1操作系统资源分配机制、资源分配策略。 2死锁：死锁的概念、产生死锁的原因、产生死锁的必要条件、死锁的预防、 死锁的避免。 3处理机管理：处理机的多级调度、作业调度、进程调度算法、调度用的状态变迁图、调度方 式。 4存储管理：存储管理功能、分

18、区分配机构、分配方法及三种放置策略；分页存贮管理的基本 概念、页式地址变换；请求分页概念和实现方法；段式系统和二维地址结构、段地址变换；段页式存 贮管理概念和实现方法。 5设备管理：设备管理功能、设备独立性概念、缓冲技术的概念和常用的缓冲技术、设备分配 技术、输入输出控制的基本功能。 6文件系统：文件和文件系统的定义、文件的逻辑结构、文件的物理结构（连续结构、串联结 构、索引结构） ；文件目录的定义、文件目录项内容、文件目录结构、文件路径名和当前目录；常用 的文件操作命令；文件共享的概念和方法；文件安全的概念和方法。 五实例操作系统（UNIX 操作系统和 Windows 操作系统） UNIX

19、操作系统和 Windows 操作系统的类型、特点、用户界面及结构；UNIX 系统的进程结构、 进程状态及变迁、UNIX 进程调度的功能和算法； UNIX 缓冲管理技术；UNIX 文件系统中主要的数据 结构及功能实现、UNIX 系统文件索引结构及文件目录结构。 254 博士研究生数据库系统测试大纲 第一部分 测试说明 一、测试性质 全国博士研究生入学测试是为高等学校招收博士研究生而设置的。其中， 数据库系统实行全 国统一测试。它的评价标准是高等学校优秀硕士毕业生能达到的及格或及格以上水平。以保证被录取 者具有较好的理论素养和专业知识，并有利于各高等学校在专业上择优选拔。 测试对象为参加博士研究生

20、入学测试的硕士毕业生，及其他具有同等学力的在职人员。 二、评价目标 1掌握数据库系统的基本概念、原理和理论。 2掌握经典数据模型及关系代数、关系演算、函数依赖、关系规范化、公理系统等关系理论。 3掌握基本的 DB 设计理论、方法、技术和工具，能熟练完成特定背景的 DB 设计。 4具有较高的数据库使用开发，尤其是 SQL 使用的技术。 5熟悉 DBMS 实现的基本理论、技术、方法和机制。 6清楚 DBS 发展的现状和趋势。 三、测试形式和试卷结构 1测试形式：闭卷、笔试。 2答题时间：180 分钟。 3试卷题型：多项选择题、问答题、论述题、证明题、计算题、设计和综合使用题。每年在上 述题型中选用

21、 35 种。 四、参考书目 1 Database System Concepts ，Abraham Silberschats，机械工业出版社。 2 数据库系统概论 ，萨斯萱编，高等教育出版社。 第二部分 考查要点 1基本概念 基本概念和理论考查范围涉及参考书中的各个章节，主要是指关键名词和术语的定义和理解，这 类问题可在上列各种题型中以不同形式表现。如实体、属性、关键字、三级模式、数据独立性、数据 完整性、事物及其特征、可串形化等。 2DBS 结构和组成 DB 的三级模式抽象结构，DBS 的体系结构，其主要组部件及其功能。 3数据模型 数据模型，主要是层次、网状、关系、E-R 模型、面向对象模

22、型等的构造形式及特点。重点是关 系及 E-R 模型，要求熟练掌握其概念、技术及建模方法。 4数据库存储组织 主要的存储数据组织方法及其特点，尤其是树形、Hash 式组织及其实现技术。 5关系数据库系统 关系代数理论 关系演算理论 SQL 语言：各类 SQL 语句的语法构成、语义和功能，特别是 Select 语句的不同使用方法。 关系规范化 函数依赖中的部分函数依赖、完全函数依赖、传递函数依赖；关系范式中的 1NF，2NF，3NF ，BCNF。 函数依赖的公理系统 公理的概念、正确性、完备性，公理的推论，闭包的计算，函数依赖的等价和复盖，最小函数依 赖集。 关系模式分解 模式分解的无损连接性、保

23、持函数依赖性及相关分解算法。 6事物及其处理 事务的概念、特征；可串行化调度的基本理论和正确性，并发控制协议和实现技术，尤其是封锁 技术；故障恢复技术和机制。 7查询处理及其优化技术；数据操纵及其存取（安全性）控制技术。 8数据库设计 DB 设计的步骤，局部 E-R 图设计，局部 E-R 图到全局 E-R 图的合并，E-R 图向关系模式的转换； 给定环境的数据库建模及相关理论和技术的综合使用。 9数据库研究的现状、主要及热点领域、前沿及发展趋势，尤其是象 OODB、分布式 DB、Internet 和 DB 等领域。 368 博士研究生“矩阵论和随机过程”测试大纲 第一部分 测试说明 一、测试性

24、质 博士生入学测试是为华中科技大学招收博士研究生而设置的。其中， “矩阵论和随机过程”主要 是针对报考计算机类的考生而设置的。该课程的评价标准是高等学校优秀硕士毕业生能达到及格或及 格以上水平，以保证被录取者具有基本的专业理论素质并有利于招收单位和导师择优选拔。 测试对象为参加博士生入学测试的硕士毕业生，以及具有同等学历的在职人员。 二、 评价目标 1 掌握矩阵论和随机过程的基本知识、基本理论和基本方法。 2 运用矩阵论和随机过程的算法和结论计算或证明相关的命题。 三、 测试形式和试卷结构 1 测试形式：闭卷、笔试 2 答题时间：180 分钟 3 试卷题型：计算题、证明题 4 各部分内容的测试

25、比例：矩阵论 60%，随机过程 40% 四、 参考书目 1 高等工程数学 ，于寅，华中理工大学出版社。 2 随机过程 ，刘次华，华中理工大学出版社。 第二部分 考察要点 一、矩阵论部分 1 基础知识： 矩阵的乘法、矩阵的初等变换、线性空间和线性子空间、线性变换、向量的相关和无关、向量的 正交化 2 特征值和特征向量 线性变换的特征值和特征向量、Jordan 标准型 3 矩阵分析和矩阵函数 矩阵函数的微分和积分、向量和矩阵的范数、矩阵函数及计算、矩阵的幂级数 二、随机过程部分 1基础知识 随机变量及其分布、随机变量的数字特征 2 随机过程的概念和基本类型 随机过程的基本概念、随机过程的分布律和数

26、字特征、几种重要的随机过程 3泊松过程 泊松过程的定义、泊松过程的基本性质、非齐次泊松过程、复合泊松过程 4 马尔可夫链 定义、转移概率、状态分类、状态空间的分解、转移概率的渐进性质、平稳分布 5 平稳随机过程 定义、联合平稳过程及相关函数的性质、平稳过程的各态历经性 6 平稳过程的谱分析 平稳过程的谱密度、谱密度的性质 369 博士研究生计算机网络（二）入学测试大纲 第一部分 一、测试性质 现代计算机网络是计算机系统结构专业的硕士生学位课，本测试大纲是专门为华中科技大 学计算机系统结构专业及其相关专业招收博士研究生而设置的，测试标准是高等学校计算机及相关 学科优秀硕士生能达到的及格或及格以上

27、的水平，以保证被录取者具有继续深造所必需的网络基础， 并有利于各有关专业作为挑选入学博士生的依据之一。 二、测试范围 重点考查网络基本结构、直接链路网络、包交换、网络互连和路由、端到端协议和数据、拥塞控 制和资源分配、协议描述和验证、网络安全及网络性能分析等内容。 三、评价标准 在考查有关网络的基本概念和基本理论的基础上，重点考查学生运用基本知识分析问题和解决网 络问题的能力。具体要求是： 正确理解并解释当前网络技术和研究前沿的新概念和新技术。 熟练掌握各种网络、协议、算法、机制及设备的基本原理、基本性质及他们之间的联系和 区别。 能运用所学的知识对未知的问题进行解释、分析、计算、设计和作图。

28、 四、测试形式 1答卷方式：闭卷、笔试。 2答题时间：180 分钟。 3试卷结构 术语简释，检验当前网络发展最前沿的学术名字或基本概念掌握程度。范围广大，但只要求简单 解释，有些英文缩写仅用中文说明即可。占 10 单项选择，考查网络领域特别重要而又容易混淆的技术和概念。要求从 3-5 个可选答案中选择最 适合的一个填空。占 20。 计算求解，考核网络领域中很重要的技术或概念，计算本身并不复杂，但以计算求结果的形式出 现。占 30。 图解设计，深入考查运用网络重点知识和技术解决未知问题的综合分析、设计能力，大多以设计 并作图显示其答题结果。占 40 五、参考书目 1Larry L. Comput

29、er Networks A System Approach 计算机网络（英文版，第二版，机械工业出版社，2000 年） 2 Andrew S. Tanenbaum, Computer Networks ,Third Edition 或熊桂喜等 中译本 计算机网络，清华大学出版社，1999.4 3 计算机网络第三版，坦尼伯姆，电子工业出版社。 4 计算机网络第二版，第三版，谢希仁，电子工业出版社。 第二部分 1网络基本结构 组建网络的基本需求 网络体系结构 实现网络的基本软件 2直接链路网络 编码、成帧、错码检测、可靠传输 802.3 以太网、无线网 802.11 3包交换 交换和转发 桥和 L

30、AN 交换 信元交换 ATM 交换机硬件结构 4网络互连 简单网络互连（IP） 路由（RIP、OSPF） 全球互连（CIDR、BGP、IPV6） 组播 5端到端协议和数据 简单多路器（UDP） 可靠字节流（TCP） 远程过程调用（RPC） 数据表示规范（ASN.1、XDR、NDR） 数据压缩（JPEG、MPEG、MP3） 6拥塞控制和资源分配 资源分配中的问题、排队原则 TCP 拥塞控制、拥塞避免机制 服务质量 7. 协议描述和验证 有限状态机模型 Petri 网模型 8网络安全 加密算法（DES、RSA、MD5） 安全机制（认证协议、消息完整性协议、公钥分发及 Diffie-Hellman

31、交换） 加密实例（PEM、PGP、SSL、TLS、HTTPS、IPsec） 防火墙及 VPN 等 9 网络性能分析 局域网（Ethernet） 网络流量分析 370 博士研究生计算机数学测试大纲 第一部分 测试大纲 一、测试性质 计算机数学是计算机科学的重要理论基础。博士研究生计算机数学测试是为华中科技大学计 算机科学和技术及其相关专业招收博士研究生而设置的。它的评价标准是高等学校计算机及相关学科 优秀硕士生能达到的及格或及格以上水平，以保证被录取者具有继续深造的必要的数学基础和素质， 并有利于各相关专业在招生工作上的择优选拔。 二、测试范围 集合论，包括集合、关系、函数；代数系统的一般概念、

32、群、格和布尔代数；图论；命题逻辑和 谓词逻辑；形式语言和自动机。 三、评价目标 在考查基本概念、基本理论的基础上，注意考查学生运用基本知识分析和解决问题的能力。具体 要求： 1正确理解各基本概念； 2熟练掌握研究对象的基本性质； 3深入理解各研究对象之间的内在联系； 4熟练掌握计算机数学中的几种典型的论证方法； 5能运用所学的知识对未知的问题进行分析、推理而加以解决。 四、测试形式和试卷结构 1答卷方式：闭卷，笔试 2答题时间：180 分钟 3考查内容及其考查比例： 基本概念：30% 论证推理：70% 五、参考书目 1 洪帆主编， 离散数学基础第二版，华中理工大学出版社，1995 年。 2 洪

33、帆、付小青编， 离散数学习题题解 ，华中理工大学出版社，1999 年。 3 陈崇昕，形式语言和自动机，北京邮电大学出版社（前三章） 第二部分 考查要点 一、集合论 1 集合，幂集，分划等概念 2 集合间的各种关系和运算，运算定律 3 笛卡尔积，关系，复合关系，逆关系等概念 4 关系的集合表示，矩阵表示和关系图表示 5 关系的复合运算，闭包运算 6 关系的性质，等价关系和偏序关系 7 函数，复合函数，逆函数 8 内射，满射和双射 二、代数系统 1 集合 A 上运算的概念，二元运算的一些特殊元素 2 运算的封闭性和代数系统的概念 3 同态，满同态以及同构的概念和性质 4 群的定义和性质 5 子群及

34、其判别 6 陪集和正规子群 7 格的定义和性质 8 有补格，分配格和布尔代数的定义及有关性质 三、图论 1 图的定义及有关的各个概念，完全图、连通图、子图、分图等。欧拉图，哈米尔顿图，图的 连通性 2 树的定义及性质，有向树的定义，二元树及二元树的周游，有向树中的一些数量关系，有向 树的使用 3 二部图的定义及其判别 4 平面图的定义及其判别 四、数理逻辑 1 命题逻辑 命题，命题联结词，命题变元，命题公式，永真公式，永假公式及可满足公式，命题 公式的等值关系和蕴含关系，命题演算的推理理论 2 谓词逻辑 谓词、个体词和量词，谓词演算公式，谓词演算的永真公式，永假公式和可满足公式，谓词演 算公式

35、的等值和蕴含，谓词演算的推理理论 五、形式语言和自动机 1、 语言及文法 语言的定义和运算、文法、文法的分类。 2、 有限自动机和右线性文法 有限自动机、不确定的有限自动机、DFA 和 NFA 的等效、有 转换的不确定的有限自动机、 正则集和正则式、右线性文法和正则集、右线性语言和有限自动机、右线性语言的性质。 371 博士研究生数据结构及算法分析入学测试大纲 第一部分 测试说明 一、测试性质 数据结构和算法分析是计算机专业的专业基础课。 数据结构和算法分析 是华中科技大学计算机软件和理论专业博士研究生入学测试的一个综合测试科目。 它的评价标准是，高等学校本学科优秀毕业生能达到的及格或及格以上

36、水平，以保 证被录取者具有基本的计算机专业理论基础，以利于计算机软件和理论专业各导师择优 选拔。 测试对象为参加博士研究生入学测试的应届或非应届硕士毕业生和具有同等学力的在职 人员。 二、测试的学科范围 1.数据结构 各种基本类型的数据结构的概念、特征、操作、存储表示和基本使用；各类查找表 的查找方法，基本的内排序和外排序方法；文件在外存储器中的表示方法；相关算法的 C/C+描述和分析。 2.算法分析 算法的基本概念,分治策略，贪心策略，动态规划，基本检索和周游方法。 三、评价目标 1.数据结构 在考察数据结构的基本概念、基本方法和相关算法的基础上，注重考察综合使用的 能力，即分析和解决实际问

37、题的能力。 2.算法分析 掌握一定的算法分析能力, 掌握算法设计的基本观点和基本方法, 能正确地选用常 用的非数值计算算法, 能站在算法设计策略的高度上设计算法。 具体要求见第二部分“考查要点” 。 四、测试形式和试卷结构 1.答卷方式：闭卷，笔试。 2.答题时间：180 分钟。 3.考查内容及其考查比例 基本概念、基本方法约占 40%50%；综合使用、算法设计(程序设计)和分析约占 60%50%。 4.试卷结构和测试题型 (1)单项选择题,多项选择题: 约 20% (2)填空题，简答题，使用题: 约 35% (3)算法设计题, 算法分析题: 约 35% (4)其它题型: 约 10% 五、参考

38、书目 1.严蔚敏等，数据结构(C 语言版)，清华大学出版社 2.余祥宣 崔国华 邹海明，计算机算法基础(前五章)，华中理工大学出版 社,2000 3.Horowitz,S Sahni,Fundamentals of Computer Algorithms.New York: Computer Science Press,1978 第二部分 考查要点 一、数据结构(约 60%) 1.数据结构和算法 C/C+描述。 数据结构、存储结构的概念；数据类型和抽象数据类型；数据结构和算法 C+描述。 2.线性表：线性表的定义和基本操作；线性表的抽象数据类型；线性表的顺序存储 结构，使用举例；线性表的链式存

39、储结构(单链表,双链表,循环链表),使用举例。 3.栈：栈的定义和基本操作；栈的抽象数据类型；顺序栈，链式栈；栈和递归,算术 表达式求值,其它使用。 4.队列：队列的定义和基本操作；队列的抽象数据类型；顺序队列，链式队列；双 端队列 ；使用举例。 5.数组和广义表 (1)数组：数组的定义和基本操作；数组的顺序存储结构，数组使用举例；特殊矩阵 和稀疏矩阵矩阵的压缩存储。 (2)广义表：广义表的定义和基本操作，广义表的抽象数据类型，广义表的存储结构， 广义表运算的实现举例。 6.字符串：字符串的定义和基本操作，字符串的存储结构，字符串操作的实现举例， 字符串和模式匹配。 7.树和二叉树 (1)树的

40、基本概念和基本操作,树的抽象数据类型。 (2)二叉树的基本概念和性质，几种特殊二叉树,二叉树的存储结构, 遍历二叉树, 线索二叉树,树和森林。 (3)遍历二叉树：前序遍历, 中序遍历, 后序遍历, 层次遍历。 (4)二叉树其它操作实现举例。 (5)线索二叉树的概念和存储结构, 二叉树的线索化, 线索二叉树的遍历。 (6)树的存储结构,树和二叉树之间的转换, 森林和二叉树之间的转换，树和森林的 遍历。 (7)带权路径长度, 哈夫曼树(Huffman)和哈夫曼算法, 哈夫曼编码树。 (8)二叉排序树的概念和基本操作,二叉排序树的建立,二叉排序树其它操作 实现举例。 8.图 (1)图的基本概念和基本

41、操作，图的抽象数据类型。 (2)图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表；邻接多重表。 (3)图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量。 (4)生成树和最小生成树的概念；克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法。 (5)最短路径，拓扑排序，关键路径。 9.查找 (1)查找的概念。 (2)顺序表的查找：顺序查找, 折半查找, 分块查找。 (3)树表的查找: 二叉排序树, 平衡二叉树。 (4)哈希(Hash)表的查找: 哈希表的概念, 哈希函数的构造方法, 哈希表的建立和查 找, 冲突的处理方法。 10.排序 (1)排序的概念 (2)交换排序：冒泡

42、排序, 快速排序。 (3)插入排序：直接插入排序, 2 路插入排序，折半插入排序, 希尔排序。 (4)选择排序：直接选择排序, 锦标赛排序,堆排序。 (5)归并排序，(6)基数排序 11.文件:文件的基本概念和基本操作；文件的物理结构：顺序文件,索引文件和索引 顺序文件, 直接存取文件，链接文件和多重链表文件，倒排文件。 12.外排序：外排序的基本过程,初始归并段的生成,多路平衡归并排序, 最佳归并树。 二、算法分析(约 40%) 1.基础知识 算法的定义,它所涉及的内容及在计算机科学中的地位和作用；算法分析的基本概念， 基本步骤及其数学工具；基本的数据结构，用 SPARKS 语言写算法；集合

43、的基本运算- 查找和合并；递归程序和消去递归的十三条规则。 2.分治法 分治法的一般方法, 二分检索, 找最大和最小元素, 归并分类, 快速分类, 选择问题, 斯特拉森矩阵乘法。 3.贪心方法 一般方法及背包问题, 带有限期的作业排序, 最优归并模式, 最小生成树, 单源点 最短路径。 4.动态规划 一般方法, 多段图, 每对结点之间的最短距离, 最优二分检索树, 0/1 背包问题, 可 靠性设计, 货郎担问题, 流水线调度问题。 5.周游和检索 基本概念和一般方法, 代码优化, 双连通分图和深度优先检索。 372 博士研究生图形图象处理入学测试大纲 第一部分 测试说明 一、测试性质 全国博士

44、研究生入学测试是为高等学校招收博士研究生而设置的。其中， 图形图象处理是计 算机使用技术专业考生测试科目。它的评价标准是高等学校优秀硕士研究生能达到及格或及格以上水 平，以保证被录取者具有基本的图形图象处理的基础和能力，并有利于学校在专业上择优选拔。 测试对象为参加博士研究生入学测试的硕士毕业生，或具有同等学历的在职人员。 二、测试形式和试卷结构 1 答题方式：闭卷，笔试。 2 答题时间：180 分钟。 3 各部分内容的测试比例：计算机图形学 80%，图象处理 20%。 4 题型比例：选择填空约 20%，简答题约 30%，计算题约 20%，论述题约 30%。 三、性质和要求 图形图象处理是研究

45、计算机处理图形图象的原理、方法和技术的科学。是计算机科学和使用 专业基础课程之一，通过本课程的学习使考生了解和掌握计算机图形图象处理中的数学原理，基本方 法和软件设计方法，为进一步深入学习这一领域的知识打下基础。同时尽量反映近年来计算机图形图 象方面最新发展所需的基本知识，为掌握这些最新成果准备条件。 四、参考书目 孙家广，杨长贵.计算机图形学（第三版）.北京：清华大学出版社，1998。 第二部分 考查要点 一、基本知识 1 计算机图形学和图象处理 2 计算机图形学的发展及使用 3 图形系统的组成和功能 4 图形设备 5 图形软件标准 6 计算机图形学的发展方向 二、基本图形生成技 1直线，圆

46、，椭圆的生成算法 2抛物线参数样条曲线，Bezier 曲线，B 样条曲线的生成 3区域填充算法 4线宽和线型的处理 5字符的存储和显示 6线段和多边形的裁剪 7 反走样技术 三、图形变换 1齐次坐标 2窗口视图变换 3二维图形和三维图形的几何变换 5 形体的投影变换 四、交互技术和用户接口 1基本交互任务和技术 2组合交互任务和技术 3用户接口的设计 4用户接口软件 五、几何造型 1形体在计算机中的表示 2边界表示的数据结构和欧拉操作 3求交算法 4集合运算 六、真实图形 1隐藏线的消除 2隐藏面的消除 3明暗效果和纹理 4光线跟踪 6 辐射度 七、图象处理 1数字图象采样理论 2图象的空间变换变换 3图象分析 4图象数据压缩 5图象识别