首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 考研报考 > 考研院校信息 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

上海理工大学光电信息与计算机工程学院考试大纲

2015-09-06 14:54:42来源：新东方在线

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

　　第一部分数据结构

　　参考教材：

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

　　第一章绪论

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

　　第二章线性表

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

　　第三章栈和队列

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

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

　　第四章串

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

　　第五章多维数组和广义表

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

　　第六章树和二叉树。

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

　　第七章图

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

　　第九章查找

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

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

　　第十章内部排序

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

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

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

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

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

　　绪论

　　数据结构定义

　　基本概念和术语

　　*算法描述和算法分析

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

　　线性表

　　线性表的基本概念

　　线性表顺序表示和实现

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

　　**线性链表

　　**循环链表

　　*双向链表

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

　　**线性表的应用举例

　　栈和队列

　　*抽象数据类型栈的定义

　　*栈的表示和实现

　　栈的应用举例：

　　迷宫求解

　　**表达式求值

　　**栈与递归的实现

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

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

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

　　串

　　串类型的定义

　　串的表示和实现

　　**串的模式匹配算法

　　串的应用举例

　　数组和广义表

　　数组的定义

　　*数组的顺序表示和实现

　　*矩阵的压缩存储：

　　特殊矩阵

　　稀疏矩阵

　　*广义表的概念

　　*广义表的存储

　　广义表的应用举例

　　树和二叉树

　　树的定义和基本术语

　　*二叉树：

　　二叉树的定义

　　二叉树的性质

　　二叉树的存储结构

　　**二叉树的遍历

　　**线索二叉树

　　树和森林：

　　树的存储结构

　　静态链表

　　树、森林和二叉树的转换

　　树的遍历

　　*树的应用举例：

　　哈夫曼树

　　哈夫曼编码

　　回溯法与树的遍历

　　图

　　*图的定义和基本术语

　　图的存储结构：

　　**邻接矩阵

　　**邻接表

　　十字链表

　　邻接多重表

　　**图的遍历：

　　深度优先搜索遍历

　　广度优先搜索遍历

　　*最小生成树：

　　生成树和最小生成树

　　普里姆算法

　　克鲁斯卡尔算法

　　有向无环图及应用：

　　*拓扑排序

　　关键路径

　　最短路径

　　查找

　　查找基本概念

　　顺序表的查找：

　　顺序查找

　　**有序表的查找

　　分块查找

　　8.3树表的查找

　　*8.3.1二叉搜索树

　　*8.3.2平衡二叉树

　　8.3.3B_树

　　8.3.4B+树

　　*8.4哈希表

　　8.4.1哈希表的基本概念

　　8.4.2构造哈希函数的方法

　　8.4.3解决哈希冲突的方法

　　8.4.4哈希表的查找

　　*第九章排序

　　9.1排序的基本概念

　　9.2插入排序

　　9.2.1直接插入排序

　　9.2.2希尔排序

　　9.3交换排序

　　9.3.1冒泡排序

　　9.3.2快速排序

　　9.4选择排序

　　9.4.1直接选择排序

　　9.4.2堆排序

　　9.5归并排序

　　9.6基数排序

　　9.7各种内部排序方法比较

　　9.8外排序

　　**二叉排序树

　　*平衡二叉树

　　*B_树

　　B+树

　　哈希表：

　　*哈希表的基本概念

　　构造哈希函数的方法

　　*解决哈希冲突的方法

　　*哈希表的查找

　　内部排序

　　排序的基本概念

　　**插入排序：

　　直接插入排序

　　希尔排序

　　**冒泡排序

　　**快速排序

　　**选择排序：

　　直接选择排序

　　堆排序

　　**归并排序

　　基数排序

　　*各种内部排序方法比较


本文关键字: 上海理工大学 考试大纲

上一页 1 2 3 4 5 6 7 8 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

测评合集

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10