考研大纲>专业课大纲#2019年上海理工大学869*数据结构及软件工程*考研究生大纲[下载版]

类目：三人行考研网>考研大纲>专业课大纲>正文

时间：2020-07-2718:30:30

一 、参考书目

《数据结构》(C语言版) ，严蔚敏等主编
，清华大学出版社，2012年

二
、考试内容要求

1、了解数据结构及其分类 、数据结构与算法的密切关系 。

2
、熟悉各种基本数据结构及其操作 ，学会根据实际问题要求来选择数据结构
。

3、掌握设计算法的步骤和算法分析方法。

4 、掌握数据结构在排序和查找等常用算法中的应用 。

5
、初步掌握文件组织方法和索引技术
。

三、考试内容

1 、数据结构基本概念及简单的算法分析

1)什么是数据结构

2)抽象数据类型及面向对象概念：数据类型;数据抽象与抽象数据类型;面向对象的概念;用于描述数据结构的语言

3)数据结构的抽象层次

4)算法定义

5)性能分析与度量：算法的性能标准;算法的后期测试;算法的事前估计;空间复杂度度量;时间复杂度度量;时间复杂度的渐进表示法;渐进的空间复杂.

2、数组

1)作为抽象数据类型的数组：数组的定义和初始化;作为抽象数据类型的数组;数组的顺序存储方式

2)顺序表：顺序表的定义和特点;顺序表的类定义;顺序表的查找
、插入和删除;使用顺序表的事例

3)字符串：字符串的抽象数据类型;字符串操作的实现;字符串的模式匹配

3、链表

1)单链表：单链表的结构;单链表的类定义;单链表中的插入与删除;带表头结点的单链表;用模板定义的单链表类;单链表的游标类;静态链表

2)循环链表：循环链表的类定义;用循环链表解约瑟夫问题;多项式及其相加：多项式的类定义;多项式的加法

3)双向链表

4 、栈和队列

1)栈：栈的抽象数据类型;栈的顺序存储表示;栈的链接存储表示

2)队列：队列的抽象数据类型;队列的顺序存储表示;队列的链接存储表示;3)队列的应用举例

4)优先级队列：优先级队列的定义;优先级队列的存储表示

5
、递归

1)递归的概念

2)迷宫问题

3)递归过程与递归工作栈

4)利用栈实现的迷宫问题非递归解法

5)广义表：广义表的概念;广义表的表示及操作;广义表存储结构的实现;广6)义表的访问算法;广义表的递归算法

6、树与森林

1)树和森林的概念：树的定义;树的术语;树的抽象数据类型

2)二叉树：二叉树的定义;二叉树的性质;二叉树的抽象数据类型

3)二叉树的表示：数组表示;链表存储表示

4)二叉树遍历：中序遍历;前序遍历;后序遍历;应用二叉树遍历的事例;二叉树遍历的游标类;不用栈的二叉树中序遍历算法

5)线索化二叉树：线索;中序线索化二叉树;前序与后序的线索化

6)堆：堆的定义;堆的建立;堆的插入与删除

7)树与森林：树的存储表示;森林与二叉树的转换;树的遍历;森林的遍历

二叉树的计数

8)霍夫曼树：路径长度;霍夫曼树;霍夫曼编码

7 、集合与搜索

1)集合及其表示：集合基本概念;以集合为基础的抽象数据类型;用位向量实现集合抽象据类型;用有序链表实现集合的抽象数据类型

2)等价类：等价关系与等价类;确定等价类的链表方法;并查集

3)简单的搜索结构：搜索的概念;静态搜索结构;顺序搜索;基于有序顺序表的对分搜索

4)二叉搜索树：定义;二叉搜索树上的搜索;二叉搜索树的插入;二叉搜索树的删除;与二叉搜索树相关的中序游标类

5)AVI树：AVI树的定义;平衡化旋转;AVI树的插入和删除;AVI树的高度

8
、图

1)图的基本概念：图的基本概念;图的抽象数据类型

2)图的存储表示：邻接矩阵;邻接表;邻接多重表

2019年上海理工大学869《数据结构及软件工程》考研大纲（下载版）