I考试说明
【考试性质】
《计算机专业基础综合二》是报考计算机科学与技术（077500）的考试科目之一。为帮助考生明确考试复习范围和有关要求，特制定出本考试大纲。
本考试大纲适用于2026年报考东莞理工学院计算机科学与技术（077500）的全国硕士研究生入学考试的准考考生。
【考查范围】
《计算机专业基础综合二》考试内容涵盖数据结构和离散数学课程。要求考生系统掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
II 试卷形式和试卷结构
A. 试卷形式
本试卷满分为150分，考试时间为180分钟。
答题方式为闭卷、笔试。
B. 试卷内容结构
数据结构75分；离散数学75分。
C. 试卷题型结构
单项选择题40分（20小题，每小题2分）、填空题50分（10小题，每小题5分）、综合应用题60分（4小题，每小题15分）
D. 考查内容
【数据结构】
【考查目标】
要求学生能够掌握数据的逻辑结构、存储结构以及其它结构定义的各种运算及应用。具体要求如下：
1、掌握算法的时间复杂度和空间复杂度分析的基本方法；
2、掌握线性表、栈、队列、树、图等数据结构；
3、掌握排序和查找等算法的实现和分析；
4、掌握算法设计的常用技术和应用。
【考查大纲】
一、绪论
（一）数据结构基本概念：
1、数据、数据元素、数据类型
2、数据的逻辑结构和存储结构
3、数据的操作
（二）算法和算法的时间复杂度：
1、算法的概念和性质
2、算法的时间效率分析
二、线性表
（一）线性表的概念
（二）顺序表
1、顺序表的存储结构
2、顺序表操作的实现
3、顺序表的效率分析
4、顺序表的应用
（三）链表
1、单链表的存储结构
2、单链表的基本操作
3、单链表的应用
4、循环单链表
5、双向链表
6、静态链表
三、堆栈和队列
（一）栈
1、栈的概念
2、栈的顺序和链式实现
（二）队列
1、队列的基本概念
2、顺序循环队列
3、链式队列
4、优先级队列
（三）栈和队列的应用
四、串
（一）串的概念和存储结构
1、串的概念
2、串的存储结构和基本算法的实现
（二）串的匹配算法
1、BF算法
2、KMP算法
五、数组
（一）数组的概念
1、数组概念
2、数组的实现
（二）特殊矩阵和稀疏矩阵的压缩存储
1、特殊矩阵的压缩存储
2、稀疏矩阵的压缩存储。
六、递归算法和广义表
（一）递归算法
1、递归算法概念
2、递归算法的设计
（二）广义表
1、广义表的概念
2、广义表的存储结构和操作实现。
七、树和二叉树
（一）树的概念
1、树的概念
2、树的存储结构
（二）二叉树
1、二叉树的概念和性质
2、二叉树的存储结构和基本算法实现。
（三）二叉树的遍历算法
1、深度递归和广度递归算法
2、遍历算法的应用
（四）线索二叉树
（五）哈夫曼树
1、哈夫曼树的概念
2、哈夫曼编码问题。
（六）树与二叉树的转换
1、树的遍历
2、树和二叉树的转换
八、图
（一）图的概念和存储结构
1、图的相关概念
2、图的存储结构
3、图的基本算法实现
（二）图的遍历算法
（三）最小生成树
1、最小生成树概念
2、普里姆(Prim)算法
3、克鲁斯卡尔(Kruskal)算法
（四）最短路径、拓扑排序和关键路径
九、排序
（一）排序的概念
（二）插入排序
1、直接插入排序
2、希尔排序
（三）选择排序
1、直接选择排序
2、堆排序
（四）交换排序
1、冒泡排序
2、快速排序
（五）归并排序
（六）基数排序
十、查找
（一）查找的概念
（二）静态查找
1、顺序查找
2、二分查找
3、索引查找
（三）动态查找
1、二叉排序树和平衡二叉树
2、B树
（四）哈希查找
1、哈希查找的概念
2、哈希函数
3、哈希冲突的解决方法
【离散数学】
【考查目标】
要求学生能够掌握离散数学的基本概念、基本原理与核心方法，掌握一些基础的离散结构的定义，以及这些结构的特性与相互关系，熟练地进行运算和应用。具体要求如下：
1、掌握命题逻辑的基本概念、等值演算与推理方法；
2、掌握集合、二元关系与函数的运算及性质；
3、掌握代数系统的定义和不同代数结构的判定；
4、掌握图的基本概念、性质以及特殊图类的判别和应用；
5、掌握组合计数的基本原理与方法。
【考查大纲】
一、数理逻辑
（一）命题逻辑
1、命题与联结词
2、命题公式与赋值
3、等值演算
4、析取范式与合取范式
5、联结词完备集
6、命题逻辑的推理理论
（二）一阶逻辑
1、一阶逻辑的基本概念
2、一阶逻辑公式及解释
3、一阶逻辑等值式与前束范式
二、集合论
（一）集合的基本概念和运算
1、集合的基本概念与基本运算
2、集合恒等式
3、有穷集合的计数
（二）二元关系和函数
1、集合的笛卡儿积和二元关系
2、关系的运算和性质
3、关系的闭包
4、等价关系和偏序关系
5、函数的定义和性质
6、函数的复合和反函数
三、代数结构
（一）代数系统的一般概念
1、二元运算及其性质
2、代数系统及其子代数和积代数
3、代数系统的同态与同构
（二）几个典型的代数系统
1、群、环与域
2、格与布尔代数
四、图论
（一）图的基本概念
1、无向图和有向图
2、通路、回路、图的连通性
3、图的矩阵表示
（二）树
1、无向树
2、根树及其应用
（三）二部图、欧拉图、哈密顿图
1、二部图
2、欧拉图
3、哈密顿图
（四）平面图及图的着色
1、平面图
2、图的着色
五、组合数学
（一）组合计数
1、排列与组合
2、二项式定理与多项式定理
（二）递推方程与生成函数
1、递推方程
2、生成函数与指数生成函数
