|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
《数据结构》研究生入学考试学习大纲
|
一、课程的地位与作用
《数据结构》课程是计算机专业的核心课程之一，是一门综合性的专业基础课，它介于数学，计算机硬件，计算机软件之间。是高级程序设计语言，编译原理，操作系统，数据库，人工智能等课程的基础。同时，数据结构的技术也广泛应用于信息科学、系统工程，应用数学，以及各种工程技术领域。
|
|
|
二、课程的教学目标与基本要求
课程目的是使学生了解计算机应用中数据对象的特性，学会在应用中， 根据现实世界中的问题选择适当的数据逻辑结构和存储结构以及相应算法， 并且培养基本的、良好的程序设计技能。
三、课程内容（重点△，难点★）
1 绪论
1.1 数据结构的有关概念
1.2 数据结构发展概况
1.3△关于算法及算法的分析
1.3.1算法
1.3.2 算法设计要求
1.3.3 ★时间复杂度
2线性表
2. 1 线性表的逻辑结构
2. 2 △线性表的顺序存储结构及运算实现
2. 3 △线性表的链式存储结构及运算
2. 3. 1 线性链表
2. 3. 2 循环链表
2. 3. 3 双向链表
2. 3. 4 静态链表
2. 4 ★一元多项式的表示及相加
3 栈和队列
3.1 栈的定义及运算
3.2 △栈的存储结构及运算实现
3.3栈应用举例
3.4 队的定义及运算
3.5 △队的存储结构及运算实现
3.5.1 队的链式存储和运算
3.5.2 循环队---队的顺序存储和运算
4 数组
4.1 数组的定义
4.2 ★稀疏矩阵的三元组表示及有关算法
4.3 稀疏矩阵的十字链表表示及相加
5 树和二叉树
5.1 树的定义及有关术语
5.2 △二叉树
5.2.1 二叉树的定义
5.2.2 二叉树的性质
5.2.3 二叉树的存储结构
5.3 △二叉树的遍历算法及线索二叉树
5.3.1 二叉树的遍历
5.3.2 ★线索二叉树
5.4 树和森林
5.4.1 树的存储结构
5.4.2森林与二叉树的转换
5.4.3树和森林的遍历
5.5 哈夫曼树及其应用
5.5.1 哈夫曼树
5.5.2 哈夫曼编码
6 图
6.1 图的定义及逻辑结构、存储方法
6.2 △图的遍历算法
6.2.1 图的深度优先搜索
6.2.2 图的广度优先搜索
6.3 △无向图的连通性
6.3.1 无向图的连通分量
6.3.2 无向图的生成树
6.3.3 ★最小生成树
6.4 △有向无环图及其应用
6.4.1 拓扑排序；
6.4.2 ★关键路径
6.5 △★单源点最短路径
7 查找
7.1 △静态查找表
7.1.1 顺序表的查找
7.1.2 有序表的折半查找
7.1.3 索引顺序表的查找
7.2 △动态查找表
7.2.1 二叉排序树
7.2.2 ★平衡二叉树
7.2.3 ★B-树
7.3 △哈希表
7. 3. 1 哈希表的定义
7. 3. 2 哈希函数
7. 3. 3 冲突处理方法
7. 3. 4 哈希表的查找
8 △内部排序
8.1 排序的概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 插入排序
8.2.3 希尔排序
8.3 快速排序
8.4 选择排序
8.4.1 简单选择排序
8.4.2 堆排序
8.5各种内部排序方法的比较
|
|
|
|
四、时间分配
|
|
|
课程分
段标识
|
序号
|
教 学 内 容
|
教学环节（学时）
|
|
|
讲
课
|
习
题
|
实
验
|
上
机
|
课
外
|
小
计
|
|
|
|
1
|
绪论
|
2
|
|
|
|
|
2
|
|
|
2
|
线性表
|
5
|
|
|
3
|
|
7
|
|
|
3
|
栈和队列
|
4
|
|
|
|
|
7
|
|
|
4
|
数组
|
4
|
|
|
|
|
4
|
|
|
5
|
树和二叉树
|
7
|
|
|
3
|
|
10
|
|
|
6
|
图
|
7
|
|
|
|
|
7
|
|
|
7
|
查找
|
7
|
|
|
2
|
|
7
|
|
|
8
|
内部排序
|
4
|
|
|
|
|
4
|
|
|
总 计
|
40
|
|
|
8
|
|
48
|
|
|
五、课程说明
|
|
|
课程英文名称
|
Data Structure
|
|
|
主要先修课程
|
C++程序设计
|
|
|
适用专业类别
|
计算机科学与技术
|
|
|
主要教材（作者、教材名称、出版社）
|
“数据结构” 严蔚敏、吴伟民 清华大学出版社
|
|
|
考核方式
|
考试
|
|
|
课程简介
|
各种类型的数据结构和查找，排序的各种方法
|
|
|
必 开
实 验
项 目
|
序号
|
项 目 名 称
|
学时
|
|
|
1
|
线性表链式存储结构的应用
|
3
|
|
|
2
|
二叉树
|
2
|
|
|
3
|
Hash表应用
|
2
|
|
|
4
|
|
|
|
|
5
|
|
|
|
|
6
|
|
|
|
|
7
|
|
|
|
|
8
|
|
|
操作系统
1 操作系统引论
1．1 操作系统的目标、作用和类型
1．2 操作系统的发展与分类
1．3 操作系统的功能与组成
1．4 市场上常用的操作系统的介绍
2 进程的描述与控制
2．1 进程的描述
2．1．1 进程的定义
2．1．2 进程的状态
2．2 进程的控制
2.2.1 原语
2.2.2 进程控制的几个基本原语
3 进程的同步与通信
3．1 进程同步的基本概念
3.1.1临界资源
3．1．2 临界区
3．1．3 硬件和软件解决进程互斥
3．2 信号量机制
3.2.1 整型信号量
3．2．2 记录型信号量
3.2.3 经典进程同步问题
3．3 进程通信
3.3.1 进程通信类型
3．3．2 直接通信和间接通信
3．3．3 消息通信机制
3.3 线程的基本概念
4 调度与死锁
4．1 调度的类型和模型
4.1.1 调度类型
4．1．2 调度队列模型
4．1．3 调度方式选择的准则
4．2 常用的进程调度算法
4．3 死锁的基本概念
4.3.1 死锁的原因
4．3．2 产生死锁的必要条件
4．3．3 处理死锁的基本方法
4．4 死锁的预防和避免
4.4.1 死锁的预防
4.4.2 系统的安全状态
4.4.3银行家算法
5 存储器管理
5．1 程序的装入和连接
5．2 连续分配存储管理方式
5.2.1 单一连续分配
5．2．2 固定分区分配
5．2．3 动态分区分配
5．2．4 动态重定位
5.3 对换
5．3．1 多道程序环境的对换
5．3．2 对换空间管理
5．3．3 进程的换入与换出
5．2 分页存储管理
5．4．1 分页存储管理的基本方法
5．4．2 地址变换机构
5．4．3 两级和多级页表
5．3 分段存储管理
5．5．1 分段存储管理的引入与原理
5．5．2 段页式存储管理
6 虚拟存储器
6．1 虚拟存储的基本概念
6．2 请求分页存储管理
6．2．1 请求分页硬件支持
6．2．2 页面分配
6．2．3 页面调入策略
6．3 页面置换
6．3．1 最佳和先进先出算法
6．3．2 LRU算法
6．3．3 Clock算法
6．3．4 其它置换算法
6．4 请求分页系统的性能问题
6.4.1 工作集
6.4.2 抖动及其预防
6．5 请求分段存储管理
7 设备管理
7.1 I/O系统的组成
7.1.1 I/O 系统的结构
7.1.2 I/O设备
7.1.3 I/O设备控制器
7.1.4 I/O通道
7.2 I/O控制方式
7.2.1 程序I/O
7.2.2 中断驱动I/O
7.2.3 DMA
7.2.4 I/O通道方式
7.3 缓冲区的作用与管理
7.4 设备分配
7.4.1 数据结构
7.4.2 分配考虑因素
7.4.3 设备独立性
7.4.4 独占设备的分配
7.4.5 SPOOLing技术
7.5 设备处理
7.5.1 设备驱动程序的功能和特点
7.5.2 设备驱动和中断处理程序的处理过程
8 文件系统
8.1 文件和文件系统
8.1.1 文件的分类
8.1.2 文件的基本操作
8.2 文件的逻辑结构
8.2.1文件逻辑结构的类型
8.2.2 常见的几种逻辑结构（顺序，索引，索引顺序）
8.3 目录管理
8.3.1文件控制块和索引结点
8.3.2 单级和两级目录结构
8.3.3 树型目录
8.3.4目录查询技术
8.4 文件共享
8.4.1 文件共享的必要性
8.4.2 常用的共享方式
8.5 文件保护
8.5.1 文件保护的重要性
8.5.2 文件保护的几种方案
9 磁盘存储器管理
9.1磁盘I/O1 操作系统引论
1.1 操作系统的目标、作用和类型
1.2 操作系统的发展与分类
1.3 操作系统的功能与组成
1.4 市场上常用的操作系统的介绍
2 进程的描述与控制
2.1 进程的描述
2.1.1进程的定义
2.1.2进程的状态
2.2 进程的控制
2.2.1 原语
2.2.2 进程控制的几个基本原语
3 进程的同步与通信
3.1 进程同步的基本概念
3.1.1临界资源
3.1.2临界区
3.1.3硬件和软件解决进程互斥
3.2 信号量机制
3.2.1 整型信号量
3.2.2记录型信号量
3.2.3经典进程同步问题
3.3 进程通信
3.3.1 进程通信类型
3.3.2直接通信和间接通信
3.3.3消息通信机制
3.3 线程的基本概念
4 调度与死锁
4.1 调度的类型和模型
4.1.1 调度类型
4.1.2调度队列模型
4.1.3调度方式选择的准则
4.2 常用的进程调度算法
4.3 死锁的基本概念
4.3.1 死锁的原因
4.3.2产生死锁的必要条件
4.3.3处理死锁的基本方法
4.4 死锁的预防和避免
4.4.1 死锁的预防
4.4.2 系统的安全状态
4.4.3银行家算法
5 存储器管理
5.1 程序的装入和连接
5.2 连续分配存储管理方式
5.2.1 单一连续分配
5.2.2固定分区分配
5.2.3动态分区分配
5.2.4动态重定位
5.3 对换
5.3.1多道程序环境的对换
5.3.2对换空间管理
5.3.3进程的换入与换出
5.2 分页存储管理
5.4.1分页存储管理的基本方法
5.4.2地址变换机构
5.4.3两级和多级页表
5.3 分段存储管理
5.5.1分段存储管理的引入与原理
5.5.2段页式存储管理
6 虚拟存储器
6.1 虚拟存储的基本概念
6.2 请求分页存储管理
6.2.1请求分页硬件支持
6.2.2页面分配
6.2.3页面调入策略
6.3 页面置换
6.3.1最佳和先进先出算法
6.3.2 LRU算法
6.3.3 Clock算法
6.3.4其它置换算法
6.4 请求分页系统的性能问题
6.4.1 工作集
6.4.2 抖动及其预防
6.5 请求分段存储管理
7 设备管理
7.1 I/O系统的组成
7.1.1 I/O 系统的结构
7.1.2 I/O设备
7.1.3 I/O设备控制器
7.1.4 I/O通道
7.2 I/O控制方式
7.2.1程序I/O
7.2.2中断驱动I/O
7.2.3 DMA
7.2.4 I/O通道方式
7.3 缓冲区的作用与管理
7.4 设备分配
7.4.1数据结构
7.4.2分配考虑因素
7.4.3设备独立性
7.4.4独占设备的分配
7.4.5 SPOOLing技术
7.5 设备处理
7.5.1设备驱动程序的功能和特点
7.5.2设备驱动和中断处理程序的处理过程
8 文件系统
8.1 文件和文件系统
8.1.1文件的分类
8.1.2文件的基本操作
8.2 文件的逻辑结构
8.2.1文件逻辑结构的类型
8.2.2 常见的几种逻辑结构（顺序，索引，索引顺序）
8.3 目录管理
8.3.1文件控制块和索引结点
8.3.2 单级和两级目录结构
8.3.3 树型目录
8.3.4目录查询技术
8.4 文件共享
8.4.1文件共享的必要性
8.4.2常用的共享方式
8.5 文件保护
8.5.1文件保护的重要性
8.5.2文件保护的几种方案
9 磁盘存储器管理
9.1磁盘I/O
9.1.1 磁盘调度算法
9.1.2 各种扫描算法
9.2外存分配
9.3 空闲存储空间的管理
10 UNIX操作系统分析
10. 1 UNIX综述
10.2 UNIX进程控制子系统
10.3 UNIX文件系统子系统
参考书籍 1） 《计算机操作系统（第三版）》西安电子科技大学出版社
汤子赢
2） 操作系统概念（中译版） （六版） 高等教育出版社
Peter Baer Galvin
9.1.1 磁盘调度算法
9.1.2 各种扫描算法
9.2外存分配
9.3 空闲存储空间的管理
10 UNIX操作系统分析
10. 1 UNIX综述
10.2 UNIX进程控制子系统
10.3 UNIX文件系统子系统
参考书籍 1） 《计算机操作系统（第三版）》西安电子科技大学出版社 汤子赢
2） 操作系统概念（中译版） （六版） 高等教育出版社 Peter Baer Galvin
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
