2023考研大纲：常州大学2023年考研初试科目 858数据结构 考试大纲

科目代码、科目名称:

858数据结构

一、基本内容

1．绪论

了解数据结构的基本概念，抽象数据类型的概念、记法和用法，以及该记法和面向对象程序设计的关系；了解高级语言的基本构造和控制结构，数据存储的特点，指针、链表概念和相关操作对本课程的影响；了解算法时间复杂度和空间复杂度的概念和基本分析方法。理解数据结构的重要性和相关课程的关系。掌握程序设计基本技巧，多个分析的范例和相应的结论。

2.线性表

了解线性表结构的用途和性质，循环链表和双向链表的原理和相关的算法设计；掌握线性表的基本概念和类型定义，线性表的顺序存储结构和相应的算法设计以及该结构下相应操作示意图的画法，掌握线性表的链接存储结构和相应的算法设计，特别是单链表的查找、插入和删除等基本操作的算法，掌握循环链表和双向链表的原理和相关的算法设计结构下相应操作示意图的画法；能够从时间和空间复杂度的角度比较顺序存储结构和链接存储结构的不同特点及适用场合，明确它们各自的优缺点。

3.栈和队列

了解栈结构的用途和性质，栈的应用范例，队列结构的用途和性质；理解和掌握栈的基本概念和类型定义，栈的链接存储结构和相应的操作示意图的画法，掌握栈的链接存储结构下相应的算法设计；掌握队列的基本概念和类型定义，队列的顺序存储(循环队)和链接存储结构下相应的算法设计以及该结构下相应操作示意图的画法；能够灵活运用栈和队列设计解决实际应用问题，掌握表达式求值算法，深刻理解递归算法执行过程中栈的状态变化过程。

4.串

了理解串的基本概念；掌握串的基本操作的算法，以及串的存储结构；理解串的模式匹配算法，尤其是KMP算法，了解串操作应用举例。

5.数组和广义表

明确数组和广义表这两种数据结构的特点；掌握数组存储时地址计算方法；掌握几种特殊矩阵的压缩存储方法；了解广义表的定义和存储结构，以及其求表头和表尾的运算。

6.树和二叉树

了解树的定义、性质和表示方法，树的各种遍历方法及实现，了解相应的算法设计；掌握树与二叉树、森林与二叉树之间的相互转换方法；理解非线性结构的特点和存储实现的困难；掌握二叉树的定义、性质和存储结构，能够正确画出相应结构的示意图；掌握二叉树的先根遍历、中根遍历、后根遍历和按层次遍历的原理及实现，掌握相应的算法设计；掌握线索化二叉树的基本概念和构造方法；掌握哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生，掌握相应的算法设计。

7.图

掌握图的基本概念和术语；掌握图的4种存储结构，明确各自的特点和适用场合；掌握图的深度和广度搜索遍历算法；了解图的连通性问题，以及有向无环图及其应用；掌握图在实际应用中的主要算法：最小生成树、最短路径、拓扑排序和关键路径的求解过程和算法。

8.查找

理解顺序查找、折半查找和分块查找的原理，掌握相应的算法设计，掌握描述折半查找过程的判定树的构造方法；掌握二叉排序树的构造和查找方法，掌握相应的算法设计；掌握平衡二叉树的4种平衡调整方法；理解B-和B+树的特点、基本操作和二者的区别；理解掌握哈希查找的原理，了解相应的算法设计；掌握哈希冲突的解决方法；具有应用适当的查找方法解决实际问题的能力；具备平均查找长度的求解和分析能力。

9.排序

掌握与排序相关的基本概念，深刻理解各种内部排序方法的基本思想、特点、实现方法及其性能分析，能从时间、空间、稳定性各个方面对各种排序方法做综合比较，并能加以灵活应用。了解归并排序的原理和相应的算法设计；了解基数排序的原理和相应的算法设计；理解和掌握直接插入排序的原理和相应的算法设计；理解和掌握冒泡排序和快速排序的原理和相应的算法设计；理解和掌握直接选择排序和堆排序的原理和相应的算法设计。

二、考试要求（包括题型、分数比例、是否使用计算器等）

1、考试形式为闭卷、笔试，考试时间为

3

小时，不使用计算器。

?

2、满分

150

分，题型包括：选择题、概念解释题、解答题、算法设计题等。其中，选择题占比约10%、概念解释题占比约20%、解答题占比约90%、算法设计题占比约30%。