1、软件水平考试（中级）软件设计师上午（基础知识）试题模拟试卷 23及答案与解析 1 软件需求分析的任务不应包括 (11)。 （ A）确定功能要求 （ B）分析数据要求 （ C）模块划分 （ D）修正开发计划 2 需求分析主要解决的问题是 (12)。 （ A）做什么 （ B）在哪里做 （ C）如何做 （ D）做的程度 3 在 PERT图中，每个任务还可以有一个 (13)时间，表示在不影响整个工期的前提下，完成任务有多少机动余地。 （ A）冗余 （ B）松弛 （ C）机动 （ D）可洽 4 程序设计小组的组 织形式有很多种，其中便于集中领导、步调统一的是 (14)。 （ A）单人小组 （ B）主程序
2、员组 （ C）无主程序员组 （ D）层次式程序员组 5 软件开发工具不包括 (15)。 （ A）需求分析工具 （ B）设计工具 （ C）编码与排错工具 （ D）版本控制工具 6 (19)为数据流图中的每个数据流、文件、加工，以及对组成数据流或文件的数据项做出说明。 （ A）小说明 （ B）数据字典 （ C）数据流图词汇表 （ D）数据逻辑 7 按制定标准的不同层次和适应范围，标准可分为国际标准、国家标准、行业 标准和企业标准等， (20)制定的标准是国际标准。 （ A） GJB （ B） IEEE （ C） ANSI （ D） ISO 8 随着一项软件产品 (成果 )的产生，直接为该软件开发者
3、带来 (21)。 （ A）专利权、商标专用权、著作权、商业秘密专有权 （ B）著作权、商业秘密专有权 （ C）专利权、著作权、商业秘密专有权 （ D）专利权、商业秘密专有权 9 老王开发了一种控制汉字输入方法的应用软件，后老王于 2000年 3月 10日去世了。该软件的保护期应截止到 (22)。 （ A） 2050年 12月 31日 （ B） 2050年 3月 10日 （ C） 2000年 3月 10日 （ D） 2000年 12月 31日 10 有 m个进程 (P0， P1， ， Pm-1)通过 n个缓冲区 (B0， B1， Bn -1)向 1个进程(Q)发送数据包，每个数据包大小与缓冲区一
4、样。要求：进程 Q接收数据包的次序与发送次序一样。为保证发送进程与接收进程正确地并行工作，需要设置 (23)。 （ A）一个信号量，初值为 0 （ B）一个信号量，初值为 1 （ C）两个信号量，初值分别为 0和 1 （ D） 3个信号量，初值分别为 n、 1、 0 11 UNIX的文件系统采用三级索引机制 。在文件控制块 (FCB)中，设置了一个索引表，共有 13个索引地址。其中，前 10个为直接索引地址，后 3个为间接索引地址，包括 1个一级索引地址、 1个二级索引地址和 1个三级索引地址。假定磁盘块的大小为 512个字节，那么 UNIX系统允许一个文件最多有 (24)页。 （ A） 13
5、 （ B） 10+256*3 （ C） 10+256+2562+2563 （ D） 10+512+512*2+512*13 12 某操作系统的虚存管理采用的页面淘汰算法是优化 (OPT)算法，为每个进程分配 3个页面。现有一个进程的一段程序，其访问的 操作数所在页面的序列为： 1 4 6 5 3 4 5 2 5 4 3 5 1 2 4 1 假定开始时内存为空，执行这段程序将产生 (25)次缺页中断 (程序的存储不计 )。 （ A） 8 （ B） 9 （ C） 13 （ D） 10 13 一个有两个作业管理进程的批处理系统，作业调度采用最高响应比优先的算法，进程调度采用基于优先数 (优先数大表示
6、优先级别高 )的算法。有以下作业序列： 作业F的运行结束时间为 (26)(假定在作业运行期间，除了有空闲的作业管理进程以外，系统不进行调度工 作 )。 （ A） 14： 50 （ B） 15： 30 （ C） 13： 40 （ D） 13： 10 14 a,b上的正规表达式 (a|b)*(aa|bb)(a|b)*描述的正规集是 (27)。 （ A）由 a和 b组成的所有串 （ B）由 a和 b组成的串，且其中含有子串 aa （ C）由 a和 b组成的串，且其中含有子串 aa和子串 bb （ D）由 a和 b组成的串，且其中或含有子串 aa，或含有子串 bb 15 已知文法 G1 (VT a,b
7、,d， VN S， A， B， S,P)，其中 P为： SdAB AaA|a BbB| 该文法属于 (28)文法。 （ A） 0型 （ B）上下文有关 （ C）上下文无关 （ D）正规 16 所有编译程序的语法分析器都使用一个 (29)，以支持语法分析的顺利进行。 （ A）栈 （ B）队 （ C）树 （ D）图 17 一种语言中不同种类的变量往往采用不同的存储分配策略， C语言中的全局变量和静态变量采用静态分配，而自动 (Auto)类变量采用 (30)。 （ A）最佳分配 （ B）首先分配 （ C）堆式分配 （ D）栈式分配 18 设二叉树根结点的层次编号为 1，则深 度为 k的完全二叉树有
8、(31)种。 （ A） 2k （ B） 2k-1 （ C） 2(k-1) （ D） 2k 19 在一个单链表中，若 p所指结点不是最后结点，在 p所指结点之后插入 s所指结点，则应执行 (32)操作。 （ A） s- link p； p- link s； （ B） s- link p- link： p- link s： （ C） S- link p- link； p s： （ D） p- link s： s- link p： 20 如果某线性表的结点不等长，但希望能按下标随机存取每个元素，可以采用 (33)表 示。 （ A）多重链表 （ B）倒排表 （ C）散列表 （ D）索引表 21 在实体
9、与实体之间可能存在多对多的关系，如一位学生可选修多门课程，一门课程可接受多位学生选修。在实现时采用 (34)可以表述这种关系。 （ A）十字链表 （ B）关联矩阵 （ C）对称链表 （ D）邻接表 22 在下列排序方法中，不稳定的方法有 (35)。 （ A）归并排序和基数排序 （ B）插入排序和希尔排序 （ C）堆排序和快速排序 （ D）选择排序和冒泡排序 23 霍夫曼 (Huffman)编码是 (36)。 （ A）有损 数据压缩编码 （ B）无损数据压缩编码 （ C）不压缩数据的编码 （ D）通道 (或称信道 )编码 24 为适应网络带宽和降低存储器存储容量的要求，科技工作者开发了许多算法，
10、用于压缩各种各样的数据。假设处理系统的计算精度足够高，由此造成的数据损失可忽略。其中，正向离散余弦变换 (FDCT)(37)。 （ A）对重构图像的质量有损失 （ B）对重构图像的质量没有损失 （ C）变换前后数据项的数目不相等 （ D）变换前后的系数具有相同含义 25 有一种型号的数字录音机使用了 32MB的 flashmemory(闪 速存储器 )，假设其中2 MB用于运行程序，其余用于存储声音数据。该录音机采用 G 723 1的声音编码标准，使用的数据速率为 5 3kbps。计算使用这种录音机时最长的录音时间为 (38)。 （ A） 12小时 34分钟 （ B） 13小时 11分钟 （
11、C） 13小时 25分钟 （ D） 14小时 4分钟 26 假设有一台摄像机，它的扫描速率为 450行 /帧 520像素 /行 25帧 /秒，图像子采样格式为 4： 2： 0。如果每个 Y、 Cr、 Cb信号量化成 8位每样本，则该摄像机输出的位速率是 (39)。 （ A） 140.4Mbps （ B） 93.6Mbps （ C） 70.2Mbps （ D） 46.8Mbps 27 (44)，是数据库恢复的基本技术。 （ A）数据库镜像 （ B）日志文件 （ C）重建记录 （ D）修复介质 28 面向对象的数据库是 (48)的集合。 （ A）数据 （ B）对象 （ C）类 （ D）关系 29
12、在程序运行过程中， (49)将方法与特定的对象动态地联系在一起，使得不同的对象在使用同样的方法时，可以因对象的状态不同而产生不同的行为，从而使得方法对具体的对象具有个性。 （ A）消息传递机制 （ B）对象自身 引用 （ C）消息传递机制和对象自身引用 （ D）参数多态 30 对象自身引用 (Self-Reference)是 OOPL中的一种特有结构。对象自身引用机制使得在进行方法的设计和实现时并不需要考虑与对象联系的细节，而是从更高一级的抽象层次，也就是类的角度来设计同类型对象的 (50)特征，从而使得方法在一个类及其子类的范围内具有共性。 （ A）方法 （ B）行为 （ C）类型 （ D）
13、动态 31 分治法也许是使用最广泛的算法设计方法，以下关于分治法的结论中正确的是(54)。 （ A）分治法能解决动态规划方 法所能解决的任何问题 （ B）分治法找到的问题的解一定是最优解 （ C）用分治法能求出任何问题的解 （ D）分治法只能把大问题简单分解成一些较小的问题 32 蒙特卡罗 (Monte Carlo)算法是一种常用的 (55)算法。 （ A）确定性 （ B）近似 （ C）概率 （ D）加密 33 递推法与递归法的关系是： (56)。 （ A）可以用递推法解决的问题，都可以用递归法解决 （ B）可以用递归法解决的问题，都可以用递推法解决 （ C）不能用递推法解决的问题，也肯定不可
14、以用递归法解决 （ D）不能用递归 法解决的问题，可以用递推法解决 34 解决 Hash法中出现的冲突问题常采用的方法是 (57)。 （ A）数字分析法、除余法、平方取中法 （ B）数字分析法、除余法、线性探查法 （ C）数字分析法、线性探查法、双散列法 （ D）线性探查法、双散列法、拉链法 35 既希望较快地查找又便于线性表动态变化的查找方法是 (58)。 （ A）顺序查找 （ B）折半查找 （ C） Hash查找 （ D）索引顺序查找 36 (59)不属于网络协议的组成要素。 （ A）词汇 （ B）语法 （ C）语义 （ D）规则 37 路由器是 (60)层的设备。 （ A）物理层 （ B
15、）数据链路层 （ C）网络层 （ D）传输层 38 以太网中采用的 CSMA/CD算法为 (61)。 （ A）非坚持型 CSMA和二进制指数退避 （ B） 1-坚持型 CSMA 和二进制指数退避 （ C） P-坚持型 CSMA和二进制指数退避 （ D） (1-P)坚持型 CSMA和二进制指数退避 39 TCP协议通过建立连接为用户提供可靠传输，与数据链路层的建立连接不同， TCP要经过 (62)才能确定一个连接。 （ A）三次握手 （ B）请求信息 （ C）接收到 信息 （ D）得到应答 40 某单位分配到的网络地址是 217 14 8 0/27。若再分成 4个子网，则可用于分配给主机的 IP
16、 地址数是 (63)。 （ A） 32 （ B） 30 （ C） 24 （ D） 8 41 计算机对主存的要求是速度快、容量大、价格低，但现实情况三者很难统一于一身，很难找到这种存储器件。为了能解决这一需求，在主存与 CPU之间增加一级 cache，其主要目的是为解决 (1)，每次 CPU访问主存时，都先要查询该单元数据是否已调入 cache。为了把主存地址变成 cache地址，常常使用 3种 cache地址映像方式，其时全相联地址映像方式，使用起来最方便、最灵活但查找很困难，为了达到 cache的要求，实现时常常采用 (2)，按照 cache字块标志的内容访问映像存储器，查找命中的 cach
17、e字块地址。 （ A）主存速度低 （ B）主存容量小 （ C）主存价格贵 （ D）主存可靠性差 （ A）硬件的相联存储器 （ B）软件的方法 （ C）软硬件结合的方法 （ D）微程序 43 海明码是一种常用的纠错码。如果被校数据是 k位二进制数，再增加若干位校验位，使得校验位的值决定于某些被校位数据，当被校数据出错时，可根 据校验位值的变化找到出错位，进而纠正出错位。若新增校验位为 r位，则校验位之位数与被校验数据之位数应满足 (3)。由校验位和被校验位数据逐位异或可得到海明校验值，如果各位海明校验值均为零，表示 (4)。 （ A） 2rk+r （ B） 2rk+r+1 （ C） 2kk+r+
18、1 （ D） 2rk+r （ A）数据传输出错 （ B）数据传输正确 （ C）数据出多位错 （ D）无法判断 45 浮点数加法中，首先必须对阶，使二数阶码相等，才能进行加法运算，对阶时要求 (5)，尾数相加后还需对尾数进行规格化、含入等处理， 才能得到运算结果。如果判断浮点加法结果溢出，可判断 (6)。 （ A）大阶变成小阶 （ B）小阶变成大阶 （ C）尾数是规格化数 （ D）不须改变阶的大小 （ A）尾数是否溢出 （ B）阶码是否溢出 （ C）尾数是否规格化 （ D）不会溢出 47 计算机运行过程中，遇到突发事件，要求 CPU暂时停止正在运行的程序，转去为突发事件服务，服务完毕，再自动返回
19、原程序继续运行，这个过程叫做中断。发生中断的原因称为中断源，它是 (7)，中断源都有规定的优先级别，中断屏蔽的作用是 (8)。 （ A）随机产生的 （ B）设计 计算机时指定的 （ C）程序人员设定的 （ D）可以随意指定 （ A）不允许响应任何中断 （ B）改变各中断源响应中断时的优先次序 （ C）只屏蔽优先级别低的中断 （ D）只屏蔽优先级别高的中断 49 风险分析包括：风险识别、 (16)、风险评估、 (17)。 （ A）风险引导 （ B）风险分散 （ C）风险预测 （ D）风险总结 （ A）风险说明 （ B）风险回避 （ C）风险比较 （ D）风险控制 51 SQL语言包括 4类，它们
20、是 (43)、数据控制，其中数据控制包括 (44)。 （ A）数据定义、数据 管理、数据恢复 （ B）数据查询、数据定义、数据操纵 （ C）数据定义、数据检索、数据删除 （ D）数据定义、数据更新、数据检索 （ A） Create、 Alert （ B） Update、 Grant （ C） Grant、 Revoke （ D） Delete 53 对象是由对象名、 (45)、 (46)组成的。 （ A）关系 （ B）属性 （ C）引用 （ D）类 （ A）实例 （ B）算法 （ C）指针 （ D）方法 55 类比二分搜索算法，设计 k分搜索算法 (k为大于 2的整数 )如下：首先检查 n/k
21、处 (n为被 搜索集合的元素个数 )的元素是否等于要搜索的值，然后检查 2n/k处的元素， ，这样，或者找到要搜索的元素，或者把集合缩小到原来的 1/k；如果未找到要搜索的元素，则继续在得到的集合上进行 k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此 k分搜索算法在最坏情况下搜索成功的时间复杂度为(57)，在最好情况下搜索失败的时间复杂度为 (58)。 （ A） O(logn) （ B） O(nlogn) （ C） O(logkn) （ D） O(nlogkn) （ A） O(logn) （ B） O(nlogn) （ C） O(logkn) （ D） O(nlogkn) 57 FTP
22、协议是 Internet常用的应用层协议，它通过 (61)协议提供服务，它是基于Client/Server结构通信的，作为服务器一方的进程，通过监听 (62)端口得知有服务请求。 （ A） TCP （ B） UDP （ C） IP （ D） DHCP （ A） 8080 （ B） 80 （ C） 25 （ D） 21 59 在面向对象技术中，类属是一种 (35)机制。一个类属类是关于一组类的一个特性抽象，它强调的是这些类的成员特征中与 (36)的那些部分，而用变元来表示与 (37)的那些部分。 （ A）包含多态 （ B）参数多态 （ C）过载多态 （ D）强制多态 （ A）具体对象无关 （ B
23、）具体类型无关 （ C）具体对象相关 （ D）具体类型相关 （ A）具体对象无关 （ B）具体类型无关 （ C）具体对象相关 （ D）具体类型相关 62 由几个实数构成的哈夫曼树，共有 (50)个结点，有 (51)个叶结点，有 (52)个二度结点。 （ A） n （ B） n-1 （ C） 2n-1 （ D） 2n （ A） n （ B） n-1 （ C） 2n-1 （ D） 2n （ A） n （ B） n-1 （ C） 2n-1 （ D） 2n 65 软件开发模型是指软件开发的全部过程，活动和任务的结构框架。主要的开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型和智能模型。螺旋模型将瀑布模
24、型和演化模型相结合，并增加了 (15)，它建立在 (16)的基础上，沿着螺线自内向外每旋转一圈，就得到其一个新版本。 喷泉模型描述了 (17)的开发模型，它体现了这种开发方法创建软件的过程所固有的(18)和 (19)的特征。 （ A）系统工程 （ B）风险分析 （ C）设计评审 （ D）进度控制 （ A）模块划分 （ B）子程序分解 （ C）设计 （ D）原型 （ A）面向对象 （ B）面向数据流 （ C）面向数据结构 （ D）面向事件驱动 （ A）归纳 （ B）推理 （ C）迭代 （ D）递归 （ A）开发各阶段之间无 “间隙 ” （ B）开发各阶段分界明显 （ C）部分开发阶段分界明显 （
25、 D）开发过程不分段 70 Developing reliable software on time and within(66)represents a difficult endeavor for many organizations. Usually business solutions have three main aspects: people,(67),and technology. The main reason for failing software projects has little to do with technology and tools, and much
26、to do with lack of process(68). Experience has shown that introducing new technology and tools in an immature or undisciplined environment is likely to increase the chaos. CASE tools are not enough. “A fool with a tool is still a fool !“ Structured method was the first wave of the software industry.
27、 This was the beginning of transforming software development from a“(69)industry“ to mass production. Software process movement if the second wave in the software industry. The process maturity movement prepares the way for the third wave of the software industry :“software industrialization“. Softw
28、are development will become like an assembly and manufacturing process. A cfiticalenabling factor is adisciplined software engineering . process with predictable quality,(70)and functionality. （ A） forecast （ B） preparation （ C） budget （ D） economy （ A） process （ B） skill （ C） organization （ D） inte
29、rface （ A） law （ B） discipline （ C） plan （ D） evaluation （ A） college （ B） family （ C） workshop （ D） cottage （ A） plan （ B） schedule （ C） effort （ D） product 75 Soon, more of the information we receive via the Internet could come(71)in digital wrappers. Wrappers are made up(72)software code thats ta
30、rgeted to do specific things with the data(73)within them, such as helping to define queries for search engines. They also keep(74)from(75)access to that code. （ A） package （ B） packaged （ C） packages （ D） packaging （ A） of （ B） off （ C） on （ D） out （ A） close （ B） closed （ C） enclose （ D） enclosed
31、（ A） insiders （ B） money （ C） outsiders （ D） warehouse （ A） gain （ B） gained （ C） gains （ D） gaining 软件水平考试（中级）软件设计师上午（基础知识）试题模拟试卷 23答案与解析 1 【正确答案】 C 【试题解析】 需求分析是指开发人员要准确理解用户的要求，进行细致的调查分析，将用户非形式的需求陈述转化为完整的需求定义，再由需求定义转换到相应的形式功能规定 (需求规格说明 )、的过程。需求分析的主要任务是确定待开发的功能、性能、数据、界面等要求。包括： (1)确定系统的综合要求。 (2)分析软件系
32、统的数据要求。 (3)导出系统的逻辑模型。 (4)修正项目计划。模块划分应该是在需求分析之后的设计阶段中概要设计中进行。 2 【正确答案】 A 【试题解析】 同上。需求分析主要解决的问题 是 “做什么 ”，概要设计和详细设计阶段解决的是 “怎么做 ”。 3 【正确答案】 B 【试题解析】 PERT 图是一个有向图，每个任务还可以有一个松弛时间 (Slack Time)，表示在不影响整个工期的前提下，完成该任务有多少机动余地。 4 【正确答案】 C 【试题解析】 人员管理是软件开发项目管理的一个重要组成部分。合理地组织好参加软件项目的人员，有利于发挥每个人的作用，有利于软件项目的成功开发。在人员
33、组织时，应考虑软件项目的特点，软件人员的素质等多方面的因素。软件设计小组的组织形式可以有：主 程序员组、非主程序员组、层次式程序员组等。主程序员组由一名经验丰富、能力强的软件设计师领导，其他程序员完成他分配的任务。这种组织形式很常见，有利于集中领导，按规范办事，但不利于发挥个人的积极性。非主程序员组内部关系平等，采取讨论、协商和互相配合来进行工作，这种形式是敏捷开发所推崇的，有利于调动成员积极性、提高能力，但由于职责不明确，往往会影响效率，也不利于与外部交流。 5 【正确答案】 D 【试题解析】 软件工具可分为软件开发工具、软件维护工具、软件管理和软件支持工具。软件开发工具通常有需求分析工 具
34、、设计工具、编码与排错工具、测试工具等；软件维护工具主要有版本控制工具、文档分析工具、开发信息库工具等。 6 【正确答案】 B 【试题解析】 SA方法的分析结果由以下几部分组成：一套分层的数据流图、一本数据字典、一组小说明 (也称加工逻辑说明 )和补充材料。数据流图描述了系统的分解，但没有对图中各成分进行说明。数据字典就是为数据流图中的每个数据流、文件、加工，以及组成数据流或文件的数据项做出说明。其中对加工的描述称为 “小说明 ”。 7 【正确答案】 D 【试题解析】 ISO是国际标准化组织， 它制定的标准是国际标准。 ANSI是美国国家标准学会，只能制定美国国家标准； IEEE 是美国电气电
35、子工程师学会，IEEE 通过的标准常常要报请 ANSI审批，使具有国家标准的性质： GJB 是我国国防科学技术工业委员会批准、颁布适合于国防部门和军队使用的标准，属于行业标准化组织。 8 【正确答案】 B 【试题解析】 由于软件具有作品、技术成果和产品的特征，随着一项软件产品(成果 )的产生，将可能为该软件开发者直接带来专利权、商标专用权、著作权、商业秘密专有权等知识产权。然而，专利权、商标专用权需要依法办理登记注 册后才能获得，而著作权和商业秘密专有权是自动产生和软件开发人采取保护措施得到的，故随着一项软件产品 (成果 )的产生，直接为该软件开发者带来的知识产权为著作权、商业秘密专有权。 9
36、 【正确答案】 A 【试题解析】 根据计算机软件保护条例关于自然人享有软件著作权的时间为终生 (有生之年 )加死亡后 50年：法人或者其他组织享有软件著作权的时间为软件首次发表后 50年。若开发完成之日 50年内未发表的，不再保护；以及法人或者其他组织变更或者终止没有承受其权利义务的法人或者其他组织的，由国家享有该软件的著作权等软 件著作权保护期限的限制的规定。自然人的老王于 2000年 3月 10日去世之后，老王所享有著作权的软件保护期应当为 50年 (2000年至 2050年 )，即截止到 2050年 12月 31日。 10 【正确答案】 D 【试题解析】 本题考查进程同步与互斥方面的知识
37、以及信号量的使用技能。原则上，为保证进程并行工作的正确性，对每一个同步或互斥条件应该设置一个信号量。首先，必须在缓冲区有内容时，接收进程才能取，也就是说， m个缓冲区中至少有 1个是有数据包时，进程 Q才能取，亦即送后再取。这是一个同步条件，需要一个信号量 S3，刚 开始时，所有缓冲区都没有数据包，接收进程不能取数据，所以该信号量的初值应该为 0。其次，当 m个缓冲区装满数据包时，没有空的缓冲区可以再容纳送来的数据包，必须等待接收进程 Q取走一个数据包，发送进程 Pi 才能向它送入数据包，亦即取后再送。这又是一个同步条件，需要一个信号量 S1，由于有 n 个缓冲区；发送进程可以在接收进程一个未
38、取的情况下连续送n 个数据包，所以它的初值应该为 n。第三，为了使 m个发送进程有序地向缓冲区放入数据包，不能出现两个进程同时向一个缓冲区放数据包的现象，应该将缓冲区编号，需要用一个变量代表将要放入数据 的缓冲区号，每放入一个数据包，该变量加 1并用 n取模 (保证该变量从 0到 n-1周而复始地变化 )。这个变量是所有发送进程共享并进行修改的，因此发送进程必须互斥地访问它，所以还要是一个信号量 S2，保证互斥关系，初值为 1。这样，正确的答案应该是 D。这里，设用于指向当前存放发送数据的缓冲区号的变量为 t，初值为 0；设指向将要从它那里取数据的缓冲区号的变量为 f，初值也为 0。下图表示发
39、送进程与接收进程利用一组缓冲区通信的流程。 11 【正确答案】 C 【试题解析】 本题主要考查有关索引文件组织和多级索引的知识。索引文 件包括一张索引表，表中的每一项是一个索引地址，指向一个磁盘块的物理块号 (每个磁盘块与一页文件大小相同 )。所谓直接索引地址是指该磁盘块内直接存放了文件的内容。因此，本题中的前 10个直接索引地址指向了该文件的前 10页。所谓间接索引地址是指该磁盘块中存放的不是文件的实际内容，而是一张索引表。其中，一级索引地址指向了一张直接索引表，直接索引表内的每一个表项指向一个文件页存放的磁盘地址：二级索引地址指向一张一级索引表：三级索引地址指向一张二级索引表。 本题中一个
40、磁盘块中有512个字节，每个整数占 2个字节，可以存放 256个整数，用以存放磁盘块物理地址。因此，一张一级索引表最多可以指向 256个文件页，一张二级索引表最终可以派生出指向 2562个文件页，一张三级索引表则达到指向 2563个文件页。连同 10个直接索引，一个文件最多可达 10+256+2562+2563个文件页。 12 【正确答案】 B 【试题解析】 本题考查的是虚存中关于优化算法和其他一些概念与运用。 由于系统为每个进程分配 3个页面的内存，意味着进程的程序运行时最多只有 3页的空间存放操作内容。所谓优化算法是在发现需要访问的操作内容所在页面不在内存时，发生缺 页中断转入操作系统程序
41、处理。操作系统将审查程序的访问页面序列，挑选从当时开始被访问时间最晚 (亦即访问页面序列中出现最靠后 )的那个页面，将其存回磁盘 (称之为淘汰 )，再将需要访问的页面调入内存，占据刚刚淘汰页面的内存区域。 表中 y表示本次访问的操作对象在内存， n表示不在内存，即发生缺页中断，需要进行淘汰与页面调入。 因此，缺页中断为 9次，正确答案为 B。 13 【正确答案】 A 【试题解析】 本题考查的内容是作业调度中的最高响应比优先算法、进程调度中的基于优先数的调度算法的概念及其应用。 所谓最 高响应比优先算法，首先需要在调度时刻计算每个后备作业的响应比。即响应比 (作业等待时间 +作业估计运行时间 )
42、/作业估计运行时间。实际上，比较不同作业响应比时起作用的是：作业等待时间 /作业估计运行时间。在计算以后，挑选响应比最大的后备作业投入运行，这个算法是比较优秀的。大家都知道，数学上可以证明短作业优先的调度算法可以得到最小的作业平均响应时间 (亦即可以得到最大的系统平均吞吐率 )。但是，它不能排除有可能出现 “无限等待 ”的现象，因为它允许短作业 “加塞 ”，如果短作业源源不断地到来，将可能使长作业在不可预计的一段时间 内得不到运行。而最高响应比优先的算法则保证在到达时间相近的一批作业中，估计运行时间小的作业 (短作业 )可以优先投入运行，在作业大小相仿时，到达时间早的作业可以先投入运行。即使是
43、很长的作业，随着后备时间的延长，其响应比也不断增大，最终将会投入运行，从而避免出现 “无限等待 ”的现象。 所谓基于优先数的调度算法，则在调度时刻比较各个进程的优先数，挑选优先级别高的进程运行。 本题中， 10： 00时，作业 A到达，此时没有别的作业，自然投入运行。到 10：20时，作业 B到达，由于还空闲一个作业管理进程，作业 B 进入系 统，进行进程调度。由于 B 的优先级别高，作业 B 投入运行， A在内存等待。到 11： 20时， B运行结束并退出，空出一个作业管理进程，系统开始作业调度。此时，作业 C、 D均已到达，由于 C的响应比 (30+40)/40=1.75 D的响应比 (0
44、+80)/80=1，作业C进入内存，在进行进程调度时，由于 C的优先数为 3，比作业 A小， A投入运行。到 11： 50时， A剩下的 30分运行时间结束，退出系统，这时作业 E已经到达。此时， D的响应比 (30+80)/80 1.375 E 的响应比 (10+30)/30 1.333，作业 D进 入内存，由于 D的优先数为 8，高于作业 C， D投入运行。到 13： 10时，作业 D运行结束。这时作业 F也早已到达，在两个后备作业中， E 的响应比(90+30)/30 4， F的响应比 (70+70)/70=2，作业 E进入运行，又由于 E 的优先数比 C大， E投入运行。到 13： 4
45、0时， E 运行结束，这时后备作业只有 F， F进入内存，由于它的优先数为 9，远大于 C，于是投入运行，到 14： 50结束运行。最后只剩下 C一个作业，于 15： 30运行结束。 各作业运行结束时间表为 A为 11： 50、 B为 11： 20、 C为 15： 30、 D为 13：10、 E 为 13： 40、 F为 14： 50。 14 【正确答案】 D 【试题解析】 用正规表达式 (简称正规式 )可以描述一个程序语言的单词集合，它表示的集合称为正规集。对于字母表 而言，正规式和它所表示的正规集递归定义如下所述。 (1)和 是正规式，它们所表示的正规集分别为 和 ； (2) a ， a是
46、正规式，它所表示的正规集为 a； (3)设 r和 s是 上的正规式，它们所表示的正规集分别为 L(r)和 L(s)，那么 (r|s)、 (rs) (连接 )和 (r)*也是正规式，它们所表示的正规集分别为 L(r) L(s)、 L(r)L(s)和 (L(r)*。 (4)仅由有限次使用以上 3个运算构造出的表达式才是正规式。 正规式中运算符的优先级从高到低依次是： *、连接和 |。 算术表达式表示计算规则，已知一个算术表达式，人们按照它所表示的计算规则能计算出一个算术值；正规表达式表示集合的计算规则，已知一个正规表达式，按照它所表示的计算规则，通过计算能得到一个正规集合。 仿照计算算术表达式计算
47、正规表达式 (a|b)*(aa|bb)(a|b)*如下：正规式 a|b 描述的是集合 (a (b a,b)， (a|b)*描述的集合是 a,b*， a,b*是由 a和 b组成的所有串的集合。正规式 aa描述的集合是 aa，正规式 (aa|bb)描述的集合是 aa bbaa,bb。正规式 (a|b)* (aa， bb)(a|b)*描述的集合是把 a,b*、 aa,bb、 a,b*3者连接起来。 15 【正确答案】 C 【试题解析】 乔姆斯基 (Chomsky)把文法分成 4种类型，即 0 型、 1型、 2型和 3型，由此产生的语言分别称为 0型、 1型、 2型和 3型语言。这几类文法的差别在于对
48、产生式的形式施加不同的限制，如下表所示。0型文法也称 短语文法， 1型文法也称上下文有关文法， 2型文法也称上下文无关文法， 2型文法的识别器模型是下推自动机。 3型文法也称线性文法 (或称正规文法 )，其识别器模型是有限状态自动机。文法 G1 的所有产生式形式都是 A ，其中 A VN， V*，且第 1条规则 SdAB 是非线性的，因此文法 G1 属于 2型文法，又称上下文无关文法。 16 【正确答案】 A 【试题解析】 描述程序语言的语法是上下文无关语法，由它产生程序语言是上下文无关语言。这种语言与下推自动机等价，即每一个程序语言的语法，都可以用一个下推自动机来识别。下推自 动机中的下推指
49、的就是一个栈，一个下推自动机的模型如下图所示。 一个语法分析器和一个下推自动机一样也由 4部分构成：一个输入，一个输出，一个栈和一个控制器。对于某一个程序语言，可以根据不同的语法分析方法构造出不同的控制器，由控制器控制分析过程中的输入、输出和进栈操作。 17 【正确答案】 D 【试题解析】 在目标程序运行时，目标代码所引用的数据对象在内存空间中。因此，在编译阶段产生目标时，要把目标代码所引用的数据对象映射到内存空间上，在运行时，再分配给需要的内存单元，这个过程称为存储分配。分配的对象有简单 数据类型 (如整、实和布尔型等 )、结构数据类型 (如数组和记录等 )和连接数据 (如返回地址、参数等 )。由于各种语言的语义不同，主要是名字的作用域和生存期不同，因而对存储空间的组织和采用的存储分配策略也不同，可分为静态和动态两大类。把过程或函数的一次执行叫一个活动，把一个活动所需要的存储空间组织在一起构成一个活动记录 (有的书上称数据区 )，不同语言的活动记录结构是不同的。如果在编译时能确定目标程序运行中所需的全部数据空间的大小及相互位置，那么，能在
