背景:
阅读全文

2018年云南大学硕士研究生入学考试《数据结构与操作系统》考试大纲

[日期:2017-10-04] 来源:云南大学

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

一、考查目标

数据结构和操作系统是计算机类专业的核心课程。《数据结构和操作系统》科目考察的内容包括《数据结构》和《操作系统》的基本内容,要求考生掌握相关的概念、方法和技术,并具备较强的程序设计能力,能够灵活应用相关的方法和技术解决实际问题。

二、考试形式与试卷结构

(一)试卷成绩及考试时间

本试卷满分为150分,考试时间为180分钟。

(二)答题方式

答题方式为闭卷、笔试。

(三)试卷内容结构

各部分内容所占分值为:

数据结构    75分

操作系统    75分

(四)试卷题型结构

选择题,简答题,综合题,程序设计题

三、考查范围

数据结构

一、考查目标

1、掌握数据结构的基本概念、方法和技术。

2、掌握程序设计的基本方法和技巧。

3、能够应用相关知识解决一些有实际背景的问题。

二、考查内容

1. 数据结构概述

数据结构的概念;

基本概念与术语;

算法的概念,算法的特性,以及算法设计的要求,算法效率的度量。

2. 线性表

线性表的基本概念和结构特点;

线性表的顺序存储方式以及两种不同的实现方法,线性表存储空间的静态分配和动态分配;

线性表的链式存储方式的实现,链表与顺序表的相似及不同之处,优缺点比较,各自适用的场合;

线性表的各种实现方式下能够实现指定的操作。

3.栈和队

栈、队列的定义及其相关数据结构的概念,包括:顺序栈,链栈,共享栈,循环队列,链队列等;

栈与队列插入删除操作的特点;栈和递归的关系;栈和队列各种实现方式。

4. 串

 串的基本概念,朴素的模式匹配算法。

5.数组

数组的定义,数组的存储,行序和列序;

特殊矩阵的定义;特殊矩阵的压缩存储。

6.树和二叉树

二叉树的概念,二叉树的五个性质;

二叉树的存储结构:顺序存储和二叉链表存储的各自优缺点及适用场合;

二叉树的三种遍历方法:先序,中序和后序,线索二叉树,线索化后二叉树的遍历方法;

哈夫曼树概念,哈夫曼树的构造方法,前缀码概念,哈夫曼编码。

树的存储表示方法,树与森林转化为二叉树,树和森林的遍历问题。

7. 图

图的基本概念,图的定义和特点;

图的几种存储形式,重点是邻接矩阵和邻接表;

深度遍历和广度遍历是图的两种基本的遍历算法;

生成树、最小生成树的概念以及最小生成树的构造:PRIM算法和KRUSKAL算法;

有向无环图,拓扑排序和关键路径问题;

最短路径问题:DIJSKTRA算法和FLOYD算法。

8. 查找

关键字、主关键字、次关键字的含义;

静态查找与动态查找的含义及区别,平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果;

顺序表的查找,折半查找,索引顺序表;

二叉排序树,平衡二叉树,B树;

哈希表的概念,哈希函数的设计,冲突解决方法的选择及冲突处理过程。

9.排序

要求掌握各种排序方法的思想和算法实现,排序算法稳定性的概念,以及各自的特点。

插入排序:直接插入、折半插入、2路插入、希尔排序;

冒泡排序,快速排序;

选择排序:简单选择、树选择、堆排序;

归并排序;

基数排序。

操作系统

一、考查目标

1、了解操作系统在计算机系统中的作用、地位,操作系统的发展历史,各类型操作系统的特点。

2、掌握操作系统资源管理的原理、机制、策略和关键技术,理解操作系统的运行过程。

3、能够运用所学的操作系统原理、方法与技术分析和解决问题。

二、考查内容

1、操作系统概述

操作系统的概念、特征、功能和提供的服务;

操作系统的发展历史与分类;

操作系统的运行环境

2、用户界面

作业的概念及作业的建立过程;

命令控制界面接口;

系统调用

3、处理机管理

(1)进程管理

进程与线程,进程的状态与转换,进程控制,进程间通信;

进程同步与互斥,信号量机制与P、V操作,经典的同步互斥模型;

死锁的预防、避免、检测和解除

(2)处理机调度

调度的基本概念,调度的目标,功能与性能衡量;

典型调度算法:先来先服务、短作业(短进程)优先、时间片轮转、基于优先级、最高响应比优先、多级反馈轮转等调度算法。

4、存储管理

存储管理的功能:虚拟存储器、地址变换、内存的分配与回收、内存信息的共享与保护;

覆盖与交换技术;

分区存储管理:基本原理、分区的分配与回收;

页式存储管理:基本原理和实现,请求页式管理中的页面置换算法:先进先出置换算法(FIFO)、最近最少使用置换算法(LRU)、最佳置换算法(OPT)、时钟置换算法(CLOCK)等;

段式与段页式管理:基本原理和实现;

工作集、局部性原理和抖动问题

5、文件管理

文件和文件系统的基本概念;

文件逻辑结构与物理结构;

文件存储管理:文件存储空间管理,文件目录管理,文件存取控制,文件系统层次结构;

磁盘组织与管理:磁盘调度算法

6、设备管理

设备管理的目的、设备管理的功能和任务;

数据传输控制方式:程序直接控制、中断、DMA、通道;

中断技术:中断的概念、中断的分类、软中断、中断的处理过程;

缓冲技术:缓冲的种类、缓冲池的管理;

设备分配与回收:设备分配用数据结构、分配原则和分配算法;

虚拟设备,Spooling技术

我要咨询或发布信息 | 编辑:yangying | 阅读:
热门培训课程
热门培训课程
热门评论