2017上海理工大学数据结构考试大纲
求学快递网考研专题重点推荐：考研专业课大纲、2016年考研专业课考试性质、考研专业课考试形式、考研专业课考查内容、考研专业课试卷结构、2016年专业课最新考试资料、历年考研专业课资料、考研专业课重点规划等资讯，给考生朋友们参考。 下面是求学快递网整理的上海理工大学2017年考研848数据结构及操作系统之数据结构考试大纲，以供各位考生参考。 《数据结构及操作系统》考试大纲 第一部分：数据结构 一、参考书目 数据结构(第二版)，严蔚敏主编，2006，清华大学出版社。 二、 考试内容要求 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) 图的存储表示：邻接矩阵;邻接表;邻接多重表 3) 图的遍历与连通性：深度优先搜索;广度优先搜索;连通分量;重连通分量 4) 最小生成树：克鲁斯卡尔算法;普里姆算法 5) 活动网络：用顶点表示活动的网络;用边表示活动的网络 9、排序 1) 插入排序：直接插入排序;对分插入排序;链表插入排序;希尔排序 2) 交换排序：起泡排序;快速排序 3) 选择排序：直接选择排序;锦标赛排序;堆排序 4) 归并排序：归并;迭代的归并排序算法;递归的表归并排序 5) 基数排序：多关键码排序;链式基数排序 6) 外排序：外排序的基本过程;k路平衡归并;初始归并段的生成;最佳归并树 10、索引与散列结构 1) 静态索引结构：线性索引;倒排表;m路静态查找树 2) 动态索引结构：动态的m路查找树;b_树;b_树的插入;b_树的删除;b+树 3) 散列：词典的抽象数据类型;散列表与散列方法;散列函数;处理溢出的闭散列方法;处理溢出的开散列方法;散列表分析
求学快递网考研专题的小编们根据网民搜索习惯第一时间公布了考研考试资讯、考研报考指南、考研复试与调剂、考研英语、考研政治、考研数学、考研专业课、考研综合复习指导、考研招生推荐等相关资讯，给考生朋友们提供学习和参考，祝考生朋友们顺利通过考试。
求学快递网考研专题重点推荐：考研专业课大纲、考研专业课真题、考研专业课试题和考研专业课辅导等最新考研信息，让您轻松备战考研！
