【计算机类职业资格】软件水平考试（中级）软件设计师上午（基础知识）试题-试卷37及答案解析.doc

1、软件水平考试（中级）软件设计师上午（基础知识）试题-试卷 37及答案解析(总分：216.00，做题时间：90 分钟)一、选择题(总题数：44，分数：216.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_2.瀑布模型(Waterfall Model)突出的缺点是不适应(9)的变动。（分数：2.00）A.软件结构B.运行平台C.用户需要D.程序语言3.Jackson设计方法是由英国的 M. Jackson 提出的，它是一种面向(10)的软件设计方法。（分数：2.00）A.对象B.数据结构C.数据流D.业务流4.

2、按照中华人民共和国著作权法的权利保护期，下列权项中，受到永久保护的是(13)。（分数：2.00）A.发表权B.修改权C.复制权D.发行权5.CRM项目实施分为业务集成，(14)和决策执行。（分数：2.00）A.系统总体设计B.业务数据分析C.决策分析D.应用业务集成分析6.下面算法是实现对 n个整数的序列进行选择排序，其中序列的“长度”n 为问题的规模。该算法的时间复杂度为(23)。 void select_sort(int a, int n) /将 a中整数序列重新排列成从小到大有序的整数序列 for(i=0；i（分数：2.00）A.O(n 3 )B.O(n 2 )C.O(n)D.O(n 4

3、 )7.将两个长度为 n的递增有序表归并成一个长度为 2n的递增有序表，最少需要进行关键字比较(24)次。（分数：2.00）A.1B.n-1C.nD.2n8.ATM协议的(25)层将从其他网络接收到数据进行重组。（分数：2.00）A.物理B.ATMC.应用适配层D.数据适配层9.X.25协议属 OSI(26)层上的操作。（分数：2.00）A.物理B.数据链路C.网络D.以上全是10.Ethernet和 Token Ring 都使用(27)交换技术。（分数：2.00）A.消息交换B.电路交换C.包交换D.信息交换11.设 A和 B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复

4、杂度为(40)。（分数：2.00）A.O(re+n-1)B.(m+n+1)C.O(m+n)D.不确定12.深度为 k的完全二叉树所含叶结点的个数最多为(43)。（分数：2.00）A.22 kB.22 k-1C.kD.2k13.若采用邻接矩阵结构存储具有 n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。（分数：2.00）A.O(n)B.O(n 2 )C.O(n 2 +1)D.以上都不对14.假定有 k个关键字互为同义词，若用线性探查法把这些同义词存人散列表中，至少要进行(48)次探查。（分数：2.00）A.L(k+1)/2B.k(k+1)C.2k(k+1)D.不确定15.在长度

5、为 n的线性表中顺序查找值为 x的元素时，查找成功的平均查找长度为(49)。（分数：2.00）A.nB.n/2C.(n+1)/2D.(n-1)/216.在单向循环链表中，若头指针为 h，那么 p所指结点为尾结点的条件是(50)。（分数：2.00）A.p=NULLB.Pnext=NULLC.p=hD.pnext=h17.二维数组 A按行优先顺序存储，其中每个元素占 1个存储单元。若 A11的存储地址为 420，A3 3的存储地址为 446，则 A55的存储地址为(51)。（分数：2.00）A.470B.471C.472D.47318.假设一个 6阶的下三角矩阵 B按列优先顺序压缩存储在一维数组

6、A中，其中 A0存储矩阵的第二个元素 b11，则 A14存储的元素是(52)。（分数：2.00）A.b63B.b62C.b64D.b5319.具有 6个顶点的连通图的广度优先生成树，其边数为(53)。（分数：2.00）A.6B.5C.7D.4设有 4道作业，它们的提交时间及执行时间如表所示。在单道程序环境下，若采用先来先服务调度算法，其平均周转时间为(15)，平均带权周转时间为(16)。 （分数：4.00）A.0.95B.2.8C.2.45D.5.25A.0.95B.2.8C.3.85D.5.25可行性分析的目的是在尽可能短的时间内用尽可能小的代价来确定问题是否有解。不属于在可行性分析阶段进行

7、的工作是(20)。可行性分析不包括对待开发软件进行(21)分析。（分数：4.00）A.研究目前正在使用的系统B.根据待开发系统的要求导出新系统的逻辑模型C.提供几个可供选择的方案D.编制项目开发计划A.技术可行性B.经济可行性C.操作可行性D.组织可行性在 UML提供的图中，(28)用于对系统的静态设计视图建模，(29)用于对系统的静态实现视图建模。（分数：4.00）A.类图B.对象图C.部署图D.构件图A.类图B.对象图C.部署图D.构件图图 8-2为一个 DFA的状态转换图，与其等价的正规表达式是(31)，在图中状态(32)是可以合并的状态。（分数：4.00）A.(0|1)*11(0*1*

8、)*B.(0|1)*110*|1*C.(0*1*)11(0|1)*D.(0*|1*)*11(0*|1*)A.q0和 q1B.q2和 q3C.q1和 q2D.q0和 q3广义表(a，(a，b)，d，e，(i，j)，k)的长度是(48)，深度是(49)。（分数：4.00）A.3B.4C.5D.6A.3B.4C.5D.68层完全二叉树至少有(52)个结点，拥有 100个结点的完全二叉树的最大层数为(53)。（分数：4.00）A.127B.128C.256D.257A.6B.7C.8D.9堆排序是(54)类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是(55)。（分数：4.00）A.

9、插入B.归并C.基数D.选择A.O(n 2 )和 O(1)B.O(nlog 2 n)和 O(1)C.O(nlog 2 n)和 O(n)D.O(n 2 )和 O(1)软件质量保证，它是为了保证产品和服务充分满足(9)要求而进行的有计划、有组织的活动。在 MeGabe等人提出的软件质量模型中，(10)属于面向软件产品操作。ISO 的软件质量评价模型由 3层组成，其中用于评价质量度量的准则是(11)。（分数：6.00）A.生产者B.用户C.开发者D.测试者A.正确性B.适应性C.可重用性D.可维护性A.SQRCB.SQDCC.SQMCD.SQM数据模型的三要素是指(12)，一个数据库系统必须能够表示

10、实体和关系，联系可以与(13)实体有关。数据库的特点之一是数据的共享，严格的讲，这里的数据共享是指(14)。（分数：6.00）A.数据结构、数据对象和共享B.数据结构、数据操作和数据控制C.数据结构、数据操作和完整性D.数据结构、数据操作和完整性约束条件A.0个B.1个C.1个或 1个以上D.2个或 2个以上A.同一应用的多个程序共享一个数据集合B.多个用户、同一语言共享数据C.多个用户共享同一个数据文件D.多种应用、多种语言、多个用户相互覆盖地使用数据集合在多处理系统中，进程调度用来决定哪个进程得到 CPU的控制。调度分为三个阶段：长期，中期，短期。长期调度是指(15)。属于中期调度增加的进

11、程状态是(16)。下面关于短期调度说法正确的是(17)。（分数：6.00）A.调度程序把 CPU分配给已装入主存储准备运行的进程B.把进程调人/调出主存储器C.决定哪些作业或进程可以竞争系统资源D.决定哪些线程共享存储器A.阻塞状态B.运行状态C.交换就绪状态D.保持状态A.又叫做作业调度B.用线程调度而不是进程调度C.在多线程系统中，短期调度只有 1种调度方式D.进程调度中不能进行线程调度客户机/服务器应用模式的框架是(35)，其中，客户机的主要功能是(36)。客户机/服务器应用模式的中间件是(37)。（分数：6.00）A.客户机，服务器，网络操作系统B.客户机，服务器，中间件C.客户机，服

12、务器，应用程序D.客户机，服务器，操作系统A.执行用户方的应用程序B.提供 GUI或 OOUIC.代用户与数据进行交互D.以上都是A.支持客户机、服务器对话，实施分布式应用的各种软件的总称B.支持客户机、服务器对话，实施分布式应用的各种硬件的总称C.支持客户机、服务器对话，实施分布式应用的各种硬件和软件的总称D.以上都不对密码学的基本原则是(59)。传统加密算法中，替代密码是(60)。换位密码是(61)。（分数：6.00）A.加密算法是公开的，作为参数的密钥也是公开的B.加密算法是公开的，作为参数的密钥是保密的C.加密算法是保密的，作为参数的密钥是公开的D.加密算法是保密的，作为参数的密钥也是

13、保密的A.对明文字母进行变换，且对明文位置进行重新排列B.对明文字母进行变换，但不对明文位置进行重新排列C.不对明文字母进行变换，但对明文位置进行重新排列D.不对明文字母进行变换，也不对明文位置进行重新排列A.对明文字母进行变换，且对明文位置进行重新排列B.对明文字母进行变换，但不对明文位置进行重新排列C.不对明文字母进行变换，但对明文位置进行重新排列D.不对明文字母进行变换，也不对明文位置进行重新排列在比较常见的公共传输系统中，(32)是以模拟技术为基础的电路交换网络；(33)是基于城域网协议的包交换公共数据网络；(34)提供基于线路交换的端到端的数字连接通道。帧中继的典型速率范围是(35)

14、。（分数：8.00）A.SMDSB.ISDNC.DDND.PSTNA.SMDSB.ISDNC.DDND.PSTNA.SMDSB.ISDNC.DDND.PSTNA.28kbps2MbpsB.56kbps2MbpsC.28kbps4MbpsD.56kbps4Mbps某系统使用两级页表，页的大小是 212字节，虚地址是 32位。地址的前 8位用作一级页表的索引。有(37)位用来指定二级索引，一级页表中有(38)项，二级页表中有(39)项，虚地址空间中有(40)页。（分数：8.00）A.20B.12C.32D.8A.2 20B.2 12C.2 32D.2 8A.2 20B.2 12C.2 32D.2

15、8A.2 20B.2 12C.2 32D.2 8确认测试计划是在(45)阶段制定的。为了提高测试的效率，应该(46)。白盒测试是结构测试，被测对象基本上是源程序，以程序的(47)为基础设计测试用例。下列不属于白盒测试的技术是(48)。（分数：8.00）A.需求分析B.详细没计C.编码D.错误推测A.选择发现错误可能性大的数据作为测试用例B.随机选取测试数据C.在完成软件编码阶段后再指定软件的测试用例D.取一切可能的输入数据作为测试数据A.应用范围B.功能C.内部逻辑D.输入数据A.基本路径测试B.条件覆盖C.循环覆盖D.错误推测对于下标所列的进程，每个进程的周转时间(精确到 1/100)在剥夺

16、情况下为(59)，非剥夺情况下为(60)。平均吞吐量在这两种情况下分别为(61)和(62)。（分数：8.00）A.15 11 3 7B.4 15 11 9C.11 3 7 15D.4 14 5 9A.15 11 3 7B.4 15 11 9C.11 3 7 15D.4 14 5 9A.15B.17C.3.75D.5A.15B.17C.3.75D.5在操作系统中，处理机管理部分由作业管理和进程管理两部分组成。作业管理把作业流分成提交、后备、运行、完成 4个状态，进程管理把进程分成就绪、执行、阻塞 3个基本状态。作业从提交到后备由(29)完成，从后备到运行由(30)完成。进程从就绪到执行由(31)

17、完成，从执行到阻塞或就绪由(32)完成。用户进程的优先进程是由(33)建立的。（分数：10.00）A.作业调度程序B.假脱机处理程序C.存储管理程序D.输入输出程序A.作业调度程序B.假脱机处理程序C.文件管理程序D.输入输出程序A.设备管理程序B.进程调度程序C.存储管理程序D.输入输出程序A.作业调度程序B.假脱机处理程序C.存储管理程序D.交通控制程序A.作业调度程序B.设备管理程序C.存储管理程序D.输入输出程序操作系统主要是对计算机系统中的全部软硬件资源进行管理，以方便用户提高计算机使用效率的一种系统软件。它的主要功能有：(34)、存储管理、文件管理、(35)设备管理。Winndow

18、s 是一个具有图形界面的(36)系统软件。UNIX 操作系统基本上是采用(37)语言编制而成的系统软件。在(38)操作系统的控制下，计算机能及时处理由过程控制反馈的信息并作出响应。（分数：10.00）A.用户管理B.处理机管C.中断管D.FO管理A.数据管理B.作业管理C.中断管理D.FO管理A.分时B.多任务C.多用户D.实时A.PascalB.宏C.汇编D.CA.网络B.分时C.批处D.实时程序语言可分成低级语言和高级语言两大类。与高级语言相比，用低级语言开发的程序，其(39)，但在(40)的场合还经常或部分地使用低级语言。在低级语言中，汇编语言与机器语言十分接近，它使用了(41)来提高程

19、序的可读性。高级语言有许多种类，其中 PROLOG是一种(42)型语言，它具有很强的(43)能力。（分数：10.00）A.运行效率低，开发效率低B.运行效率低，开发效率高C.运行效率高，开发效率低D.运行效率高，开发效率高A.对时间和空间有严格要求B.并行处理C.事件驱动D.电子商务A.简单算术表达式B.助记忆符号C.伪指令D.定义存储语句A.命令B.交互C.函数D.逻辑A.控制描述B.输入/输出C.函数定义D.逻辑推理某些操作系统把一条命令的执行结果输出给下一条命令，作为它的输入并加以处理，这种机制称为(44)；使执行命令的结果不在屏幕上显示而引向另一个文件，这种机制称为(45)。使命令所需

20、要的处理信息不从键盘接收而取自另一文件，这种机制称为(46)。操作系统不从键盘逐条接受命令并执行，而调用一个正文文件，执行其中保存的一系列命令，这种方式属于(47)方式，编写这样的文件符合(48)的语法规则。（分数：10.00）A.链接B.管道(线)C.输入重新定向D.输出重新定向A.清屏B.屏蔽显示C.输出重新定向D.管道(线)A.输入重新定向B.读保护C.管道(线)D.批处理A.系统生成B.初始装入C.批处理D.管道(线)A.会话语言B.交互语言C.机器语言D.命令语言数据库系统由数据库、(49)和硬件等组成，数据库系统是在(50)的基础上发展起来的。数据库系统由于能减少数据冗余，提高数据

21、独立性，并集中检查(51)，由此获得广泛的应用。数据库提供给用户的接口是(52)，它具有数据定义、数据操作和数据检查功能，可独立使用，也可以嵌入宿主语言使用。(53)语言已被国际标准化组织采纳为标准的关系数据语言。（分数：10.00）A.操作系统B.文件系统C.编译系统D.数据库管理系统A.数据系统B.文件系统C.解释系统D.数据库管理系统A.数据完整性B.数据层次性C.数据的操作性D.数据兼容性A.数据库语言B.过程化语言C.宿主语言D.面向对象语言A.QUELB.SEQUELC.SQLD.ALPHA关系运算以关系代数为理论基础，关系代数的最基本操作是并、差、笛卡尔积、(54)。用 表示关系

22、R和关系 S的(55)。设有关系 R、R、S、S如下表所示，R 和 S左外连接的结果是(56)。 (S)的结果为(57)， 的元组个数为(58)。 （分数：10.00）A.投影、联接B.联接、选择C.选择、投影D.交、选择A.联接B.笛卡尔积C.9联接D.自然联接A.B.C.D.A.(5，7，2)，(6，7，2)B.(7，2，3)1C.(4，4，5)，(7，2，3)D.(2，3，5)，(4，3，5)1A.0B.1C.2D.3编制一个好的程序首先要确保它的正确性和可靠性，除此以外，通常更注重源程序的(59)。还应强调良好的编程风格，例如，选择标识符的名字时应考虑(60)：在书写语句时应考虑(61

23、)；在书写功能性注解时应考虑(62)。 源程序中应包含一些内部文档，以帮助阅读和理解源程序，源程序的内部文档通常包括选择合适的标识符、注解和(63)。（分数：10.00）A.易使用性、易维护性和效率B.易使用性、易维护性和易移植性C.易理解性、易测试性和易修改性D.易理解性、安全性和效率A.名字长度越短越好，以减少源程序的输入量B.多个变量共用一个名字，以减少变量名的数目C.选择含义明确的名字，以正确提示所代表的实体D.尽量用关键字作名字，以使名字标准化A.把多个短的语句写在同一行中，以减少源程序的行数B.尽量使用标准文本以外的有特殊功效的语句，以提高程序的功效C.尽量消除表达式中的括号，以简

24、化表达式D.避免使用测试条件“非”，以提高程序的可读性A.仅为整个程序作注解B.仅为每个模块作注解C.为程序段作注解D.为每个语句作注解A.程序的视觉组织B.尽量不用或少用 GOTO语句C.检查输入数据的有效性D.设计良好的输出报表The(66)is a channels capacity which directly reflects the data transfer rate of the channel.(67)functions in a NetWare network which is used to define addressing schemes. The(68)is a n

25、etwork layer device that supports multiple LAN interfaces and segments LANs into smaller collision and broadcast domains.(69)is the popular LAN developed under the direction of the IEEE802.3. The(70 is a device which enables digital microcomputers to communicate across analog telephone lines.（分数：10.

26、00）A.volumeB.bandwidthC.noiseD.delayA.NetBEUIB.IPC.IPXD.NCPA.repeaterB.hubC.bridgeD.routerA.Token RingB.Token BusC.EthernetD.FDDIA.repeaterB.modemC.hubD.printerCommunication via e-mail is by far the most common Internet activity. You can(71 )with anyone in the world who has an Internet address or e-

27、mail(72)with a system connection to the Internet. All you need is(73)the Internet and an e-mail program. Two of the most widely used e-mail programs are Microsofts(74)and Netscapes Navigator. A typical e-mall message has three basic(75): header, message, and signature.（分数：10.00）A.connectB.exchangeC.

28、communicateD.gameA.accountB.NoC.userD.administratorA.attach withB.graspC.possessD.access toA.YahooB.ExploreC.FoxmailD.Outlook ExpressA.packetsB.elementsC.framesD.cells软件水平考试（中级）软件设计师上午（基础知识）试题-试卷 37答案解析(总分：216.00，做题时间：90 分钟)一、选择题(总题数：44，分数：216.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上

29、，答在试卷上不得分。_解析：2.瀑布模型(Waterfall Model)突出的缺点是不适应(9)的变动。（分数：2.00）A.软件结构B.运行平台C.用户需要 D.程序语言解析：解析：软件工程的基础知识，瀑布模型突出的缺点是不适应用户需求的变动，模型工程并不和软件结构、运行平台程序语言有很大的关系。3.Jackson设计方法是由英国的 M. Jackson 提出的，它是一种面向(10)的软件设计方法。（分数：2.00）A.对象B.数据结构C.数据流 D.业务流解析：解析：软件工程的基础知识，Jackson 设计方法是一种面向数据结构的软件设计方法，Jackson 分析方法是面向数据流的分析方

30、法。4.按照中华人民共和国著作权法的权利保护期，下列权项中，受到永久保护的是(13)。（分数：2.00）A.发表权B.修改权 C.复制权D.发行权解析：解析：中华人民共和国著作权法第二十条规定：作者的署名权、修改权、保护作品完整权的保护期不受限制。”中华人民共和国著作权法第二十一条规定：“公民的作品，其发表权、本法第十条第一款第(五)项至第(十七)项规定的权利的保护期为作者终生及其死亡后五十年，截止于作者死亡后第五十年的 12月 31日；如果是合作作品，截止于最后死亡的作者死亡后第五十年的 12月 31日。法人或者其他组织的作品、著作权(署名权除外)由法人或者其他组织享有的职务作品，其发表权、

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

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

33、整起到指导作用。 决策执行。依据数据分析所提供的可预见性的分析报告，企业可以将在业务过程中所学到的知识加以总结利用，对业务过程和业务计划等做出调整。通过调整达到增强与客户之间的联系，使业务运作更适应市场要求的目的。6.下面算法是实现对 n个整数的序列进行选择排序，其中序列的“长度”n 为问题的规模。该算法的时间复杂度为(23)。 void select_sort(int a, int n) /将 a中整数序列重新排列成从小到大有序的整数序列 for(i=0；i（分数：2.00）A.O(n 3 )B.O(n 2 ) C.O(n)D.O(n 4 )解析：解析：算法中的控制结构是两重循环，所以基本操

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

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

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

37、ernet 和 Token Ring都使用包交换技术。11.设 A和 B是两个单链表，其表中元素有序递增。请分析算法的时间复杂度。其时间复杂度为(40)。（分数：2.00）A.O(re+n-1)B.(m+n+1)C.O(m+n) D.不确定解析：解析：设 A表和 B表的长度分别为 m和 n，则该算法的时间复杂度为 O(m+n)。12.深度为 k的完全二叉树所含叶结点的个数最多为(43)。（分数：2.00）A.22 kB.22 k-1 C.kD.2k解析：解析：深度为 k的完全二叉树所含叶结点的个数最多的情况，一定是满二叉树的情况，即第 k层上具有最多结点的情况。根据二叉树的性质 1，第 k层上

38、最多有 2k-1(上标)：个结点。位于第 k层上的结点，均为叶结点。13.若采用邻接矩阵结构存储具有 n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为(47)。（分数：2.00）A.O(n)B.O(n 2 ) C.O(n 2 +1)D.以上都不对解析：解析：n 个顶点的图的邻接矩阵是一个 n阶方阵，有 n行 n列。从顶点 Vi出发，对图进行广度优先遍历，需对矩阵的第 i行逐列检测非零元(若 aij1，则说明顶点 vj与 vi之间有边存在，vi 就是vi的邻接顶点)。根据广度优先遍历的思想，每一个顶点都要轮换着做出发顶点，即矩阵的每一行都将要被逐列检测。显然，算法中要用一个两重循环来组织

39、逐行逐列的检测操作，所以，算法的时间复杂度是 n的平方阶。14.假定有 k个关键字互为同义词，若用线性探查法把这些同义词存人散列表中，至少要进行(48)次探查。（分数：2.00）A.L(k+1)/2 B.k(k+1)C.2k(k+1)D.不确定解析：解析：存入第 1个，需要探查一次；存入第 2个，需要探查两次 j；存人第 k个需要探查 k次；因此至少要进行 1+2+3+k=k(k+1)/2次探查。15.在长度为 n的线性表中顺序查找值为 x的元素时，查找成功的平均查找长度为(49)。（分数：2.00）A.nB.n/2C.(n+1)/2 D.(n-1)/2解析：解析：假设在每个位置查找的概率相等

40、，即有 pi=1/n；若是从表尾往表头方向查找，则在每个位置上的查找比较次数为 Cn=1，Cn-1=2,.C1=n。因此，查找成功的平均查找长度为16.在单向循环链表中，若头指针为 h，那么 p所指结点为尾结点的条件是(50)。（分数：2.00）A.p=NULLB.Pnext=NULLC.p=hD.pnext=h 解析：解析：此题是考查数据结构的链表知识。根据单向循环链表的定义和题中的答案，不难得出正确答案。因为.P=NULL，链表的节点是不能为空的，肯定错了；p-next=NULL，在最后一个指针为空的情况下，不能连成环，这是单向链表定义，所以错了；p=h，将头指针赋值给尾指针，显然也不正确

41、，P 就不是尾指针了。17.二维数组 A按行优先顺序存储，其中每个元素占 1个存储单元。若 A11的存储地址为 420，A3 3的存储地址为 446，则 A55的存储地址为(51)。（分数：2.00）A.470B.471C.472 D.473解析：解析：设二维数组 A有 m行 n列，每个元素占 C个存储单元，基地址 loc(A00)=d;则行主顺序存储的寻址公式为: loc(Aij)=loc(A00)+(in+j)C=d+(in+j)C。18.假设一个 6阶的下三角矩阵 B按列优先顺序压缩存储在一维数组 A中，其中 A0存储矩阵的第二个元素 b11，则 A14存储的元素是(52)。（分数：2.

42、00）A.b63 B.b62C.b64D.b53解析：解析：此题要寻找 Ak与 bij之间的关系。6 阶下三角阵 b从第 1列到第 6列，每一列的元素个数依次为：6、5、4、3、2、1，元素总数为 6(6-1)/2=21。按列顺序存放在一维数组 A21中(b11 存放在 A0中)，列之前的第 1列到第 j-1列元素个数为：6+5+4+(6-(j-1)+1)；(6+6-(j-1)+1)(j-1)/2=(14-j)(j-1)/2。第 i列上的第 i行之前有 i-j个元素。因此有：k=(14-i)(j-1)/2+i-j。 已知k=14，根据每一列的元素个数，显然列号 j应该满足条件 2 于是有：k=

43、(14-j)(i-1)/2+i-j=(14-3)(3-1)/2+j-3=8+i i=k-8=14-8=6。所以，A14存储的是元素 b63。19.具有 6个顶点的连通图的广度优先生成树，其边数为(53)。（分数：2.00）A.6B.5 C.7D.4解析：解析：连通图的生成树具有两个特点：所有顶点是连通的；不构成回路。n 个顶点要连通必须要有 n-1条边，再多一条边必形成回路。所以，具有 6个顶点的连通图的广度优先生成树，其边数为 5。设有 4道作业，它们的提交时间及执行时间如表所示。在单道程序环境下，若采用先来先服务调度算法，其平均周转时间为(15)，平均带权周转时间为(16)。 （分数：4.

44、00）A.0.95B.2.8 C.2.45D.5.25解析：A.0.95B.2.8C.3.85D.5.25 解析：解析：若采用先来先服务调度算法，其调度顺序为 1234，各时间如表：可行性分析的目的是在尽可能短的时间内用尽可能小的代价来确定问题是否有解。不属于在可行性分析阶段进行的工作是(20)。可行性分析不包括对待开发软件进行(21)分析。（分数：4.00）A.研究目前正在使用的系统B.根据待开发系统的要求导出新系统的逻辑模型C.提供几个可供选择的方案D.编制项目开发计划 解析：A.技术可行性B.经济可行性C.操作可行性D.组织可行性 解析：解析：可行性分析的任务是从技术上、经济上、操作上分

45、析需解决的问题是否存在可行的解。技术可行性考虑现有的技术能否实现该系统；经济可行性考虑开发该系统能否带来经济效益；操作可行性考虑该软件的操作方式是否容易被用户接受。 在进行可行性分析时，通常要先研究目前正在使用的系统，然后根据待开发系统的要求导出新系统的高层逻辑模型。有时可提出几个供选择的方案，并对每个方案从技术上、经济上、操作上进行可行性分析，在对各方案进行比较后，选择其中的一个作为推荐方案，最后对推荐方案给出一个明确的结论，如“可行”、“不可行”，或“等某条件成熟后可行”。在 UML提供的图中，(28)用于对系统的静态设计视图建模，(29)用于对系统的静态实现视图建模。（分数：4.00）A

46、.类图 B.对象图C.部署图D.构件图解析：A.类图B.对象图C.部署图D.构件图 解析：解析：在 UML提供的图中，类图展现了一组对象、接口、协作和它们之间的关系，类图用于对系统的静态设计视图建模。对象图展现了一组对象以及它们之间的关系，对象图描述了在类图中所建立的事物的实例的静态快照。构件图展现了一组构件之间的组织和依赖，构件图专注于系统的静态实现视图，它与类图相关，通常把构件映射为一个或多个类、接口或协作。部署图运行处理节点以及其中的配置，部署图给出了体系结构的静态实施视图。所以(28)应选 A，(29)应选 D。图 8-2为一个 DFA的状态转换图，与其等价的正规表达式是(31)，在图

47、中状态(32)是可以合并的状态。（分数：4.00）A.(0|1)*11(0*1*)* B.(0|1)*110*|1*C.(0*1*)11(0|1)*D.(0*|1*)*11(0*|1*)解析：A.q0和 q1B.q2和 q3 C.q1和 q2D.q0和 q3解析：解析：首先将所有状态分成两个子集，一个由终态组成，一个由非终态组成，即q0,q1， q2,q3。在读入符号 1后，状态 q0和 q1分别转换为第一个子集中的状态 q1和第二个子集中的状态q2，所以第一个子集中的状态 q0和 q1是可区别的；而第二个子集中的状态 q2和 q3在读入符号 0,1后均转换为第二个子集的状态，因此得到了新的划

48、分q0，q1，q2,q3；即 q2和 q3是不可区分的状态，它们可以合并。 q2 和 q3在读入符号 0,1后均转换为自身的状态，则后面部分可化为结尾部分为字符 0和 1的任意组合，这时就可以排除(31)题中的 B和 D选项；再找一个表达式来排除其中的一个答案，可看到表达式一定要能产生 1011开头的式子，而 C不包括这样的表达式，所以排除 C。广义表(a，(a，b)，d，e，(i，j)，k)的长度是(48)，深度是(49)。（分数：4.00）A.3B.4C.5 D.6解析：A.3 B.4C.5D.6解析：解析：广义表的长度是指广义表中元素的个数，表中元素有 a，(a,b)，d，e，(i，j)，k)，共 5个：广义表的深度是指广义表展开后所含的括号的最大层数，题中的广义表共有 3层。8层完全二叉树至少有(52)个结点，拥有 100个结点的完全二叉树的最大层数为(53)。（分数：4.00）A.127B.128 C.256D.257解析：A.6B.7 C.8D.9解析：解析：第 1层有 2 0 ，第 2层有 2 1 ，第 7层有 2 6 ，所以 8层完全二叉树的结点数目至少有 2 0 +2 6 +1=2 7 -1+1=128个。设最大层数为 n，根结点编号为 1则最大层上