一、考试内容数据结构1、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构。（2）算法的定义、算法的基本特性以及算法分析的基本概念。2、线性表（1）线性关系、线性表的定义，线性表的基本操作。（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。3、堆栈与队列（1）堆栈与队列的基本概念、基本操作。（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。（3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。4、串（1）串的基本概念、串的基本操作和存储结构。（2）串的模式匹配算法和改进的KMP算法5、数组和广义表（1）数组的概念、多维数组的实现（2）对称矩阵和稀疏矩阵的压缩存储（3）广义表的基本概念6、树与二叉树（1）树的定义和性质（2）二叉树的概念、性质和实现（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用（6）树的计数7、图（1）图的定义，基本概念，图的分类，常用名词术语。（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。（3）图的遍历操作。（4）最小生成树，最短路径，AOV网与拓扑排序。8、文件及查找（1）数据文件的基本概念和基本术语，数据文件的基本操作。（2）顺序文件、索引文件、散列(Hash)文件。（3）顺序文件的顺序查找方法、排序连续顺序文件的折半查找方法以及其他文件的基本查找方法。9、内排序（1）排序的基本概念，排序方法的分类。（2）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。二、考试要求数据结构1、建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的基本概念与基本方法2、掌握线性表的基本概念以及两种存储结构的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。3、掌握堆栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。4、充分了解串的基本概念、掌握串的存储结构和相关的操作算法。5、掌握数组、广义表和稀疏矩阵的基本概念，物理结构和基本操作的实现6、充分了解树型结构的逻辑特征，掌握各种存储结构的构造原理，能够熟练地利用常用的三种遍历方法，掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉排序树的建立以及在二叉排序树中查找一个结点存在与否的过程。7、充分了解图的逻辑结构的特点，掌握常用的两种存储方法，掌握最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的具体求解过程。8、充分了解各种顺序文件的结构与相应的查找方法；了解各种查找算法之间时空效率的差异；从结构与操作上了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。9、充分了解各种排序方法的排序特点和排序过程，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。操作系统1、操作系统概述（1）计算机基本构成、处理器的内部结构、高速缓冲存储器CACHE；（2）操作系统的概念、演变历程、特性、分类、运行环境、功能（3）存储器的层次结构2、进程进程、进程描述及进程状态转换3、线程、对称多处理SMP和微内核（1）线程的概念，定义线程的必要性和可能性；（2）线程的功能特性与实现方式；（3）对称多处理SMP体系结构；（4）操作系统的体系结构（微内核与巨内核）及其性能分析。4、并发性（1）并发性问题及相关概念，如临界区、互斥、信号量和管程等；（2）进程互斥、同步和通信的各种算法；（3）死锁的概念、死锁的原因和条件（4）死锁的预防、避免和检测算法。5、存储器管理（1）分区存储管理、覆盖与交换；（2）页式管理及段式管理；（3）段、页式存储管理方法及实现技术；（4）虚存的原理及相关的各种算法和数据结构。6、单处理器调度（1）处理器的三种调度类型；（2）进程调度的各种算法及其特点。7、多处理器调度和实时调度（1）多处理器对进程调度的影响（2）多处理器环境下的进程和线程调度算法；（3）实时进程的特点；（4）限期调度和速率单调调度方法。8、设备管理和磁盘调度（1）操作系统中输入/输出功能的组织；（2）中断处理；（3）设备驱动程序、设备无关的软件接口和spooling技术；（4）缓冲策略；（5）磁盘调度算法；（6）磁盘阵列。9、文件系统（1）文件系统特点与文件组织方式；（2）文件系统的数据结构；（3）目录的基本性质及其实现方法；（4）磁盘空间的管理。10、分布式系统（1）分布式处理的特点、类型；（2）多层体系结构、中间件技术；（3）机群系统；（4）分布式进程管理相关的操作系统设计问题。操作系统1、解操作系统所管辖的软、硬件资源；了解操作系统的关键概念，从整体上把握操作系统的特性与功能等概念；建立操作系统的资源管理和应用接口的职能概念。2、掌握进程的本质特征，明确进程的动态特性，熟悉进程状态间转换的原因，建立进程是资源分配单元和一种运行实体的基本理念。3、理解引入线程作为基本运行实体的必要性和可能性；掌握线程各种实现方式及其特点；熟悉SMP体系结构、操作系统的体系结构（微内核与巨内核）。4、能够利用信号量、管程等技术解决互斥合同步问题；理解死锁的概念和产生死锁的充分必要条件；熟练掌握死锁的预防、避免和检测算法；了解处理死锁问题时避免饥饿的方法。5、了解存储管理的功能及存储管理对多道程序设计的支持；掌握段、页式存储管理方法及实现技术；重点掌握虚存的原理及相关的各种算法和数据结构。6、了解长程、中程和短程三种调度类型；重点掌握进程调度的各种算法及其适用环境。7、了解调度粒度的概念，熟悉多处理器环境下进程和线程调度算法，了解实时进程的本质，掌握限期调度和速率单调调度方法。8、了解输入输出设备及操作系统中输入/输出功能的组织、掌握中断处理、设备驱动程序、设备无关的软件接口和spooling等技术，重点掌握各种用于提高性能的缓冲策略和磁盘调度算法；了解可提高性能和可靠性的各种磁盘阵列配置方式。9、了解文件系统特点与文件组织，掌握文件系统的基本数据结构，了解文件、目录的基本性质及其实现方法；重点掌握磁盘空间的管理、文件系统的性能及可靠性、文件系统的安全性及保护机制等。10、了解分布式处理的特点、类型；掌握多层体系结构、中间件技术和机群系统的基本概念和特点；重点掌握进程迁移、分布式全局状态的认定、分布式互斥与死锁预防等技术。编译原理1、引论（1）编译器的基本概念（2）编译阶段和编译器伙伴2、词法分析（1）词法分析器（2）正规式（3）有限自动机和扫描器生成器3、语法分析（1）上下文无关文法（2）各种语法分析技术，如自上而下分析和自下而上分析，LR分析器4、语法制导的翻译（1）S属性和L属性（2）自上而下翻译（3）继承属性的自上而下计算（4）递归计算5、类型检查（1）类型体制（2）简单类型检查器（3）类型表达式的等价（4）函数和算符的重载6、运行环境运行时存储空间和组织管理7、中间代码生成（1）常用的中间代码表示：后缀表示、图形表示和三地址表示（2）声明、赋值和布尔表达式8、代码生成（1）代码生成涉及的主要问题（2）目标机器（3）基本块和流图9、代码优化（1）优化的主要种类（2）流图中的循环（3）全局数据流分析介绍（4）代码改进变换编译原理1、了解编译器的基本概念和基本结构2、了解词法分析器的作用，掌握记号的描述和识别方法，掌握识别有限自动机的基本定义和从正规式建立识别器的方法3、了解语法分析器的作用，掌握上下文无关语言和文法的相关概念和性质，掌握各种语法分析技术，如自上而下分析，自下而上分析，以及LR分析器。4、掌握上下文无关文法制导下的语言翻译，5、了解类型体制的基本概念，了解简单类型检查器和类型表达式的等价6、了解程序的运行时存储空间和组织管理7、了解中间代码的表示，了解程序设计语言的结构如何翻译成中间形式8、了解代码生成中涉及的基本问题，包括存储管理、指令选择、寄存器分配和计算次序选择等基本问题9、掌握代码优化的主要种类和代码改进变换。中国科学院计算技术研究所一九九二年招收硕士学位研究生入学考试试题试题名称：软件基础一.填空（每空1分）1线性表可采用的存储结构有和二种。2用于拓扑排序的图是图。3操作系统的特征是和。4根据联接在文法符号上的属性之间的依赖关系，可把属性分为和两大类。5进程间存在的制约关系可以归结为和两种。6产生死锁的原因是和。7对逻辑表达式的计算可采用和方式。8有n个结点的完全二叉树的深度为。9在串的模式匹配中，若主串长为m，子串长为n，则KMP算法的时间复杂度为。10.二叉树的遍历方式有、和三种；图的遍历方式有和两种。二.简答1（3分）什么是哈希（Hash）查找？2（4分）UNIX系统中设备管理的主要特点是什么？3（3分）树(A(B(E(K , L) , F) , (C(G) , D(H(M) , I , J)所对应的二叉树表示是什么?4（3分）已知初始关键字为49，38，65，97，76，13，27，49，现分别用直接插入排序和快速排序方法对之进行排序，请分别给出两种方法第二趟排序之后的结果。5（4分）什么是地址重定位？动态重定位的结果是什么？6（3分）什么是数据的逻辑结构和物理结构？7（5分）程序运行的所需的一片连续存储活动记录有哪些域？它们各有什么作用？8（5分）有一C语言程序如下：main（）int x；x = 25；printf（“%dn”，x）；经过编译联接后，由符号调试器跟踪其执行，却无法检查变量x的值，因为调试器报告“无此变量”。试解释其原因。三.问答题1（8分）试比较Pascal程序（语法结构位置任意，空格等空白字符作为单词分隔符）和Fortran程序（语法结构位置固定，空格无意义）对词法分析的影响。2（8分）下列文法是否为LR（1）文法？若是，给出分析表，若不是，是说明理由。S AAA aA | a3（8分）设一消息缓冲区由如下信息组成：Sptr指向发送进程的指针Nptr指向下一个消息缓冲区的指针Size消息长度Text消息正文请给出两个进程通过该类消息缓冲区进行通讯的过程。4（8分）Swap指令是一条可在一个存储周期内完成交换两个字节的内容的操作的硬件指令。其功能用Pascal语言描述如下：procedure Swap（var a，b：integer）var temp：integer；begintemp：= a；a：= b：b：= temp；end请用该指令实现关锁原语Lock（w）和开锁原语Unlock（w）。四.算法设计1（9分）二叉树的深度定义为由根结点到叶子结点的最长路径，设计一算法，计算二叉树的深度。2（9分）写出堆排序（heap sort）的算法，指出其最坏情况下的时间复杂度。中 国 科 学 院 计 算 技 术 研 究 所一 九 九 二 年 招 收 硕 士 学 位 研 究 生 入 学 考 试 试 题 答 案试 题 名 称 ： 软 件 基 础一 . 填 空1 顺 序 结 构 、 链 表 结 构2 有 向 无 环 图3 程 序 共 行 （ 并 发 ） 、 资 源 共 享 （ 共 享 ）4 综 合 属 性 、 继 承 属 性5 互 斥 、 同 步6 系 统 资 源 不 足 、 进 程 推 进 顺 序 非 法7 严 格 计 算 （ 直 接 计 算 ） 、 短 路 计 算89 O（ m+n）10. 先 序 、 中 序 、 后 序 、 深 度 优 先 、 广 度 优 先二 .1 由 关 键 字 直 接 计 算 记 录 存 放 位 置 的 查 找 方 法 称 为 哈 希 查 找 。 （ 3 分 ）2 UNIX 系 统 中 设 备 管 理 的 特 点 有 ： （ 4 分 ）(a) 块 设 备 管 理 和 字 符 设 备 管 理 具 有 相 似 的 层 次 结 构 ；(b) 把 字 符 设 备 作 为 特 别 文 件 处 理 ；(c) 采 用 了 完 善 的 缓 冲 技 术 ；(d) 引 入 了 “ 预 先 读 ” 、 “ 异 步 写 ” 和 “ 延 迟 写 ” 方 式 。34 直 接 插 入 排 序 第 二 趟 的 结 果38 49 65 97 76 13 27 49快 速 排 序 第 二 趟 的 结 果13 27 38 49 49 65 76 97 1log2 n5 由 于 一 个 作 业 装 入 到 与 其 地 址 空 间 不 一 致 的 存 储 空 间 所 引 起 的 、 有 关 地址 部 分 的 填 整 过 程 ， 称 之 为 地 址 重 定 位 。 动 态 重 定 位 的 特 点 是 ： 在 程 序执 行 时 才 进 行 重 定 位 ， 它 需 要 硬 件 的 支 持 。6 逻 辑 结 构 指 数 据 元 素 之 间 的 逻 辑 关 系 ； 物 理 结 构 指 数 据 结 构 在 计 算 机 存储 中 的 映 像 。7 活 动 记 录 包 含 （ 答 对 4 个 即 可 得 分 ）(1) 临 时 工 作 单 元 ： 用 于 存 放 计 算 过 程 中 所 需 的 临 时 变 量 ；(2) 局 部 数 据 ： 用 于 存 放 对 应 当 前 活 动 记 录 的 程 序 单 元 的 局 部 数 据 ；(3) 保 存 机 器 态 部 分 ： 用 于 保 存 当 前 的 程 序 计 数 器 、 寄 存 器 的 值 等 等 ；(4) 访 问 链 ： 把 当 前 执 行 的 程 序 单 元 可 访 问 的 活 动 记 录 联 结 起 来 ；(5) 控 制 链 ： 把 所 有 活 动 记 录 按 它 们 生 成 的 次 序 联 结 起 来 ；(6) 实 在 参 数(7) 返 回 值8 该 变 量 在 编 译 时 被 优 化 掉 了 ， 所 以 无 法 检 查 其 值 。三 . 问 答 题 ：1(a) Fortran 的 词 法 分 析 比 Pascal 的 词 法 分 析 复 杂 ；(b) Fortran 语 言 将 一 行 分 为 标 号 、 续 行 、 语 句 、 注 释 四 个 区 ， 出 现 在 不 同区 域 的 符 号 具 有 不 同 的 含 义 。 词 法 分 析 器 必 须 结 合 符 号 出 现 的 位 置 才可 判 定 其 属 性 ； 而 Pascal 语 言 中 的 记 号 识 别 则 与 位 置 无 关 ；(c) Fortran 语 言 认 为 空 格 无 意 义 ， 使 得 对 某 些 符 号 的 识 别 取 决 于 后 面 的 符号 ； 而 在 Pascal 语 言 中 ， 每 遇 过 一 个 空 白 字 符 ， 则 认 为 一 个 记 号 已 识别 完 毕 。2 该 文 法 不 是 LR（ 1） 文 法 。 因 为 其 为 二 义 文 法 。S A1A2可 将 任 意 输 入 串 aa a 截 取 任 意 长 度 的 前 缀 归 约 为 A1， 而 将 剩 下 的 全部 归 约 为 A2。3 发 送 进 程 在 发 送 消 息 之 前 ， 先 在 自 己 的 内 存 空 间 设 置 一 发 送 区 ， 填 入消 息 正 文 等 信 息 ， 然 后 调 用 发 送 原 语 （ Send） 。 进 入 发 送 程 序 后 ， 先 找到 接 受 进 程 的 PCB， 再 申 请 获 得 一 消 息 缓 冲 区 空 间 ， 然 后 互 斥 进 入 接受 进 程 的 消 息 队 列 ， 找 到 队 尾 ， 把 消 息 缓 冲 区 挂 在 队 尾 ， 把 消 息 正 文及 长 度 等 从 发 送 区 复 制 到 消 息 缓 冲 区 ， 最 后 通 过 V操 作 通 知 接 收 进 程 ，并 退 出 发 送 程 序 ， 发 送 进 程 继 续 执 行 。 接 收 进 程 在 读 取 消 息 之 前 ， 先 在 自 己 的 内 存 空 间 设 置 一 接 收 区 ， 然 后使 用 Read 原 语 ， 在 进 入 读 取 程 序 后 ， 先 通 过 P 操 作 检 查 有 无 消 息 ，然 后 互 斥 进 入 消 息 队 列 ， 移 出 队 列 中 的 第 一 个 消 息 ， 并 把 消 息 从 缓 冲区 复 制 到 接 收 区 ， 最 后 释 放 缓 冲 区 ， 退 出 读 取 程 序 ， 接 收 进 程 继 续 执