云南大学计算机工程与技术复试题

2009 操作系统和编译原理 操作系统的主要功能是什么 操作系统的功能 1 操作系统的主要功能 资源管理 程序控制 人机交互 2 计算机系统的资源可分为设备资源和信息资源两大类 3 操作系统包括五个方面的管理功能 进程与处理器管理 作业管理 存储管理 设备管理 文件管理 什么是进程 进程和程序的区别是什么 从用户角度来看 进程是应用程序的一个执行过程 从操作系统核心角度来看 进程代表 的是操作系统分配的内存 CPU 时间片等资源的基本单位 是为正在运行的程序提供的运 行环境 进程与应用程序的区别在于应用程序作为一个静态文件存储在计算机系统的硬盘 等存储空间中 而进程则是处于动态条件下由操作系统维护的系统资源管理实体 区别 1 进程是一个动态概念 而程序是一个静态概念 程序是指令的有序集合 无执行含义 进程则强调执行的过程 2 进程具有并行特征 独立性 异步性 程序则没有 3 不同的进程可以包含同一个程序 同一程序在执行中也可以产生多个进程 自底向上的语法分析的关键是什么 什么时候进行归约 按照哪条产生式进行归约 数据结构和算法 什么是算法的时间复杂度 如果一个问题的规模是 n 解决这一问题所需算法所需要的时间是 n 的一个函数 T n 则 T n 称为这一算法的时间复杂度 简述数据的逻辑结构和物理结构的概念和两者的关系 数据元素之间的逻辑关系称为数据的逻辑结构 数据的逻辑结构可以看作是从具体问题抽 象出来的数学模型 它与数据的存储无关 数据结构在计算机中的表示 又称映像 称为 数据的物理结构 或称存储结构 它所研究的是数据结构在计算机中的实现方法 包括数 据结构中元素的表示及元素间关系的表示 什么是算法 算法的性质有哪些 算法就是解决问题的方法 算法的一般性质包括 通用性 对于那些符合输入类型的任意输入数据 都能根据算法进行问题求解 包保证计 算结构的正确性 有效性 组成算法的每一条指令都必须是能够被人或机器确切执行的 确定性 算法每执行一步之后 对于它的下一步 应该有明确的指示 即 保证每一步之 后都有关于下一步动作的指令 不能缺乏下一步指令或仅仅含有模糊不清的指令 有穷性 算法的执行必须在有限步内结束 快速排序在什么情况下效率最高 什么情况下最差 最坏情况下 是整个序列都已经有序或完全倒序 此时最差 相反则最高 什么是递归算法 递归算法就是一个函数通过不断对自己直接或间接的调用而求得最终结果的一种思维巧妙 但是开销很大的算法 堆的特征是什么 如何利用堆进行排序 大顶堆是建立一个完全二叉树 然后将最大值输出 什么是贪心算法 贪心算法就是总是做出在当前看来最好的选择 也就是说贪心算法并不是从整体最优考虑 它所做出的选择只是在某种意义上的局部最优选择 贪心算法不弄对所有问题都产生整体 最优解 但对很多问题它能产生整体最优解 在一些情况下 即使贪心算法不能得到整体 最优解 其结果却是最优解的很好近似 树的遍历有几种方法 先序遍历 中序遍历 后序遍历 对链表设置头节点的好处是什么 它具有两个优点 1 由于开始结点的位置被存放在头结点的指针域中 所以在链表的第一 个位置上的操作就和在表的其它位置上操作一致 无须进行特殊处理 2 无论链表是否为 空 其头指针是指向头结点的非空指针 空表中头结点的指针域空 因此空表和非空表的 处理也就统一了 分治法的基本思想是什么 为什么采用递推关系进行分治算法的时间复杂度分析 分治法的设计思想是 将一个难以直接解决的大问题 分割成一些规模较小的相同问题 以便各个击破 分而治之 分治法是用递归算法解决问题的 离散数学 什么是命题和谓词的区别 什么是等价关系 设 R 是定义在集合 A 上的一个关系 若 R 是自反的 对称的和传递的 则 R 称为等价关 系 什么是偏序关系 设 A 是一个集合 如果 A 上的一个关系 R 满足自反性 反对称性和传递性 则称 R 是 A 上的一个偏序关系 什么是全序关系 在偏序集中 如果 A 是一个链 则称为全序集合 在这种情况下 二元关 系 称为全序关系 首先你要知道什么是二元关系 比如实数中的 大小 关系 集合的集合中的 包含 关系就是两种二元关系 所谓偏序 即偏序关系 是一种二元关系 所谓全序 即全序关系 自然也是一种二元关系 全序是指 集合中的任两个元素之间都可以比较的关系 比如实数中的任两个数都可以比 较大小 那么 大小 就是实数集的一个全序关系 偏序是指 集合中只有部分元素之间可以比较的关系 比如复数集中并不是所有的数都可 以比较大小 那么 大小 就是复数集的一个偏序关系 显然 全序关系必是偏序关系 反之不成立 任何命题的主合取范式都是存在并且唯一吗 存在 但是不唯一 简述有向图和无向图的关系 软件工程 谈谈你对软件工具的理解 你用过什么软件工具 软件工具是指为支持计算机软件的开发 维护 模拟 移植或管理而研制的程序系统 它 是为专门目的而开发的 在软件工程范围内也就是为实现软件生存期中的各种处理活动 包括管理 开发和维护 的自动化和半自动化面开发的程序系统 什么是软件的可维护性 软件可维护性即维护人员对该软件进行维护的难易程度 具体包括理解 改正 改动和改进 该软件的难易程度 决定可维护性的因素 1 系统的大小 2 系统的年龄 3 结构 合理性 可维护性可通过 7 个质量特性来衡量 可理解性 可测试性 可修改性 可靠性 可移植性 可使用性 效率 软件开发和写程序有什么不同 软件包含程序 程序是软件的一部分 软件是程序 数据及其相关文档的完整集合 程序只是为了实现软件的功能和性能要求而编写的指令序列 什么是软件设计的 高内聚 低耦合 内聚就是一个模块内各个元素彼此结合的紧密程度 高内聚就是一个模块内各个元素彼此 结合的紧密程度高 耦合 一个软件结构内不同模块之间互连程度的度量 高内聚就是一个模块之间的代码的相关性强 低耦合就是不同模块之间的互联程度低 简述 CASE 在软件工程中的作用 CASE 即 Computer Aided Software Engineering 中文意思是计算机辅助软件工程 在 CASE 工具辅助下进行软件开发 可以提高软件开发效率 改善软件质量 为什么要进行软件测试 常用软件测试方法有哪些 1 软件测试是为了发现错误而执行程序的过程 2 一个好的测试用例能够发现至今尚未发现的错误 3 一个成功的测试是发现了至今尚未发现的错误的测试 因此 测试阶段的基本任务应该是根据软件开发各阶段的文档资料和程序的内容结构 精 心设计一组 高产 的测试用例 利用这些用例执行程序 找出软件中潜在的各种错误和 缺陷 方法 静态测试 动态测试 动态测试根据测试用例的设计方法不同 分为黑盒测试和白 盒测试 谈谈你对保证软件质量的技术和方法的认识 以检测为重 以过程管理为重 以新产品开发为重 提高软件生产率有哪些基本手段 使用软件重用技术可以减少软件开发活动中大量的重复性工作 这样就能提高软件生产率 什么是软件的可靠性和可用性 软件的可靠性 指在给定的时间内 在规定的环境条件下系统完成所指定功能的概率 软件的可用性 产品在特定使用环境下为特定用户用于特定用途时所具有的有效性 效率 和用户主观满意度 可靠性就是指运行的稳定性 可用性就是操作的便利性 什么是软件重用 实现软件重用的方法有哪些 软件重用 是指在两次或多次不同的软件开发过程中重复使用相同或相似软件元素的过程 软件元素包括程序代码 测试用例 设计文档 设计过程 需要分析文档甚至领域知识 1 知识重用 例如 软件工程知识的重用 2 方法和标准的重用 例如 面向对象 方法或国家制定的软件开发规范的重用 3 软件成分的重用 什么是软件移植 你认为若构造一个工具 实现 Windows 软件到 Unix Linux 的移植有意义吗 难 度大不大 使某软件在不同的计算机平台上进行有效转换 从而达到多系统兼容 数据库 数据库系统的基本概念 数据 实际上就是描述事物的符号记录 数据的特点 有一定的结构 有型与值之分 如整型 实型 字符型等 而数据的值 给出了符合定型的值 如整型值 15 数据库 是数据的集合 具有统一的结构形式并存放于统一的存储介质内 是多种应 用数据的集成 并可被各个应用程序共享 数据库存放数据是按数据所提供的数据模式存放的 具有集成与共享的特点 数据库管理系统 一种系统软件 负责数据库中的数据组织 数据操纵 数据维护 控制及保护和数据服务等 是数据库的核心 数据库管理系统功能 1 数据模式定义 即为数据库构建其数据框架 2 数据存取的物理构建 为数据模式的物理存取与构建提供有效的存取方法与手段 3 数据操纵 为用户使用数据库的数据提供方便 如查询 插入 修改 删除等以 及简单的算术运算及统计 4 数据的完整性 安生性定义与检查 5 数据库的并发控制与故障恢复 6 数据的服务 如拷贝 转存 重组 性能监测 分析等 为完成以上六个功能 数据库管理系统提供以下的数据语言 1 数据定义语言 负责数据的模式定义与数据的物理存取构建 2 数据操纵语言 负责数据的操纵 如查询与增 删 改等 3 数据控制语言 负责数据完整性 安全性的定义与检查以及并发控制 故障恢复 等 数据语言按其使用方式具有两种结构形式 交互式命令 又称自含型或自主型语言 宿 主型语言 一般可嵌入某些宿主语言中 数据库管理员 对数据库进行规划 设计 维护 监视等的专业管理人员 数据库系统 由数据库 数据 数据库管理系统 软件 数据库管理员 人员 硬 件平台 硬件 软件平台 软件 五个部分构成的运行实体 数据库应用系统 由数据库系统 应用软件及应用界面三者组成 文件系统阶段 提供了简单的数据共享与数据管理能力 但是它无法提供完整的 统 一的 管理和数据共享的能力 层次数据库与网状数据库系统阶段 为统一与共享数据提供了有力支撑 关系数据库系统阶段 数据库系统的基本特点 数据的集成性 数据的高共享性与低冗余性 数据独立性 物理独立性与逻辑独立性 数据统一管理与控制 数据库系统的三级模式 1 概念模式 数据库系统中全局数据逻辑结构的描述 全体用户公共数据视图 2 外模式 也称子模式与用户模式 是用户的数据视图 也就是用户所见到的数据 模式 3 内模式 又称物理模式 它给出了数据库物理存储结构与物理存取方法 数据库系统的两级映射 1 概念模式到内模式的映射 2 外模式到概念模式的映射 4 2 数据模型 数据模型的概念 是数据特征的抽象 从抽象层次上描述了系统的静态特征 动态行 为和约束条件 为数据库系统的信息表与操作提供一个抽象的框架 描述了数据结构 数 据操作及数据约束 E R 模型的基本概念 1 实体 现实世界中的事物 2 属性 事物的特性 3 联系 现实世界中事物间的关系 实体集的关系有一对一 一对多 多对多的联 系 E R 模型三个基本概念之间的联接关系 实体是概念世界中的基本单位 属性有属性 域 每个实体可取属性域内的值 一个实体的所有属性值叫元组 E R 模型的图示法 1 实体集表示法 2 属性表法 3 联系表示法 层次模型的基本结构是树形结构 具有以下特点 1 每棵树有且仅有一个无双亲结点 称为根 2 树中除根外所有结点有且仅有一个双亲 从图论上看 网状模型是一个不加任何条件限制的无向图 关系模型采用二维表来表示 简称表 由表框架及表的元组组成 一个二维表就是一 个关系 在二维表中凡能唯一标识元组的最小属性称为键或码 从所有侯选健中选取一个作为 用户使用的键称主键 表 A 中的某属性是某表 B 的键 则称该属性集为 A 的外键或外码 关系中的数据约束 1 实体完整性约束 约束关系的主键中属性值不能为空值 2 参照完全性约束 是关系之间的基本约束 3 用户定义的完整性约束 它反映了具体应用中数据的语义要求 4 3 关系代数 关系数据库系统的特点之一是它建立在数据理论的基础之上 有很多数据理论可以表 示关系模型的数据操作 其中最为著名的是关系代数与关系演算 关系模型的基本运算 1 插入 2 删除 3 修改 4 查询 包括投影 选择 笛卡尔积运算 4 4 数据库设计与管理 数据库设计是数据应用的核心 数据库设计的两种方法 1 面向数据 以信息需求为主 兼顾处理需求 2 面向过程 以处理需求为主 兼顾信息需求 数据库的生命周期 需求分析阶段 概念设计阶段 逻辑设计阶段 物理设计阶段 编码阶段 测试阶段 运行阶段 进一步修改阶段 需求分析常用结构析方法和面向对象的方法 结构化分析 简称 SA 方法用自顶向下 逐层分解的方式分析系统 用数据流图表达数据和处理过程的关系 对数据库设计来讲 数据字典是进行详细的数据收集和数据分析所获得的主要结果 数据字典是各类数据描述的集合 包括 5 个部分 数据项 数据结构 数据流 可以是 数据项 也可以是数据结构 数据存储 处理过程 数据库概念设计的目的是分析数据内在语义关系 设计的方法有两种 1 集中式模式设计法 适用于小型或并不复杂的单位或部门 2 视图集成设计法 设计方法 E R 模型与视图集成 视图设计一般有三种设计次序 自顶向下 由底向上 由内向外 视图集成的几种冲突 命名冲突 概念冲突 域冲突 约束冲突 关系视图设计 关系视图的设计又称外模式设计 关系视图的主要作用 1 提供数据逻辑独立性 2 能适应用户对数据的不同需求 3 有一定数据保密功能 数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径 以 提高数据库访问速度有效利用存储空间 一般 RDBMS 中留给用户参与物理设计的内容大 致有索引设计 集成簇设计和分区设计 数据库管理的内容 1 数据库的建立 2 数据库的调整 3 数据库的重组 4 数据库安全性与完整性控制 5 数据库的故障恢复 6 数据库监控 Armstrong 公理的完备性的含义是什么 Armstrong 公理系统的完备性指的是 对于 R 所逻辑蕴含的每一函数依赖 必定可以由 R 出发根据 Armstrong 公理系统推导出来 相对文件系统而言 数据库的数据独立性指什么 数据库的数据独立性包括物理数据独立性和逻辑数据独立性 物理独立性 用户应用程序与数据库中数据彼此独立 应用程序不需了解数据库中数据 如何存储 通过模式 内模式映射实现 逻辑独立性 用户应用程序与数据库的逻辑结构相互独立 数据的逻辑结构改变了 应 用程序可以不变 通过外模式 模式映射实现 简述数据库中码的概念 简述数据库中依赖逻辑蕴含的概念 网络与分布式 什么是 CSMA CD 简述其基本原理 CSMA CD 是英文 carrier sense multiple access collision detected 的缩写 可把它翻成 载波 侦察听多路访问 冲突检测 或 带有冲突检测的载波侦听多路访问 所谓载波侦听 carrier sense 意思是网络上各个工作站在发送数据前都要总线上有没有数据传输 若干 数据传输 称总线为忙 则不发送数据 若无数据传输 称总线为空 立即发送准备好 的数据 所谓多路访问 multiple access 意思是网络上所有工作站收发数据共同使用同一条 总线 且发送数据是广播式的 所谓冲突 collision 意思是 若网上有两个或两个以上 工作站同时发送数据 在总线上就会产生信号的混合 哪个工作站都同时发送数据 在总 线上就会产生信号的混合 哪个工作站都辨别不出真正的数据是什么 这种情况称数据冲 突又称碰撞 为了减少冲突发生后又的影响 工作站在发送数据过程中还要不停地检测自 己发送的数据 有没有在传输过程中与其它工作站的数据发生冲突 这就是冲突检测 工作原理 先听后发 边发边听 冲突停发 随机重发 简述模拟信号数字化的基本原理 在网络多路复用机制中 ADSL 采用的是哪一种 多路复用技术主要有 多路复用技术主要有 频分多路复用 时分多路复用 波分复用 码分复用 ADSL 采用频分多路复用 TCP 传输连接建立时为什么要使用 三次握手 的机制 简述虚电路和数据报 数据报 Datagram 面向无连接的数据传输 工作过程类似于报文交换 采用数据报方式传输时 被 传输的分组称为数据报 虚电路 Virtual Circuit 的概念 虚电路是面向连接的数据传输 工作过程类似于线路交换 不同之处在于此时 的电路是虚拟的 对比的方面虚电路数据报 连接的建立必须有不要 目的站地址仅在连接建立阶段使用 每个 分组使用短的虚电路号 每个分组都有目的站的全地址 路由选择在虚电路连接建立时进行 所 有分组均按同一路由 每个分组独立选择路由 当路由器出故障所有通过了出故障的路由器的 虚电路均不能工作 出故障的路由器可能会丢失分 组 一些路由可能会发生变化 分组的顺序 总是按发送顺序到达目的站到达目的站时可能不按发送顺 序 端到端的差错处理由通信子网负责 由主机负责 端到端的流量控制 由通信子网负责 由主机负责 什么是 IP 地址 逻辑上 IP 地址如何构成 所谓 IP 地址就是给每个连接在 Internet 上的主机分配的一个 32bit 地址 半双工总线型局域网的覆盖范围取决于什么因素 通常路由协议有距离向量法和链路状态法 RIP 和 OSPF 分别是哪一种 RIP 是距离向量法 OSPF 是链路状态法 OSPF 是链路状态路由协议 而 RIP 是距离矢量路由协议 简述计算机网络和分布式系统的异同 计算机网络中每台电脑都是独立的 同等重要的 分布式计算机系统中有主电脑和终端之分 计算机网络是指将有独立功能的多台计算机 通过通信设备线路连接起来 在网络软件的 支持下 实现彼此之间资源共享和数据通信的整个系统 网际互联常用的网间连接器有哪些 分别对应哪一层的协议转换 TCP IP 和 OSI 网络体系结构的异同 什么是网桥 网桥工作在数据链路层 它根据 MAC 帧的目的地址对收到的帧进行转发或过滤 当网桥 收到一个帧时 并不是向所有的接口转发此帧 而是先检查此帧的目的 MAC 地址 然后 再确定将该帧转发到哪一个接口 或者是把它丢弃 网桥分为透明网桥和源路由网桥两大 类 谈谈你了解的几种网络安全技术 你认为他们分别适用于什么场合 Internet 划分成很多自治系统 AS 在 AS 内部和 AS 之间的路由通常采用什么协议实现路由 选择 简述数据链路层和传输层在流量控制上的区别 决定局域网特征的主要技术有哪些 a 用来传输数据的传输介质 b 用来连接各种设备的拓补结构 c 用以共享资源的介质访问控制方法 这三种技术在很大程度上决定了传输数据的类型 网络的响应 吞吐量和效率 以及网络 的应用等各种网络特性 七 面向对象 面向对象方法的 封装性 有什么问题 怎样解决 为什么说面向对象设计所获得的软件结构同问题本身的结构是一致的 继承机制是面向对象技术的重要特征 谈谈继承机制软件技术所产生的作用 简述面向对象方法的概念 一 在后序遍历的线索二叉树中 如何找结点直接前驱 在中序线索二叉树中 如何 找节点的直接前驱 中序线索二叉树 若结点的 ltag 1 lchild 指向其前驱 否则 该结点的前驱是以该结 点为根的左子树上按中序遍历的最后一个结点 若 rtag 1 rchild 指向其后继 否则 该结点的后驱是以该结点为根的右子树上按中序遍历的第一个结点 在后序线索二叉树 中查找结点 p 的前驱 若结点 p 无左子树 则 p lchild 指向其前驱 否则 若结点 p 有左子树 当其右子树为空时 其左子树的根 即 p lrchild 为其后序前驱 当其右 子树非空时 其右子树的根 即 p rchild 为其后序前驱 在后序线索二叉树中查找结点 p 的后继 若结点 p 为根 则无后继 若结点 p 为其 双亲的右孩子 则其后继为其双亲 若结点 p 为其双亲的左孩子 且双亲无右子女 则其 后继为其双亲 若结点 p 为其双亲的左孩子 且双亲有右子女 则结点 p 的后继是其双亲 的右子树中按后序遍历的第一个结点 所以 求后序线索二叉树中结点的后继要知道其双 亲的信息 要使用栈 所以说后序线索二叉树是不完善的 二 高速缓冲存储器 主存和主存 辅存的差别 cache 与主存的信息交换速度相当快 主存与辅存之间的交换很慢 因为外寸其实就是外设 需要 I O 指令才行 有 DMA 的可直接交换 没有 DMA 的需要 CPU 当中介 CACHE 与主存之间是以 块 为单