出国留学网

目录

2014年848数据结构及操作系统考研大纲——上海理工大学光电学院

【 liuxue86.com - 考研大纲 】

2014年848数据结构及操作系统考研大纲——上海理工大学光电学院

    第一部分:数据结构

    一、参考书目

  数据结构(第二版),严蔚敏主编,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、树与森林

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

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

  3) 二叉树的表示:数组表示;链表存储表示

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

  5) 线索化二叉树:线索;中序线索化二叉树;前序与后序的线索化

  6) 堆:堆的定义;堆的建立;堆的插入与删除

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

  二叉树的计数

  8) 霍夫曼树:路径长度;霍夫曼树;霍夫曼编码

  7、集合与搜索

  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、设备管理

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

  7、文件管理

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

    三、试卷结构

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

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


相关推荐: 2014年上海理工大学光电信息与计算机工程学院考研大纲汇总
           2014年上海理工大学考研大纲汇总
           2014年招生简章上海理工大学汇总


考研大纲汇总 考研英语大纲 考研政治大纲 考研数学大纲 考研专业课大纲

  想了解更多考研大纲网的资讯,请访问: 上海考研大纲

本文来源:https://www.liuxue86.com/a/1500976.html
考研院校库(挑大学·选专业)
院校搜索
专业查询
延伸阅读
为了更好的做好备考复习工作,很多小伙伴们都在关注2021考研英语大纲什么时候出,下面由出国留学网小编为你精心准备了“2021考研英语大纲在什么时候出?”,持续关注本站将可以持续获取
2020-07-11
七月伴随着炎炎夏日的到来,2021考研英语大纲整体发生了什么变化呢?下面由出国留学网小编为你精心准备了“2021考研英语大纲整体走向变化大吗?”,持续关注本站将可以持续获取更多的考
2020-07-08
2019年考研复试已经开始了,小编为大家提供贵州师范大学地理与环境科学学院2019考研复试大纲,请大家查看各科目考试大纲,做好考试准备!贵州师范大学2019考研复试大纲:综合自然地
2019-03-29
今天小编为大家提供贵州师范大学生命科学学院(含荞麦研究中心)2019考研复试大纲,一起来看看吧!希望大家能够抓紧时间进行复习!贵州师范大学2019考研复试大纲:中学生物学教学论(科
2019-03-29
今天小编为大家提供贵州师范大学2019考研复试大纲:体育基础理论,一起来看看吧!希望大家尽早准备复试,按时参加复试,不要错过考试时间!贵州师范大学2019考研复试大纲:体育基础理论
2019-03-29
数据结构及操作系统上海理工大学考研内容要求及参考书目已公布,出国留学考研网为大家提供上海理工大学2019考研大纲:848数据结构及操作系统,更多考研资讯请关注我们网站的更新!上海理
2018-08-18
考研大纲频道为大家提供长沙理工大学2019考研大纲:850数据结构,一起来了解一下吧!更多考研资讯请关注我们网站的更新!长沙理工大学2019考研大纲:850数据结构科目代码:850
2018-09-26
上海理工大学数据结构及软件工程考研主要考什么呢?出国留学考研网为大家提供上海理工大学2019考研大纲:869数据结构及软件工程,更多考研资讯请关注我们网站的更新!上海理工大学201
2018-08-17
考研大纲频道为大家提供长沙理工大学2019考研复试大纲:F0802操作系统,一起来看看吧!更多考研资讯请关注我们网站的更新!长沙理工大学2019考研复试大纲:F0802操作系统科目
2018-09-26
考研大纲频道为大家提供长沙理工大学2019考研大纲:848现代汉语,我们一起来看看考试内容及题型吧!更多考研资讯请关注我们网站的更新!长沙理工大学2019考研大纲:848现代汉语科
2018-09-20