计算机软件技术基础复习题.pdf

1 计算机软件技术基础复习题 一 基本概念 1 在操作系统中 进程是资源分配 调度和管理的最小单位 2 进程在运行过程中有 3 种基本状态 它们是运行态 就绪态和等待待态 3 计算机系统的层次结构中 位于硬件系统之外的所有层次统称为虚拟机 4 操作系统向用户提供了 3 种类型界面 分别是命令界面 程序界面和图形界面 5 进程与程序的根本区别在于静态与动态的特点 6 存储器间接寻址方式指令中给出的是操作数地址所在的存储地址 CPU 需要访问内存两 次才能获得操作数 7 操作系统中引入多道程序设计的目的是提高设备利用率 8 引入缓冲的主要目的是改善 CPU 和 I O 设备之间速度不匹配的情况 9 I O 通道方式的数据交换方式是存储设备与 I O 设备直接交换信息而不经过 CPU 来完成 10 CPU 输出数据的速度远远高于打印机的打印速度 可以采用缓冲技术解决这一矛盾 11 采用页式存储管理不会产生内存碎片 12 冯诺依曼计算机工作方式的基本特点是按地址访问并顺序执行 13 计算机主频的周期是指时钟周期 14 存储周期是指存储器进行连续读写操作所允许的最短时间间隔 15 CPU 输出数据的速度远远高于打印机的打印速度 可以采用缓冲技术解决这一矛盾 16 提供支持程序浮动的寻址方式是相对寻址 17 计算机的外围设备是指除了 CPU 和内存以外的其它设备 18 在主存和 CPU 之间增加 Cache 的目的是解决主存和 CPU 之间速度不匹配的问题 19 操作系统的功能包括处理机管理 存储管理 文件管理和设备管理 20 现在主要采用总线结构作为计算机硬件之间的连接方式 21 一般的程序设计语言的定义都涉及语法 语义和语用三个方面 其中描述如何用语言基 本符号组成程序中各个语法成分的一组规则称为语法 对程序中各个语法成分含义的描 述称为语义 涉及语言符号及其使用者之间关系的内容称为语用 22 程序设计语言一般分为低级语言和高级语言两大类 其中低级语言又称为面向机器的语 言 高级语言又称为通用程序语言 23 计算机软件开发技术的发展 经历了面向机器的编程 面向过程的软件开发 面向对象 的软件开发和面向组件的软件开发等若干阶段 24 程序设计方法的分类 按设计技术大致可以分为 结构化程序设计方法 面向对象程序 设计方法 组件化程序设计方法 分布式程序设计方法和嵌入式程序设计方法等 25 DFA 的含义是确定的有穷自动机 确定的意思是指状态变迁函数的每次转向的状态是唯 一的 26 乔姆斯基 Chomsky 把文法分成四种类型 其中 2 型文法又称为上下文无关文法 3 型 文法又称为正则或正规文法 27 编译方式与解释方式的根本区别在于是否生成目标代码 28 编译程序的工作一般分为以下过程 词法分析 语法分析 语义分析 中间代码 生成 目标代码生成 代码优化 29 动态存储分配时 可以采用的分配方法有栈式存储分配和堆存储分配 30 在自底向上语法制导翻译中 带有语义信息的语法树随着归约动作自底向上建立起来的 在这一过程中 句柄归约和语义动作调用的关系是同时动作 31 文法的二义性和语言的二义性是两个不同的概念 32 在属性文法的翻译中 若为文法符号设置属性变量时 如果该属性的值是沿语法树自底 2 向上给出 则为它设置综合属性 33 自顶向下的分析是以文法的开始符号为树根 采用最左推导方法 逐步地为输入符号串 自上而下地构造一棵语法树 34 在属性文法的翻译中 若为文法符号设置属性变量时 如果该属性的值是沿语法树自上 而下给出 则为它设置继承属性 35 一个上下文无关文法称为是 LL 1 文法 当且仅当同一非终结符的各个产生式的可选集 互不相交 36 路由器技术的核心内容是提高路由器性能的方法 37 典型的局域网可以看成三部分构成 网络服务器 工作站和通信设备 38 在数据传输过程中 经常要增加一位来校验数据传输的正确性 该位称为奇偶校验位 39 在网络的拓扑结构中 中心结点的故障对星型拓扑结构危害最大 40 1000 BASE T 标准 使用 5 类非屏蔽双绞线 双绞线长度可达到 100m 41 所有 IP 地址都由国际组织 NIC 负责统一分配 其中 ENIC 负责欧洲地区 APNIC 负责 亚太地区 lnterNIC 负责美国及其他地区 42 关于 POP3 说法是 电子邮件客户端应用程序从邮件服务器接收邮件时使用的协议 43 集线器运行在 OSI 的物理层和链路层 路由器运行在 OSI 的网络层 44 在网络的拓扑结构中 常见的有星型拓扑结构 环形拓扑结构 树型拓扑结构和网状 拓扑结构 45 因特网的域名体系代表实际物理连接 46 虚拟企业的技术平台一般采用企业内部网 Intranet 47 从网络拓扑结构上说 CSMA CD 与 Token Bus 是针对总线拓扑结构的局域网设计的 48 计算机网络发展的奠基石是美国的 ARPANET 网络 49 关于防火墙的功能是 可以检查进出内部网络的通信量 可以使用应用网关在应用层上 建立协议过滤和转发功能 可以使用过滤技术在网络层对数据包进行选择 50 建立计算机网络的主要目的是实现计算机资源的共享 二 简答题 1 操作系统的概念及功能 操作系统 操作系统是系统软件 它管理计算机的资源并提高各种资源的使用效率 控 制程序的正常执行 为用户提供一个友好界面 方便用户使用 操作系统的功能 实现处理机管理 存储管理 设备管理 文件管理并为用户提供使用 接口 2 试叙述 Spooling 系统的基本思想 在硬盘中开辟两个缓冲区 输入井和输出井 只要输入井中有空闲空间 就可以不断地 把作业送入输入井 只要内存中有空闲空间 就可以从输入井中调若干作业进入内存运行 运行结果不是直接送输出设备 而是送入输出井 只要输出设备空闲 就可以从输出井中取 出结果输出 从而实现了输入 运行与输出的并行工作 3 进程的几种基本状态及其转换 进程有三种基本状态 就绪态 运行态和等待态 就绪态因调度运行态 运行态发生某一事件等待态 运行态时间片到就绪态 等待态事件已经发生就绪态 或画图 p46 图 3 5 4 CISC 指令集结构的缺点 3 CISC 指令集结构的缺点是 大部分指令使用频率较低 无论是硬件还是软件上都造成很大浪费 指令系统的复杂性带来了计算机体系结构的复杂 增加了成本且易产生错误 指令系统的复杂性使 VLSI 大规模集成电路 的设计变得复杂 由于指令系统的复杂 使得运行速度变慢 由于指令系统的不均衡性 指令长度的种类多 指令周期不同等 不利于采用先进 技术来提高系统性能 5 简单说明 RISC 指令集结构的设计原则 RISC 指令集结构的设计原则是 指令集中只保留使用频率高的指令和常用指令 保证指令系统的均衡性 即指令尽可能简单 最好在一个机器周期内完成 指令最好 等长 或限制长度的种类 指令的操作尽可能在寄存器内完成任务 以简单有效的方式支持现代编程技术 如增加对高级语言的支持 6 解释什么是主存的访问时间 存储周期 存储器频宽 存储器带宽和存储器宽度 访问时间 主存储器从接到访问请求到信息被读到数据总线上所需的时间 存储周期 连续两次访问请求之间的最小时间间隔 存储器频宽 存储器被连续访问时 每秒钟传送信息的位数 存储器带宽 存储器每个时钟周期传送的字节数 存储器宽度 一次可以访问的字节数 7 解释什么是指令周期 机器周期 CPU 周期 和时钟周期 它们之间有什么关系 指令周期 取出并执行一条指令所需的时间 包括取指 分析和执行所需的全部时间 机器周期 指令周期可划分为几个阶段 每个阶段所需的时间 通常指取指时间 时钟周期 又称节拍周期 是处理操作的最基本单位 它们之间的关系 一个指令周期包含若干个机器周期 一个机器周期包含若干时钟周期 8 某虚拟存储器的用户空间共有 32 个页 每页 1KB 主存 16KB 假定某时刻系统为用户 的第 0 1 2 3 页分别分配的物理块号分别为 5 10 4 7 试回答 写出逻辑地址和物理地址的格式 虚拟地址 0A5CH 对应的物理地址是多少 画图表示该虚拟地址映射到物理地址的变换过程 逻辑 页号 5 位 页内 10 位物理 块号 4 位 块内 10 位 125CH 9 一个 460 字的程序 其内存访问序列为 10 11 104 170 73 309 185 245 246 434 458 364 假定页面大小为 100 个字 内存中有 200 个字供该程序使用 回答下列问题 页表起始地址 页表长度 0 5 1 10 2 4 3 7 00010 1001011100 0100 1001011100 4 给出页面访问序列 例如 此题前 5 个页面访问序列为 0 0 1 1 0 采用先进先出的页面替换算法 其缺页次数是多少 采用最近最少使用的页面替换算法 其缺页次数是多少 0 0 1 1 0 3 1 2 2 4 4 3 6 次 7 次 10 若某计算机数据线 地址线都是 8bit 有一条相对寻址的无条件转移指令存于主存的 20H 单元中 指令给出的位移量 D 00010101B 设该指令占用 2 个字节 问 取该指令时 PC 的内容 该指令执行结束时 PC 的内容 取该指令时 PC 的内容是 20H 该指令执行结束时 PC 的内容是 PC 2 D 00100000 00000010 00010101 00110111B 37H 11 计算机系统中总线结构的概念及优点 总线 所谓总线就是指若干信号线的集合 由这些信号线组成在两个以上部件间传送信 息的公共通路 用途 沟通计算机系统中各部件的信息传递 并使不同厂商提供的产品能互换组合 优点 便于故障诊断和维修 便于模块化结构设计 简化了系统设计 便于系统的扩展 和升级 便于生产各种兼容的软硬件 12 举例说明计算机编译程序和解释程序 编译程序就是一个语言翻译程序 它把一种语言 称作源语言 书写的程序翻译成另一种 语言 称作目标语言 的等价的程序 源语言通常是一个高级语言 如 FORTRAN C 或 Pascal 目标语言通常是一个低级语言 如汇编或机器语言 这里 高级语言 FORTRAN C 或 Pascal 的编译器就是编译程序 还有一种高级语言翻译程序 从源程序的编译到执行只有一个阶段 解释执行阶段 它同时处理源程序和数据 按源程序中语句的动态顺序 逐句地进行分析解释 并立即予以 执行 这种翻译程序称为解释程序 最常见的高级语言 BASIC 就是在解释环境下运行的 在 解释方式下 最终并不生成目标程序 这是编译方式与解释方式的根本区别 13 简述组件化的软件开发技术的活动过程 组件化的软件开发技术的活动过程是 1 收集组件 这一活动是指对从本地或远程资源可获得的组件进行仔细分析 从中发现并收集对自己 有用的组件 2 改善组件质量 这一活动是指在仔细分析组件的文档或详细说明书的基础之上 与组件开发商和用户进 行必要的讨论 并在不同的环境设置下运行组件 发现组件中可能存在的不足之处 并加以 改进 使之达到改善组件质量的目的 3 使组件能相互适应 这一活动是指通过编写一些简单的程序作为用户需求与组件产生的相应动作之间的缓 冲区 这个缓冲区可给组件提供缺省的信息 减少不希望发生的动作 实现互操作 4 组装组件 这一活动是指通过一些通用的基础设施 对组件仓库中的组件进行集成 组装出软件 由组件组装的系统容易重新组合以满足新的需求 5 14 路由器与交换机的区别 路由器的一个作用是连通不同的网络 另一个作用是选择信息传送的线路 路由器与交换机的区别体现在以下四个方面 1 工作层次不同 交换机工作在 OSI 的第二层 数据链路层 它的工作原理比较简单 路由器工作在 OSI 的第三层 网络层 可以得到更多的协议信息 路由器可以做出更加智能的转发决策 2 数据转发所依据的对象不同 交换机是利用物理地址或者 MAC 地址来确定转发数 据的目的地址 而路由器则是利用不同网络的 IP 地址来确定数据转发的地址 3 传统的交换机只能分割冲突域 不能分割广播域 而路由器可以分割广播域 4 路由器提供了防火墙的服务 它仅仅转发特定地址的数据包 不传送不支持路由 协议的数据包传送和未知目标网络数据包的传送 从而可以防止广播风暴 15 网关的主要功能及分类 网关的主要功能是计算路由和跨越可见的局域网的最初边界 传输分组数据 因此它被 看作是通往 Internet 的大门 主要有 3 类网关 协议网关 应用网关和安全网关 它们之间惟一的共同特性就是网关 作为两个不同区域 地区或系统间的中介所起的功能是相同的 协议网关常用在使用不同协议的网络间进行协议转换 应用网关是在两种不同格式问翻译数据的系统 安全网关是一些技术的混合 这些技术很重要 而且互不相同 并足以代表它们各自的 类别 这些技术的范围可从协议层的过滤到相当复杂的应用层过滤 16 TCP IP 参考模型的应用层协议名称及功能 应用层包含所有的高层协议 应用层协议 如网络终端协议 Telnet 允许一台计算机上的用户登录到远程计算机上并进行操作 文件传输协议 FTP 用于文件传输 简单邮件传输协议 SMTP 用于电子邮件系统进行邮件的发送 简单网络管理协议 SNMP 用于网络的管理 如网络设备的配置与管理 超文本传输协议 HTTP 用于 WWW 服务 浏览网页 17 TCP IP 参考模型的各层名称及功能 TCP IP 参考模型将网络划分为四个层次 主机一网络层 互联层 传输层和应用层 1 主机一网络层 主机一网络层包含了 OSl 参考模型中的物理层和数据链路层 也叫网络接口层或网络存 取层 是 TCP IP 参考模型的最底层 负责通过网络发送和接收 IP 数据包 2 互联层 互联层是整个体系结构的关键部分 使主机可以把分组发往任何网络并到达目的主机 与 OSI RM 参考模型的网络层一样 这一层主要处理路由选择 流量控制和网络拥塞 3 传输层 TCP IP 参考模型中传输层的主要功能是在网络中的源主机与目的主机的对等实体间建 立基于会话的端到端连接 4 应用层 由于没有需要 所以 TCP IP 参考模型没有表示层和会话层 传输层之上便是应用层 18 网桥的作用及分类 网桥是一个局域网与另一个局域网之间建立连接的桥梁 网桥属于网络层的一种设备 它的作用是扩展网络和通信手段 在各种传输介质中转发数据信号 扩展网络的距离 同时 又有选择地将有地址的信号从一个传输介质发送到另一个传输介质 并能有效地限制两个介 6 质系统中无关紧要的通信 网桥可分为本地网桥和远程网桥 本地网桥是指在传输介质允许长度范围内互联网络的 网桥 远程网桥是指连接的距离超过网络的常规范围时使用的远程桥 通过远程桥互联的局 域网将成为城域网或广域网 如果使用远程网桥 则远程桥必须成对出现 19 以太网技术的优缺点 优点 使用最为广泛 协议简单 站点接入与安装很方便 在低负载时基本没有时延 缺点 发送时延的不确定 不适合实时性 网络负载加重 网络效率就下降很多 无忧 先级 确保正确信号检测 限制了站间的最大距离 发送数据前 要进行冲突检测 发送时 世要监听 最小帧长 64 字节 大量使用模拟部件 20 给出下述文法所对应的正规式 S 0A 1B A 1S 1 B 0S 0 把后两个产生式代入第一个产生式有 S 01 01S S 10 10S 有 S 01S 10S 01 10 01 10 S 01 10 01 10 01 10 即 01 10 01 10 为所求的正规式 三 分析与设计 1 银行家算法中 有 A B C D 四种资源 五个进程 考虑如下的资源分配状态 其中 AL 为可用资源向量 U 为各进程已占用资源矩阵 N 为各进程尚需资源矩阵 ABCDABCD AL 1 6 2 2 0032p1 1000p2 U 1354p3 0332p4 0014p5 0012p1 1750p2 N 2356p3 0652p4 0656p5 回答下列问题 简单叙述什么是银行家算法 为什么它可以避免产生死锁 该状态是安全状态吗 为什么 如果进程 P3 提出资源请求 1 2 2 1 能否立即给予满足 要求给出计算过程 各资源矩阵的变化情况 当某一进程申请一组资源时 要先测试系统是否安全 如果安全则可以分配 否则不予分 配 测试的方法是 是否能找到一个安全序列 保证在任一时刻系统所剩资源至少满足一个进 程的最大需求 如能找到则系统安全 可以分配 否则系统不安全 不予分配 此时存在一个安全序列 P1 P4 P5 P2 P3 故系统是安全的 若 P3 提出请求 1 2 2 1 因为 1 2 2 1 2 3 5 6 7 1 2 2 1 0 2 1 n0m1m0n n m 0 1 所求文法为 G S S A a b P S 其中 P 为 S AA A aAb 2 所求文法为 G S S A 0 1 P S 其中 P 为 S 1S0 A A 0A1 8 已知 NFA x y z 0 1 M x z 其中 M x 0 z M y 0 x y M z 0 x z M x 1 x M y 1 M z 1 y 构造相应 的 DFA 根据题意有 NFA 图如下 下表由子集法将 NFA 转换为 DFA II0 closure MoveTo I 0 I1 closure MoveTo I 1 A x B z A x B z C x z D y C x z C x z E x y D y E x y E x y F x y z A x F x y z F x y z E x y xy 0 z 0 1 0 0 1 0 110 10 9 对下面的文法 G E TE E E T FT T T F PF F F P E a b 1 证明该文法是 LL 1 文法 2 构造它的预测分析表 1 计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集 FIRST 集合有 FIRST E FIRST T FIRST F FIRST P a b FIRST E FIRST T FIRST F FIRST P a b FIRST T FIRST T a b FIRST F FIRST P a b FIRST F FIRST P FIRST P a b FOLLOW 集合有 FOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E 不包含 FOLLOW T FOLLOW T FIRST E FOLLOW E FOLLOW F FIRST T FOLLOW T a b 不包含 FOLLOW F FOLLOW F FIRST T FOLLOW T a b FOLLOW P FIRST F FOLLOW F a b 不包含 各产生式的 SELECT 集合有 SELECT E TE FIRST T a b SELECT E E SELECT E FOLLOW E SELECT T FT FIRST F a b SELECT T T FIRST T a b SELECT T FOLLOW T SELECT F PF FIRST P a b AD 00 F 0 ECB 1 00 1 1 11 SELECT F F SELECT F FOLLOW F a b SELECT P E SELECT P a a SELECT P b b SELECT P 可见 相同左部产生式的 SELECT 集的交集均为空 所以文法 G E 是 LL 1 文法 2 构造它的预测分析表 文法 G E 的预测分析表如下 ab E TE TE TE TE E E T FT FT FT FT T T T T T F PF PF PF PF F F P E a b 10 构造下述文法 G S 的自动机 S A0 A A0 S1 0 该自动机是确定的吗 若不确定 则对它确定化 该自动机相应的语言是什么 由于该文法的产生式 S A0 A A0 S1 中没有字符集 VT的输入 所以不是确定的自动机 要将其他确定化 必须先用代入法得到它对应的正规式 2 分 把 S A0 代入产生式 A S1 有 A A0 A01 0 A 0 01 0 0 0 01 代入 S A0 有该文法的 正规式 0 0 01 0 3 分 所以 改写该文法为确定的自动机为 2 分 由于状态 A 有 3 次输入 0 的重复输入 所以上图只是 NFA 下面将它确定化 下表由子集法将 NFA 转换为 DFA 3 分 0 WX 0 Z 0 0 Y 1 0 A 0 0 1 CB 12 11 令文法 G E 为 E T E T E T T F T F T F F E i 证明 E T F 是它的一个句型 指出这个句型的所有短语 直接短语和句柄 可为 E T F 构造一棵语法树 见下图 所以它是句型 从语法树中容易看出 E T F 的短语有 T F 是句型 E T F 的相对于 T 的短语 也是相对于规则 T T F 的直接短语 E T F 是句型 E T F 的相对于 E 的短语 句型 E T F 的句柄 最左直接短语 是 T F 四 单选题测试 1 若 P V 操作的信号量 S 的初值为 2 当前值为 1 则等待进程的数目是 A 0B 1C 2D 3 2 采用段式存储管理的系统中 若地址用 24 位表示 其中 8 位表示段号 则允许每段的最 大长度是 A 224B 216C 28D 232 3 如果有 3 个进程共享 4 个同类资源 为使这 3 个进程不陷入死锁 每个进程至多需要这 类资源数是 A 1B 2C 3D 4 4 若 RAM 中每个存储单元是 16 位 则下面所述正确的是 A 地址线是 16 位B 地址线与 16 无关 C 地址线与 16 与有关D 地址线不得少于 16 位 5 在相对寻址方式中 若指令中地址码是 X 则操作数的地址是 A XB PC XC X 段基址D 变址寄存器 X 6 一个进程被唤醒 其含义是 A 该进程重新占有了 CPUB 该进程的优先权变为最大 C 该进程的 PCB 移至等待队列首D 该进程变为就绪状态 7 在下列文件的物理结构中 不利于文件长度动态增长的是 A 顺序结构B 链接结构C 索引结构D HASH 结构 8 在通常的语法分析方法中 特别适用于表达式的分析方法是 A LR 分析法B 算符优先分析法 C 递归下降分析法D LL 1 分析法 9 对于下列一串汇编指令 MOVAX A ADD AX B MOV T