2015年上海理工大学120100管理科学与工程考研大纲

　　上海理工大学硕士研究生入学
　　《数据结构及操作系统》考试大纲
　　第一部分：数据结构
　　一、参考书目
　　数据结构（第二版），严蔚敏主编，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年全国各学校考研大纲汇总