2019年考研电子科技大学820 计算机专业基础考试大纲.pdf

返回 相关 举报
2019年考研电子科技大学820 计算机专业基础考试大纲.pdf_第1页
第1页 / 共3页
2019年考研电子科技大学820 计算机专业基础考试大纲.pdf_第2页
第2页 / 共3页
亲,该文档总共3页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
考试科目 820 计算机专业基础 考试形式 笔试(闭卷) 考试时间 180 分钟 考试总分 150 分 本科目包括数据结构和计算机操作系统两门课程,总分 150 分,两门课程各占 75 分 数据结构 一、总体要求 数据结构是计算机程序设计的重要理论技术基础,是计算机科学与技术学科的核心课程。要求: 1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上,能够 分析算法的 时间复杂度与空间复杂度。 3.能够选择合适的数据 结构和 算法策略 进行问题求解,具备采用 C 或 C+或 JAVA 语言设计与实现算法的能力。 二、内容 1. 数据结构及算法的相关概念和术语 ( 1)数据结构及算法的概念; ( 2)数据的逻辑结构和存储结构; ( 3)算法的定义及特性; ( 4)算法时间复杂度和空间复杂度的分析方法。 2线性表 ( 1)线性表的定义 ( 2)线性表的基本操作及在顺序存储及链式存储上的实现; ( 3)各种变形链表(循环链表、双向链表、带头结点的链表等)的表示和基本操作的实现; ( 4)递归过程的特点及实现方法; ( 5)栈和队列的基本概念;栈 和队列的顺序存储结构、链式储存结构及其存储特点;( 6)栈和队列的应用 ( 7)循环队列的判满、判空方法; ( 8)特殊矩阵的压缩储存; 3广义表的基本概念、存储结构和基本操作 4树和二叉树 ( 1)树与森林的基本概念 ( 2)树与森林的存储结构及遍历 ( 3)二叉树的定义及 6 大性质 ( 4)二叉树的顺序储存与链式储存结构 ( 5)二叉树的先序、中序、后序三种遍历方式的关系以及实现;层序遍历的实现 ( 6)线索二叉树的基本概念与构造方法 ( 7)树与二叉树的应用:二叉排序树;二叉平衡树;哈夫曼树与哈夫曼编码 5图 ( 1)图的基本概念和术语; ( 2)图的存储结构:邻接矩阵、邻接表、逆邻接表; ( 3)遍历算法:深度优先搜索算法和广度优先搜索算法; ( 4)应用:最小生成树;最短路径,拓扑排序和关键路径。 6查找 ( 1)查找的基本概念;静态查找与动态查找; ( 2)顺序查找、折半查找、索引查找 ( 3)哈希查找 哈希函数的基本构造方法,解决地址冲突的基本策略; ( 4)各种查找算法的时间复杂度和空间复杂度。 7排序 ( 1)排序的基本概念 ( 2)插入排序 ( 3)简单选择排序 ( 4)希尔排序 ( 5)快速排序 ( 6)堆排序 ( 7)归并排 序 ( 8)基数排序 ( 9)排序算法的比较。 三、题型及分值比例 1. 填空题( 10 分) 2. 单选 题( 20 分) 3. 简答题( 30 分) 4. 算法题( 15 分) 其中算法题分为阅读、修改和编写算法三类: (1)阅读算法:阅读指定算法,回答使用的数据结构、算法实现的功能或执行的结果; (2)修改算法:阅读指定算法,指出算法的错误并修正;指出算法的不足并改进;按给定功能填写算法空缺部分; (3)编写算法:根据算法功能要求,选择或者设计合适的数据结构,用程序设计语言编写算法,实现指定功能。 以上皆可分析给定或者设计 的算法时空复杂度。 操作系统部分 一、总体要求 主要考察学生对 操作系统基本概念、原理 的理解程度,重点考察 操作系统 的 设计方法与实现技术 ,同时 能够 具备 运用所学的操作系统原理、方法与技术分析问题和解决问题 的能力 。 二、内容及比例 1. 操作系统的基本概念 1) 批处理与多道程序设计 2) 分时系统与实时系统 3) 操作系统的基本类型与特征 4) 并发与并行的概念 5) 操作系统的层次结构与功能模块 6) 程序的并发执行与顺序执行 2. 进程管理 1) 进程 : 进程控制块、进程的几种基本状态与状态转换(进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活 等) 2) 进程的同步与互斥: 临界资源、临界区、进程 同步与 互斥问题、信号量 机制以及 P、 V 操作、管程机制 。 3) 进程间通信:进程通信的类型(直接通信和间接通信方式)、消息传递系统中的几个问题、消息缓冲队列通信机制。 4) 线程与进程 的调度 :线程与进程的基本概念,调度的类型、调度队列模型、调度方式、进程调度算法(先来先服务、短进程优先、时间片轮转、基于优先级的调度算法等)。 5) 死锁 :死锁的基本概念,死锁定理、死锁预防、死锁避免与处理死锁的基本方法、银行家算法。 6) 综合应用:生产者消费者问题、 读者和写者问题、哲学家进餐问题 等。 3. 内 存管理 1) 内存管理的需求:重定位、内存保护、内存共享 2) 程序的装入和链接:静态装入和可重定位装入、静态链接、动态链接、运行时动态链接。 3) 分区存储管理 :分区方式( 单一连续分区 、 固定分区 、 可变式分区 )、分区 分配算法 (首次适应算法、循环首次适应算法、最佳适应法、最坏适应法等)。 4) 段式管理与页式管理:段、页、碎片等基本概念、段式管理与页式管理机制 5) 虚拟内存:局部性原理、虚拟内存概念、请求分段与请求分页、段页式管理、段页式地址结构与地址转换、页面置换算法( OPT、先进先出、 LRU、 Clock、改进型 Clock 置换)、抖动 4. 设备管理 1) I/O 系统的:基本概念、 I/O 控制方式(程序 I/0、中断、 DMA、通道)、相关数据结构、缓冲管理(单缓冲、双缓冲、循环缓冲、缓冲池) 2) 磁盘管理与磁盘调度算法: SSTF 算法, SCAN 算法, CSCAN 算法, N-STEP-SCAN 算法, FSCAN算法 3) 设备分配、设备处理 、 虚拟设备 , Spooling 系统 5. 文件系统 1) 基本概念:文件和文件系统、目录、文件结构的物理结构和逻辑结构 (顺序文件、索引顺序文件、索引文件、 HASH 文件) 、文件共享(基于索引节点、基于符号链接实现文件共享) 2) 外存分配方法: 连续分配、链接 分配、索引分配 3) 目录管理:单级目录、二级目录、多级目录 4) 文件存储空间的管理 技术 : 位示图、空闲链表、索引 三、题型及分值比例 1. 填空题( 10 分) 2. 单选 题( 10 分) 3. 简答题( 20 分) 4. 应用题( 35 分)
展开阅读全文
相关资源
相关搜索
资源标签

考研文库@kaoyanwenku.com