24考研085410自命题901考试内容

由目标院校给出的考试大纲展开

考试形式和试卷结构
答题方式

闭卷、笔试

题量、题分及考试时间

总分为150分，考试时间为180分钟。
  
（一）绪论
1．考核知识点
数据结构；抽象数据类型；算法；算法的时间复杂度；算法的空间复杂度。
2．考核内容
(1)数据结构的基本概念和术语；

1. 数据结构三要素：逻辑结构、存储结构(物理结构)、运算；注意区分两大逻辑结构（线性结构和非线性结构）＋四大存储结构（顺序、链式、索引、散列）

(2)抽象数据类型的表示与实现；

1. 对外的结构关系及相关操作
2. ADT（抽象数据类型）

(3)算法的基本概念和算法的性能分析方法。

1. 算法的定义：对特定问题求解步骤的描述，是指令的有限序列
2. 五个特性＋四个评价，5个特性：有穷性、确定性、可行性、输入、输出，4个评价：正确性、可读性、健壮性、高效率与低存储
3. 时间复杂度有小到高排为：“常对幂指阶”O(1) < O(log2(n)) < O(n) < O(nlog2(n)) < O(n²) < O(n^3) < O(2^n) <O(n!) < O(n^n)

（二） 线性表
1．考核知识点
线性表；顺序表；链表；顺序存储结构；链式存储结构。
2．考核内容
(1)线性表的定义和逻辑结构特性；

线性表是一个一对一的结构，看到线性表时刻记得标出！分两类：顺序和链式！

(2)线性表的顺序存储方法和基本操作算法实现；

1. 顺序表的特点：可以随机访问；占用存储空间连续；插入删除不方便、需要移动元素；涉及随机存取
2. 在顺序存储的结构体定义中除了定义定长数组(静态分配)，通常再定义一个length记录长度

(3)线性表的链式存储方法和基本操作算法实现；

链表结构体的定义：

typedef struct LNode {

          ElemType data;

          struct LNode *next;

}LNode , *LinkList;

1. 头指针始终指向链表的第一个结点(无论是否有头结点)
2. 头结点的引入：使得对链表第一个位置上的操作和其他位置的操作一致，无需特别处理

！注：当题目没给头结点时默认无头结点

两个创建结点的写法：1、(LNode *)malloc(sizeo(LNode));   2、(LinkList)malloc(sizeo(LNode));

静态链表：是借用数组实现的描述线性表的链式存储结构；结构体中除了data还有int型的next，next指向下一个元素的数组下标

静态链表的特点：插入不需要移动元素，只需要修改指针；需要一次性分配大量空间，不允许扩容

23年代码题（对链表的操作）

（三）栈和队列
1．考核知识点
栈；递归；链队列；循环队列。

*****递归为应用题代码题考察的重点

2．考核内容
(1)掌握栈的类型定义、表示和基本操作的实现；

1. 栈分为三类：顺序栈、链栈和共享栈
2. 链栈使用单链表实现，默认没有头结点，所有操作均在表头进行，既表头为栈顶（也就是链表开始的位置，个人习惯箭头向右时最左侧的那个结点）

(2)运用栈的特性设计算法；

栈的特性为FILO或LIFO，考察用链栈实现某算法可能性较大！链栈在头部进行插入和删除操作

(3)递归算法的设计思路和设计方法；（考察重点！）

递归就是将原问题划分为规模更小的问题，直到到达边界条件（既递归出口），然后逐层返回汇聚成原问题

递归常用于二叉树的遍历及图的深度优先遍历

(4)队列的类型定义、表示和基本操作的实现

1. 队列属于想线性结构的一种，所以可以用顺序存储或链式存储的方式进行实现
2. 队列又分为3种类型：循环队列、链式队列和双端队列

！特别注意：链式存储的队列是头出尾进（头是链表开始的位置，个人习惯箭头向右时最左侧的那个结点）

（四）串
1．考核知识点
串的定义、基本运算算法，串的模式匹配定义和算法。
2．考核内容
(1)串类型的定义及其表示方法；

1. 串的定义：由零个或多个字符组成的有限序列，子串通常包括自己及空串
2. 串的长度不包括最后的'\n'，数组的长度包括'\n'
3. 串的存储结构大致分为3类：定长顺序存储（静态数组），堆分配（动态数组分配）和块链式（一个结点内既可以存放一个字符，也可以存放多个字符）

(2)串基本算法的实现方法；

了解熟悉串基本算法的代码实现

(3)串的应用算法。

1. 串的应用算法大致分为：简单模式匹配（BF算法）主串和模式串同时滑动；和KMP算法，KMP只需要求解next[]数组，后面只和模式串有关
2. KMP算法通常有两种，第一种是next[]数组存放模式串可能失配位置的下一次跳转位置，还有一种改进的用nextVal[]数组存放

KMP算法求解next[]数组的大致过程为：当模式串第一位就发生失配时next[1] = 0（不论串元素的下标是从0开始的还是1开始的） ; 当不是模式串第一位失配时，将模式串发生失配元素的前面复制一份下移，并后移一位与模式串错开一位，当原模式串（失配元素前的部分）和复制下来的一部分模式串匹配上时，next的值为两个模式串垂直方向上匹配成功的元素个数+1（串的下标从1 开始；从0开始时next数组值为匹配成功的元素个数）

改进后的nextVal[]数组和原求next[]数组区别在于：“当原模式串（失配元素前的部分）和复制下来的一部分模式串匹配上”后还需要查看此时复制下来的模式串在原模式串失配的位置，两个垂直对齐的元素k和j是否一样，不一样就和求解next一样，如果一样就直接令nextVal值为原模式串跳转的位置

（五）数组和广义表
1．考核知识点
数组；稀疏矩阵；广义表的定义和基本运算
2．考核内容
(1) 数组的定义和数组的顺序表示方法；
(2) 数组元素顺序存储的地址计算；
(3) 特殊矩阵和稀疏矩阵的压缩存储方法；

1. 特殊矩阵分为：对称矩阵、三角矩阵（上三角或下三角元素相同）、三对角矩阵(主对角线及主对角线左右两边有元素)
2. 对于对称矩阵只用存上三角或下三角部分及主对角线
3. 稀疏矩阵有四种存储方式：三元组（存放行列下标和值）、伪地址（存放按行或列优先方式下，第n个遍历到的次序和值）、邻接表（用行或列下标作为索引，行/列内非0元素串成链表，存放列/行下标和值）、十字链表（用一个大的矩阵，左上角存放原稀疏矩阵的规模、非0元素的个数及链接行索引和列索引的头结点，再用行索引和列索引链接原稀疏矩阵）
4. 关于十字链表中结点的结构如下图所示：

(4) 广义表的定义和基本运算；

1. 广义表是线性结构的推广但不是线性结构，是层次结构，每个表用( )表示，每个元素用逗号隔开，所有元素可以是原子元素也可以是广义表元素；广义表可以是一个递归的定义，可以无限深(此时这个广义表中有元素是自己
2. 对广义表的运算基本为：求深度(只算广义表，不算原子元素，两种求法：1、数左括号，但同级的只记录一次；2、用方块表示原子元素，圆圈表示广义表元素，画层序图，数圆圈的个数，但同一层多个圆圈只记录一个)、长度、表头(第一个逗号前的元素，也就是第一个元素：可能是广义表也可能是原子元素)、表尾（除了第一个元素外，剩余元素组成的表，表尾一定是广义表）

（六）树和二叉树
1．考核知识点
二叉树的存储结构及其遍历的方法；二叉树的线索化；哈夫曼树的构造方法及其编码的生成。
2．考核内容
(1) 树和二叉树的定义、术语和基本逻辑结构特性；
(2) 二叉树的基本性质；
(3) 二叉树存储结构；
(4) 二叉树的遍历算法思想，掌握递归和非递归遍历算法实现；
(5) 线索二叉树的基本概念和相应算法；
(6) 树和森林的存储方法及与二叉树的之间的转换方法；
（七）图
1．考核知识点
图的逻辑结构；邻接表；深度优先遍历；广度优先遍历；最小生成树、拓扑排序、关键路径、  最短路径。
2．考核内容
(1) 图的基本概念、术语和基本逻辑结构特征；
(2) 图的存储结构；
(3) 图的深度优先和广度优先遍历算法；
(4) 最小生成树、拓扑排序、关键路径、最短路径的应用。
 
（八）查找
1．考核知识点
顺序查找；折半查找；分块查找；二叉排序树；平衡二叉树；哈希表。
2．考核内容
(1) 静态查找表、动态查找表和哈希查找的基本概念；
(2) 静态查找表的各种查找方法如：顺序查找、折半查找、分块查找；
(3) 动态查找表的各种查找方法如二叉排序树与平衡二叉树，B树等；
(4) 哈希表的概念和查找方法和哈希函数的构造方法、解决冲突的基本方法；
（九）排序
1．考核知识点
直接插入排序；希尔排序；冒泡排序；快速排序；堆排序；归并排序；基数排序。
2．考核内容
(1) 排序的基本概念；
(2) 基于插入思想的排序算法如：直接插入排序、希尔排序；
(3) 基于交换思想的排序算法如：冒泡排序、快速排序；
(4) 基于选择思想的排序算法如：简单选择排序、堆排序；
(5) 其它排序算法如：归并排序、基数排序；

 
 参考书目：
《数据结构（C语言版）》，严蔚敏等，清华大学出版社，2018年