【计算机类职业资格】中级软件设计师上午试题-33及答案解析.doc

《【计算机类职业资格】中级软件设计师上午试题-33及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】中级软件设计师上午试题-33及答案解析.doc（25页珍藏版）》请在麦多课文档分享上搜索。

1、中级软件设计师上午试题-33 及答案解析(总分：75.00，做题时间：90 分钟)直接存储器访问(DMA)是一种快速传送大量数据常用的技术。工作过程大致如下所述。1向 CPU 申请 DMA 传送。2向 CPU 申请 DMA 控制器接管 (1) 的控制权。3在 DMA 控制器的控制下，在存储器和 (2) 之间直接进行数据传送，在传送过中不需要 (3) 的参与。开始时需提供要传送的数据的 (4) 和 (5) 。4传送结束后，向 CPU 返回 DMA 操作完成信号。（分数：5.00）A.系统控制台B.系统总线C.I/O 控制器D.中央处理器A.外部设备B.运算器C.缓存D.中央处理器A.外部设备B.

2、系统时钟C.系统总线D.中央处理器A.结束地址B.起始地址C.设备类型D.数据速率A.结束地址B.设备类型C.数据长度D.数据速率一般来说，Cache 的功能 (6) 。某 32 位计算机的 Cache 容量为 16KB，Cache 块的大小为 16B，若主存与Cache 的地址映射采用直接映射方式，则主存地址为 1234E8F8(十六进制)的单元装入的 Cache 地址为 (7) 。在下列 Cache 替换算法中，平均命中率最高的是 (8) 。（分数：3.00）A.全部由软件实现B.全部由硬件实现C.由硬件和软件相结合实现D.有的计算机由硬件实现，有的计算机由软件实现A.00 0100 01

3、00 1101(二进制)B.01 0010 0011 0100(二进制)C.10 1000 1111 1000(二进制)D.11 0100 1110 1000(二进制)A.先入后出(FILO)算法B.随机替换(RAND)算法C.先入先出(FIFO)算法D.近期最少使用(1RU)算法1.瀑布模型(Waterfall Model)突出的缺点是不适应 (9) 的变动。（分数：1.00）A.软件结构B.运行平台C.用户需要D.程序语言2.Jackson 设计方法是由英国的 M. Jackson 提出的，它是一种面向 (10) 的软件设计方法。（分数：1.00）A.对象B.数据结构C.数据流D.业务流软

4、件设计包括 4 个既独立又相互联系的活动，分别为 (11) 、 (12) 、数据设计和过程设计。（分数：2.00）A.用户手册设计B.语言设计C.体系结构设计D.文档设计A.文档设计B.程序设计C.实用性设计D.接口设计3.按照中华人民共和国著作权法的权利保护期，下列权项中，受到永久保护的是 (13) 。（分数：1.00）A.发表权B.修改权C.复制权D.发行权4.CRM 项目实施分为业务集成， (14) 和决策执行。（分数：1.00）A.系统总体设计B.业务数据分析C.决策分析D.应用业务集成分析在进程运行的过程中，把选择置换出页面的算法叫做页面置换算法。其中，选择的被淘汰的页面，将是暂时不

5、使用的或者在最长时间内不再被访问的页面的算法是 (15) ；总是选择淘汰最先进入内存的页面的算法是 (16) ；而选择淘汰在最近一段时间内最久未用的页面的算法是 (17) 。在一个请求分页系统中，假如系统分配给一个作业的物理块数为 3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2，则采用 FIFO 和 LRU 算法的缺页次数分别是 (18) ， (19) 。（分数：5.00）A.最近最久未使用置换算法B.最佳置换算法C.最少使用置换算法D.先进先出置换算法A.最近最久未使用置换算法B.最佳置换算法C.最少使用置换算法D.先进先出置换算法A.最近最久未使用置换算法B.最佳

6、置换算法C.最少使用置换算法D.先进先出置换算法A.6B.7C.8D.9A.6B.7C.8D.9软件开发的螺旋模型综合了瀑布模型和演化模型的优点，还增加了 (20) 。采用螺旋模型时，软件开发沿着螺线自内向外旋转，每转一圈都要对 (21) 进行识别和分析，并采取相应的对策。螺旋线第一圈的开始点可能是一个 (22) 。从第二圈开始，一个新产品开发项目开始了，新产品的演化沿着螺旋线进行若干次迭代，一直运转到软件生命期结束。（分数：3.00）A.版本管理B.可行性分析C.风险分析D.系统集成A.系统B.计划C.风险D.工程A.原型项目B.概念项目C.改进项目D.风险项目5.下面算法是实现对 n 个整

7、数的序列进行选择排序，其中序列的“长度”n 为问题的规模。该算法的时间复杂度为 (23) 。void select_sort(int a, int n)/将 a 中整数序列重新排列成从小到大有序的整数序列for(i=0；ij=i;for(k=i+1; kif(akif(j!=i)w=aj);aj=ai；ai=w;（分数：1.00）A.B.C.D.6.将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 (24) 次。（分数：1.00）A.1B.n-1C.nD.2n7.ATM 协议的 (25) 层将从其他网络接收到数据进行重组。（分数：1.00）A.物理B.

8、ATMC.应用适配层D.数据适配层8.X.25 协议属 OSI (26) 层上的操作。（分数：1.00）A.物理B.数据链路C.网络D.以上全是9.Ethernet 和 Token Ring 都使用 (27) 交换技术。（分数：1.00）A.消息交换B.电路交换C.包交换D.信息交换根据乔姆斯基于 20 世纪 50 年代建立的形式语言的理论体系，语言的文法被分为 4 种类型，即 0 型(短语文法)，1 型(上下文有关文法)、2 型(上下文无关文法)和 3 型(正规文法)。其中，2 型文法与 (28) 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与

9、之等价 (29) 。从文法描述语言的能力来说， (30) 最强， (31) 最弱，由 4 类文法的定义可知： (32) 必是2 型文法。（分数：5.00）A.线性有限自动机B.非确定的下推自动机C.图灵机D.有限自动机A.确定的有限自动机B.图灵机C.非确定的下推自动机D.非确定的有限自动机A.1 型文法B.2 型文法C.3 型文法D.0 型文法A.3 型文法B.2 型文法C.0 型文法D.1 型文法A.1 型文法B.0 型文法C.3 型文法D.2 型文法静态成员函数仅能访问 (33) 。静态数据成员的初始化必须在 (34) 。（分数：2.00）A.静态的数据成员B.非静态的成员函数C.非静态

10、的数据成员D.以上都不对_数据库系统由数据库、 (35) 和硬件等组成，数据库系统是在 (36) 的基础上发展起来的。数据库系统由于能减少数据冗余，提高数据独立性，并集中检查 (37) ，由此获得广泛的应用。数据库提供给用户的接口是 (38) ，它具有数据定义、数据操作和数据检查功能，可独立使用，也可以嵌入宿主语言使用。 (39) 语言已被国际标准化组织采纳为标准的关系数据语言。（分数：5.00）A.数据库管理系统B.文件系统C.编译系统D.操作系统A.编绎系统B.解释系统C.文件系统D.数据库管理系统A.数据完整性B.数据的可用性C.数据的操作性D.安全性A.数据库语言B.过程化语言C.宿主

11、语言D.数据库管理系统A.JAVAB.SQLC.CD.ALPHA10.设 A 和 B 是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为 (40) 。（分数：1.00）A.O(re+n-1)B.(m+n+1)C.O(m+n)D.不确定设长度为 n 的链队列用单循环链表表示，若只设头指针，则人队、出队操作的时间是 (41) ；若只设尾指针，需要的时间为 (42) 。（分数：2.00）A.O(n2)，O(1)B.O(n)，O(1)C.O(n2-1)，O(n)D.O(n-1)，O(n-1)A.O(1)，O(1)B.O(n)，O(1)C.O(n2)，O(1)D.O(n)，O(n)

12、11.深度为 k 的完全二叉树所含叶结点的个数最多为 (43) 。（分数：1.00）A.2kB.2k-1C.kD.2k原型化方法是一类动态定义需求的方法， (44) 不是原型化方法所具有的特征。与结构化方法相比，原型化方法更需要 (45) 。衡量原型开发人员能力的重要标准是 (46) 。（分数：3.00）A.提供严格定义的文档B.加快需求的确定C.简化项目管D.加强用户参与和决策A.熟练的开发人员B.完整的生命周期C.较长的开发时间D.明确的需求定义A.丰富的编程技巧B.灵活使用开发工具C.很强的协调组织能力D.快速获取需求12.若采用邻接矩阵结构存储具有 n 个顶点的图，则对该图进行广度优先

13、遍历的算法时间复杂度为 (47) 。（分数：1.00）A.O(n)B.O(n2)C.O(n2+1)D.以上都不对13.假定有 k 个关键字互为同义词，若用线性探查法把这些同义词存人散列表中，至少要进行 (48) 次探查。（分数：1.00）A.L(k+1)/2B.k(k+1)C.2k(k+1)D.不确定14.在长度为 n 的线性表中顺序查找值为 x 的元素时，查找成功的平均查找长度为 (49) 。 （分数：1.00）A.nB.n/2C.(n+1)/2D.(n-1)/215.在单向循环链表中，若头指针为 h，那么 p 所指结点为尾结点的条件是 (50) 。（分数：1.00）A.p=NULLB.Pn

14、ext=NULLC.p=hD.pnext=h16.二维数组 A 按行优先顺序存储，其中每个元素占 1 个存储单元。若 A11的存储地址为 420，A3 3的存储地址为 446，则 A55的存储地址为 (51) 。（分数：1.00）A.470B.471C.472D.47317.假设一个 6 阶的下三角矩阵 B 按列优先顺序压缩存储在一维数组 A 中，其中 A0存储矩阵的第二个元素b11，则 A14存储的元素是 (52) 。（分数：1.00）A.b63B.b62C.b64D.b5318.具有 6 个顶点的连通图的广度优先生成树，其边数为 (53) 。（分数：1.00）A.6B.5C.7D.4若关键

15、字是非负整数，快速排序、归并排序、堆排序和基数排序中 (54) 最快。若要求辅助空间为 O(1)，应选 (55) 。（分数：2.00）A.快速排序B.归并排序C.堆排序D.基数排序A.快速排序B.归并排序C.堆排序D.基数排序多媒体计算机中的媒体信息是指 (56) ，多媒体技术的主要特性有 (57) 。目前音频卡具备的功能有 (58) 。在多媒体计算机中常用的图像输入设备是 (59) 。国际标准 MPEG-2 采用了分层的编码体系，提供了 4种技术，它们是 (60) 。（分数：5.00）A.数字、文字、图像B.声音、图形C.动画、视频D.全部A.多样性、可扩充性B.多样性、集成性、交互性C.多

16、样性、集成性、可扩充性D.多样性、集成性、交互性、可扩充性A.录制和回放数字音频文件、实时解/压缩数字音频文件、混音B.录制和回放数字音频文件、实时解/压缩数字音频文件、语音特征识别C.混音、语音特征识别、实时解压缩数字音频文件D.以上全部A.数码照相机B.数码照相机、彩色扫描仪、视频信号数字化仪、彩色摄像机C.数码照相机、彩色扫描仪、视频信号数字化仪D.数码照相机、彩色扫描仪A.空间可扩展性、信噪比可扩充性、框架技术、等级技术B.时间可扩充性、空间可扩展性、硬件扩展技术、软件扩展技术C.数据分块技术、空间可扩展性、信噪比可扩充性、框架技术D.空间可扩展性、时间可扩充性、信噪比可扩充性、数据分

17、块技术某种中继设备提供运输层及运输层以上各层之间的协议转换，这种中继设备是 (61) 。从 OSI 协议层次来看，用以实现不同网络间的地址翻译、协议转换和数据格式转换等功能的路由器属于 (62) 范畴。当采用数据报服务时，负责端到端的流量控制的是 (63) 。路由器的主要功能是 (64) 。下列接人方式中， (65) 不属于 ISP 的接入方式。（分数：5.00）A.转发器B.网桥C.网关D.路由器A.网络层B.数据链路层C.物理层D.运输层A.主机(端系统)和通信子网B.通信子网C.主机(端系统)D.交换机A.在链路层对数据帧进行存储转发B.路径的选择C.放大传输信号D.用于传输层及以上各层

18、的协议转换A.帧中继(PR. )方式B.仿真终端方式C.专线(DDN)方式D.ISDN 方式Software design is a (66) process. It requires a certain (67) of flair on the part of the designer. Design can net be learned from a book. It must be practiced and learnt by experience and study of existing systems. A well (68) software system is straigh

19、t forward to implement and maintain, easily (69) and reliable. Badly (68) software systems, although they may work are (70) to be expensive to maintain, difficult to test and unreliable.（分数：5.00）A.createB.createdC.creatingD.creativeA.amountB.amountedC.mountD.mountedA.designB.designedC.designingD.des

20、ignsA.understandB.understandsC.understandingD.understoodA.likeB.likelyC.unlikeD.unlikelyBasically, a (71) is a standalone process or a set of integrated processes that runs on a router or server to control the flow of (72) application traffic (73) through it. Typically, firewalls are (74) on the ent

21、ry point to a public network such as the Internet. They could be considered traffic cops. The firewall s (75) is to ensure that all communication between an organizations network and the Internet conform to the organizations security policies.（分数：5.00）A.routerB.clientC.firewallD.switchA.networkB.net

22、workedC.netD.networkyA.passB.passedC.passingD.passesA.placedB.placeC.putD.getA.maleB.poleC.roleD.rule中级软件设计师上午试题-33 答案解析(总分：75.00，做题时间：90 分钟)直接存储器访问(DMA)是一种快速传送大量数据常用的技术。工作过程大致如下所述。1向 CPU 申请 DMA 传送。2向 CPU 申请 DMA 控制器接管 (1) 的控制权。3在 DMA 控制器的控制下，在存储器和 (2) 之间直接进行数据传送，在传送过中不需要 (3) 的参与。开始时需提供要传送的数据的 (4) 和

23、(5) 。4传送结束后，向 CPU 返回 DMA 操作完成信号。（分数：5.00）A.系统控制台B.系统总线 C.I/O 控制器D.中央处理器解析：A.外部设备 B.运算器C.缓存D.中央处理器解析：A.外部设备B.系统时钟C.系统总线D.中央处理器 解析：A.结束地址B.起始地址 C.设备类型D.数据速率解析：A.结束地址B.设备类型C.数据长度 D.数据速率解析：解析 这是一道考查 DMA 方式的概念题，解答起来容易，具体知识请参见教程 3.4.10 节有关 DMA的内容。一般来说，Cache 的功能 (6) 。某 32 位计算机的 Cache 容量为 16KB，Cache 块的大小为 1

24、6B，若主存与Cache 的地址映射采用直接映射方式，则主存地址为 1234E8F8(十六进制)的单元装入的 Cache 地址为 (7) 。在下列 Cache 替换算法中，平均命中率最高的是 (8) 。（分数：3.00）A.全部由软件实现B.全部由硬件实现C.由硬件和软件相结合实现D.有的计算机由硬件实现，有的计算机由软件实现 解析：A.00 0100 0100 1101(二进制)B.01 0010 0011 0100(二进制)C.10 1000 1111 1000(二进制) D.11 0100 1110 1000(二进制)解析：A.先入后出(FILO)算法B.随机替换(RAND)算法C.先入

25、先出(FIFO)算法D.近期最少使用(1RU)算法 解析：解析 Cache 的出现是基于两种因素：首先，是由于 CPU 的速度和性能提高很快而主存速度较低且价格高，第二就是程序执行的局部性特点。因此，才将速度比较快而容量有限的 SRAM 构成 Cache，目的在于尽可能发挥 CPU 的高速度。很显然，要尽可能发挥 CPU 的高速度就必须用硬件实现其全部功能。Cache 与主存之间可采取多种地址映射方式，直接映射方式是其中的一种。在这种映射方式下，主存中的每一页只能复制到某一固定的 Cache 页中。由于 Cache 块(页)的大小为 16B，而 Cache 容量为 16KB。因此，此 Cach

26、e 可分为 1024 页。可以看到，Cache 的页内地址只需 4 位即可表示；而 Cache 的页号需用 10位二进制数来表示；在映射时，是将主存地址直接复制，现主存地址为 1234E8F8(十六进制)，则最低 4位为 Cache 的页内地址，即 1000，中间 10 位为 Cache 的页号，即 1010001111。Cache 的容量为 16KB 决定用这 14 位编码即可表示。题中所需求的 Cache 的地址为 10100011111000。Cache 中的内容随命中率的降低需要经常替换新的内容。替换算法有多种，例如，先入后出(FILO)算法、随机替换(RAND)算法、先入先出(FIF

27、O)算法、近期最少使用(LRU)算法等。这些替换算法各有优缺点，就以命中率而言，近期最少使用(LRU)算法的命中率最高。1.瀑布模型(Waterfall Model)突出的缺点是不适应 (9) 的变动。（分数：1.00）A.软件结构B.运行平台C.用户需要 D.程序语言解析：解析 软件工程的基础知识，瀑布模型突出的缺点是不适应用户需求的变动，模型工程并不和软件结构、运行平台程序语言有很大的关系。2.Jackson 设计方法是由英国的 M. Jackson 提出的，它是一种面向 (10) 的软件设计方法。（分数：1.00）A.对象B.数据结构C.数据流 D.业务流解析：解析 软件工程的基础知识，

28、Jackson 设计方法是一种面向数据结构的软件设计方法，Jackson 分析方法是面向数据流的分析方法。软件设计包括 4 个既独立又相互联系的活动，分别为 (11) 、 (12) 、数据设计和过程设计。（分数：2.00）A.用户手册设计B.语言设计C.体系结构设计 D.文档设计解析：A.文档设计B.程序设计C.实用性设计D.接口设计 解析：解析 设计模型可以表示成金字塔，这种形状的象征意义是重要的，金字塔是极为稳固的物体，它具有宽大的基础和低的重心。像金字塔一样，我们希望构造坚固的软件设计，通过用数据设计建立宽广的基础，用体系结构和接口设计建立坚固的中部，以及应用过程设计构造尖锐的顶部，从而

29、创建出不会被修改之风轻易“吹倒”的设计模型。3.按照中华人民共和国著作权法的权利保护期，下列权项中，受到永久保护的是 (13) 。（分数：1.00）A.发表权B.修改权 C.复制权D.发行权解析：解析 中华人民共和国著作权法第二十条规定：作者的署名权、修改权、保护作品完整权的保护期不受限制。”中华人民共和国著作权法第二十一条规定：“公民的作品，其发表权、本法第十条第一款第(五)项至第(十七)项规定的权利的保护期为作者终生及其死亡后五十年，截止于作者死亡后第五十年的 12 月 31 日；如果是合作作品，截止于最后死亡的作者死亡后第五十年的 12 月 31 日。法人或者其他组织的作品、著作权(署名

30、权除外)由法人或者其他组织享有的职务作品，其发表权、本法第十条第一款第(五)项至第(十七)项规定的权利的保护期为五十年，截止于作品首次发表后第五十年的 12 月 31 日，但作品自创作完成后五十年内未发表的，本法不再保护。”第(五)项至第 (十七)项规定的权利为包括复制权、发行权、出租权、展览权、表演权、放映权、广播权、信息网络传播权、摄制权、改编权、翻译权、汇编权以及应当由著作权人享有的其他权利。4.CRM 项目实施分为业务集成， (14) 和决策执行。（分数：1.00）A.系统总体设计B.业务数据分析 C.决策分析D.应用业务集成分析解析：解析 CRM 项目的实施可以分为 3 步，即应用业

31、务集成，业务数据分析和决策执行。应用业务集成。将独立的市场管理，销售管理与售后服务进行集成，提供统一的运作平台。将多渠道来源的数据进行整合，实现业务数据的集成与共享。这一环节的实现，使系统使用者可以在系统内得到各类数据的忠实记录，代表目前真实发生的业务状况。业务数据分析。对 CRM 系统中的数据进行加工、处理与分析将使企业受益匪浅。对数据的分析可以采用OLAP 的方式进行，生成各类报告；也可以采用业务数据仓库(Business Information Warehouse)的处理手段，对数据做进一步的加工与数据挖掘，分析各数据指标间的关联关系，建立关联性的数据模型用于模拟和预测。这一步所取得的结

32、果将是非常重要的，它不单反映业务目前状况同时也对未来业务汁划的调整起到指导作用。决策执行。依据数据分析所提供的可预见性的分析报告，企业可以将在业务过程中所学到的知识加以总结利用，对业务过程和业务计划等做出调整。通过调整达到增强与客户之间的联系，使业务运作更适应市场要求的目的。在进程运行的过程中，把选择置换出页面的算法叫做页面置换算法。其中，选择的被淘汰的页面，将是暂时不使用的或者在最长时间内不再被访问的页面的算法是 (15) ；总是选择淘汰最先进入内存的页面的算法是 (16) ；而选择淘汰在最近一段时间内最久未用的页面的算法是 (17) 。在一个请求分页系统中，假如系统分配给一个作业的物理块数

33、为 3，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2，则采用 FIFO 和 LRU 算法的缺页次数分别是 (18) ， (19) 。（分数：5.00）A.最近最久未使用置换算法B.最佳置换算法 C.最少使用置换算法D.先进先出置换算法解析：A.最近最久未使用置换算法B.最佳置换算法C.最少使用置换算法D.先进先出置换算法 解析：A.最近最久未使用置换算法 B.最佳置换算法C.最少使用置换算法D.先进先出置换算法解析：A.6B.7C.8D.9 解析：A.6B.7 C.8D.9解析：解析 最佳置换算法是一种理想化的算法，它具有最好的性能，但却难于实现。其所选择的被淘汰的页面

34、，将是不使用的，或者是在最长时间内不再被访问的页面。先进先出算法(HF0)总是选择作业中在主存驻留时间最长的一页淘汰，即先进入主存的页面，先退出主存。最近最少使用算法(LRU)总是根据一个作业再执行过程中过去页面轨迹来推断未来的行为，认为过去一段时间里不曾被访问的页，在最近的将来可能也不会被访问。若在主存中为每一作业进程开辟 3 页，采用先进先出淘汰算法，页面调度过程如下所示：2 3 2 1 5 2 4 5 3 2 5 2- - - - - - - - - - - - - - - - - - 2 2 2 2 5 5 5 5 3 3 3 33 3 3 3 2 2 2 2 2 5 511 1 4

35、4 4 4 4 2* * * * * * * * *缺页次数为 9。采用 LRU 算法，页面调度过程如下所示：2 3 2 1 5 2 4 5 3 2 5 2- - - - - - - - - - - - - - - - - - - 2 2 2 2 2 2 2 2 3 3 3 33 3 3 5 5 5 5 5 5 5 51 1 1 4 4 4 2 2 2* *， * * * * *缺页次数为 7。软件开发的螺旋模型综合了瀑布模型和演化模型的优点，还增加了 (20) 。采用螺旋模型时，软件开发沿着螺线自内向外旋转，每转一圈都要对 (21) 进行识别和分析，并采取相应的对策。螺旋线第一圈的开始点可能

36、是一个 (22) 。从第二圈开始，一个新产品开发项目开始了，新产品的演化沿着螺旋线进行若干次迭代，一直运转到软件生命期结束。（分数：3.00）A.版本管理B.可行性分析C.风险分析 D.系统集成解析：A.系统B.计划C.风险 D.工程解析：A.原型项目B.概念项目 C.改进项目D.风险项目解析：解析 螺旋模型的图形表示为，在笛卡尔坐标的四个象限上分别表达了四个方面的活动，即：制定计划一确定软件目标，选定实施方案，弄清项目开发的限制条件；风险分析一分析所选方案，考虑如何识别和消除风险；实施工程一实施软件开发；客户评估一评价开发工作，提出修正建议。从这 4个方面的活动可以看，螺旋模型增加并强调了风

37、险分析的作用，从概念项目开始，不断识别和分析新的风险，直到软件生命期结束。5.下面算法是实现对 n 个整数的序列进行选择排序，其中序列的“长度”n 为问题的规模。该算法的时间复杂度为 (23) 。void select_sort(int a, int n)/将 a 中整数序列重新排列成从小到大有序的整数序列for(i=0；ij=i;for(k=i+1; kif(akif(j!=i)w=aj);aj=ai；ai=w;（分数：1.00）A.B. C.D.解析：解析 算法中的控制结构是两重循环，所以基本操作是在内层循环中的“比较”，它的重复执行次数是：*对时间复杂度而言，只需要取最高项，并忽略常数系

38、数。6.将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 (24) 次。（分数：1.00）A.1B.n-1C.n D.2n解析：解析 考生首先要明白两个前提：一是要归并的两个表都是递增有序的，且长度都为 n，二是题目问的是最少的关键字比较次数，即最好的情况下的比较次数；而最好的情况应该是：一个表的所有关键字都大于(或小于)另一个表的所有关键字，如：(1 2 3 4)与(5 6 7 8)。比较的时候有两个指针分别指向两个表的第一个元素，由于一个表的关键字要都大于另一个表的关键字，所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后，先被并人到新表

39、中，这时关键字大的表的指针还是指向第一个元素没变，此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长，也就是n。7.ATM 协议的 (25) 层将从其他网络接收到数据进行重组。（分数：1.00）A.物理B.ATMC.应用适配层 D.数据适配层解析：解析 ATM 协议的应用适配层将从其他网络接收到数据进行重组。物理层实现比特的传输，数据适配层负责数据的封装。8.X.25 协议属 OSI (26) 层上的操作。（分数：1.00）A.物理B.数据链路C.网络D.以上全是 解析：解析 x. 25 规定了主机与公共交换网之间的协议，而主机不必关心网络内部标准。x25 规定了主机

40、 DTE 和网络设备 DCE 之间的 3 个层次上的接口。物理层：相当于 OSI 参考模型的第一层。采用 x.21理接口，也可以选择类似于 RS 232C 的 X.21his。链路层：相当于 OSI 参考模型的第二层。采用 LAP 和LAP链路访问规程，当 DTE 与 DCE 之间有多个并列物理电路时允许使用多链路规程(MLP)。分组层：相当于 OSI 参考模型的第三层。网络向主机提供多信道的虚电路业务，包括虚呼叫和永久虚电路业务。9.Ethernet 和 Token Ring 都使用 (27) 交换技术。（分数：1.00）A.消息交换B.电路交换C.包交换 D.信息交换解析：解析 Ether

41、net 和 Token Ring 都使用包交换技术。根据乔姆斯基于 20 世纪 50 年代建立的形式语言的理论体系，语言的文法被分为 4 种类型，即 0 型(短语文法)，1 型(上下文有关文法)、2 型(上下文无关文法)和 3 型(正规文法)。其中，2 型文法与 (28) 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说， (30) 最强， (31) 最弱，由 4 类文法的定义可知： (32) 必是2 型文法。（分数：5.00）A.线性有限自动机B.非确定的下推自动机 C.图灵机D.有限自动机解析：A.确

42、定的有限自动机 B.图灵机C.非确定的下推自动机D.非确定的有限自动机解析：A.1 型文法B.2 型文法C.3 型文法D.0 型文法 解析：A.3 型文法 B.2 型文法C.0 型文法D.1 型文法解析：A.1 型文法B.0 型文法C.3 型文法 D.2 型文法解析：解析 乔姆斯基把文法分成 4 种类型，即 0 型、1 型、2 型和 3 型。 0 型文法也称短语文法，0 型文法的能力相当于图灵机(Turing)，或者说任何 0 型语言都是递归可枚举的。1 型文法也称上下文有关文法，其能力相当于线形界限自动机。对非终结符进行替换时不必考虑上下文，并且一般不允许替换成空串。2 型文法也称上下文无关

43、文法，其能力相当于非确定的下推自动机。3 型文法也称右线性文法，由于这种文法等价于正规式，所以也称正规文法。3 型文法的能力相当于有限自动机。从文法描述语言的能力来说，0 型文法最强，3 型文法最弱。语言的文法可以表示成一个四元组(VT(下标)，VN(下标)，S，P)。由 3 型文法的定义：一个文法 G 式 3 型文法，如果 G 是二型文法，并且 G 的每个产生。式 AB 或 A，其中 V*T，A，BVN(下标)，可知 3 型文法必是 2 型文法。静态成员函数仅能访问 (33) 。静态数据成员的初始化必须在 (34) 。（分数：2.00）A.静态的数据成员 B.非静态的成员函数C.非静态的数据

44、成员D.以上都不对解析：_解析：解析 静态数据成员的访问方式是：类名：静态数据成员名。但是，不能直接访问私有的数据成员。静态数据成员的初始化必须在类外，例如：class Astatic int i：public：/.数据库系统由数据库、 (35) 和硬件等组成，数据库系统是在 (36) 的基础上发展起来的。数据库系统由于能减少数据冗余，提高数据独立性，并集中检查 (37) ，由此获得广泛的应用。数据库提供给用户的接口是 (38) ，它具有数据定义、数据操作和数据检查功能，可独立使用，也可以嵌入宿主语言使用。 (39) 语言已被国际标准化组织采纳为标准的关系数据语言。（分数：5.00）A.数据库

45、管理系统 B.文件系统C.编译系统D.操作系统解析：A.编绎系统B.解释系统C.文件系统D.数据库管理系统 解析：A.数据完整性 B.数据的可用性C.数据的操作性D.安全性解析：A.数据库语言 B.过程化语言C.宿主语言D.数据库管理系统解析：A.JAVAB.SQL C.CD.ALPHA解析：解析 本题考查数据库的基础知识。数据库系统由数据库、数据库管理系统和硬件等组成，数据库系统是在文件系统的基础上发展起来的。数据库系统由于能减少数据冗余，提高数据独立性，并集中检查数据完整性，由此获得广泛的应用。数据库提供给用户的接口是数据库语言，它具有数据定义、数据操作和数据检查功能，可独立使用，也可以嵌

46、入宿主语言使用。SQL 语言已被国际标准化组织采纳为标准的关系数据语言。10.设 A 和 B 是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为 (40) 。（分数：1.00）A.O(re+n-1)B.(m+n+1)C.O(m+n) D.不确定解析：解析 设 A 表和 B 表的长度分别为 m 和 n，则该算法的时间复杂度为 O(m+n)。设长度为 n 的链队列用单循环链表表示，若只设头指针，则人队、出队操作的时间是 (41) ；若只设尾指针，需要的时间为 (42) 。（分数：2.00）A.O(n2)，O(1)B.O(n)，O(1) C.O(n2-1)，O(n)D.O(n-

47、1)，O(n-1)解析：A.O(1)，O(1) B.O(n)，O(1)C.O(n2)，O(1)D.O(n)，O(n)解析：解析 只设头指针时，入队操作的时间为 O(n)，出队操作的时间为 O(1)；只设尾指针时，入队操作的时间为 O(1)，出队操作的时间也为 O(1)。11.深度为 k 的完全二叉树所含叶结点的个数最多为 (43) 。（分数：1.00）A.2kB.2k-1 C.kD.2k解析：解析 深度为 k 的完全二叉树所含叶结点的个数最多的情况，一定是满二叉树的情况，即第 k 层上具有最多结点的情况。根据二叉树的性质 1，第 k 层上最多有 2k-1(上标)：个结点。位于第 k 层上的结点

48、，均为叶结点。原型化方法是一类动态定义需求的方法， (44) 不是原型化方法所具有的特征。与结构化方法相比，原型化方法更需要 (45) 。衡量原型开发人员能力的重要标准是 (46) 。（分数：3.00）A.提供严格定义的文档 B.加快需求的确定C.简化项目管D.加强用户参与和决策解析：A.熟练的开发人员B.完整的生命周期 C.较长的开发时间D.明确的需求定义解析：A.丰富的编程技巧B.灵活使用开发工具C.很强的协调组织能力D.快速获取需求 解析：解析 原型化方法实际上是一种快速确定需求的策略，对用户的需求进行提取、求精，快速建立最终系统工作是模型的方法。原型化方法与结构化方法不同，它不是追求也不可能要求对需求的严格定义、较长的开发时间和熟练的工作人员，但是该方法要求完整的生命周期。为了加快模型的建立，它需要加强用户的参与和决策，以求尽快地将需求确定下来，采用这样一个(与最终系统相比)相对简化的模型就可以简化项目的管理。原型化是一种动态设计过程，衡量原型化人员能力的重要标准是能快速获得需求的能力，至于是否有熟练的程序编制调试能力、很强的协调组织能力以及灵活使用工具软件的能力都不是最重要的。12.若采用邻接矩阵结构存储具有 n 个顶点的图，则对该图进行广度优先遍历的算法时