|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
2021年硕士研究生自命题科目考试大纲
|
科目代码、科目名称:
|
858 数据结构
|
| 一、基本内容
1．绪论
了解数据结构的基本概念，抽象数据类型的概念、记法和用法，以及该记法和面向对象程序设计的关系；了解高级语言的基本构造和控制结构，数据存储的特点，指针、链表概念和相关操作对本课程的影响；了解算法时间复杂度和空间复杂度的概念和基本分析方法。理解数据结构的重要性和相关课程的关系。掌握程序设计基本技巧，多个分析的范例和相应的结论。
2.线性表
了解线性表结构的用途和性质，循环链表和双向链表的原理和相关的算法设计；掌握线性表的基本概念和类型定义，线性表的顺序存储结构和相应的算法设计以及该结构下相应操作示意图的画法，掌握线性表的链接存储结构和相应的算法设计，特别是单链表的查找、插入和删除等基本操作的算法，掌握循环链表和双向链表的原理和相关的算法设计结构下相应操作示意图的画法；能够从时间和空间复杂度的角度比较顺序存储结构和链接存储结构的不同特点及适用场合，明确它们各自的优缺点。
3.栈和队列
了解栈结构的用途和性质，栈的应用范例，队列结构的用途和性质；理解和掌握栈的基本概念和类型定义，栈的链接存储结构和相应的操作示意图的画法，掌握栈的链接存储结构下相应的算法设计；掌握队列的基本概念和类型定义，队列的顺序存储(循环队)和链接存储结构下相应的算法设计以及该结构下相应操作示意图的画法；能够灵活运用栈和队列设计解决实际应用问题，掌握表达式求值算法，深刻理解递归算法执行过程中栈的状态变化过程。
4.串
了理解串的基本概念；掌握串的基本操作的算法，以及串的存储结构；理解串的模式匹配算法，尤其是KMP算法，了解串操作应用举例。
5.数组和广义表
明确数组和广义表这两种数据结构的特点；掌握数组存储时地址计算方法；掌握几种特殊矩阵的压缩存储方法；了解广义表的定义和存储结构，以及其求表头和表尾的运算。
6.树和二叉树
了解树的定义、性质和表示方法，树的各种遍历方法及实现，了解相应的算法设计；掌握树与二叉树、森林与二叉树之间的相互转换方法；理解非线性结构的特点和存储实现的困难；掌握二叉树的定义、性质和存储结构，能够正确画出相应结构的示意图；掌握二叉树的先根遍历、中根遍历、后根遍历和按层次遍历的原理及实现，掌握相应的算法设计；掌握线索化二叉树的基本概念和构造方法；掌握哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生，掌握相应的算法设计。
7.图
掌握图的基本概念和术语；掌握图的4种存储结构，明确各自的特点和适用场合；掌握图的深度和广度搜索遍历算法；了解图的连通性问题，以及有向无环图及其应用；掌握图在实际应用中的主要算法：最小生成树、最短路径、拓扑排序和关键路径的求解过程和算法。
8.查找
理解顺序查找、折半查找和分块查找的原理，掌握相应的算法设计，掌握描述折半查找过程的判定树的构造方法；掌握二叉排序树的构造和查找方法，掌握相应的算法设计；掌握平衡二叉树的4种平衡调整方法；理解B-和B+树的特点、基本操作和二者的区别；理解掌握哈希查找的原理，了解相应的算法设计；掌握哈希冲突的解决方法；具有应用适当的查找方法解决实际问题的能力；具备平均查找长度的求解和分析能力。
9.排序
掌握与排序相关的基本概念，深刻理解各种内部排序方法的基本思想、特点、实现方法及其性能分析，能从时间、空间、稳定性各个方面对各种排序方法做综合比较，并能加以灵活应用。了解归并排序的原理和相应的算法设计；了解基数排序的原理和相应的算法设计；理解和掌握直接插入排序的原理和相应的算法设计；理解和掌握冒泡排序和快速排序的原理和相应的算法设计；理解和掌握直接选择排序和堆排序的原理和相应的算法设计。
|
| 二、考试要求（包括题型、分数比例、是否使用计算器等）
1、考试形式为闭卷、笔试，考试时间为3小时，不使用计算器。
2、满分150分，题型包括：选择题、概念解释题、解答题、算法设计题等。其中，选择题占比约10%、概念解释题占比约20%、解答题占比约90%、算法设计题占比约30%。
|
| 三、主要参考书目
[1] 严蔚敏,李冬梅,吴伟民.数据结构（C语言版|第2版）.北京:人民邮电出版社,2015
[2] 李冬梅,张琪.数据结构习题解析与实验指导.北京:人民邮电出版社,2017
[3] 闫玉宝等.数据结构(第二版).北京:清华大学出版社,2014
[4] 严蔚敏,吴伟民,米宁.数据结构题集(C 语言版).北京:清华大学出版社,2003
[5] 王红梅,胡明,王涛.数据结构(C++版)学习辅导与实验指导.北京:清华大学出版社,2007
|
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
