一、考试性质

　　本课程是人工智能专业、机器人专业和大数据科学专业的专业基

　　础必修课，其涵盖知识是相关专业研究生开展创新研究必须具备的基

　　础。

　　二、考查目标

　　本课程主要考核线性表、树、图数据结构表示方法、操作及应用；

　　常用查找与排序算法；算法时间、空间复杂度分析等。

　　三、适用范围

　　本考试大纲适用于我校人工智能学院的081200计算机科学与技

　　术和085410人工智能专业的硕士研究生招生考试。

　　四、考试形式和试卷结构

　　（一）试卷满分及考试时间

　　试卷满分：150分；考试时间：180分钟。

　　（二）试卷内容结构

　　1)数据结构及算法的基础知识：约25分；

　　2)数据结构及算法的应用与分析：约95分；

　　3)数据结构及算法的代码分析、设计与实现：约30分。

　　（三）试卷题型结构及分值比例

　　五、考查内容

　　1．绪论

　　（1）数据结构的研究内容

　　（2）基本概念和术语

　　（3）抽象数据类型的表示与实现

　　（4）算法和算法分析

　　2．线性表

　　（1）线性表的定义和特点

　　（2）线性表的类型定义

　　（3）线性表的顺序表示和实现

　　（4）线性表的链式表示和实现

　　（5）顺序表和链表的比较

　　（6）线性表的应用

　　3.栈和队列

　　（1）栈和队列的定义和特点

　　（2）栈的表示和操作的实现

　　（3）栈与递归

　　（4）队列的表示和操作的实现

　　（5）栈与队列的应用：表达式计算；迷宫问题等

　　4.串、数组和广义表

　　（1）串的类型定义、存储结构及其运算

　　（2）数组的定义、存储以及特殊矩阵的压缩存储

　　5.树和二叉树

　　（1）树和二叉树的定义

　　（2）树和二叉树的抽象数据类型定义=（3）二叉树的性质和存储结构

　　（4）遍历二叉树和线索二叉树

　　（5）树和森林

　　（6）哈夫曼树及其应用

　　6.图

　　（1）图的定义和基本术语

　　（2）案例引入

　　（3）图的类型定义

　　（4）图的存储结构

　　（5）图的遍历

　　（6）图的应用：最小生成树、最短路径、拓扑排序、关键路径等

　　7.查找

　　（1）查找的基本概念

　　（2）线性表的查找：顺序查找、折半查找、分块查找

　　（3）树表的查找：二叉排序树、平衡二叉树、B-树、B+树

　　（4）散列表的查找

　　8.排序

　　（1）基本概念和排序方法概述

　　（2）插入排序：直接插入排序、折半插入排序、希尔排序

　　（3）交换排序：冒泡排序、快速排序

　　（4）选择排序：简单选择排序、树形选择排序、堆排序

　　（5）归并排序

　　（6）基数排序

　　（7）外部排序

　　（8）各种排序时间、空间复查度和算法稳定性等方面综合比较

　　六、参考书目

　　严蔚敏，李冬梅，吴伟民.数据结构（C语言版）（第2版），人民邮电出版社，2017年