研招网 > 上海研招网 > 上海理工大学 > 考研大纲

2015年上海理工大学081103系统工程考研大纲


  上海理工大学硕士研究生入学
  《数据结构及操作系统》考试大纲
  第一部分:数据结构
  一、参考书目
  数据结构(第二版),严蔚敏主编,2006,清华大学出版社。
  二、考试内容要求
  1、了解数据结构及其分类、数据结构与算法的密切关系。
  2、熟悉各种基本数据结构及其操作,学会根据实际问题要求来选择数据结
  构。
  3、掌握设计算法的步骤和算法分析方法。
  4、掌握数据结构在排序和查找等常用算法中的应用。
  5、初步掌握文件组织方法和索引技术。
  三、考试内容
  1、数据结构基本概念及简单的算法分析
  1)什么是数据结构
  2)抽象数据类型及面向对象概念:数据类型;数据抽象与抽象数据类型;
  面向对象的概念;用于描述数据结构的语言
  3)数据结构的抽象层次
  4)算法定义
  5)性能分析与度量:算法的性能标准;算法的后期测试;算法的事前估计;
  空间复杂度度量;时间复杂度度量;时间复杂度的渐进表示法;渐进的空
  间复杂.
  2、数组
  1)作为抽象数据类型的数组:数组的定义和初始化;作为抽象数据类型的数
  组;数组的顺序存储方式
  2)顺序表:顺序表的定义和特点;顺序表的类定义;顺序表的查找、插入和
  删除;使用顺序表的事例
  3)字符串:字符串的抽象数据类型;字符串操作的实现;字符串的模式匹
  配
  3、链表
  1)单链表:单链表的结构;单链表的类定义;单链表中的插入与删除;带
  表头结点的单链表;用模板定义的单链表类;单链表的游标类;静态链表
  2)循环链表:循环链表的类定义;用循环链表解约瑟夫问题;多项式及其
  相加:多项式的类定义;多项式的加法
  您所下载的资料来源于kaoyan.com考研资料下载中心
  获取更多考研资料,请访问http://download.kaoyan.com
  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树的高
  度
  您所下载的资料来源于kaoyan.com考研资料下载中心
  获取更多考研资料,请访问http://download.kaoyan.com
  8、图
  1)图的基本概念:图的基本概念;图的抽象数据类型
  2)图的存储表示:邻接矩阵;邻接表;邻接多重表
  3)图的遍历与连通性:深度优先搜索;广度优先搜索;连通分量;重连通
  分量
  4)最小生成树:克鲁斯卡尔算法;普里姆算法
  5)活动网络:用顶点表示活动的网络;用边表示活动的网络
  9、排序
  1)插入排序:直接插入排序;对分插入排序;链表插入排序;希尔排序
  2)交换排序:起泡排序;快速排序
  3)选择排序:直接选择排序;锦标赛排序;堆排序
  4)归并排序:归并;迭代的归并排序算法;递归的表归并排序
  5)基数排序:多关键码排序;链式基数排序
  6)外排序:外排序的基本过程;k路平衡归并;初始归并段的生成;最佳
  归并树
  10、索引与散列结构
  1)静态索引结构:线性索引;倒排表;m路静态查找树
  2)动态索引结构:动态的m路查找树;b_树;b_树的插入;b_树的删除;
  b+树
  3)散列:词典的抽象数据类型;散列表与散列方法;散列函数;处理溢出
  的闭散列方法;处理溢出的开散列方法;散列表分析
  第二部分:操作系统
  一、参考书目
  汤小丹等,《计算机操作系统》(第三版),西安电子科技大学出版社,2007年
  二、考试内容范围
  要求考生重点掌握操作系统设计方法与实现技术,能够运用所学的操作系统原
  理、方法与技术分析问题和解决问题。
  1、操作系统引论
  操作系统的目标与作用;操作系统的发展与分类;操作系统的基本特性与主要
  功能。
  2、进程管理
  您所下载的资料来源于kaoyan.com考研资料下载中心
  获取更多考研资料,请访问http://download.kaoyan.com
  进程的基本概念;进程控制;进程同步(进程同步的基本概念、实现临界区互
  斥的基本方法、信号量、经典同步问题);进程通信(共享存储系统、消息传递
  系统、管道通信);线程概念;线程的实现。
  3、处理机调度
  调度的基本概念;调度的基本准则;典型调度算法(先来先服务调度算法、短作
  业(短进程、短线程)优先调度算法、时间片轮转调度算法、优先级调度算法、
  高响应比优先调度算法、多级反馈队列调度算法)。
  4、死锁
  死锁的基本概念;死锁预防;死锁避免(系统安全状态、银行家算法);死锁检
  测与解除。
  5、存储器管理
  程序装入与链接;连续分配管理方式;非连续分配管理方式(基本分页存储管
  理方式、基本分段存储管理方式;段页式存储管理方式);虚拟存储器的基本概
  念;请求分页存储管理方式;请求分段存储管理方式;页面置换算法(最佳置换
  算法(OPT)、最近最久未少使用置换算法(LRU)、时钟置换算法(CLOCK))。
  6、设备管理
  I/O系统;I/O控制方式;缓冲管理;I/O软件;设备分配;磁盘存储器的管理
  (磁盘性能、磁盘调度、磁盘高速缓存)。
  7、文件管理
  文件与文件系统的基本概念;文件的逻辑结构(顺序文件;索引文件;索引顺序
  文件);外存分配方式(连续分配、链接分配、索引分配);文件控制块和索引节
  点;目录结构;文件存储空间的管理方法;文件共享;文件保护。
  三、试卷结构
  基本知识测试占50%,综合应用测试占50%。
  命题着重考察考生对基本概念、基本知识和基本理论的掌握情况,以及对基本方
  法的运用能力。

  点击【2015年上海理工大学研究生考试大纲】查看更多考研大纲。
【相关阅读】
研究生招生专业索引
2015年全国各学校考研大纲汇总

  友情提示:
  考研信息数量巨大,整理过程中难免出错,欢迎广大研友指正。此外很多历史数据已无处查找,所以为保证考研信息的完整性,考研网真诚欢迎广大研友帮忙补充信息,可回复评论或发送内容至http://bbs.kaoyan.com/f3p1
  本文系考研网精心整理,转载请注明出处。
考研帮最新资讯更多

考研帮地方站

你可能会关心:

查看目标大学的更多信息

分数线、报录比、招生简章
一个都不能错过

× 关闭