西安理工大学计算机科学与工程学院
硕士研究生入学考试课程《数据结构》考试大纲
科目代码：863
科目名称：数据结构
第一部分 考试说明
一、考试性质
数据结构是计算机各专业的专业基础课。考核目标是测试计算机科学与技术及相近各
专业的本科毕业生对于该课程的知识掌握程度,以保证被录取者具有本学科基本的专业理论
基础及程序设计能力,以利于计算机科学与技术及软件工程学科的导师择优选拔硕士研究
生。
考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。
二、考试范围
各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各种基本查找表
的概念、特征及其查找方法；基本的内排序方法及其应用；用 C 语言(或 C++)进行算法描述,
并对算法进行分析。
三、评价目标
考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和
解决实际问题的能力,注重考查算法和程序设计的能力。
具体要求见本考试大纲第二部分的“考查要点”。
四、考试形式与试卷结构
1.答卷方式:闭卷,笔试。
2.答题时间:180 分钟。
3.考查内容及其考查比例
基本概念、基本知识、基本方法约占 50%～60%；综合应用、算法和程序设计与算法分
析约占 50%～40%。
4.试卷结构与考试题型
试卷共 150 分,基本的考试题型有：
(1)单项选择题和多项选择题；
(2)填空题(基本概念、基本知识、基本方法)；
(3)简答题；
(4)应用题(求解问题)；
(5)算法和程序设计与分析题；
五、教材和参考书
教材: 《数据结构》(C 语言版)，严蔚敏、吴伟民编著,清华大学出版社,2009.6
第二部分 考查要点
1.数据结构基本概念和术语
了解数据元素、数据结构、抽象数据类型、存储结构等概念；算法概念及算法设计
的基本要求 ；
掌握算法分析方法、语句的频度和估算时间复杂度、空间复杂度分析方法。
2.线性表
理解线性表的定义和基本操作；线性表的抽象数据类型定义；
掌握线性表的顺序存储结构及应用方法；
掌握线性表的链式存储结构(单链表,双链表,循环链表)。
3.栈和队列
理解栈的定义和基本操作及栈的抽象数据类型定义；
掌握顺序栈及链式栈的操作方法；
掌握栈在递归算法、 算术表达式求值及其它应用。
理解队列的定义和基本操作及队列的抽象数据类型；
掌握顺序队列及链式队列的操作方法；应用举例。
4.字符串
理解字符串的定义和基本操作及字符串的存储结构；
掌握字符串的基本操作；
了解字符串模式匹配应用。
5.数组
理解数组的定义和基本操作；
掌握数组的顺序存储结构及应用；
掌握特殊矩阵和稀疏矩阵的压缩存储。
6.树和二叉树
理解树的基本概念和基本操作,树的抽象数据类型。
理解二叉树的概念和性质,特殊二叉树及二叉树的存储结构；
掌握二叉树的生成与建立。
掌握遍历二叉树：前序遍历,中序遍历,后序遍历,层次遍历。
掌握线索二叉树的概念和存储结构,二叉树的线索化,线索二叉树的遍历。
理解树的存储结构；
掌握树与二叉树之间的转换,森林与二叉树之间的转换,森林的遍历方法。
掌握树的路径长度和带权路径长度；
理解哈夫曼树(Huffman)的概念,并掌握哈夫曼算法, 哈夫曼编码树。
7.图
理解图的基本概念和基本操作，图的抽象数据类型。
掌握图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表，十字链表；邻接
多重表。
掌握图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量。
理解生成树、最小生成树的概念，并掌握克鲁斯卡尔(Kruskal)算法,普里姆(Prim)
算法。
掌握从一个顶点到其余各顶点的最短路径,每对顶点之间的最短路径。
9.查找
理解查找的概念,关键字比较次数,平均查找长度。
掌握顺序表的查找:顺序查找,折半查找,分块查找方法。
掌握树表的查找:二叉排序树,二叉排序树的的概念和基本操作,二叉排序树的建立,
二叉排序树其它操作实现。平衡二叉树。
掌握哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找
方法,冲突处理方法。
10.排序
理解排序的稳定性、比较关键字次数、移动记录次数、顺序表的排序、链接表(单
链表)等排序概念。
掌握若干内排序方法与算法：
a)交换排序:冒泡排序,快速排序。
b)插入排序:直接插入排序,2 路插入排序,折半插入排序,希尔排序。
c)选择排序:直接选择排序,堆排序。
d)归并排序。
e)基数排序。
掌握各种排序算法的评价，了解其应用。
您现在的位置： 