华中科技大学计算机学院
硕士研究生入学《数据结构》考试大纲
                    第一部分 考试说明
一、考试性质
数据结构是计算机各专业的专业基础课。它的评价标准是高等学校计算机科学与技术各专业本科毕业生能达到的及格或及格以上水平,以保证被录取者具有基本的专业理论基础及程序设计能力,以利于计算机科学与技术各专业的导师择优选拔硕士研究生。
    考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。
二、考试范围
    各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各种基本查表的概念、特征及其查方法，基本的内排序和外排序方法；文件在外存储器中的基本表示方法；用C语言(或C++)描述算法和程序设计,算法分析。
三、评价目标
在考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和解决实际问题的能力,注重考查算法和程序设计的能力。
    具体要求见本考试大纲第二部分的“考查要点”。
四、考试形式与试卷结构
    1.答卷方式:闭卷,笔试。
    2.答题时间:180 分钟。
    3.考查内容及其考查比例
基本概念、基本知识、基本方法约占40%～50%；综合应用、算法和程序设计与算法分析约占60%～50%。
    4.试卷结构与考试题型
试卷共150分,基本的考试题型有：
(1)单项选择题和多项选择题；
(2)填空题(基本概念、基本知识、基本方法)；
(3)画图题；
(4)简答题；
    (5)应用题(求解问题)；
    (6)算法和程序设计填空题；
    (7)算法和程序设计与分析题；
    (8)其它题型。
 
五、教材和参考书
    教材: 《数据结构》(C语言版)，严蔚敏、吴伟民编著,清华大学出版社,1997.4
第二部分 考查要点
    1.数据结构和算法
    数据结构、存储结构的概念；数据类型与抽象数据类型；算法的概念,用C/C++描述算法和程序设计,算法分析初步。
    2.线性表
    线性表的定义和基本操作；线性表的抽象数据类型；线性表的顺序存储结构，
应用举例；线性表的链式存储结构(单链表,双链表,循环链表),应用举例。
3.栈
    栈的定义和基本操作；栈的抽象数据类型；顺序栈，链式栈；栈和递归算法, 算术表达式求值,其它应用。
    4．队列
    队列的定义和基本操作；队列的抽象数据类型；顺序队列，链式队列；双端
队列的定义和基本操作；应用举例。
    5.数组和广义表
    (1)数组
    数组的定义和基本操作；数组的顺序存储结构，应用举例；特殊矩阵和稀疏
矩阵的压缩存储。
    (2)广义表
广义表的定义和基本操作,广义表的抽象数据类型,广义表的存储结构。
  *广义表运算的实现举例。
    6.字符串
    字符串的定义和基本操作,字符串的存储结构,字符串操作的实现举例,字符串和模式匹配。
    7.树和二叉树
    (1)树的基本概念和基本操作,树的抽象数据类型。
(2)二叉树的概念和性质,特殊二叉树；二叉树的存储结构；
(3)二叉树的生成与建立。 
    (4)遍历二叉树：前序遍历,中序遍历,后序遍历,层次遍历。
    (5)二叉树其它操作实现举例。
    (6)线索二叉树的概念和存储结构,二叉树的线索化,线索二叉树的遍历。
    (7)树的存储结构,树与二叉树之间的转换,森林与二叉树之间的转换,树和
森林的遍历。
    (8)树的路径长度和带权路径长度,哈夫曼树(Huffman)的概念,哈夫曼算法, 哈夫曼编码树。
    (9)二叉排序树的的概念和基本操作,二叉排序树的建立,二叉排序树其它操作实现举例。
    8.图
    (1)图的基本概念和基本操作，图的抽象数据类型。
    (2)图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表，十字链表；邻接多重表。
    (3)图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量。
    (4)生成树、最小生成树的概念；克鲁斯卡尔(Kruskal)算法,普里姆(Prim)
算法。
  *(5)从一个顶点到其余各顶点的最短路径,每对顶点之间的最短路径。
  *(6)拓扑排序和关键路径
    9.查
    (1)查的概念,关键字比较次数,平均查长度。
    (2)顺序表的查:顺序查,折半查,分块查。
    (3)树表的查:二叉排序树,平衡二叉树。
    (4)哈希(Hash)表的查:哈希表的概念,哈希函数构造方法,哈希表的建立和查,冲突处理方法。
    10.排序
    (1)排序的概念；排序的稳定性；比较关键字次数,移动记录次数；顺序表的排序,链接表(单链表)的排序。
(2)内排序方法与算法
(a)交换排序:冒泡排序,快速排序。
    (b)插入排序:直接插入排序,2路插入排序,折半插入排序,希尔排序。
    (c)选择排序:直接选择排序,锦标赛排序,堆排序。
    (d)归并排序。
(e)基数排序。
(3)各种排序算法的评价和应用。
    11.文件
    (1)文件的基本概念, 文件的基本操作。
    (2)文件的物理结构：顺序文件, 索引文件与索引顺序文件, 直接存取文件，
链接文件和多重链表文件，倒排文件。
  *12.外排序
外排序的基本过程, 初始归并段的生成,多路平衡归并排序,最佳归并树。
说明:带“*”号的章节为一般考查内容,其余为重点考查内容。
                 
硕士研究生入学《离散数学》考试大纲
第一部分 考试大纲
一、考试性质
离散数学是计算机科学的重要理论基础。硕士研究生《离散数学》考试是为华中科技大学计算机科学和技术及其相关专业招收硕士研究生而设置的。它的评价标准是高等学校计算机及相关学科本科毕业生能达到的及格或及格以上水平，以保证被录取者具有继续深造的必要的数学基础和素质，并有利于各相关专业在招生工作上的择优选拔。
考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。
二、考试范围
集合论，包括集合、关系、函数；代数系统的一般概念、、格和布尔代数；图论；命题逻辑和谓词逻辑。
三、评价目标
在考查基本概念、基本理论的基础上，注意考查学生运用基本知识分析和解决问题的能力。具体要求：
1． 正确理解各基本概念；
2． 熟练掌握研究对象的基本性质；
3． 深入理解各研究对象之间的内在联系；
4． 熟练掌握离散数学中的几种典型的论证方法；
5． 能运用所学的知识对未知的问题进行分析、推理而加以解决。
四、考试形式与试卷结构
1． 答卷方式：闭卷，笔试
2． 答题时间：180分钟
3． 考查内容及其考查比例：
①基本概念：30%
②论证推理：70%
五、参考书目
1． 洪帆主编， 《离散数学基础》第二版，华中理工大学出版社，1995年。
2． 洪帆、付小青编， 《离散数学习题题解》，华中理工大学出版社，1999年。
第二部分 考查要点
一、 集合论
1． 集合，幂集，分划等概念
2． 集合间的各种关系和运算，运算定律
3． 笛卡尔积，关系，复合关系，逆关系等概念
4． 关系的集合表示，矩阵表示和关系图表示
5． 关系的复合运算，闭包运算
6． 关系的性质，等价关系和偏序关系
7． 函数，复合函数，逆函数
8． ，满射和双射
二、 代数系统
1． 集合A上运算的概念，二元运算的一些特殊元素
2． 运算的封闭性和代数系统的概念
3． 同态，满同态以及同构的概念和性质
4． 的定义和性质
5． 子及其判别
6． 格的定义和性质
7． 有补格，分配格和布尔代数的定义及有关性质
三、 图论
1． 图的定义及有关的各个概念，完全图、连通图、子图、分图等。欧拉图，哈米尔顿图，图的连通性
2． 树的定义及性质
3． 二部图的定义及其判别
4． 平面图的定义及其判别
四、 数理逻辑
1． 命题逻辑
命题，命题联结词，命题变元，命题公式，永真公式，永假公式及可满足公式，命题
公式的等值关系和蕴含关系，命题演算的推理理论
2． 谓词逻辑
谓词、个体词和量词，谓词演算公式，谓词演算的永真公式，永假公式和可满足公式，谓词演算公式的等值和蕴含，谓词演算的推理理论
硕士研究生入学《计算机组成原理》考试大纲
                  第一部分 考试说明
一、考试性质
计算机组成原理是计算机专业的专业基础课。它的评价标准是高等学校计算机科学与技术各专业本科毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的专业理论基础及程序设计能力，以利于计算机科学与技术各专业的导师择优选拔硕士研究生。
    考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。
二、考试范围
计算机系统概论，计算机中数据的表示方法，运算方法与运算器，存储系统，指令系统，中央控制器，系统总线，输入输出原理。
三、评价目标
在考查基本概念、基本理论的基础上，注重考查学生运用基本知识分析和解决实际问题的能力。
四、考试形式与试卷结构
1.答卷方式：闭卷，笔试。
    2.答题时间： 180分钟。
    3.考查内容及其考查比例：基本概念占40分、理解占30分、综合能力占80分；合计150分。
4.试卷结构与考试题型：填空题、选择、名词、术语解释、简答题、计算题、及设计题、分析论述题等。
五、参考书目
《计算机组成原理》，白中英主编，科学出版社。
《计算机组成原理》，高建生、莫正坤、谭志虎编写，华中科技大学出版社。
第二部分 考查要点
1．计算机系统的相关概念，计算机系统层次结构的实际含义。
2．计算机中数的表示法，机器数的定义及与真值的互换，信息校验的实际意义和方法。二叉树公式
3．补码算术运算方法及逻辑实现原理；运算器的功能，功能部件和结构。74181和74182芯片的功能及设计长字长ALU的方法。
4．存储系统及有关概念；现代主存储器的结构和工作原理、设计原理和方法；高速主存设置的有关知识。高速缓冲存储器结构和工作原理及替换策略等相关知识。磁表面存储器及光盘存储器的原理和相关知识。虚拟存储器概念及有关内容。
5．指令系统的意义和重要性；指令格式，指令和操作数的寻址方式和寻址过程；完备性指令系统的设计。
6． 中央控制器的功能与组织，指令处理的相关知识和控制原理，时序发生器设置的意义及时序产生器的组织和工作原理。微程序控制器和硬布线控制器的设计思想、原理、组织特征、工作原理及有关知识；流水CPU的有关概念。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。