2011年上海理工大学数据结构及计算机组成原理考研大纲_跨考网

《数据结构及计算机组成原理》考试大纲和参考书目

　　第一部分 数据结构

　　第一章 绪论

　　明确数据结构的定义、研究的内容，掌握算法及算法分析的概念，了解抽象数据类型的概念。

　　第二章 线性表

　　掌握线性表的概念，两种存储结构顺序表和链表的表示和实现、掌握链表（单链表、单循环链表和双向链表）上的查找、插入、删除基本操作及能编写链表上的综合操作程序。

　　第三章 栈和队列

　　掌握栈的概念，掌握顺序栈、链栈的进栈、出栈操作程序。能利用栈写出表达式求值过程，能用栈读写递归程序。

　　掌握队列的概念，掌握循环队列、循环链队列的入队、出队操作程序。

　　第四章 串

　　掌握串的基本运算的含义，掌握求子串位置的定位函数，理解KMP模式匹配算法和时间复杂度。

　　第五章 多维数组和广义表

　　掌握多维数组及特殊矩阵的地址公式，广义表的运算和存储。了解广义表的递归算法。

　　第六章 树和二叉树。

　　掌握树、二叉树的定义、术语，二叉树的性质，掌握二叉树的递归和非递归遍历算法，掌握中序线索二叉树的概念和遍历算法，掌握Haffman树及其应用，了解树与二叉树的关系，了解回溯法与树的遍历。

　　第七章 图

　　掌握图的定义、术语，掌握图的存储，图的遍历算法，掌握最小生成树、拓扑排序、关键路径、最短路径概念，了解其算法。

　　第九章 查找

　　掌握有序表的查找算法和查找的时间复杂度，掌握二叉排序树的查找、插入和删除算法，掌握平衡二叉树和B-树的插入、删除概念。

　　掌握哈希表构造、解决冲突的方法及哈希表的查找。

　　第十章 内部排序

　　掌握直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序和希尔排序算法和时间复杂度，了解基数排序的概念。

　　专业课《数据结构》考试大纲和参考书目

　　参考教材:《数据结构·C语言版》 , 严蔚敏主编 , 清华大学出版社

　　参考用书:《数据结构习题详解》, 李春葆编著, 清华大学出版社

　　课程内容（无标记章节一般了解、不考，打*号标记章节要求掌握，打**号标记章节要求重点掌握）

　　绪论

　　数据结构定义

　　基本概念和术语

　　*算法描述和算法分析

　　抽象数据类型的表示和实现

　　线性表

　　线性表的基本概念

　　线性表顺序表示和实现

　　线性表的链式表示和实现：

　　**线性链表

　　**循环链表

　　*双向链表

　　顺序存储结构与链式存储结构的比较

　　**线性表的应用举例

　　栈和队列

　　*抽象数据类型栈的定义

　　*栈的表示和实现

　　栈的应用举例：

　　迷宫求解

　　**表达式求值

　　**栈与递归的实现

　　*抽象数据类型队列的定义

　　*链队列—队列的链式表示和实现

　　**循环队列—队列的顺序表示和实现

　　串

　　串类型的定义

　　串的表示和实现

　　**串的模式匹配算法

　　串的应用举例

　　数组和广义表

　　数组的定义

　　*数组的顺序表示和实现

　　*矩阵的压缩存储：

　　特殊矩阵

　　稀疏矩阵

　　*广义表的概念

　　*广义表的存储

　　广义表的应用举例

　　树和二叉树

　　树的定义和基本术语

　　*二叉树：

　　二叉树的定义

　　二叉树的性质

　　二叉树的存储结构

　　**二叉树的遍历

　　**线索二叉树

　　树和森林：

　　树的存储结构

　　静态链表

　　树、森林和二叉树的转换

　　树的遍历

　　*树的应用举例：

　　哈夫曼树

　　哈夫曼编码

　　回溯法与树的遍历

　　图

　　*图的定义和基本术语

　　图的存储结构：

　　**邻接矩阵

　　**邻接表

　　十字链表

　　邻接多重表

　　**图的遍历：

　　深度优先搜索遍历

　　广度优先搜索遍历

　　*最小生成树：

　　生成树和最小生成树

　　普里姆算法

　　克鲁斯卡尔算法

　　有向无环图及应用：

　　*拓扑排序

　　关键路径

　　最短路径

　　查找

　　查找基本概念

　　顺序表的查找：

　　顺序查找

　　**有序表的查找

　　分块查找