2020年中国石油大学（北京）《数据结构》考试大纲.docx

新祥旭考研官网 http:/www.xxxedu.net/2020 年中国石油大学（北京） 数据结构考试大纲第一部分 考试说明一、考试性质数据结构是计算机各专业的专业基础课。它的评价标准是高等学校计算机科学与技术各专业本科毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的专业理论基础及程序设计能力，以利于计算机科学与技术各专业的导师择优选拔硕士研究生。二、考试要求 考生能够理解数据结构的基本概念；掌握数据结构中逻辑结构、存储结构的基本概念和差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析；能够选择合适的数据结构和方法进行问题求解；能够针对具体问题设计正确的数据结构加以应用；具备采用 C 语言(或 C+)语言设计与实现算法的能力。本课程包括：算法的基本概念、分析和设计方法；软件开发中常用的各类结构，包括线性结构、树结构、图结构；查找、排序等各类常用算法。主要考察学生对数据结构基础知识的理解、是否具备对现有常用结构和算法的应用能力、是否具备针对具体应用设计合适数据结构的能力。三、主要参考书目数据结构(C 语言版)，严蔚敏、吴伟民编著,清华大学出版社,1997.4数据结构（AR），连远锋、吴双元编著，清华大学出版社，2019.9第二部分 考查要点1.数据结构和算法数据结构、存储结构的概念；数据类型与抽象数据类型；算法的概念,用 C/C+描述算法和程序设计,算法分析初步。2.线性表线性表的定义和基本操作；线性表的抽象数据类型；线性表的顺序存储结构，应用举例；线性表的链式存储结构(单链表,双链表,循环链表),应用举例。3.栈栈的定义和基本操作；栈的抽象数据类型；顺序栈，链式栈；栈和递归算法, 算术表达式求值,其它应用。4队列队列的定义和基本操作；队列的抽象数据类型；顺序队列，链式队列；双端队列的定义和基本操作；应用举例。5.数组和字符串数组的定义和基本操作；数组的顺序存储结构，应用举例；特殊矩阵和稀疏矩阵的压缩存储。 字符串的定义和基本操作,字符串的存储结构,字符串操作的实现举例,字符串和模式匹配。6.树和二叉树(1)树的基本概念和基本操作,树的抽象数据类型。(2)二叉树的概念和性质,特殊二叉树；二叉树的存储结构；(3)二叉树的生成与建立。 (4)遍历二叉树：前序遍历,中序遍历,后序遍历,层次遍历。(5)二叉树其它操作实现举例。(6)线索二叉树的概念和存储结构,二叉树的线索化,线索二叉树的遍历。新祥旭考研官网 http:/www.xxxedu.net/(7)树的存储结构,树与二叉树之间的转换,森林与二叉树之间的转换,树和森林的遍历。(8)树的路径长度和带权路径长度,哈夫曼树(Huffman)的概念,哈夫曼算法, 哈夫曼编码树。(9)二叉排序树的的概念和基本操作,二叉排序树的建立,二叉排序树其它操作实现举例。7.图(1)图的基本概念和基本操作，图的抽象数据类型。(2)图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表，十字链表；邻接多重表。(3)图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量。(4)生成树、最小生成树的概念；克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法。(5)从一个顶点到其余各顶点的最短路径,每对顶点之间的最短路径。(6)拓扑排序和关键路径8.查找(1)查找的概念,关键字比较次数,平均查找长度。(2)顺序表的查找:顺序查找,折半查找,分块查找。(3)树表的查找:二叉排序树,平衡二叉树。(4)哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找,冲突处理方法。9.排序(1)排序的概念；排序的稳定性；比较关键字次数,移动记录次数。(2)内排序方法与算法：交换排序:冒泡排序,快速排序。插入排序:直接插入排序,2 路插入排序,折半插入排序,希尔排序。接选择排序,锦标赛排序,堆排序。归并排序。基数排序。(3)各种排序算法的评价和应用。