武汉工程大学2024年硕士研究生复试算法与数据结构考试大纲一、课程总体要求考生应认真把握该课程的考试、学习要求、考核知识点和有关考核的具体问题。 要求数据结构算法设计题编程全部采用C语言。1、基本理论知识(l)什么是数据结构、基本概念和基本术语、数据结构的发展简史及它在计算机科学中所处的地位,算法的描述和算法分析。(2)什么是线性表、在线性表上常进行的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。(3)栈和队列的定义、表示方法和实现。(4)串的定义及其基本操作。(5)数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和操作。(6)树的定义、基本术语和存储结构、二叉树的定义和性质,二叉树的存储结构及其各种操作,哈夫曼树。(7)图的定义和术语、图的存储结构及其各种操作。(8)各种查找方法的算法、适用范围及时间复杂度的分析。(9)内部排序、基数排序和比较排序,各种基本排序方法的算法和时间复杂度。2、基本技能(1)能阅读用类C语言编写的算法。(2)能分析算法所完成的功能、运行结果和时间复杂度。(3)能根据要求用类C语言编写算法。二、考核知识点第一章 绪论1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。2.实现关系的两种方法(顺序和链式)及相应的存储结构。3.算法、算法的特性、如何用类C语言来描述算法。4.评价算法好坏的主要标准、“0(f(n)"的形式定义、了解算法的渐近时间复杂度、语句的频度、最坏情况时间复杂度和平均时间复杂度的概念。第二章 线性表1.线性表的定义和操作。2.顺序存储线性表的实现和运算。3.链式存储线性表(静态链表和动态链表),带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链 表的实现和查找对插入、删除等基本操作。4.链表应用举例一一一元多项式的表示及相加的算法。第三章 栈和队列1.栈和队列的定义及其存储结构、循环队列。2.栈和队列的主要运算。3.栈的应用举例一一表达式求值的过程。第四章 串1.串的定义、空串、空格串。2.串的基本操作。3.串的顺序存储结构及在顺序存储结构下基本操作的实现。第五章 数组和广义表1.数组的顺序存储结构。2.二维数组的按行存储及按列存储和计算数组元素的地址计算公式。3.矩阵的压缩存储、特殊矩阵的表示。4.广义表的定义和操作(HEAD和TAIL)。第六章 树和二叉树1.树的定义和术语。2.树的存储表示法孩子表示法、双亲表示法、孩子兄弟表示法。3.树和森林转换为二叉树的方法。4.二叉树(完全;二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构顺序表示法和二叉链表表示法。5.二叉树遍历的递归算法。6.树的路径长度、树的带权路径长度、Huffman树的构造方法。第七章 图1.图的定义。2.图的基本术语。(1)图及无向图、有向图、网、子图、连通图、强连通图。(2)顶点的度、入度、出度。(3)顶点间路径、路径长度、环。3.图的存储结构(l)邻接矩阵。(2)邻接表(含逆邻接表)。4.遍历图(l)深度优先插索遍历图的算法及其时间复杂度。(2)广度优先插索遍历图的算法及其时间复杂度。5.生成树(1)生成树、最小生成树的概念。(2)最小生成树的算法(Prim算法和Kruskai算法)及其时间复杂度。6.最短路径(l)求源点到其余各顶点间的最短路径。DijKstra算法的思想及其时间复杂度。(2)求各顶点对间的最短路径。Floyed算法的思想及其时间复杂度。第九章 查找1.查找的定义关键字、查找、平均查找长度。2.静态查找表的查找算法及其效率(最坏和平均长度)。(l)顺序查找。(2)折半查找。(3)分块查找(索引顺序表的查找)。3.动态查找表(1)二叉排序树的查找算法及其效率。(2)平衡二叉树(AVid树)的定义。4.哈希表(l)哈希法的特点。(2)哈希函数和散列地址。(3)构造哈希函数的几种方法。直接定址法、除留余数法、平方取中法、折叠法、数字分析法。(4)处理冲突的方法。冲突的处理,开放定址法和链地址法,开放定址法又分为线性探测再散列、二次探测再散列和伪随机探测再散列。第十章 内部排序1.排序的目的、分类和排序方法的稳定性的定义。2.插入排序。 (1)直接插入排序的算法。 (2)折半插入排序的算法。3.希尔排序的思想。4.选择排序的思想。5.堆排序的方法、堆的定义、初始堆的求取。6.起泡排序的思想。7.快速排序的算法、快速排序的最坏情况时间复杂度的分析。8.归并排序的思想、影响归并排序稳定性的因素。9.基数排序的思想及特点。三、考试要求（包括考试时间、总分、考试方式、题型、分数比例等）考试时间2小时，总分100分，考试方式为闭卷考试，试卷题型及分数比例为:选择题和判断题共40分；简答题30分; 算法设计题：30分;四、主要参考书目1、严蔚敏,李冬梅,吴伟民.数据结构(C语言版 第2版)M.北京：清华大学出版社, 2015年2、秦友淑，曹化工.C语言程序设计教程（第二版）M.武汉：华中科技大学出版社，2002年