上海理工大学硕士研究生入学

《数据结构及操作系统》考试大纲

第一部分：数据结构

一、参考书目

数据结构（第二版），严蔚敏主编，2006，清华大学出版社。

二、 考试内容要求

1、了解数据结构及其分类、数据结构与算法的密切关系。

　　2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。

　　3、掌握设计算法的步骤和算法分析方法。

　　4、掌握数据结构在排序和查找等常用算法中的应用。

5、初步掌握文件组织方法和索引技术。

三、考试内容

1、 数据结构基本概念及简单的算法分析 

　　1)什么是数据结构

　　2) 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言

　　3) 数据结构的抽象层次

　　4) 算法定义

　　5) 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.

2、 数组

　　1)作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式

　　2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例

　　3) 字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配

3、链表 

　　1) 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表

　　2) 循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法

　　3) 双向链表

4、栈和队列 

　　1) 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示

　　2) 队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3) 队列的应用举例

　　4) 优先级队列：优先级队列的定义；优先级队列的存储表示

5、递归 

　　1) 递归的概念

　　2) 迷宫问题

　　3) 递归过程与递归工作栈

　　4) 利用栈实现的迷宫问题非递归解法

　　5) 广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广6) 义表的访问算法；广义表的递归算法

6、树与森林

　　www.xuecan.net

　　1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型

　　2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型

　　3) 二叉树的表示：数组表示；链表存储表示

　　4) 二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二 叉树遍历的游标类；不用栈的二叉树中序遍历算法

　　5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化

　　6) 堆：堆的定义；堆的建立；堆的插入与删除

　　7) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历

　　二叉树的计数

　　8) 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码

7、集合与搜索  www.xuecan.net

　　1) 集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型

　　2) 等价类：等价关系与等价类；确定等价类的链表方法；并查集

　　3) 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索

　　4) 二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除；与二叉搜索树相关的中序游标类

　　5) AVI树：AVI树的定义；平衡化旋转；AVI树的插入和删除；AVI树的高度

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、进程管理

进程的基本概念； 进程控制；进程同步（进程同步的基本概念、 实现临界区互斥的基本方法、 信号量、经典同步问题）；进程通信（共享存储系统、消息传递系统、管道通信）；线程概念；线程的实现。

3、处理机调度

调度的基本概念；调度的基本准则；典型调度算法（先来先服务调度算法、短作业（短进程、短线程）优先调度算法、时间片轮转调度算法、优先级调度算法、高响应比优先调度算法、多级反馈队列调度算法） 。 

4、死锁

死锁的基本概念；死锁预防；死锁避免（系统安全状态、银行家算法）；死锁检测与解除。

5、存储器管理 

程序装入与链接；连续分配管理方式； 非连续分配管理方式（基本分页存储管理方式、基本分段存储管理方式；段页式存储管理方式）； 虚拟存储器的基本概念；请求分页存储管理方式；请求分段存储管理方式；页面置换算法（最佳置换算法（OPT）、最近最久未少使用置换算法（LRU）、时钟置换算法（CLOCK））。 

6、设备管理www.xuecan.net

 I/O系统；I/O 控制方式；缓冲管理；I/O软件；设备分配；磁盘存储器的管理（磁盘性能、磁盘调度、磁盘高速缓存）。

7、文件管理

文件与文件系统的基本概念；文件的逻辑结构（顺序文件；索引文件；索引顺序文件）；外存分配方式（连续分配、链接分配、索引分配）；文件控制块和索引节点；目录结构；文件存储空间的管理方法；文件共享；文件保护。 

三、试卷结构

基本知识测试占50%，综合应用测试占50%。

命题着重考察考生对基本概念、基本知识和基本理论的掌握情况，以及对基本方法的运用能力。