资源描述
考试科目 8 2 0计 算机 专业 基础 考试形式 笔试（ 闭卷 ） 考试时间 1 8 0分 钟 考试总分 1 5 0 分 本科目 包括 数 据结 构 和计 算机 操作 系统 两 门课程 ，总 分1 5 0 分 ，两 门课程 各 占 7 5 分 数据结构 一、总体要求 数 据结 构 是 计算 机 程序设 计的 重要 理论 技术 基 础 ， 是 计算 机科 学与 技 术学科 的核 心课 程 。 要 求： 1 . 理解 数据 结构 的基 本概 念； 掌握 数据 的逻 辑结 构 、 存储结 构及 其差 异， 以及 各种基 本操 作的 实现 。 2 . 掌握 基本 的数 据处 理原 理和方 法的 基础 上， 能够 分析算 法的 时间 复杂 度与 空间复 杂度 。 3 . 能够 选择 合适 的数 据结 构和算 法策 略 进 行问 题求 解， 具备 采用 C 或 C+ 或 JA VA 语言 设 计 与实现 算法 的能 力 。 二、内容 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) 阅 读算 法 ： 阅读 指定 算 法，回 答 使 用的 数据 结 构 、算 法 实 现 的功 能 或 执 行 的结果 ； ( 2) 修改 算 法： 阅读 指定 算 法 ， 指出 算法的 错误并修 正； 指出 算法的 不足 并 改 进； 按给 定功能 填 写 算法 空 缺 部 分； (3) 编写 算法： 根据 算法 功 能要 求， 选择 或者设 计合 适的 数据结 构 ， 用程 序设 计语 言 编写 算法 ， 实 现指定 功能 。 以 上 皆可 分析 给定 或者 设计 的 算法 时空 复杂 度。 操作 系统部 分 一 、 总 体要 求 主 要 考察 学生 对操 作系 统基 本 概 念 、 原 理 的理 解程 度， 重点 考察 操作 系统 的设 计 方法 与实 现技 术， 同 时 能 够 具 备运 用所 学的 操作 系 统原 理、 方法 与技 术分 析 问题 和解 决问 题的 能 力 。 二、 内 容及 比例 1 . 操 作 系统 的基 本概 念 1 ) 批 处 理与 多道 程序 设计 2 ) 分 时 系统 与实 时系 统 3 ) 操 作 系统 的基 本类 型与 特征 4 ) 并 发 与并 行的 概念 5 ) 操 作 系统 的层 次结 构与 功能 模 块 6 ) 程 序 的并 发执 行与 顺序 执行 2. 进程 管 理 1 ) 进 程 : 进 程控 制块 、 进 程的 几 种基 本状 态与 状态 转换 （进 程 的 创建 、 进 程的 终止、 进程 的 阻 塞 与 唤醒 、 进 程的 挂起 与激 活 等） 2 ) 进 程 的同 步与 互斥 ： 临 界资 源 、 临 界区 、 进 程同 步与 互 斥问 题、 信号 量机 制以 及 P 、 V 操 作 、管 程 机 制 3 ) 进 程 间通 信： 进程 通信 的类 型 （直 接通 信和 间接 通信 方 式） 、 消 息 传递 系统 中 的几个 问题 、 消 息 缓冲 队列 通信 机制 4) 线程 与 进程 的调度:线程与 进程 的 基本 概念 ， 调度 的 类型、 调 度队列 模型 、 调 度 方式 、 进程 调 度 算法 （ 先 来先 服务 、短 进 程优 先、 时间 片 轮 转、 基 于优 先 级 的调 度算 法等 ） 5) 死锁 :死锁 的基本 概念，死 锁定 理、死 锁预 防 、死 锁 避免 与 处理 死锁的 基本 方 法、 银行 家算法 6 ) 综 合 应用 ：生 产者 消费 者问 题 、读 者和 写者 问题 、哲 学 家进 餐问 题等 3. 内存 管 理 1 ) 内 存 管理 的需 求： 重定 位、 内 存保 护、 内存 共享 2 ) 程 序 的装 入和 链接 ：静 态装 入 和可 重定 位装 入、 静态 链 接、 动态 链接 、运 行时 动 态链 接。 3) 分区 存 储 管 理 ： 分区 方式 （ 单一 连 续 分区 、 固 定分 区、 可 变式 分区 ） 、 分区 分配 算 法 （ 首 次 适 应 算法 、循 环首 次适 应算 法 、最 佳适 应法 、 最 坏适 应 法等 ） 4 ) 段 式 管理 与页 式管 理： 段、 页 、碎 片等 基本 概念 、段 式 管理 与页 式管 理机 制 5) 虚拟 内 存 ： 局 部 性 原理、 虚 拟 内存 概念、 请 求分 段 与请求 分页 、 段页 式 管 理 、 段页 式地 址 结 构 与 地址 转换 、 页 面置 换算 法 （ OP T 、 先进 先出 、 LRU、C lock 、改 进型 Clo c k 置换 ）、 抖动 4. 设备 管 理 1) I/O 系统 的 ： 基 本 概念 、 I /O 控 制方 式 （ 程 序 I/ 0 、 中断、 DM A 、 通 道） 、 相 关 数据 结 构、 缓 冲 管 理（ 单缓 冲、 双缓 冲、 循 环缓 冲、 缓冲 池） 2 ) 磁 盘 管理 与磁 盘调 度算 法： S S T F 算 法 ， S C A N 算 法， C S C A N 算 法， N - S T E P - S C A N 算 法， F S C A N 算 法 3 ) 设 备 分配 、设 备处 理、 虚拟 设 备， S po o l in g 系 统 5. 文件 系 统 1) 基本 概念： 文件 和文 件系 统、 目录 、 文件 结构的物 理结 构和逻 辑结构 （ 顺序 文件 、 索引 顺 序 文 件、 索 引文 件、 H A S H 文 件） 、 文 件共 享 （基 于索 引 节点、 基于 符号 链接实 现 文件 共享 ） 2 ) 外 存 分配 方法 ：连 续分 配、 链 接分 配、 索引 分配 3 ) 目 录 管理 ：单 级目 录、 二级 目 录、 多级 目录 4 ) 文 件 存储 空间 的管 理技 术： 位 示图 、空 闲链 表、 索引新祥旭考研官网 http:/www.xxxedu.net/
展开阅读全文